 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Semaphore" programming – news ·newspapers ·books ·scholar ·JSTOR(September 2025) (Learn how and when to remove this message) |
Incomputer science, asemaphore is avariable orabstract data type used to control access to a common resource by multiplethreads and avoidcritical section problems in aconcurrent system such as amultitasking operating system. Semaphores are a type ofsynchronization primitive. A trivial semaphore is a plain variable that is changed (for example, incremented or decremented, or toggled) depending on programmer-defined conditions.
A useful way to think of a semaphore as used in a real-world system is as a record of how many units of a particular resource are available, coupled with operations to adjust that recordsafely (i.e., to avoidrace conditions) as units are acquired or become free, and, if necessary, wait until a unit of the resource becomes available.
Though semaphores are useful for preventing race conditions, they do not guarantee their absence. Semaphores that allow an arbitrary resource count are calledcounting semaphores, while semaphores that are restricted to the values 0 and 1 (or locked/unlocked, unavailable/available) are calledbinary semaphores and are used to implementlocks.
The semaphore concept was invented byDutchcomputer scientistEdsger Dijkstra in 1962 or 1963,[1] when Dijkstra and his team were developing anoperating system for theElectrologica X8. That system eventually became known as theTHE multiprogramming system.
Suppose a physicallibrary has ten identical study rooms, to be used by one student at a time. Students must request a room from the front desk. If no rooms are free, students wait at the desk until someone relinquishes a room. When a student has finished using a room, the student must return to the desk and indicate that the room is free.
In the simplest implementation, theclerk at thefront desk knows only the number of free rooms available. This requires that all of the students use their room while they have signed up for it and return it when they are done. When a student requests a room, the clerk decreases this number. When a student releases a room, the clerk increases this number. The room can be used as long as desired and rooms cannot be booked in advance.
In this scenario, the front desk count-holder represents a counting semaphore, the rooms are the resource, and the students representprocesses/threads. The value of the semaphore in this scenario is initially 10, with all rooms empty. When a student requests a room, they are granted access, and the value of the semaphore is changed to 9. After the next student comes, it drops to 8, then 7, and so on. If someone requests a room and the current value of the semaphore is 0,[2] they are forced to wait until a room is freed (when the count is increased from 0). If one of the rooms was released, but there are several students waiting, any method can be used to select the one who will occupy the room (likeFIFO or random selection). And of course, a student must inform the clerk about releasing their room only after leaving it.
When used to control access to apool of resources, a semaphore tracks onlyhow many resources are free. It does not keep track ofwhich of the resources are free. 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. The librarian above may turn the lights off in the study hall when there are no students remaining, or may place a sign that says the rooms are very busy when most of the rooms are occupied.
The success of the protocol requires applications to follow it correctly. Fairness and safety are likely to be compromised (which practically means a program may behave slowly, act erratically,hang, orcrash) if even a single process acts incorrectly. This includes:
Even if all processes follow these rules,multi-resourcedeadlock 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 thedining philosophers problem.
Counting semaphores are equipped with two operations, historically denoted as P and V (see§ Operation names for alternative names). Operation V increments the semaphoreS, and operation P decrements it.
The value of the semaphoreS represents the number of units of available resource units when non-negative. In some implementations, negative values indicate the number of processes waiting for the resource. The P operationwastes time orsleeps until a resource protected by the semaphore becomes available, at which time the resource is immediately claimed. The V operation is the inverse: it makes a resource available again after the process has finished using it.One important property of semaphoreS is that its value cannot be changed except by using the V and P operations.
A simple way to understandwait (P) andsignal (V) operations is:
Many operating systems provide efficient semaphore primitives that unblock a waiting process when the semaphore is incremented. This means that processes do not waste time checking the semaphore value unnecessarily.
The counting semaphore concept can be extended with the ability to claim or return more than one "unit" from the semaphore, a technique implemented inUnix. The modified V and P operations are as follows, using square brackets to indicateatomic operations, i.e., operations that appear indivisible to other processes:
function V(semaphore S, integer I): [S ← S + I]function P(semaphore S, integer I):repeat: [if S ≥ I: S ← S − Ibreak]
However, the rest of this section refers to semaphores with unary V and P operations, unless otherwise specified.
To avoidstarvation, a semaphore has an associatedqueue of processes (usually withFIFO semantics). If a process performs a P operation on a semaphore that has the value zero, the process is added to the semaphore's queue and its execution is suspended. When another process increments the semaphore by performing a V operation, and there are processes on the queue, one of them is removed from the queue and resumes execution. When processes have different priorities the queue may be ordered thereby, such that the highest priority process is taken from the queue first.
If the implementation does not ensure atomicity of the increment, decrement, and comparison operations, there is a risk of increments or decrements being forgotten, or of the semaphore value becoming negative. Atomicity may be achieved by using a machine instruction that canread, modify, and write the semaphore in a single operation. Without such a hardware instruction, an atomic operation may be synthesized by using asoftware mutual exclusion algorithm. Onuniprocessor systems, atomic operations can be ensured by temporarily suspendingpreemption or disabling hardwareinterrupts. 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 locking variable is manipulated using atest-and-set-lock command.
Consider a variableA and a boolean variableS.A is only accessed whenS is marked true. Thus,S is a semaphore forA.
One can imagine a stoplight signal (S) just before a train station (A). In this case, if the signal is green, then one can enter the train station. If it is yellow or red (or any other color), the train station cannot be accessed.
Consider a system that can only support ten users (S=10). Whenever a user logs in, P is called, decrementing the semaphoreS by 1. Whenever a user logs out, V is called, incrementingS by 1 representing a login slot that has become available. WhenS is 0, any users wishing to log in must wait untilS increases. The login request is enqueued onto a FIFO queue until a slot is freed.Mutual exclusion is used to ensure that requests are enqueued in order. WheneverS increases (login slots available), a login request is dequeued, and the user owning the request is allowed to log in. IfS is already greater than 0, then login requests are immediately dequeued.
In theproducer–consumer problem, one process (the producer) generates data items and another process (the consumer) receives and uses them. They communicate using a queue of maximum sizeN and are subject to the following conditions:
The semaphore solution to the producer–consumer problem tracks the state of the queue with two semaphores:emptyCount, the number of empty places in the queue, andfullCount, the number of elements in the queue. To maintain integrity,emptyCount may be lower (but never higher) than the actual number of empty places in the queue, andfullCount may be lower (but never higher) than the actual number of items in the queue. Empty places and items represent two kinds of resources, empty boxes and full boxes, and the semaphoresemptyCount andfullCount maintain control over these resources.
The binary semaphoreuseQueue ensures that the integrity of the state of the queue itself is not compromised, for example, by two producers attempting to add items to an empty queue simultaneously, thereby corrupting its internal state. Alternatively amutex could be used in place of the binary semaphore.
TheemptyCount is initiallyN,fullCount is initially 0, anduseQueue is initially 1.
The producer does the following repeatedly:
produce: P(emptyCount) P(useQueue) putItemIntoQueue(item) V(useQueue) V(fullCount)
The consumer does the following repeatedly
consume: P(fullCount) P(useQueue) item ← getItemFromQueue() V(useQueue) V(emptyCount)
Below is a substantive example:
fullCount is 0, the consumer blocks.emptyCount constraining their entry.useQueue and deposit items in the queue.fullCount is incremented, allowing one consumer to enter its critical section.Note thatemptyCount 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 onuseQueue before filling empty places. Note thatemptyCount + 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). Given a shared resource, the pattern requires a private "priv" semaphore (initialized to zero) for each process (or class of processes) involved and a single mutual exclusion "mutex" semaphore (initialized to one). The pseudo-code for each process is:
voidprocess(intproc_id,intres_id){resource_acquire(proc_id,res_id);<usetheresourceres_id>;resource_release(proc_id,res_id);}
The pseudo-code of the resource acquisition and release primitives are:
voidresource_acquire(intproc_id,intres_id){P(mutex);if(<theconditiontoaccessres_idisnotverifiedforproc_id>){<indicatethatproc_idissuspendedforres_id>;V(mutex);P(priv[proc_id]);<indicatethatproc_idisnotsuspendedforres_idanymore>;}<indicatethatproc_idisaccessingtheresource>;pass_the_baton();// See below}
voidresource_release(intproc_id,intres_id){P(mutex);<indicatethatproc_idisnotaccessingtheresourceres_idanymore>;pass_the_baton();// See below}
Both primitives in turn use the "pass_the_baton" method, whose pseudo-code is:
voidpass_the_baton(intres_id){if/* <the condition to access res_id is true for at least one suspended process> */{intp=<choosetheprocesstowake>;V(priv[p]);}else{V(mutex);}}
Remarks
The pattern is called "passing the baton" because a process that releases the resource as well as a freshly reactivated process will activate at most one suspended process, that is, shall "pass the baton to it". The mutex is released only when a process is going to suspend itself (resource_acquire), or when pass_the_baton is unable to reactivate another suspended process.
The canonical names V and P come from the initials ofDutch words. V is generally explained asverhogen ("increase"). Several explanations have been offered for P, includingproberen ("to test" or "to try"),[6]passeren ("pass"), andpakken ("grab"). Dijkstra's earliest paper on the subject[1] givespassering ("passing") as the meaning forP, andvrijgave ("release") as the meaning for V. It also mentions that the terminology is taken from that used in railroad signals. Dijkstra subsequently wrote that he intendedP to stand forprolaag,[7] short forprobeer te verlagen, literally "try to reduce", or to parallel the terms used in the other case, "try to decrease".[8][9][10]
InALGOL 68, theLinux kernel,[11] and in some English textbooks, theV andP operations are called, respectively,up anddown. In software engineering practice, they are often calledsignal andwait,[12]release andacquire[12] (standardJava library),[13] orpost andpend. Some texts call themvacate andprocure to match the original Dutch initials.[14][15]
Amutex is alocking mechanism that sometimes uses the same basic implementation as the binary semaphore. However, they differ in how they are used. While a binary semaphore may be colloquially referred to as a mutex, a true mutex has a more specific use-case and definition, in that only thetask that locked the mutex is supposed to unlock it. This constraint aims to handle some potential problems of using semaphores:
java.util.concurrent.Semaphore| General | |
|---|---|
| Process calculi | |
| Classic problems | |
| General | |
|---|---|
| Levels | |
| Multithreading | |
| Theory | |
| Elements | |
| Coordination | |
| Programming | |
| Hardware | |
| APIs | |
| Problems | |
