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

Have you considered using a semaphore instead of a condition variable? A semaphore is waitable and can represent a "queue is non-empty" status even when no threads are waiting.

Answer 2

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 3

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).

Answer 4

Example 12-3 of this C++ threading blog post should give you a reference implementation, but I think you're dangerously close to success on your own. Addressing your specific concerns:

1. It is not illegal to signal when there are no waiters. It's totally legitimate, and you can leverage that fact. (Where did you read this, btw?)
2. pthread_cond_broadcast causes one major problem: the herd of elephants charge, where all n threads awake and start pulling memory between caches even though only one of them can possibly make forward progress. It will work, but it's not as efficient.
3. You can signal from anywhere, even from a thread that never has to deal with the mutex in question. Your pthread_cond_wait calls must release the read mutex; that is the only requirement, and that's the only mutex that ever needs to interact with the condition variable.

Following from #3, there is one major problem with your idea: The writer thread must lock both the read and write mutexes. If it does not, what happens when the queue size is 1 and you have a reader and a writer acting at the same time?

Answer 5

A simple boost::condition example is located here.