<- People Behind Informatics


All 0-9 A B C D E F G H I J K L M N O P Q R S T U V W XY Z




 
Semaphores
The first conceptually sound and general solution for the mutual exclusion problem is given by E. W. Dijkstra in the 1960s, with his semaphores. Dijkstra's model was the operation of railroads: consider a stretch of railroad in which there is a single track over which only one train at a time is allowed. Guarding this track is a semaphore. A train must wait before entering the single track until the semaphore is in a state that permits travel. When the train enters the track, the semaphore changes state to prevent other trains from entering the track. A train that is leaving this section of track must again change the state of the semaphore to allow another train to enter. This example relates to the binary semaphore. In a generalized version, a semaphore appears to be an integer value with two associated operations, originally called by Dijsktra P (proberen, to test in Dutch) and V (verhogen, increment). The semaphore value represents the number of free “rail tracks”, i.e. the number of processes that may enter the critical section. The P operation checks the semaphore value. If this is positive then the semaphore value is decremented and the calling process enters the critical section. Otherwise it is forced to wait. The V operation simply increments the semaphore value. If the semaphore value becomes n (n > 0) then the first n waiting processes may be released automatically to re-enter the P operation. The P and V operations are atomic, i.e. they can be executed only fully or not at all. An atomic operation is similar to a goal in soccer: either the ball is over the line, then it is a goal, otherwise it is not a goal. There is no such thing as a “half” goal or a half V operation. If the initial value of the semaphore is A, the number of the P operations is nP and the number of the V operations is nV, then nP <= A + nV always holds. This is called the semaphore invariant. Mutual Exclusion Demonstration using Semaphores http://cne.gmu.edu/modules/ipc/pink/swsem.html [Sources: (Tanenbaum, 1987) Andrew S. Tanenbaum, Operating Systems – Design and Implementation; (Silberschatz, Galvin, 1994) Abraham Silberschatz, Peter B. Galvin, Operating System Concepts; Laszlo Böszörmenyi: Notes to the Virtual Exhibition "People behind Informatics"]
 

 

<- People Behind Informatics


Home  |  Top  |  Search  |  Gallery  | Glossary  | Sitemap  |  Making Of  |  Help