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'' (''mut''ual ''ex''clusion 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 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 recommend the following information sources. * http://tutorgig.com/encyclopedia/getdefn.jsp?query=Semaphore * 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. [lexfiend] 8 Dec 2005: Also see [http://groups.google.com/group/comp.lang.tcl/browse_thread/thread/8c180128d0f19d7/4a07846980cc3f45] for some insight into when semaphores are ''not'' necessary. ---- See also [The Montana, Utah & Texas] for a railroad visualisation of mutex semaphores :) ---- [[ [Category Threads] ]]