Semaphores are special constructs invented by E. W. Dijkstra for concurrent process synchronization. Only two operations are allowed on semaphores: wait and signal (originally called P and V operations respectively by Dijkstra). There is usually a count and a queue associated with each semaphore. The wait and signal operations must be done indivisibly, in the sense that only one process can operate on a semaphore at any one time. This can be achieved on a single-processor system like the PC by simply disabling interrupts during such operations. Wait and signal may be implemented as follows:wait(S): If the count of semaphore S is greater than zero, subtract 1 from it and continue, otherwise put the calling thread in semaphore S's queue and schedule the execution of another ready-to-run thread.
signal(S): If no thread is waiting on semaphore S, add 1 to its count and continue, otherwise move the first thread waiting in semaphore S's queue to the ready-to-run queue.
The wait operation allows a process or thread to relinquish use of the CPU to other ready-to-run processes or threads when it is waiting on a certain event to occur. When such an event occurs, a signal operation can be used to inform the waiting process to proceed with its normal operation.
A semaphore can be thought of as a jar holding cookies. The count associated with the semaphore corresponds to the number of cookies in the jar. Each wait operation is analogous to removing a cookie from the jar. When the jar is empty, one has to wait until someone tosses in some more cookies (signal operations).
Semaphores serve many useful purposes. For example, they may be used to guard against concurrent access of shared variables among a number of concurrent threads, or to synchronize the execution of two threads. The following example demonstrates the latter:
Thread #1 Thread #2 {processing) {processing} wait(checkpoint) signal(checkpoint) {processing} {processing}Here, checkpoint is a semaphore with a count of zero. The jar is empty. When thread #1 performs the wait operation, it blocks itself (since the jar is empty) until thread #2 signals it to resume (puts a cookie in the jar). And this concludes our short introduction to counting semaphores.