Version 13 of semaphores

Updated 2003-10-19 15:27:40

Invented by Edsger Dijkstra as a low-level synchronization primitive.

A semaphore holds an integer >= 0, and supports two atomic operations: P(S) (or wait) and V(S) (or signal). V(S) atomically increments the value of S; P(S) atomically decrements it if S > 0, otherwise it blocks until some other task executes V(S).

One common use of semaphores is to implement mutexes (mutual exclusion locks). Each shared resource is guarded by a semaphore; the resource is unlocked when S = 1 and locked when S = 0. P(S) acquires the lock (blocking if necessary) and V(S) releases it (awakening any tasks blocked waiting for the lock). By initializing P to some number n > 0, semaphores can also support n-at-a-time access.

P and V stand for the Dutch words proberen (to test) and verhogen (to increment). - RS learnt that they're from railroad terminology, where semaphores guard blocks of track: P(asseren - red light) and V(rijgeven - green light).


ulis, 2003-05-31:

Semaphores operation can be generalized to permit more than one consumer by initializing the semaphore counter to more than 1.

It was demonstrated that the implementation of a semaphore needs a test and set operation. Such an operation is an atomic operation that permits without interference to test if a counter is zero and increment it.

A lock file is a kind of semaphore and the test and set operation is implemented with [open $fn {WRONLY CREAT EXCL}]. This operation is garanteed an atomic operation by most of the operating systems.

For others implementations, see: How do I manage lock files in a cross platform manner in Tcl

DKF (02-Jun-2003) notes that most processors have something equivalent to a test-and-set operation that sets a bus flag to lock out other processors in the SMP cluster. That's the basis for all the semaphore/mutex/critical-section code in higher-level libraries...


elfring 19 Oct 2003 I recommed the following information sources.

  • The documents by Kenneth A. Reek on the topic "The Well-Tempered Semaphore: Theme With Variations" on the page

"http://www.cs.rit.edu/~kar/papers/index.html " describe different synchronization semantics. The semantics of implementations by E. W. Dijkstra, POSIX, C. A. R. Hoare and P. Brinch Hansen are compared.


[ Category Threads ]