Go backward to Lock Variables Go up to Top Go forward to Barriers

Semaphores

Edgar Dijkstra.

Semaphore s = INIT(1)
P1: loop     P2: loop
      P(s)         P(s)
      C1           C2
      V(s)         V(s)

• Counter variable holding natural number.
• Atomic operations P and V.
• P(s): if s>0 then s <-s-1 else block.
• V(s): if processes blocked on s then release some process else s <-s+1.

Typically implemented by locks!