Semaphore (programming)

From Wikipedia, the free encyclopedia - View original article

Jump to: navigation, search

In computer science, particularly in operating systems, a semaphore is a variable or abstract data type that is used for controlling access, by multiple processes, to a common resource in a parallel programming or a multi user environment.

A useful way to think of a semaphore is as a record of how many units of a particular resource are available, coupled with operations to safely (i.e., without race conditions) adjust that record as units are required or become free, and, if necessary, wait until a unit of the resource becomes available. Semaphores are a useful tool in the prevention of race conditions; however, their use is by no means a guarantee that a program is free from these problems. Semaphores which allow an arbitrary resource count are called counting semaphores, while semaphores which are restricted to the values 0 and 1 (or locked/unlocked, unavailable/available) are called binary semaphores.

The semaphore concept was invented by Dutch computer scientist Edsger Dijkstra in 1965,[1] and has found widespread use in a variety of operating systems.

Library analogy[edit]

Suppose a library has 10 identical study rooms, to be used by one student at a time. To prevent disputes, students must request a room from the front desk if they wish to make use of a study room. When a student has finished using a room, the student must return to the desk and indicate that one room has become free. If no rooms are free, students wait at the desk until someone relinquishes a room.

The clerk at the front desk does not keep track of which room is occupied or who is using it, nor does he or she know if the room is actually being used, only the number of free rooms available, which she only knows correctly if all of the students actually use their room and return them when they're done. When a student requests a room, the clerk decreases this number. When a student releases a room, the clerk increases this number. Once access to a room is granted, the room can be used for as long as desired, and so it is not possible to book rooms ahead of time.

In this scenario the front desk represents a semaphore, the rooms are the resources, and the students represent processes. The value of the semaphore in this scenario is initially 10. When a student requests a room he or she is 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 resulting value of the semaphore is negative,[2] they are forced to wait. When multiple people are waiting, they will either wait in a queue, or use round-robin scheduling and race back to the desk when someone releases a room (depending on the nature of the semaphore).

Important observations[edit]


Processes are trusted to follow the protocol. Fairness and safety are likely to be compromised (which practically means a program may behave slowly, act erratically, hang or crash) if even a single process acts incorrectly. This includes:


Semantics and implementation[edit]

Counting semaphores are equipped with two operations, historically denoted as V (also known as signal()) and P (or wait())(see below). Operation V increments the semaphore S, and operation P decrements it. The semantics of these operations are shown below. Square brackets are used to indicate atomic operations, i.e., operations which appear indivisible from the perspective of other processes.


A simple way to understand wait() and signal() operations is:


The counting semaphore concept can be extended with the ability to claim or return more than one "unit" from the semaphore, a technique implemented in UNIX. The modified V and P operations are as follows:

 function V(semaphore S, integer I):     [S ← S + I]  function P(semaphore S, integer I):     repeat:         [if S >= I:             S ← S - I             break] 

To avoid starvation, a semaphore has an associated queue of processes (usually a first-in, first out). 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 by priority, so that the highest priority process is taken from the queue first.


Example: Producer/consumer problem[edit]





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) 




Function name etymology[edit]

The canonical names V and P come from the initials of Dutch words. V stands for verhogen ("increase"). Several explanations have been offered for P, including proberen for "to test" or "to try,"[3] passeren for "pass," and pakken for "grab." However, Dijkstra wrote that he intended P to stand for the portmanteau prolaag,[4] short for probeer te verlagen, literally "try to reduce," or to parallel the terms used in the other case, "try to decrease."[5][6][7] This confusion stems from the fact that the words for increase and decrease both begin with the letter V in Dutch, and the words spelled out in full would be impossibly confusing for those not familiar with the Dutch language.

In ALGOL 68, the Linux kernel,[8] and in some English textbooks, the V and P operations are called, respectively, up and down. In software engineering practice, they are often called signal and wait, release and acquire (which the standard Java library[9] uses), or post and pend. Some texts call them vacate and procure to match the original Dutch initials.

Semaphores vs. mutexes[edit]


  1. Mutexes have a concept of an owner, which is the process that locked the mutex. Only the process that locked the mutex can unlock it. In contrast, a semaphore has no concept of an owner. Any process can unlock a semaphore.
  2. Unlike semaphores, mutexes provide priority inversion safety. Since the mutex knows its current owner, it is possible to promote the priority of the owner whenever a higher-priority task starts waiting on the mutex.
  3. Mutexes also provide deletion safety, where the process holding the mutex cannot be accidentally deleted. Semaphores do not provide this.

See also[edit]

Notes and references[edit]

  1. ^ Dijkstra, Edsger W. Cooperating sequential processes (EWD-123). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription) (September 1965)
  2. ^ The Little Book of Semaphores Allen B. Downey
  3. ^ Silberschatz, Galvin & Gagne 2008, p. 234
  4. ^ Dijkstra, Edsger W. EWD-74. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription)
  5. ^ Dijkstra, Edsger W. MULTIPROGAMMERING EN DE X8 (EWD-51). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin.  (original; transcription) (in Dutch)
  6. ^ Dijkstra's own translation reads "try-and-decrease", although that phrase might be confusing for those unaware of the colloquial "try-and..."
  7. ^ (PATCH 1/19) MUTEX: Introduce simple mutex implementation Linux Kernel Mailing List, 19 December 2005
  8. ^ Linux Kernel hacking HOWTO
  9. ^ java.util.concurrent.Semaphore

External links[edit]