Part 8 of 8 · 3 min read
Exercises
Easy
Easy 1: Detection by hand (20 minutes)
Total (3, 2). Allocation: P0 (1, 0), P1 (1, 1), P2 (1, 1). Request: P0 (0, 0), P1 (1, 0), P2 (0, 1). Is any thread deadlocked?
Done when: the work vector at each step and a verdict.
Hint
Start with Available = total minus the sum of the Allocation rows.
Easy 2: Name the difference (20 minutes)
State in two sentences how the detection algorithm differs from the banker's safety check.
Done when: a mention of Request versus Need, and of the present versus the worst case.
Hint
The banker looks at maximum claims; the detector looks at actual requests.
Easy 3: Pick a victim (20 minutes)
Three deadlocked transactions have changed 2, 50 and 400 rows. Say which one a database would pick as the victim, and why.
Done when: the 2-row transaction, with the reason that the least work is lost.
Hint
The cost is the work that would be lost.
Medium
Medium 1: Find the deadlocked set (45 minutes)
Total (5, 4). Allocation: P0 (2, 1), P1 (1, 1), P2 (1, 1), P3 (1, 0). Request: P0 (0, 1), P1 (1, 0), P2 (0, 2), P3 (1, 1). Trace the detection algorithm.
Done when: a trace with each step and the set of deadlocked threads, if there is one.
Hint
Compute Available first: it is (5 − 5, 4 − 3) = (0, 1).
Medium 2: Run the detector (45 minutes)
Write the detection algorithm in C for N threads and M types, and run it on the example of section 2 with P3 requesting (0, 2) and then (0, 1).
Done when: one run reporting P2 and P3 deadlocked, and one reporting none.
Hint
Mark threads with an all-zero Allocation as finished before the loop.
Medium 3: Catch EDEADLK (45 minutes)
Write a program with two processes that lock bytes 0 and 1 of a file with fcntl(F_SETLKW) in opposite order. Print the result of the second request of each process.
Done when: one process prints error 35 and the other succeeds, once the loser releases its lock.
Hint
One process needs a pipe to the other so that the two first locks happen before either second one.
Hard
Hard 1: Time the recovery (60 minutes)
Run the timeout-and-rollback program with timeouts of 1, 10, 100 and 1000 ms for 5 s each, with 4 threads. Report transfers, rollbacks and the total money.
Done when: a table like the one in section 5, and a sentence on how your numbers differ.
Hint
Use timedlock with an absolute deadline from CLOCK_REALTIME.
Hard 2: Add victim fairness (60 minutes)
Add a per-thread count of rollbacks. Make a thread whose count is above the average wait twice as long before it retries. Run both versions for 5 s and compare the spread of the per-thread transfer counts.
Done when: two sets of four per-thread counts, and a statement about which is fairer.
Hint
Compare the maximum and minimum of the four counts.
Hard 3: Wait-for detector for a lock library (90 minutes)
Write wrapper functions my_lock and my_unlock that record the owner of each mutex and the lock each thread waits for. Add a function that runs the cycle search of page 2 and prints the deadlocked threads. Test it on the two-lock deadlock.
Done when: the detector prints the two thread ids of the deadlocked set of page 1.
Hint
A thread's wait must be recorded before pthread_mutex_lock and cleared after it returns.