Subj : Re: Implementing lock-free data structures
To   : comp.programming.threads
From : SenderX
Date : Thu Mar 10 2005 12:58 pm

>I was going to do a write up of general instructions on how to
> implement lock-free data structures using RCU, atomic_ptr,
> hazard pointers, Boehm GC, etc... since it doesn't appear that
> anyone else has, except for COW objects and linked lists, and
> it's clear that lock-free won't take off until there's better
> documentation.

Yeah. There are a number very subtle issues:

- coping with reading stale data
- the fact that deleted objects can exist in collection
- rules for removing global pointers to objects before deferred free
- can you pop an object from a lock-free collection and immediately insert 
it into another?
- can you mix per-object non-atomic refcounting with lock-free collections?


A simple generic solution for the last two is to have writer threads inc an 
objects refcount before the deferred function is called, and have the 
deferred function decrement the per-object refcount. That would extend 
object lifetime and would allow for objects to concurrently exist in 
multiple lock-free linked lists and be passed between them at will without 
using true atomic refcounts. And all the refcount inc's and dec's will be 
only be performed by writer threads; readers need not bother with adjusting 
per-object refcounts. Of course this only scratched the surface...

:O

.