Semaphore (programming)
|
|
- This article is about the computer science application of mutual exclusion. For other uses, see Semaphore.
A semaphore is a protected variable (or abstract data type) and constitutes the classic method for restricting access to shared resources (e.g. storage) in a multiprogramming environment. They were invented by Edsger Dijkstra and first used in the THEOS operating system.
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)
{
await s > 0 then s = s-1; /* must be atomic once s > 0 is detected */
}
V(Semaphore s)
{
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 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.
P and V stand for Dutch "Probeer", try (to decrement), and "Verhoog", increment. 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 initialise the semaphore before any requests are made. The P and V operations must be indivisible, which means that each of the operations may not be executed multiple times concurrently. A process wishing to execute an operation that is already being executed by another process must wait for it to complete first.
In English textbooks the V and P operations are sometimes called, respectively, up and down. In software engineering practice they are called signal and wait or release and take.
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.
| Contents |
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 like 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.
Example of Usage of Semaphore
Since semaphores can have a count associated with them, they are usually made use of when more than one threads cooperatively need to achieve an objective. Consider this example:- We have a thread(A) that needs information from two databases before proceeding. The access to these two DBs is controlled by two separate threads(B,C). These two threads have a message processing loop and anybody desirous of their service needs to post a message into their message queue. Our first thread initialises a semaphore S with init(S,-1). It then posts a DBDataRequest to both the threads(B,C) and adds a reference to the semaphore as well in the request it posted. After this it immediately does P(S) and blocks. The other two threads meanwhile take their own time to obtain the information and post the responses back and also do a V(S) on the passed semaphore. Only after both threads have done their part of V(S) will the first thread be able to continue. This is exactly what we wanted as well. A semaphore used in this way is called a "counting semaphore".
Apart from a counting semaphore we also have a blocking semaphore. A blocking semaphore is a semaphore that is initialised with the value of 0. This has the effect that any thread that does a P(S) will block until another thread does a V(S). This kind of construct is very useful when we need to control the order of execution amongst threads.
Then there is also the binary semaphore, which is nothing but a mutex. It is always initialised with the value of 1.
See also
External links
- The Little Book of Semaphores (http://greenteapress.com/semaphores).
de:Semaphor (Informatik) es:Semáforo (programación) fr:Sémaphore (informatique) nl:Semafoor pl:Semafor (informatyka)