SEMAPHORES

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. It was invented by Edsger Dijkstra and first used in the THE operating system.
The value of the semaphore is initialized to the number of equivalent shared resources it is implemented to control. In the special case where there is a single equivalent shared resource, the semaphore is called a binary semaphore. The general case semaphore is often called a counting 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)
{
wait until 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 using a special instruction such as test-and-set (if the architecture's instruction set supports it), or (on uniprocessor systems) ignoring interrupts in order to prevent other processes from becoming active.