Subject: Re: [boost] [lockfree] review
From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2011-09-15 14:05:24
Hans Boehm wrote:
> Alexander Terekhov <terekhov <at> web.de> 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
lock_queue_wait() is meant to block the calling thread and set waiters
bit only if locked bit is actually set (an RMW operation).
The races for setting/clearing bits are resolved by RMWs on the same
(&lock) memory location.
The situation is no different when (&lock) memory location would be
protected by a lock except that with RMWs the program is lock-free on