Re: [boost] [lockfree] review

Subject: Re: [boost] [lockfree] review
From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2011-08-31 09:20:03

Hans Boehm wrote:
[...]
> > I'm really interested to know the exact number/names of algorithms.
> I asked Doug Lea this question 3 or 4 years ago when this was still being
> actively discussed.  He's more of an expert on practical concurrent
> algorithms.  I got back a bunch of answers.  One simple and common example is
> the algorithm for releasing a queued lock.  I need to set the lock state to
> unlocked and then check the queue for waiters.  If those are reordered, I get
> lost wakeup problems.  ... 

Dejavu...

http://www.mailarchive.ca/lists/comp.unix.solaris/2003-12/0937.html#start937

The relevant part is:

------
> > > and subsequent store-load barrier + load to check whether you have a
> > > blocked waiter to unblock? Store-load barrier is known to be "the most
> > > expensive"...
> > 
> > The store-load barrier is avoided by carefully setting up the sleeping and
> > blocking interactions so that the above code + the slow paths can
> > never loose a waiter.
> 
> And you can do it without atomic read-{modify-}write on the fast 
> path in mutex_exit()? Hmm. Please elaborate.

Casper already got this, but here: 

1. As long as the thread is on-CPU, you spin. Blocking is a four-stage
process: 
2. atomically set the waiters bit, 
3. re-scan all of the other CPUs on the system, checking to make sure
the owner is still not running on them. 
4. check that the lock hasn't changed while you were looking. 
5. Finally, block. If any of the above steps fail, you go back to
spinning. 
6. if a thread is in the "critical section" (i.e. after the load and
before the clear) when we are resuming it (either from an interrupt or
in a context switch), we back up the program counter to the beginning of
mutex_exit.
 
There are further complications, but that's the crucial bit. 

• jonathan 

Received on Tue Dec 09 2003 - 17:05:23 PST
------

regards,
alexander.