Subj : Re: RCU+SMR To : comp.programming.threads From : David Hopwood Date : Sat Jul 09 2005 12:31 am Joe Seigh wrote: > David Hopwood wrote: > >> 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? Do you mean , or something more recent? Possibly there's nothing wrong with it. However, the correctness argument seems very informal, and I don't see any discussion of what memory consistency model is being assumed (apart from an assumption that the ABA problem does not occur). It also looks expensive: two CAS operations for enqueue in the best case, and one CAS to dequeue each item (rather than being able to dequeue multiple items at once, which should be possible since we have a single reader). Although a message queue must in general handle multiple writers, most such queues will in fact only be written by a single writer; the problem is that the language implementation doesn't know that statically. So it should be possible to do much better than Michael's algorithms for this application. > 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 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. I'll post it here with the subject "Implementing message passing on multiprocessors". -- David Hopwood .