CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 6 of 7 · 4 min read

Diagnosis

Telling a deadlock from a slow program

In plain words: A hung program may be deadlocked, but it may also be waiting for the network, sleeping on purpose, or looping forever. The test is: are the blocked threads waiting for each other?

Linux shows what each thread of a process is waiting for. The files under /proc/<pid>/task/<tid>/ list one thread each. The file wchan names the kernel function where the thread sleeps. For the stuck program of section 1, the listing was:

345 dl1g  state=S  wchan=hrtimer_nanosleep     (main thread: in sleep())
347 dl1g  state=S  wchan=futex_do_wait         (T1: blocked on a lock)
348 dl1g  state=S  wchan=futex_do_wait         (T2: blocked on a lock)

Two threads sleeping in futex_do_wait means they wait on mutexes. That is a first hint. A debugger gives the full answer. The program was run under gdb and stopped with abort() after 1 s. The command thread apply all bt showed one thread inside pthread_mutex_lock on B, and the other inside the same call on A. Printing the mutex field __data.__owner gave the thread id of the owner:

(gdb) print A.__data.__owner      ->  403     (thread 2 holds A)
(gdb) print B.__data.__owner      ->  404     (thread 3 holds B)
Thread 2 (LWP 403) is waiting in lock(B)      B is owned by 404
Thread 3 (LWP 404) is waiting in lock(A)      A is owned by 403

Now the cycle is visible: 403 waits for a lock owned by 404, and 404 waits for a lock owned by 403. That is the full proof of a deadlock: a cycle of threads, each waiting for a lock the next one holds.

Where the debugger cannot attach, a program can detect its own stuck state with pthread_mutex_timedlock, which gives up at a fixed time and returns ETIMEDOUT (the bank program used this). A timeout alone does not prove a deadlock, since the owner may be only slow, but it is a cheap alarm.

Blocked thread

A blocked thread is a thread that the kernel has put to sleep because it cannot continue until some event happens, such as a lock being released; it uses no processor time until the event occurs.

Example: a thread waiting in pthread_mutex_lock on a lock owned by another thread is blocked, and shows futex_do_wait in its wchan file.

Interview angle

"What are the four conditions for deadlock?" is a classic question. Give the four names with one line each, then add which one a programmer usually breaks (circular wait, by fixing a lock order). A strong answer also says that the conditions are necessary: remove one, and a deadlock cannot occur.

Check yourself: 1. What does futex_do_wait in a thread's wchan file tell you? 2. What would you print to find out which thread owns a mutex? 3. Why is a timeout from pthread_mutex_timedlock not proof of a deadlock?

Words you will meet

Word Meaning
Deadlock A set of threads each blocked on a resource held by another in the set
Resource Anything a thread can wait for: a lock, a device, a file, memory
Instance One identical unit of a resource type
Reusable resource A resource that is released unchanged and used again
Consumable resource A resource that is created by one thread and destroyed by another
Hold and wait Holding one resource while waiting for another
Preemption Taking a resource away from its holder by force
Circular wait A cycle of threads each waiting for the next
Interleaving One order of the steps of several threads
Blocked Asleep in the kernel, waiting for an event

Quick notes

  • A deadlock is a state in which every thread in a set is blocked, waiting for a resource that is held by another thread in the same set, so that none of them can ever continue.
  • A resource instance is one identical unit of a resource type: a thread that requests the type may be given any free instance, and a type with a single instance can serve only one thread at a time.
  • The necessary conditions for deadlock are four properties of a system.
  • An interleaving is one particular order in which the steps of several threads are carried out on the machine; the same program can have many interleavings, and a bug that appears in only a few of them is called timing-dependent.
  • A blocked thread is a thread that the kernel has put to sleep because it cannot continue until some event happens, such as a lock being released; it uses no processor time until the event occurs.