Part 5 of 7 · 2 min read
Ordering
In plain words: A relay runner waits for the baton. The second runner cannot start until the first has arrived and handed it over. The baton is the signal. The analogy stops in one place: the baton is a physical thing, and a post can happen before the wait, with the semaphore keeping the count.
A semaphore that starts at 0 has no free units. The first wait sleeps. It becomes a one-way signal: one thread calls post when an event has happened, and another calls wait to wait for it. Unlike the condition variable of page 4, a semaphore keeps its value, so the order of the two calls does not matter: a post before the wait is remembered, and the wait returns at once. There is no lost wakeup.
sem_t done; /* sem_init(&done, 0, 0): "step 1 has not finished" */
void *first(void *a) { /* step 1 */ sem_post(&done); }
void *second(void *a) { sem_wait(&done); /* step 2: runs after step 1 */ }
The test started the second thread first. It waited, and step 1, which sleeps 100 ms, signalled:
ordering:
step 1 finished
step 2 starts after step 1
Two semaphores solve the rendezvous problem: two threads A and B each do something before and something after a meeting point, and neither may pass the point until both have arrived. Both semaphores start at 0.
| Thread A | Thread B |
|---|---|
a1 (before) |
b1 (before) |
post(a_arrived) |
post(b_arrived) |
wait(b_arrived) |
wait(a_arrived) |
a2 (after) |
b2 (after) |
Whichever thread arrives first posts its own semaphore and then waits for the other's. The second to arrive posts, finds the other's post waiting, and both pass. The order post before wait is important: if both waited first, both would sleep for ever.
Rendezvous
A rendezvous is a synchronisation point at which two or more threads must all arrive before any of them continues, implemented for two threads with two semaphores initialised to 0, each thread posting its own and then waiting for the other's.
Example: threads A and B each finish their first phase, post, wait for the other, and only then start the second phase.
Check yourself: 1. What is the initial value of a signalling semaphore, and why? 2. Why does a semaphore not suffer the lost wakeup that a condition variable does? 3. What happens in the rendezvous if both threads wait before posting?