semaphore
<programming, operating system> The classic method for 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-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,
i.e. no other process can access the semaphore
during the their execution.
To avoid busy-waiting, 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)
Nearby terms:
semantic gap « semantic network « semantics «
semaphore
» semi » Semi-Automatic Ground Environment »
semicolon
|