On Wed, May 20, 2015 at 5:15 PM, Gottlob Frege
Using condition variables does require mutexes, but you only need to grab the mutex when someone is actually waiting. So you can have a separate (atomic) flag 'waiting' and then only grab the mutex when it is true.
But that is an extra atomic op on every push (checking the flag). Of course, it could probably be a relaxed atomic (I think), which is almost free on many platforms.
And it gets tricky ensuring that you don't have a case where someone is waiting but every pusher missed seeing the flag.
If the waiting is inside the queue implementation, you can possibly hide the flag inside the head pointer, getting the extra atomic op for free.
I touched on some of this in my Lock-free talk at BoostCon/C++Now last week.
Aren't these tricky corner cases what "synchronic" is supposed to address? http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4195.pdf