Boost logo

Boost :

Subject: Re: [boost] [lockfree] review
From: Hans Boehm (Hans.Boehm_at_[hidden])
Date: 2011-09-13 19:47:04

Alexander Terekhov <terekhov <at>> writes:

> Hans Boehm wrote:
> [...]
> > Although the existence of such an algorithm is interesting, the point is
> > avoiding the equivalent of the sequentuially consistent store here is
> > incredibly complicated, appears to require scheduler help and, at least for
> > me, would require careful study of the proof before I were willing to
> > implement it. On the other hand, the algorithm using the equivalent of
> > sequentially consistent atomics (which I think is still far more widely
> > is orders of magnitude simpler. If you understand the complex algorithm,
> > assume you can add the ordering constraints corectly.
> With waiters bit (0x80000000) and atomic RMW, mutex is simply:
> (pseudo-code below)
> WHILE atomic_bit_test_set_hlb(&lock, 1) // efficient acquire MO
> lock_queue_wait(&lock, 1) // wait if locked bit is set
> for lock() and
> uintptr_t lock_queue
> IF atomic_decrement_rel(lock_queue = &lock) // release MO
> THEN lock_queue_wake(lock_queue, 1)
I'm not sure I understand your syntax here.

I don't see the correctness argument. What prevents the sequence:

1. In thread T0, performing unlock, atomic_decr_rel update completes, sees no
waiters, puts updated (released) lock word in store buffer. (I'm informally
viewing memory_order_release as just putting a value in a store buffer, which
I think is reasonable here.)
2. Thread T1 tries to acquire the lock, sees it still held, since store buffer
hasn't drained. Enqueues itself.
3. Thread T0s store buffer drains. Thread T1 is now waiting on an unlocked

The real point here again is that such arguments are subtle. I don't want to
have to deal with them unless performance considerations warrant that I do,
especially since we have lots of evidence that even experts get these things


Boost list run by bdawes at, gregod at, cpdaniel at, john at