Re: [boost] [lockfree] review

Subject: Re: [boost] [lockfree] review
From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2011-08-31 16:59:07

Hans Boehm wrote:
[...]
> Although the existence of such an algorithm is interesting, the point is that
> 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 used)
> is orders of magnitude simpler.  If you understand the complex algorithm, we
> 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) 

for unlock() (lock_queue uintptr_t pointer may become indeterminate by
the time of lock_queue_wake() and implementation should handle it
(spurious wakes are okay)).

Similarly, for semaphore:

sema_lock:

  WHILE !atomic_decrement_if_binand_7FFFFFFF_is_not_zero_hlb(&lock) 
    lock_queue_wait(&lock, 0) // wait if sema value is zero

sema_unlock:

  uintptr_t lock_queue
  IF atomic_increment_rel(lock_queue = &lock) > 0x80000000
    THEN lock_queue_wake(lock_queue, 1)

regards,
alexander.