Semaphore (programming)
Encyclopedia : S : SE : SEM : Semaphore (programming)
- This article is about the computer science application of mutual exclusion. For other uses, see Semaphore.
Semaphores are the classic solution to the dining philosophers problem, although they do not prevent all deadlocks.
Semaphores can only be accessed using the following operations:
P(Semaphore s)Notice that incrementing the variable s must not be interrupted, and the P operation must not be interrupted after s is found to be nonzero. This can be done by special instruction (if the architecture's instruction set supports it) or by ignoring interrupts in order to prevent other processes from becoming active.V(Semaphore s)
Init(Semaphore s, Integer v)
The canonical names P and V come from the initials of Dutch words. V stands for verhoog, or "increase." Several explanations have been given for P (including passeer "pass," probeer "try," and pakken "grab"), but in fact Dijkstra wrote that he intended P to stand for the made-up portmanteau word prolaag,[link] short for probeer te verlagen, or "try-and-decrease."[link][link] (A less ambiguous English translation would be "try-to-decrease.") This confusion stems from the unfortunate characteristic of the Dutch language that the words for increase and decrease both begin with the letter V, and the words spelled out in full would be impossibly confusing for non–Dutch-speakers.
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 (or maybe sleeps) 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.
In English textbooks, and in the programming language ALGOL 68, the P and V operations are sometimes called, respectively, down and up. In software engineering practice they are called wait and signal, or take and release, or pend and post.
To avoid busy-waiting, a semaphore may have an associated queue of processes (usually a FIFO). 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.
Semaphores today
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 and channels. In addition to their inadequacies in dealing with 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. Hoare, Hansen, Andrews, Wirth, and even Dijkstra have called semaphores obsolete.#redirectExample usage
Since semaphores can have a count associated with them, they are usually made use of when multiple threads cooperatively need to achieve an objective. Consider this example:- We have a thread A that 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 desirous of their service needs to post a message into their 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 callsP(S), which blocks. The other two threads meanwhile take their time obtaining the information; when each thread finishes obtaining the information, it callsV(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."
P(S) will block until another thread does a V(S). This kind of construct is very useful when the order of execution among threads needs to be controlled.
The simplest kind of semaphore is the "binary semaphore," used to control access to a single resource. It is essentially the same as a mutex. It is always initialized with the value 1. When the resource is in use, the accessing thread calls P(S) to decrease this value to 0, and restores it to 1 with the V operation when the resource is ready to be freed.
See also
External links
- [semaphore.h] programming interface - The Open Group Base Specifications Issue 6, IEEE Std 1003.1
- [A simple in-process semaphore using C#]
- [J2SE class]
- [Python Semaphore Objects]
- [Inter-Process Communication Tutorial]
- [Citations from CiteSeer]
- [Description from the Portland Pattern Repository]
- [The Little Book of Semaphores] by Allen B. Downey
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.