CSE Roadmap

Common tier · about 5 hours · 8 parts

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.