Fast conditional lock concept check

I have a lockless FIFO queue. Multiple producers, one consumer. Scheduler coordinates which messages get passed to workers that have nothing to do. Obviously, if a worker runs out of input, it can either exit, or sleep. This poses a problem - how to put workers to sleep and efficiently wake them up. Lockless queue will either return the element from queue, or null if such element doesn't exist. For this, I worked out a conditional lock that is intended to be as fast as possible under normal operation, and still safe in case threads are suspended.



public class WaitLock {

    public void blockOn()
    {
        synchronized( lock ) {
            try {
                waiting = true;

                // possibly additional book-keeping
                // add thread to a pool, ...
                // since this is synchronized, wake() cannot interrupt
                // since waiting was set before

                lock.wait();
            } catch (InterruptedException e) { }
        }
    }
    
    public void wake()
    {
        if (waiting) {                // 1)
            synchronized( lock ) {
                waiting = false;
                lock.notifyAll();
            }
        }
    }
    
    private Object lock = new Object();
    private volatile boolean waiting;
}

void addToQueue()
{
  queue.add( x );
  waitlock.wake()
}

It's Java, but the idea should be understandable. Replace (synchronized(lock) with boost::mutex::scoped_lock( lock ), and lock.wait with boost::condition. When a worker runs out of work, it calls blockOn(). Every time an element is added to the queue, wake is called. If the thread isn't blocking, the overhead will be minimal, if it is, state is woken up in a thread-safe manner. The lock will always be used only in this manner, wake is always called after there's at least one element in the queue which will not be removed until the thread is woken up. 1) indicates possible problems (perhaps just one of them)


    Thread1                            Thread2
1) wake() {
2)   if(waiting) //false
3)                                     synchronized(lock) {
4)                                       waiting = true
5) }

// Although Thread2 was already out of work, waiting wasn't set soon enough, 
// and wake() will be missed

This could lead to Thread2 erroneously sleeping until another thread calls wake(). One solution to this is that I wait with a timeout. The other is to use optimistic approach, and simply sit out until next message is added to the queue (message are plentiful, and arrive frequently, but that's not really a solution) Is there a better way to achieve this:


[ Thread ] ---+  add + wake()
[ Thread ] ---+-----------------> [Consumer] // must sleep if no input
[ Thread ] ---+

I could obviously spin in consumer, but spinning makes me dizzy...

Topic Locked