CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 2 of 7 · 2 min read

The graph

In plain words: A seating chart in a restaurant shows which guest sits at which table, and which guests wait at the door for a table. A resource-allocation graph is the same idea for threads and resources. It draws two things at once: which resource each thread holds, and which resource each thread is waiting for. The analogy stops at one place: in a restaurant, a waiting guest can leave and eat elsewhere, while an edge of the graph records a wait that has no way out.

The graph has two kinds of node. Each thread is a circle, written T1, T2 and so on. Each resource type is a box, written R1, R2. Inside the box, one dot stands for each instance. The graph also has two kinds of edge, both drawn as arrows:

Edge Direction Meaning
Request edge thread → resource type The thread has asked for an instance and is waiting
Assignment edge resource instance → thread The instance has been given to the thread

Here is the two-lock deadlock of page 1 as a graph (A and B are single-instance resources):

    T1 --request--> [B]            T1 holds A, waits for B
    [B] --assigned--> T2           B is held by T2
    T2 --request--> [A]            T2 holds B, waits for A
    [A] --assigned--> T1           A is held by T1

    Follow the arrows:  T1 -> B -> T2 -> A -> T1      (a cycle)

A request edge turns into an assignment edge when the resource is granted, and the assignment edge disappears when the thread releases the resource. The graph therefore changes as the program runs. A cycle in the graph is a ring of arrows that leads back to its start.

Resource-allocation graph

A resource-allocation graph is a directed graph with threads and resource types as nodes, a request edge from a thread to a resource type it waits for, and an assignment edge from a resource instance to the thread that holds it.

Example: the edges T1 → B, B → T2, T2 → A, A → T1 form a cycle, and describe the deadlock of page 1.

Check yourself: 1. In which direction does a request edge point, and in which direction an assignment edge? 2. What happens to the graph when a thread gets the resource it was waiting for? 3. Draw the graph for a thread that holds lock X and waits for lock Y, which is free.