CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Draw the graph (20 minutes)

Draw the resource-allocation graph for this state: T1 holds R1 and waits for R2, T2 holds R2 and waits for R3, T3 holds R3 and waits for R1. All resources have 1 instance.

Done when: a drawing with 3 request edges and 3 assignment edges, and the cycle marked.

Hint

Request edges point to the box, assignment edges point from the box.

Easy 2: Wait-for graph (20 minutes)

Turn the graph of Easy 1 into a wait-for graph, and write the cycle with arrows.

Done when: a graph with three nodes T1 → T2 → T3 → T1.

Hint

Replace each pair "thread, box, owner" by one arrow from thread to owner.

Easy 3: Cycle or deadlock? (20 minutes)

For each case, say whether a cycle proves a deadlock: (a) three mutexes, (b) a pool of 5 identical connections, (c) two files each opened by a single process.

Done when: three answers: yes for (a) and (c), "not alone" for (b).

Hint

With several instances, a free one may be held by a thread outside the cycle.

Medium

Medium 1: Trace the two walkers (30 minutes)

For waits_for = {1, 2, 3, 1, -1}, trace slow and fast step by step from thread 0 and write the cycle that the function returns.

Done when: a table of the values of slow and fast at each loop, and the cycle T3 T1 T2 (the same three threads, listed from the meeting point).

Hint

fast moves two steps while slow moves one, so fast enters the cycle first.

Medium 2: Run the finder (45 minutes)

Compile the function of section 2 with a main that holds the waits_for array of section 4. Print the result for every thread. Then change the array so that T2 waits for nobody and run it again.

Done when: the five lines of section 4 for the first run, and "no cycle ahead" for every thread in the second.

Hint

Initialise the array in main and loop i from 0 to 4.

Medium 3: A cycle that clears (30 minutes)

Build your own made-up example with one type of 2 instances and one of 1 instance, with a cycle that is not a deadlock. Show the order in which the threads finish.

Done when: a table like section 3 and a finishing order written out.

Hint

One thread outside the cycle should wait for nothing.

Hard

Hard 1: Read the graph from gdb (60 minutes)

Make a program with three threads and three locks in a ring (page 1, Hard 1). Run it under gdb, stop it with abort(), and read the owner of each lock and the lock each thread waits for. Fill an array waits_for from your findings and run the function of section 2.

Done when: the array, the output of the function, and the cycle with real thread ids.

Hint

pthread_mutex_t has a field __data.__owner in glibc.

Hard 2: Add a hanger-on (60 minutes)

Add a fourth thread that waits for a lock held by one of the three deadlocked threads. Show with the function that it reaches the cycle but is not on it. Explain what happens to the program if you kill this fourth thread.

Done when: the function output, and a note that the deadlock stays.

Hint

Its row in the array points to a thread on the cycle.

Hard 3: A general cycle search (90 minutes)

Write a depth-first search that finds a cycle in a graph with several outgoing edges per node, given as an adjacency list. Test it on the 4-node graphs of this page and on a graph with no cycle.

Done when: it finds T1 T2 T3 in the 4-thread ring and reports none for the acyclic one, in under 40 lines of C.

Hint

Keep a colour for each node: white, grey while on the current path, black when done.