Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Find the critical section (20 minutes)
A shared list is updated by n = n + 1; list[n] = item;. Mark the critical section and name the shared data.
Done when: both statements are in one critical section, with n and list as shared data.
Hint
Both statements together change the list.
Easy 2: Name the requirement (20 minutes)
A lock lets thread A in 5 times in a row while B waits. Which requirement is in question? A lock lets A and B both in. Which one?
Done when: bounded waiting, then mutual exclusion.
Hint
Bounded waiting is about being passed again and again.
Easy 3: Trace the lock variable (20 minutes)
Write a trace table of two threads that both enter through the lock variable of attempt 1, starting with locked = 0.
Done when: a table in which both threads read 0 before either writes 1.
Hint
Put both reads before both writes.
Medium
Medium 1: Break strict alternation (30 minutes)
Thread 1 spends 10 seconds in its remainder section after its first turn. Describe what thread 0 does in that time, and which requirement fails.
Done when: thread 0 enters once, then waits for the whole 10 seconds, so progress fails.
Hint
Thread 0 cannot take two turns in a row.
Medium 2: Trace Peterson (30 minutes)
Write the trace for Peterson's algorithm if thread 1 sets turn first and then thread 0 does. Who enters first?
Done when: thread 1 enters first, because thread 0 wrote turn last.
Hint
The last write to turn decides who waits.
Medium 3: Run the broken lock (30 minutes)
Write the lock-variable program of section 3 and run it five times. Report the number of lost updates each time.
Done when: five runs with fewer than 2,000,000 each, and a sentence about the variation.
Hint
The result is different each time, because of the timing.
Hard
Hard 1: Reproduce the reordering (60 minutes)
Write Peterson's lock around a shared volatile counter, with plain variables and then with __atomic sequentially consistent operations. Run each five times and report the totals.
Done when: the plain version loses updates on a multiprocessor, and the atomic version never does.
Hint
Compile with -O2 and make the counter volatile too.
Hard 2: Prove it (60 minutes)
Write a careful argument that Peterson's algorithm satisfies mutual exclusion, assuming sequentially consistent memory. Use the last write to turn.
Done when: a proof of at most one page, that covers the case where both threads reach their test.
Hint
Suppose both are inside, and look at the last write to turn.
Hard 3: Extend to three threads (60 minutes)
Explain why Peterson's two-thread algorithm cannot be used directly for three threads, and sketch how a tournament of two-thread locks could be arranged.
Done when: a diagram of a tree of 2-thread locks, with the number of locks a thread acquires going up the tree.
Hint
A tree for 3 threads needs lock levels, one at each level of the tree.