semaphore
restricting access to shared resources (e.g. storage) in a
{multi-processing} environment. They were invented by
{Dijkstra} and first used in {T.H.E} {operating system}.
A semaphore is a {protected variable} (or {abstract data
type}) which can only be accessed using the following
operations:
P(s)
Semaphore s;
{
while (s ◦◦ 0) ; /▫ wait until s>0 ▫/
s ◦ s-1;
}
V(s)
Semaphore s;
{
s ◦ s:1;
}
Init(s, v)
Semaphore s;
Int 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-wait}s (or maybe {sleep}s) 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}, i.e. no other process
can access the semaphore during the their execution.
To avoid {busy-wait}ing, a semaphore may have an associated
{queue} of processes (usually a {FIFO}). If a process does a
P on a semaphore which is zero the process is added to the
semaphore's queue. When another process increments the
semaphore by doing a V and there are tasks on the queue, one
is taken off and resumed.
(1995-02-01)