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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk