[Openmcl-devel] Thread safe message queues
ron at flownet.com
Tue Sep 28 09:39:23 PDT 2010
Oh, right, semaphores count. Duh.
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:
> push data
> signal semaphore
> 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.
> -- Nikodemus
More information about the Openmcl-devel