[Openmcl-devel] Thread safe message queues

[Ron Garret]

I'm trying to write a thread-safe message queue, i.e. a data structure that multiple threads can push things on to and multiple threads can pop things off of, with the invariant that everything that gets pushed eventually gets popped exactly once.  Also, a thread that tries to pop an empty queue should block until another thread pushes something on to the queue.

Once upon a time I wrote one of these for the original MCL, but the solution I used back then turns out to rely on the fact that MCL wasn't "really" multithreaded.  Now that we have real threads running on real cores the solution I used then won't work.  Before I start rooting around in the old OS texts and reinventing the wheel I thought I'd ask if anyone has already solved this problem.

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 what happens when a thread tries to pop an empty queue.  It needs to block, so it waits for the semaphore.  When another thread pushes something onto the queue it signals the semaphore, which unblocks the thread waiting on the queue.

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.

This worked in the old MCL because you could wrap the lock release and semaphore wait inside a without-intterrupts form.  But with real threads there is no such thing as without-interrupts, so I find myself at a loss.  I know this is a solved problem.  I'm not asking anyone to do my homework for me, but if you happen to know the answer or have a pointer ready at hand it would save me a lot of trouble.

Thanks,
rg