Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #670

Re: Locking primitives in userspace

Show all headers | View raw

Steve Thompson wrote:
> 
> I've been writing some multi-threaded code and have some question
> about userspace locking primitives and best practices.
> 
> Firstly, I've written my own locking primitives, possibly for no other
> reason than to be familiar with the low-level details.  I've read
> Ulrich Drepper's paper[0] on "fast userspace mutexes", which discusses
> the kernel futex facility and considered the pthread_mutex_* calls
> which one might use.  There are also POSIX semaphores.

Linux's futex interface isn't really optimal for mutexes and condvars 
because the kernel doesn't maintain 'waiters bit' (e.g. 0x80000000) 
indicating that there are queued waiters. 

With waiters bit, mutex would be simply 

  WHILE atomic_bit_test_set_hlb(&lock, 1) // efficient 'acquire' 
    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) 
     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_rel_hlb(&lock) 
    lock_queue_wait(&lock, 0) // wait if sema value is zero

sema_unlock:

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

(Semaphores need stronger memory barriers because they can be used as
atomic flags/counters with lock() signalling something and unlock()
consuming the signal.)

For condvar, it is better to let the kernel set waiters bit and then
unlock the associated mutex. 

The signal would be simply 

   IF cv_queue 
     THEN cv_queue_wake(&cv_queue, 1) 

and broadcast 

   IF cv_queue 
     THEN cv_queue_wake(&cv_queue, UINT_MAX) 

regards, 
alexander.

Back to comp.programming.threads | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Locking primitives in userspace Steve Thompson <thomps2048@yahoo.ca> - 2011-10-30 16:26 -0400
  Re: Locking primitives in userspace Steve Thompson <thomps2048@yahoo.ca> - 2011-11-06 06:54 -0500
    Re: Locking primitives in userspace Mark <i@dontgetlotsofspamanymore.invalid> - 2011-11-07 11:42 +0000
      Re: Locking primitives in userspace Steve Thompson <thomps2048@yahoo.ca> - 2011-11-10 09:42 -0500
  Re: Locking primitives in userspace Alexander Terekhov <terekhov@web.de> - 2011-11-08 08:30 +0100

csiph-web