Subj : Re: RCU+SMR
To   : comp.programming.threads
From : Chris Thomasson
Date : Sat Jul 09 2005 06:42 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 util it was empty and then repeated the whole
> process by grabbing the shared LIFO stack again.

Yep. That works very well. I have used the simple scheme for a while as 
well. I used an atomic exchange for the consumers:


typedef struct n_
{
  struct n_ *next; /* = 0 */
  void *state;

} n_t;


typedef struct q_
{
  n_t *front; /* = 0 */

} q_t;




static q_t q;




// producer

n_t *o, *c, *n = malloc( sizeof( *n ) );

o = q.front;

do
{
  n->next = o;
  c = o;
  o = InterlockedCompareExchangePointer
        ( &q.front,
          n,
          c );
}

while ( c != o );




// consumer

n_t *f = InterlockedExchangePointer( &q.front, 0 );

if ( ! f ) { return EAGAIN; }

// reverse order of f, and process.




LIFO producers are inherently not affected by aba. On the other hand, LIFO 
consumers are affected, but only if there is a "compare" type method being 
used for synchronization. Using an atomic exchange to set the stack anchor 
to zero can get around aba wrt LIFO lock-free stacks. Was that similar to 
your initial solution?


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

.