|
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 multi-processing environment. They were invented by Edsger Dijkstra and first used in the THE 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)
{
while (s <= 0)
; /* wait until s>0 */
s = s-1; /* must be atomic operation */
}
V(Semaphore s)
{
s = s+1; /* must be atomic operation */
}
Init(Semaphore s, Integer v)
{
s = v;
}
Notice that incrementing and decrementing the variable s (only one statement in the implementation above, but probably more than one instructions for the CPU) must not be interrupted. 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 to become 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.
The V operation is sometimes known as "up", and the P operation as "down".
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
Much like GOTO, semaphores were an idea that originally seemed the best way to solve problems. They have since fallen out of favor except for textbook scenarios. Better-structured alternatives are preferred, such as the monitor pattern, resource-sharing environments, and various built-in constructs in more sophisticated modern languages. Since their inception, Hoare, Hansen, Andrews, Wirth, and even Dijkstra have all come out against the Semaphore.
See also
| 
