[Openmcl-devel] Thread safe message queues

[Paul Krueger]

I have some code that implements something very much like this if anyone wants it. Its fifo is not exactly lockless, but it does use separate reader and writer locks and implements in a way that eliminates all lock contention between readers and writers. Readers only contend with other readers and writers only contend with other writers. So if you have a single reader and single writer there is no lock contention. It's pretty simple (the test functions take more space than the implementation itself), but let me know if anyone wants it and I'll send it to you directly.

Paul

On Sep 28, 2010, at 4: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
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel