CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 2 of 7 · 2 min read

The semaphore

In plain words: A car park has a sign showing the number of free spaces. A car that arrives when the sign shows a number above zero takes a space and the sign goes down by one. A car that finds zero waits at the barrier. A car that leaves adds one to the sign and lets a waiting car in. The analogy stops in one place: a car park attendant counts, and a semaphore must do the count and the waiting as one atomic act.

A semaphore is an integer variable, never negative, that can be changed only by two operations, each of which is atomic:

  • wait (also called P, from Dutch, or sem_wait): if the value is above zero, decrease it by one and continue. If the value is zero, sleep until it becomes above zero, then decrease it.
  • post (also called V, or sem_post): increase the value by one, and wake a sleeping thread if there is one.

In pseudo-code, with the whole body of each operation executed atomically:

wait(s):   while s.value == 0: sleep
           s.value = s.value - 1

post(s):   s.value = s.value + 1
           wake one sleeping thread, if any

The value can start at any number from zero up. What that number means depends on the use, as the next sections show.

A trace of a semaphore that starts at 2, with three threads that call wait and then post:

Step Action Value after State
1 A waits 1 A continues
2 B waits 0 B continues
3 C waits 0 C sleeps (value is 0)
4 A posts 1, then C wakes and takes it: 0 C continues
5 B posts 1 nobody waiting

The key property, the invariant, is stated in section 5. For now note that at most 2 threads got past wait at any time: the value 2 allowed two.

Semaphore

A semaphore is a non-negative integer, changed only by the atomic operations wait (decrease the value, sleeping first if it is zero) and post (increase the value and wake a waiting thread), used to control access to shared resources and to order events.

Example: a semaphore with value 2 lets two threads pass wait, and the third sleeps until one of them calls post.

Check yourself: 1. What does wait do when the value is 0? 2. In the trace, who runs after step 4, and why? 3. Why must wait be atomic?