A semaphore is a programming construct designed by E. W. Dijkstra in the late 1960s. Dijkstra's model was the operation of railroads. Consider a stretch of railroad where a single track is present over which only one train at a time is allowed.
A semaphore synchronizes travel on this track. A train must wait before entering the single track until the semaphore is in a state that permits travel. When the train enters the track, the semaphore changes state to prevent other trains from entering the track. A train that is leaving this section of track must again change the state of the semaphore to allow another train to enter.
In the computer version, a semaphore appears to be a simple integer. A thread waits for permission to proceed and then signals that the thread has proceeded by performing a P operation on the semaphore.
The thread must wait until the semaphore's value is positive, then change the semaphore's value by subtracting 1 from the value. When this operation is finished, the thread performs a V operation, which changes the semaphore's value by adding 1 to the value. These operations must take place atomically. These operations cannot be subdivided into pieces between which other actions on the semaphore can take place. In the P operation, the semaphore's value must be positive just before the value is decremented, resulting in a value that is guaranteed to be nonnegative and 1 less than what it was before it was decremented.
In both P and V operations, the arithmetic must take place without interference. The net effect of two V operations performed simultaneously on the same semaphore, should be that the semaphore's new value is 2 greater than it was.
The mnemonic significance of P and V is unclear to most of the world, as Dijkstra is Dutch. However, in the interest of true scholarship: P stands for prolagen, a made-up word derived from proberen te verlagen, which means try to decrease. V stands for verhogen, which means increase. The mnemonic significance is discussed in one of Dijkstra's technical notes, EWD 74.
sem_wait(3RT) and sem_post(3RT) correspond to Dijkstra's P and V operations. sem_trywait(3RT) is a conditional form of the P operation. If the calling thread cannot decrement the value of the semaphore without waiting, the call to returns immediately with a nonzero value.
The two basic sorts of semaphores are binary semaphores and counting semaphores. Binary semaphores never take on values other than zero or one, and counting semaphores take on arbitrary nonnegative values. A binary semaphore is logically just like a mutex.
However, although not always enforced, mutexes should be unlocked only by the thread that holds the lock. Because no notion exists of “the thread that holds the semaphore,” any thread can perform a V or sem_post (3RT) operation.
Counting semaphores are nearly as powerful as conditional variables when used in conjunction with mutexes. In many cases, the code might be simpler when implemented with counting semaphores rather than with condition variables, as shown in Example 4–14, Example 4–15, and Example 4–16.
However, when a mutex is used with condition variables, an implied bracketing is present. The bracketing clearly delineates which part of the program is being protected. This behavior is not necessarily the case for a semaphore, which might be called the go to of concurrent programming. A semaphore is powerful but too easy to use in an unstructured, indeterminate way.