Updated 2018-07-13 22:20:04 by pooryorick ▲

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

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). AW unlikely, since the verb Passeren means 'to pass (through)'.

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 guaranteed 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 2003-06-02: The 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...

AW: And it would be nice to have support for this since going through the file system is slow, not to mention the cleanup problems when crashing while locked (since the file remains on disk, the lock remains and everything comes to a halt. Note that I am talking interprocess locking, not intra-process). At least on windows, a real (provided by the OS) mutex will be released by the system, whatever the way your program terminates. I recently learned however that no equivalent exists on OsX, and since that is bsd based I assume Linux is the same?

elfring 2003-10-19: I recommend the following information sources.

lexfiend 2005-12-08: Also see [2] for some insight into when semaphores are not necessary.

See also The Montana, Utah & Texas for a railroad visualisation of mutex semaphores :)

AW: The tcl thread extension has mutexes, however these are only intraprocess, not interprocess, i.e. your having the mutex is visible in other threads of your program, but not in other programs.

Tcl semaphore package.

Category Threads