[Openmcl-devel] Thread safe message queues
nikodemus at random-state.net
Tue Sep 28 04:04:58 CDT 2010
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:
wait on semaphore
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.
More information about the Openmcl-devel