Both blocking and non blocking queue

Question

I need to set up a producer-consumer scheme with two threads linked by a queue (the producer pushing tasks into the queue, the consumer executing them as they come).

Since the queue will be empty most of the time I must make it so that the consumer thread can sleep and be woken up as soon as something is pushed by the producer. However I must ensure that the producer is never blocked, not even shortly. In other words, I need some one-sided blocking queue.

There are lock free queues, but since those are by definition, well, lock free, it isn't possible for the consumer thread to be blocked by them.

I have thought of associating a lock free queue with a condition variable. When the consumer thread finds the queue empty it would sleep waiting for the condition to be notified. The producer thread would notify the condition when pushing a task into the queue waking up the consumer thread (if it was sleeping). However, condition variable must be protected by mutex, that mean there is still a small chance for the producer thread to be blocked when trying to acquire it to notify the condition.

I have yet to find a really good way to solve this problem so your ideas are more then welcome.

Note : I'm planning to use boost thread to implement this.

Note 2 : I'm not considering the case where the producer trys to push something and the queue is full. This is never going to happen.

Answer 1

tbb library provides both blocking and non-blocking queues:

• tbb::concurrent_queue<> provides non-blocking try_pop() and push() for unlimited growth.
• tbb::concurrent_bounded_queue<> provides push() which can block if capacity limit is specified and when it is reached; and pop() which waits for items in empty queue. It also provides non-blocking try_push() and try_pop() alternatives for the same queue.