[concurrency-interest] Lock-free mania

Joseph Seigh jseigh_cp00 at xemaps.com
Mon Apr 16 22:02:45 EDT 2007

Eric Crahen wrote:

> */Joseph Seigh <jseigh_cp00 at xemaps.com>/* wrote:
>     Testing isn't necessarily all that difficult either. Some lock-free
>     algorithms allow you to make
>     observations that aren't available to lock based algorithms. You can
>     use this to verify that
>     your code works under some boundary conditions, e.g. that you've
>     avoided
>     certain race
>     conditions.
> That's very interesting. Do you have any examples of using this to 
> your advantage in testing a lock-less data structure?

In testing PDR (PCOW Deferred Reclamation) algorithms, I usually  add a 
state to memory objects (
current, stale (pending reclamation), and deallocated, and make a count 
of the observed stated.  If
you see a high enough stale count without seeing any deallocated objects 
(which you shouldn't see from
an application program), you know you are getting preempted threads 
holding references to objects
pending reclamation and the memory reclamation is working by not 
deallocating the objects too soon.
I believe Paul McKenney uses the same technque to stress test RCU in the 
Linux kernel.

In lock-free, usually your boundary conditions have race conditions (the 
race condition being on the
safe side).  If you can detect executions in the race condition 
interval, you know you're executing
near the boundary but staying on the safe side.

Joe Seigh

More information about the Concurrency-interest mailing list