Boost logo

Boost :

From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2003-06-05 11:48:01

"Victor A. Wagner, Jr." wrote:
> I'm baffled that they want to penalize (time and space) those for whom a
> naked semaphore works.

Show me please an example illustrating "naked semaphore" in work.
> It's blatantly clear to anyone who's had to write a
> mutex that it's additional code on TOP of a semaphore.

Optimization strategies aside for a moment (they are different for mutexes and
semaphores) a binary semaphore can be used as "normal" POSIX mutex.

 Mutexes and semaphores

 A mutex is represented by a pair (Lock-bit, Queue). The Lock-bit is 1 if a thread
 is in a critical section protected by the mutex, and is 0 otherwise. In terms of the
 formal specification, the Lock-bit is 0 iff the mutex is NIL. The Queue contains the
 threads that are blocked in Acquire (awaiting its WHEN condition).

 The user code for Acquire and Release is designed for fast execution of a LOCK
 clause when there is no contention for its mutex. In this case an Acquire-Release
 pair executes a total of 5 instructions, taking 10 microseconds on a MicroVAX II.
 This code is compiled entirely in-line. Acquire consists of two sequential actions:
 test-and-set the Lock-bit (implemented atomically in the hardware); call a Nub
 subroutine if the bit was already set. The user code for Release is two sequential
 actions: clear the Lock-bit; call a Nub subroutine if the Queue is not empty.

 The Nub subroutine for Acquire (after acquiring the spin-lock) first adds the
 calling thread to the Queue. Then it tests the Lock-bit again. If it is still 1, this
 thread is de-scheduled and the general scheduling algorithm is invoked to determine
 what to do with this processor. On the other hand, if the Lock-bit is now 0, the
 thread is removed from the Queue, the spin-lock is released, and the entire Acquire
 operation (beginning at the test-and-set) is retried.

 The Nub subroutine for Release (after acquiring the spin-lock) checks to see if
 there are any threads in the Queue. If there are, it takes one, adds it to the ready
 pool, and invokes the general scheduling algorithm, which will assign the thread to
 a suitable processor if one is available.

 The implementation of semaphores is the same as mutexes: P is the same as
 Acquire and V is the same as Release.


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