Semaphore (programming)
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 T.H.E operating system.Semaphores are the classic solution to the Dining philosophers problem.
Semaphores can only be accessed using the following operations:
P(Semaphore s)
{
while (s == 0) ; /* wait until s>0 */
s = s-1;
}
V(Semaphore s)
{
s = s+1;
}
Init(Semaphore s, Integer v)
{
s = v;
}P and V stand for Dutch "Proberen", to test, and "Verhogen", to 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.