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.