[Openmcl-devel] Thread safe message queues

[Ron Garret]

Oh, right, semaphores count.  Duh.

Thanks.

rg

On Sep 28, 2010, at 2:04 AM, Nikodemus Siivola wrote:

> 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