Semaphore (programming)

For other uses, see Semaphore.

In computer science, a semaphore is a protected variable or abstract data type which constitutes the classic method for restricting access to shared resources such as shared memory in a parallel programming environment. A counting semaphore is a counter for a set of available resources, rather than a locked/unlocked flag of a single resource. It was invented by Edsger Dijkstra^[1]. Semaphores are the classic solution to preventing race conditions in the dining philosophers problem, although they do not prevent resource deadlocks ^{[citation needed]}.

Introduction

Semaphores can only be accessed using the following operations. Those marked atomic should not be interrupted (that is, if the system decides that the "turn is up" for the program doing this, it shouldn't stop it in the middle of those instructions) for the reasons explained below.

P(Semaphore s) // Acquire Resource
{
  wait until s > 0, then s := s-1;
  /* Testing and decrementing s must be atomic to avoid race conditions */
}

V(Semaphore s)  // Release  Resource
{
  s := s+1;   /* must be atomic */
}

Init(Semaphore s, Integer v)
{
  s := v;
}

Notice that incrementing the variable s must not be interrupted, and the P operation must not be interrupted after s is found to be greater than 0. This can be done using a special instruction such as test-and-set (if the architecture's instruction set supports it), or (on uniprocessor systems) ignoring interrupts to prevent other processes from becoming active.

The value of a semaphore is the number of units of the resource which are free. (If there is only one resource, a "binary semaphore" with values 0 or 1 is used.) The P operation busy-waits (uses its turn to do nothing) or maybe sleeps (tells the system not to give it a turn) until a resource is available, whereupon it immediately claims one. V is the inverse; it simply makes a resource available again after the process has finished using it. Init is only used to initialize the semaphore before any requests are made. The P and V operations must be atomic, which means that no process may ever be preempted in the middle of one of those operations to run another operation on the same semaphore.

The canonical names P and V come from the initials of Dutch words. V stands for verhogen, or "increase". Several explanations have been given for P (including proberen for "to test"^[2], passeer for "pass", probeer "try", and pakken "grab"), but in fact Dijkstra wrote that he intended P to stand for the made-up word prolaag,^[3] short for probeer te verlagen, literally "try-to-reduce", or to parallel the terms used in the other case, "try-to-decrease". ^[4]^[5]^[6] 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 non-Dutch-speakers.

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

To avoid busy-waiting, a semaphore may have an associated queue of processes (usually a first-in, first out). If a process performs a P operation on a semaphore which has the value zero, the process is added to the semaphore's queue. 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.

Analogy

Assume the 'resources' are toilets in a public restroom, and the 'processes' which want access to toilets are people either waiting in a queue for any toilet to be available or people who are already using the toilet. A person sitting outside the toilet keeps track of how many toilets are free at the moment and who should go in next.

The number of free toilets is the value of the semaphore indicating the number of free resources (toilets) available. When a process (person) wants access to a toilet the semaphore (incharge) will tell him whether he has to wait in the queue or whether he can use the toilet. If the toilet is free the person (process) gets the access and the number of free toilets is decreased by 1 (same as P or down operation). It means number of free resources is less by 1. If the number of free toilets is 0 the person (process) has to wait in the queue till it becomes free (it means the process has to sleep till s>0). Once the person uses the toilet (process finishes it work with the resource) the next person can use it. It means the number of free toilets is increased by 1 (this is same as calling V or Up operation). Now s has become greater than 0 and the person waiting (process sleeping) can have access to the toilet (resource).

The process of asking for available toilets (checking if resource is free), updating the number of free toilets (resources), and waiting in the queue should not be disturbed by any other process. This is called atomic action.

The queue is a first in first out queue which means the first person standing in the queue will get a chance to use a free toilet first. However the queue can be arranged if a person standing somewhere in the queue wants to use the toilet urgently (if a process has more priority).

The counting semaphore concept can be extended with the ability of claiming or returning more than one 'unit' from the semaphore. This is indeed the way the classical UNIX semaphore works. The modified P and V operations work like this:

P(Semaphore s, integer howmany)
{
  wait until s >= howmany;
  s := s - howmany; /* must be atomic operation */
}

V(Semaphore s, integer howmany)
{
  s := s + howmany; /* must be atomic */
}

To understand why it is better than just calling the simple version of P 'howmany' times consider the following problem. Let's say you have a pool of N resources, say fixed size buffers. You may want to use a counting semaphore initialised to N to keep track of the number of the buffers available. When a process wants to allocate a buffer, it calls P on the semaphore and gets a buffer. If there are no buffers available, a process waits until some other process releases a buffer and invokes V on the semaphore.

Consider that there are two processes that respectively want to acquire K < N and L < N buffers, such that K + L > N. The naïve implementation would have the first process call the simple decrementing variant P on the semaphore K times, and it would have the second process call the simple decrementing variant P on the semaphore L times. However, this approach can lead to a deadlock: Imagine that the operating system allows the first process to run. Then, when the first process has only acquired control of Z buffers (such that Z < K and Z + L > N), the operating system preempts the first process to allow the second process time to run. The second process begins acquiring buffers. However, when the second process acquires (N - Z) buffers, the semaphore becomes 0 and the second process gets suspended to wait for some other process to free up more buffers (because L > N - Z). The operating system eventually allows the first process to resume, continuing its quest to acquire the remaining (K - Z) buffers that it needs. Unfortunately, since the semaphore is 0, the first process cannot complete this task, so it too becomes suspended to wait for some other process to free up more buffers. Neither the first nor the second process can acquire enough buffers to continue, and therefore neither returns any buffers to the pool. Thus, they are stuck in a deadlock situation.

With the modified semaphore version, the first process will ask for K buffers (or more precisely, semaphore units), which it will get in an atomic operation, leaving N-K units on the semaphore. Then the second process arrives, decrements the semaphore down to N-K-L and since that is a negative number, will wait. As the first process releases buffers and increments the semaphore, as soon as the semaphore reaches 0 it means that there are L elements available in the pool, the second process can be woken up and can receive all of its buffers.

It should be noted that the semaphore count is not necessarily equal to the buffers available in the pool. The checking and waiting twice for the s >= 0 condition in P is needed to guarantee that as multiple processes are added to the semaphore's waiting list they do not disturb each other's request: a process does not change the semaphore's count until it is next in the queue. In real implementations it is done without actually activating up the waiting process for the intermediate step.

Semaphores today as used by programmers

Semaphores remain in common use in programming languages that do not intrinsically support other forms of synchronization. They are the primitive synchronization mechanism in many operating systems. The trend in programming language development, though, is towards more structured forms of synchronization, such as monitors (though these advanced structures typically employ semaphores behind the scenes). In addition to their inadequacies in dealing with (multi-resource) deadlocks, semaphores do not protect the programmer from the easy mistakes of taking a semaphore that is already held by the same process, and forgetting to release a semaphore that has been taken.

Example usage

Since semaphores have a count associated with them, they may be employed when multiple threads need to achieve an objective cooperatively. Consider this example:

A thread named A needs information from two databases before it can proceed. Access to these databases is controlled by two separate threads B, C. These two threads have a message-processing loop; anybody needing to use one of the databases posts a message into the corresponding thread's message queue. Thread A initializes a semaphore S with init(S,-1). A then posts a data request, including a pointer to the semaphore S, to both B and C. Then A calls P(S), which blocks. The other two threads meanwhile take their time obtaining the information; when each thread finishes obtaining the information, it calls V(S) on the passed semaphore. Only after both threads have completed will the semaphore's value be positive and A be able to continue. A semaphore used in this way is called a "counting semaphore."

Apart from a counting semaphore, there is a "blocking semaphore". A blocking semaphore is a semaphore that is initialized to zero. This has the effect that any thread that does a P operation on the semaphore blocks.

Hardware support

The use of semaphores normally requires hardware support to guarantee the atomicity of operations that require it. Computer machine languages typically include instructions that are designed specifically with semaphores in mind. These special instructions carry out a read-modify-write cycle to memory that is not only uninterruptible but excludes all other operations to the same location in memory by any other processors or input/output devices. The special instructions guarantee that a semaphore procedure using them can test and alter a semaphore in a single, atomic operation.

Binary semaphore vs. Mutex

A mutex is a binary semaphore, usually including extra features like ownership or priority inversion protection. The differences between mutexes and semaphores are operating system dependent. Mutexes are meant to be used for mutual exclusion only and binary semaphores are meant to be used for event notification and mutual exclusion.

Notes and references

^ http://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html E. W. Dijkstra, Cooperating sequential processes. Technological University, Eindhoven, The Netherlands, September 1965.
^ Silberschatz, Galvin, & Gagne 8th Ed. p.234
^ http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD74.PDF
^ http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD51.html MULTIPROGAMMERING EN DE X8 from the E.W. Dijkstra Archive (in Dutch)
^ Dijkstra's own translation reads "try-and-decrease", although that phrase might be confusing for those unaware of the colloquial "try-and..."
^ http://lkml.org/lkml/2005/12/19/34 Linux Kernel Mailing List: [PATCH 1/19] MUTEX: Introduce simple mutex implementation
^ Kernel hacking howto on linuxgrill.com
^ java.util.concurrent.Semaphore

Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operating System Concepts (8th ed.), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5
The Little Book of Semaphores, by Allen B. Downey, Green Tea Press.

External links

Over Seinpalen (EWD 74), in which Dijkstra introduces the concept (in Dutch)
semaphore.h programming interface - The Open Group Base Specifications Issue 6, IEEE Std 1003.1
The Little Book of Semaphores, by Allen B. Downey

[1] ttp://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html E. W. Dijkstra, Cooperating sequential processes. Technological University, Eindhoven, The Netherlands, September 1965.

[2] Silberschatz, Galvin, & Gagne 8th Ed. p.234

[3] ttp://www.cs.utexas.edu/users/EWD/ewd00xx/EWD74.PDF

[4] ttp://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD51.html MULTIPROGAMMERING EN DE X8 from the E.W. Dijkstra Archive (in Dutch)

[try-and-5] Dijkstra's own translation reads "try-and-decrease", although that phrase might be confusing for those unaware of the colloquial "try-and..."

[6] ttp://lkml.org/lkml/2005/12/19/34 Linux Kernel Mailing List: [PATCH 1/19] MUTEX: Introduce simple mutex implementation

[7] Kernel hacking howto on linuxgrill.com

[8] java.util.concurrent.Semaphore

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]