concurrent queue in C++

Question

I am trying to design a queue which could be simultaneously accessed by multiple read/write threads. I prefer using 2 mutexes, one apiece for read and write. Doing write is simple enough, lock the write mutex, append data, unlock and you are done.

The issue is with read. If there's no data in the in queue I'd like my thread to wait till data is available. 1 obvious way to do this is to acquire read mutex and keep polling the queue every N clock cycles but this is obviously not the best approach. Which brings me to condition variables. Does anybody have any good resource which discusses blocking queue implementation in C++ with condition variables (preferably pthreads based)?

Specifically, I see the following issues:

1. Once a write is done, the writer thread would do a pthread_cond_signal that data exists but how does it know that some reader thread is waiting? It is illegal to call pthread_cond_signal unless there is a pthread_cond_wait.
2. Is it okay to call pthread_cond_broadcast instead of pthread_cond_signal? Perhaps that might circumvent the issue with pthread_cond_wait. Also this seems more logical as multiple reader threads is definitely a real possibility.
3. It also appears that the reader and writer threads must be locked with the same mutex to make use of the condition variable. If this is true then we have a severe problem.

Answer 1

I have an implementation using the same mutex from http://danborn.net/code/ but like I mentioned earlier since this uses a condition variable it also uses 1 mutex.

And here's the boost version, again with single mutex: http://www.justsoftwaresolutions.co.uk/threading/implementing-a-thread-safe-queue-using-condition-variables.html

Answer 2

I think you've misunderstood something -- it is perfectly legal to call pthread_cond_signal even if no threads are waiting on that condition.

Also, in the context of multithreaded programming, calling something a "read" operation usually implies that it does not change the state of the shared resource. If by "read" you really mean "remove an item from the head of the queue", that changes the state of the queue (in other words, it's also a "write".) It might be better to think in terms of "consumer and producer" rather than "reader and writer" for your situation.

A single mutex (to guarantee exclusive access to the queue), and two condition variables ("data available", "free space available") should be enough for your situation. (If the queue can grow dynamically, you won't need a "free space available" condition variable; I just mention that for completeness.)

If your reading threads are strictly readers (that is, they do not modify the shared queue data structure in any way, such as by popping an item out of the queue), the pthread_rwlock family of calls may also be an appropriate solution. In this paradigm, there are read locks (which multiple readers can hold simultaneously, but force writers to block until the readers are done), and write locks (which ensure exclusive access by the thread holding the write lock, blocking any other writers and readers).