Version 12 of semaphores

Updated 2003-07-03 14:34:32

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...


[ Category Threads ]