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?