Part 7 of 7 · 2 min read
Exercises
Easy
Easy 1: Who can enter? (20 minutes)
A read-write lock is held in read mode by two threads. Say which of a new reader and a new writer can enter at once.
Done when: the reader can (with reader preference), and the writer must wait.
Hint
Readers share, a writer needs everyone out.
Easy 2: Spot the cycle (20 minutes)
Five philosophers each hold the left fork and wait for the right. Write the wait-for chain.
Done when: P0 waits for P1 waits for P2 waits for P3 waits for P4 waits for P0.
Hint
Each waits for the next philosopher's fork.
Easy 3: Pick the lock (20 minutes)
Choose mutex or read-write lock for: a counter incremented by every thread, and a settings table read by every request and changed once a day.
Done when: mutex for the counter and read-write lock for the table.
Hint
A counter has no read-only phase.
Medium
Medium 1: Measure readers (45 minutes)
Write the mutex and read-write lock test with 1, 2 and 4 reader threads. Report the times.
Done when: a table in which the read-write lock stays flat up to your processor count while the mutex grows.
Hint
Keep the work under the lock the same in both runs.
Medium 2: Starve the writer (45 minutes)
Write the test with three overlapping readers and a writer using pthread_rwlock_timedwrlock. Run it with both preference settings.
Done when: a timeout under reader preference and a short wait under writer preference.
Hint
PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP is the writer setting.
Medium 3: Deadlock the philosophers (30 minutes)
Write the naive philosophers with a 1 ms pause between the two locks. Run it with a timeout and show that nobody eats.
Done when: 0 meals and a stuck report.
Hint
End the program with _exit after a timer, since it cannot join.
Hard
Hard 1: Both fixes (60 minutes)
Add the ordering fix and the seat-limit fix. Run 2 seconds each and report meals per philosopher.
Done when: a table like section 4, and a sentence on fairness.
Hint
Use the same pauses in both fixes.
Hard 2: Back off and retry (60 minutes)
Replace the second lock by trylock: if it fails, put the first fork down, wait a random 1 to 3 ms and retry. Count the meals and the retries.
Done when: a working run with some retries, and a note on the risk of livelock.
Hint
Release the first fork before the pause.
Hard 3: A fair read-write lock (90 minutes)
Build a read-write lock from a mutex and condition variables that serves waiting threads in order of arrival, and test that neither a writer nor a reader starves in the overlapping-readers test.
Done when: the writer gets the lock in under 100 ms and no reader waits more than 1 s.
Hint
Use a ticket number for each arriving thread.