CSE Roadmap

Common tier · about 5 hours · 7 parts

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.