Subj : Re: RCU+SMR
To   : comp.programming.threads
From : Joe Seigh
Date : Thu Jun 30 2005 11:35 pm

David Hopwood wrote:
> Joe Seigh wrote:
> 
>> Jomu wrote:
>>
>>> Any references to code? Some sample lock-free queue or something like?
> 
> [...]
> 
>> And as you can see by this topic practically being a monologue,
>> there's no huge demand for this kind of stuff, so I'm taking
>> advantage of the more leisurely schedule that allows.
> 
> 
> What would be really useful is a lock-free *multiple-writers*,
> single-reader FIFO message queue. An implementation of a message-
> passing concurrent language uses this kind of queue for all
> communication between processes, and would benefit from an
> implementation with very low overhead on multiprocessors. The
> queue entries have to be traceable by a GC.
> 

What's wrong with Maged Michael's lock-free FIFO and variations
on that?  The only problem I'm aware of is that if you use the
GC to avoid the ABA problem you can trash the GC if you have
a high rate of usage.

Way back, I came up with a scheme where you make the queue a lock-free
LIFO stack using compare and swap.  The single reader just grabbed the
entire queue using compare and swap, reversed order making it FIFO
and worked off of that util it was empty and then repeated the whole
process by grabbing the shared LIFO stack again.

-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.