CSE Roadmap

Core tier · about 5 hours · 7 parts

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.