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 datatype) 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)