Subj : Re: RCU+SMR
To   : comp.programming.threads
From : Chris Thomasson
Date : Sat Jul 09 2005 06:57 am

>> 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 until it was empty and then repeated the whole
>> process by grabbing the shared LIFO stack again.
>
> These comments prompted me to think of another way of implementing message
> passing that greatly reduces the need for (and hence the overhead of)
> synchronization.

Joes idea of converting an IBM freelist into a queue does reduce the number 
instructions normally needed for a lock-free queue. Consumers only need an 
atomic exchange, and producers need a normal cas loop. Look on my site for 
my implementation of a zero-overhead queue that does not need any 
synchronization instructions, just a dependant-load for the consumer and a 
store barrier for the producer. However, it is a single-producer/consumer 
queue. But you can use it in various distributed message passing schemes to 
help reduce their synchronization overhead.




> I'll post it here with the subject "Implementing message
> passing on multiprocessors".

There was one scheme I used that avoided synchronization instructions for a 
certain type of thread-to-thread message passing. The basic scheme was that 
each producer thread had its own zero-overhead single-producer/consumer 
queue that would be sampled by dedicated consumer threads. This allowed me 
to create a fairly efficient "many-producer/few-consumer" distributed 
messaging passing system.


-- 
http://appcore.home.comcast.net/
(portable lock-free data-structures)

.