Home Articles FAQs XREF Games Software Instant Books BBS About FOLDOC RFCs Feedback Sitemap
irt.Org

semaphore

You are here: irt.org | FOLDOC | 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

FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL

©2018 Martin Webb