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.

Spark

boost lockfree queues can be blocking, you can just use that. – Fawnfawna

Fwiw, the mutex in a cvar/mtx pair isn't to protect the condition variable; it's to protect the predicate data. Worth mentioning because there is no need for the producer to latch the mutex before signaling the cvar. Your predicate state (queue condition) is lock-free. The consumer would obviously need to unlatch the mutex immediately upon waking, but thats really all there would be to it. – Sparling

What happens to producer when it wants to post but the queue is full? – Farrish

@Fawnfawna : as far as I can tell from the doc, both boost::lockfree::spsc_queue and boost::lockfree::queue pod() method return immediately no matter if something was popped or not. So I don't see how I can block the consumer thread with these. Did I misunderstand something ? – Spark

@MaximYegorushkin : I consider this case will never happen. – Spark

@Sparling : it appears you're right. The producer thread doesn't need to lock the mutex to notify the condition, therefore it is never going to be blocked. I will test this solution. Thanks. – Spark

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.

Archibold

I think the OP needs a single data structure supporting both of blocking and non-blocking operations – Hemia