Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From: Alexander Terekhov <terekhov@web.de>
Newsgroups: comp.programming.threads
Subject: Re: mutex and condition variable implementation using futex
Date: Mon, 15 Aug 2011 11:31:59 +0200
Organization: A noiseless patient Spider
Lines: 38
Message-ID: <4E48E78F.5A0B6048@web.de>
References: <6752ab19-9142-471e-8b83-14fdc3784567@glegroupsg2000goo.googlegroups.com>
Reply-To: terekhov@web.de
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Injection-Info: mx04.eternal-september.org; posting-host="MCbSEzW5qwGLFMNXJh39IQ"; logging-data="7673"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19jiYu69J65H7FFnzdxrXzhS6zfMUaJzRQ="
X-Mailer: Mozilla 4.77 [en] (Windows NT 5.0; U)
X-Accept-Language: en
Cancel-Lock: sha1:zkEaY9wLTzVP8vYTwClttUPHccA=
Xref: x330-a1.tempe.blueboxinc.net comp.programming.threads:513


Sudhanshu Shukla wrote:
[...]
> Any hints for further optimizing the mutex and condition variables 
> would be greatly appreciated.

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.

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.