In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple threads and avoid critical section problems in a concurrent system such as a multitasking operating system.
A trivial semaphore is a plain variable that is changed (for example, incremented or decremented, or toggled) depending on programmer-defined conditions.
Suppose a physical library has ten identical study rooms, to be used by one student at a time.
When a student requests a room, they are granted access, and the value of the semaphore is changed to 9.
Some other mechanism (possibly involving more semaphores) may be required to select a particular free resource.
The paradigm is especially powerful because the semaphore count may serve as a useful trigger for a number of different actions.
This includes: Even if all processes follow these rules, multi-resource deadlock may still occur when there are different resources managed by different semaphores and when processes need to use more than one resource at a time, as illustrated by the dining philosophers problem.
Atomicity may be achieved by using a machine instruction that can read, modify, and write the semaphore in a single operation.
Without such a hardware instruction, an atomic operation may be synthesized by using a software mutual exclusion algorithm.
On uniprocessor systems, atomic operations can be ensured by temporarily suspending preemption or disabling hardware interrupts.
This approach does not work on multiprocessor systems where it is possible for two programs sharing a semaphore to run on different processors at the same time.
To solve this problem in a multiprocessor system, a locking variable can be used to control access to the semaphore.
The producer does the following repeatedly: The consumer does the following repeatedly Below is a substantive example: Note that emptyCount may be much lower than the actual number of empty places in the queue, for example, where many producers have decremented it but are waiting their turn on useQueue before filling empty places.
Note that emptyCount + fullCount ≤ N always holds, with equality if and only if no producers or consumers are executing their critical sections.
The "Passing the baton" pattern[3][4][5] proposed by Gregory R. Andrews is a generic scheme to solve many complex concurrent programming problems in which multiple processes compete for the same resource with complex access conditions (such as satisfying specific priority criteria or avoiding starvation).
Several explanations have been offered for P, including proberen ("to test" or "to try"),[6] passeren ("pass"), and pakken ("grab").
Dijkstra subsequently wrote that he intended P to stand for prolaag,[7] short for probeer te verlagen, literally "try to reduce", or to parallel the terms used in the other case, "try to decrease".
In software engineering practice, they are often called signal and wait,[12] release and acquire[12] (standard Java library),[13] or post and pend.