Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Why the loop? (20 minutes)
Give two reasons why a wait must be in a while loop.
Done when: a spurious wakeup, and another thread changing the condition after the wakeup.
Hint
Think of what happens between the signal and the relock.
Easy 2: Signal or broadcast (20 minutes)
A queue has one condition variable not_empty and many identical consumers. After one item is added, which call is enough? A memory allocator frees a block that may suit several waiting requests. Which call?
Done when: signal for the first and broadcast for the second.
Hint
Does the change help one waiter or several?
Easy 3: Name the mistake (20 minutes)
A thread sets ready = 1 and signals without holding the mutex, while another tests the flag under the mutex. What can go wrong?
Done when: the waiter can test 0 and then sleep after the signal was sent, so the signal is lost.
Hint
The test and the wait must be under one hold of the mutex.
Medium
Medium 1: Reproduce the lost wakeup (30 minutes)
Write the test of section 3 with and without the flag, using pthread_cond_timedwait.
Done when: a timeout for the version without the check and an immediate return for the version with it.
Hint
Use an absolute time for timedwait.
Medium 2: Signal against broadcast (30 minutes)
Start three waiters on one flag. Set the flag and call signal, count how many wake, then repeat with broadcast.
Done when: 1 of 3 and 3 of 3.
Hint
Let the main thread sleep before it sets the flag, so all three wait.
Medium 3: Run the monitor (30 minutes)
Write the account monitor of section 5. Start three customers who withdraw 50 each and a depositor who deposits 20 ten times. Print the final balance.
Done when: all three get their money and the final balance is 50.
Hint
Broadcast in deposit.
Hard
Hard 1: A one-shot event (60 minutes)
Write an event type with event_set and event_wait using a mutex, a flag and a condition variable, so that any number of threads can wait and one thread sets it. Test with 8 waiters.
Done when: all 8 waiters return, also those that call event_wait after the event was set.
Hint
The flag keeps the memory, so late waiters never sleep.
Hard 2: A barrier (90 minutes)
Write a reusable barrier for n threads with a mutex, a counter and a condition variable. Test with 4 threads over 1,000 rounds.
Done when: in each round, no thread passes before all four have arrived, checked by a shared round counter.
Hint
Use a generation number so that a fast thread cannot rejoin the old round.
Hard 3: Timed wait (60 minutes)
Write a get_with_timeout function for the account monitor that waits for funds for at most 200 ms using pthread_cond_timedwait, and returns an error if the time runs out.
Done when: a test that returns ETIMEDOUT with no deposits, and succeeds when a deposit arrives within 100 ms.
Hint
pthread_cond_timedwait takes the absolute CLOCK_REALTIME time.