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.Eoperating 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)
