Part 7 of 7 · 2 min read
Exercises
Easy
Easy 1: Trace values (20 minutes)
A semaphore starts at 2. Give the value and who sleeps after: wait, wait, wait, post, post.
Done when: 1, 0, 0 (third waiter sleeps), then the sleeper wakes and takes the unit (0), then 1.
Hint
A waiter that sleeps takes the unit as soon as a post arrives.
Easy 2: Initial value (20 minutes)
Choose the initial value for: a lock, a pool of 5 printers, a signal that "data is ready".
Done when: 1, 5 and 0.
Hint
A lock needs one unit, a signal needs none until the event.
Easy 3: Invariant (20 minutes)
A semaphore starts at 5, with 8 completed waits and 4 completed posts. Give the value.
Done when: 5 + 4 − 8 = 1.
Hint
The invariant is initial + posts − waits.
Medium
Medium 1: Limit a region (30 minutes)
Write a program in which 8 threads enter a region guarded by a semaphore of 3, hold it for 100 ms, and record the maximum number inside.
Done when: a maximum of 3 and a total time near 0.30 s.
Hint
Count the threads inside with a mutex-protected counter.
Medium 2: Order two threads (30 minutes)
Write two threads in which the second prints "B" only after the first printed "A", using a semaphore at 0. Start the second thread first.
Done when: the output "A" then "B" in every run.
Hint
sem_init(&s, 0, 0).
Medium 3: Write a rendezvous (30 minutes)
Write the two-semaphore rendezvous for 2 threads, with a random sleep before the meeting point. Check that "after" is never printed before both "before" lines.
Done when: 100 runs in which both "before" lines come first.
Hint
Post first, then wait.
Hard
Hard 1: Build a semaphore (60 minutes)
Build z_wait and z_post from a mutex and a condition variable, and test it as a lock with 4 threads and 500,000 rounds each.
Done when: the total of 2,000,000 and a timing against sem_t.
Hint
The loop in z_wait is essential.
Hard 2: Barrier from semaphores (90 minutes)
Build a reusable barrier for n threads from semaphores and a counter, avoiding the problem that a fast thread laps the others.
Done when: 1,000 rounds with 4 threads in which no thread starts round k + 1 before all finish round k.
Hint
Two turnstile semaphores are one known design.
Hard 3: Misuse (60 minutes)
Write a program with a binary semaphore used as a lock and an extra sem_post in an error path. Show that two threads can then be in the critical section together. Fix it with a mutex.
Done when: a run that shows the violation, and the fix that detects it.
Hint
A mutex with the error-checking type reports a wrong unlock.