CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 6 of 7 · 3 min read

Cost

How big and how often

In plain words: Searching a graph for a cycle takes time. For n threads, the general search takes about n² steps (OSC). For single-owner locks, the two-walker function takes about n steps for one starting thread. Both are cheap when n is 100. They are not cheap if the check runs on every lock request in a kernel that performs millions of requests a second.

There are three common choices for when to look for a cycle:

When Cost Result
On every blocked request Highest A deadlock is found the moment it forms
At fixed intervals, such as once a minute Low A deadlock may last up to one interval
When processor use falls Low A deadlock shows up as idle processors

The third rule works because of a fact from page 1: a deadlocked thread sleeps. If many threads are deadlocked, the machine does less work, and processor use falls. Page 5 compares the choices in more depth.

A related alarm is cheaper than any graph search: the timeout. The bank program of page 1 asked for the second lock with pthread_mutex_timedlock and a 1 s limit. A timeout proves nothing alone, but it shows that something has waited too long, and the program can then run the graph search to confirm.

Deadlock check

A deadlock check is a run of a cycle-finding algorithm over the current waits and owners; because it costs time proportional to the number of threads or more, the system chooses when to run it, on every request, at fixed intervals or when the machine looks idle.

Example: a database that runs its check every 1 s finds a deadlock at most 1 s after it forms.

Interview angle

"How would you detect a deadlock in a running system?" Build the wait-for graph (who waits for whom), search it for a cycle, and say when you would run the check. Mention that with multiple-instance resources a cycle is necessary but not sufficient, and that a thread behind the cycle is not part of the deadlock.

Check yourself: 1. Why is it a bad idea to run the check at every lock request in a kernel? 2. Why does a fall in processor use hint at a deadlock? 3. What can a timeout tell you, and what can it not tell you?

Words you will meet

Word Meaning
Resource-allocation graph Nodes are threads and resource types; edges show requests and assignments
Request edge An arrow from a waiting thread to the resource type it wants
Assignment edge An arrow from a resource instance to its holder
Wait-for graph A graph of threads only: X → Y when X waits for something Y holds
Cycle A path of edges that returns to its start
Deadlocked set The blocked threads that wait only on each other
Victim A thread chosen to be stopped or rolled back to break a deadlock (page 5)

Quick notes

  • 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.
  • A wait-for graph is a directed graph whose nodes are threads, with an edge from thread X to thread Y when X is blocked waiting for a resource that Y.
  • A cycle in a resource-allocation graph is a path of edges that returns to its starting node; it is necessary for a deadlock, and it is sufficient only if every resource type on the cycle has a single instance.
  • A deadlocked set is a set of blocked threads in which every thread waits for a resource that only another thread of the set can release; threads that merely wait.
  • A deadlock check is a run of a cycle-finding algorithm over the current waits and owners; because it costs time proportional to the number of threads or more, the system.