[Openmcl-devel] Thread safe message queues

[Nikodemus Siivola]

On 28 September 2010 11:25, Ron Garret <ron at flownet.com> wrote:

> Just for the record, the solution that doesn't work any more is to
> use a lock and a semaphore.  When a thread wants to push or pop it
> first grabs the lock.  That is straightforward.  The tricky part is

You want to first decrement the semaphore, and then pop.

> The reason this doesn't work with real threads is that a thread
> trying to pop an empty queue has to release the lock before waiting
> on the semaphore, otherwise you have a deadlock (because no other
> thread can grab the lock, so no other thread can push anything on to
> the queue).  But in between releasing the lock and waiting on the
> semaphore another thread could push something onto the queue and
> signal the semaphore before the first thread waits on it.  So now you
> have a popping thread blocked on a non-empty queue, which is bad.

Assuming a thread-safe queue, the correct protocol looks like this:

WRITER:
  push data
  signal semaphore

READER:
  wait on semaphore
  pop data

The queue will never be empty when it tries to pop a datum from it.
This construct is often called a "mailbox".

If you implement this on top of a lockless fifo, you don't even need a
separate lock for push & pop.

If you _do_ need a lock for the fifo, grabbing and releasing that lock
is part of the push & pop operations.

Cheers,

 -- Nikodemus