Should a lockfree queue use a condition variable?

Question

Suppose I have a lockfree queue in a multithreaded setting. I already provide a try_dequeue() method which allows for an optional failure (communicated via the return type) if the queue is empty.

I've found it convenient to have an always-succeeding T dequeue() method which will not return while the queue is empty. As a consumer, I don't really care when I get my product, I just want to know as soon as one's available.

My implementation of dequeue() is pretty simple:

while (true) {
    if (try_dequeue succeeded) return result;
    std::unique_lock<std::mutex> lk(mtx_);
    cond_.wait(lk, [this]{ return !empty(); });
}

Where cond_ is signalled by enqueuers and mtx_ guards cond_.

The excess serialization and between-dequeuer contention caused by lk seems to slow things down. empty() certainly doesn't need anything to be locked.

In any case, does cond_ seem out of place here? The only reason I'm hesitant to remove it is the case where there's a dequeuer (or multiple dequeuers) that are waiting for a new item to come in and are spinning idly on the CPU with no indication for the enqueuing thread to get priority.

It would seem that perhaps this_thread::yield() is more appropriate here, but the standard only guarantees that the method is a hint, so there is a possibility of starving here.

It appears that boost::lockfree::queue does not provide a dequeue-like method at all. Hopefully the nuclear option is avoidable.

As user rwong points out, we may consider a solution to this problem as a "hybrid" or "semi-blocking" approach because it would be desirable to have dequeuers block on empty queues, yet it would also be nice for enqueuers not to have to make a full context switch to the kernel at the same time.

Note: Yes, technically the inclusion of mtx_ in the queue removes the lockfree attribute, but I think this is an accurate characterization anyway since dequeue() is the only method that uses mtx_ (enqueuers signal without locking).

Answer 1

You can use try_lock for signaling the cond_ when enqueueing. This will have a race condition that can be circumvented by making the wait timed.

The idea is that if the try_lock fails then either another enqueuer is also trying to wake the dequeuers so we might as well let him do the work or the dequeuer is trying to wait and he may or may not have check the condition yet. If he hasn't then fine he'll see the queue isn't empty and release and try again, if he has checked then he'll check again after the timeout expires.