Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Safe or not? (20 minutes)
A system has 12 units of one type. A holds 5 and may need up to 10, B holds 2 and may need up to 4, C holds 2 and may need up to 9. Is the state safe? Give a safe sequence if there is one.
Done when: the free count, the needs, and an order, or a proof that none fits.
Hint
Free units are 12 minus 9, and each thread's Need is its maximum minus its holding.
Easy 2: Compute Need (20 minutes)
Given Max rows (7, 5, 3) and (3, 2, 2), and Allocation rows (0, 1, 0) and (2, 0, 0), compute the Need rows.
Done when: (7, 4, 3) and (1, 2, 2).
Hint
Subtract each Allocation entry from the Max entry in the same place.
Easy 3: Name the three steps (20 minutes)
List the three steps taken when a thread requests resources in the banker's algorithm, in order.
Done when: three correct steps, including the pretend grant.
Hint
The test against Need comes first, then the test against Available.
Medium
Medium 1: Trace the safety algorithm (45 minutes)
Use the table of section 3 but change P0's allocation to (3, 1) and so Available to (1, 2). Trace the safety algorithm.
Done when: the new Need rows, the work vector (1, 2), and a verdict with the reason.
Hint
If no row fits the first work vector, the state is unsafe straight away.
Medium 2: Test three requests (45 minutes)
On the state of section 3, test the requests P1 asks (2, 1), P2 asks (3, 0) and P3 asks (2, 2). Say whether each is refused for exceeding the claim, made to wait, granted, or refused as unsafe.
Done when: three decisions with a reason each.
Hint
Check Need first, then Available, and only then run the safety algorithm.
Medium 3: Run the C code (45 minutes)
Compile the code of section 5 with a main that prints whether the start state is safe, then add the request function and try the six requests.
Done when: the six output lines of section 5 on your machine.
Hint
Keep a copy of alloc before each request so you can restore it.
Hard
Hard 1: Count safe sequences (60 minutes)
Write a recursive program that counts all safe sequences for the state of section 3. Confirm that it finds 12.
Done when: the number 12, and a list of the first three sequences.
Hint
Recurse on the set of threads that are still unfinished, with the work vector as a parameter.
Hard 2: An unsafe state that does not deadlock (60 minutes)
Build a made-up unsafe state in which the threads, by choosing not to ask for their full claim, all finish. Run it as a small simulation.
Done when: a state with no safe sequence and a run that still finishes, plus a sentence on why unsafe is not deadlocked.
Hint
Use a thread whose real need is smaller than its declared claim.
Hard 3: Avoidance for a thread pool (90 minutes)
A pool has 6 connections. Four jobs each declare a maximum claim of 3 connections and acquire them one at a time. Write a simulation with the banker's check, and one without it. Count in 1,000 random runs how often the version without the check ends up stuck.
Done when: two counts, with the version with the check showing 0 stuck runs.
Hint
A job asks for one connection at a time with a random pause in between.