Part 8 of 8 · 3 min read
Exercises
Easy
Easy 1: Match the rule (20 minutes)
Match each rule with the condition it removes: (a) spool the output, (b) take all locks at once, (c) release on failure and retry, (d) take locks in numeric order.
Done when: four correct pairs, each with one reason.
Hint
Spooling is about who uses the device.
Easy 2: Fix the order (20 minutes)
A thread locks X then Y, and another locks Y then X. Give X rank 1 and Y rank 2 and rewrite the second thread so that it follows the rule.
Done when: the second thread takes X and then Y.
Hint
The order of unlocking does not matter for deadlocks, only the order of locking.
Easy 3: Spot the cost (20 minutes)
Give one cost for each of the four methods in section 1.
Done when: four sentences, one per method.
Hint
Think of idle resources, extra waiting, wasted attempts, and extra rules.
Medium
Medium 1: Make it safe by ordering (45 minutes)
Write the 4-account transfer program with random pairs and 4 threads, using lock ordering. Run it for 3 s and print the total.
Done when: no stuck run in 5 tries, and a total of 4,000.
Hint
Use lo and hi as in section 5, and skip the case a == b.
Medium 2: Try-lock with back-off (45 minutes)
Write the trylock version with a random pause of 1 to 10 microseconds. Count the failed second locks.
Done when: a working run with a count of retries, and a total of 4,000.
Hint
rand_r with a per-thread seed avoids a shared lock in the random generator.
Medium 3: One big lock (30 minutes)
Write the one-lock version and measure transfers per second with 2 and 4 threads, three runs each.
Done when: a table with six numbers and the range for each thread count.
Hint
Stop the threads with a flag and join them before you read the counters.
Hard
Hard 1: Compare the three (60 minutes)
Put the three programs behind one flag and run each with 2 and 4 threads, three runs of 2 s. Report transfers per second and say which was fastest on your machine.
Done when: a table of 18 runs summarised in six cells, and a sentence that says what you cannot conclude from it.
Hint
Use the same random seeds so the three programs do the same work.
Hard 2: Add the rank checker (60 minutes)
Wrap each account's lock in the RLock structure with rank equal to its account number. Run the correct program, then change one code path to lock in the wrong order, and show the abort message.
Done when: a correct run, and an abort with the account numbers in the message.
Hint
The top variable must be saved and restored in runlock, as in section 6.
Hard 3: Order by address (90 minutes)
Replace the account numbers by a rule based on the address of the lock ((uintptr_t)&acc->m). Handle a == b. Test with 2,000,000 random transfers.
Done when: a run with no stuck lock and a correct total, plus a note on why the address order works as well as the number order.
Hint
Compare pointers cast to uintptr_t, not with < on pointers of different objects.