Part 2 of 7 · 2 min read
A deadlock
In plain words: Two cars drive onto a one-lane bridge from opposite ends and meet in the middle. Neither can pass, and each waits for the other to back up. Nothing is broken, and every driver is behaving politely. The situation is stuck because of the way the cars are placed. The analogy stops in one place: a driver can reverse, but a thread blocked on a lock has no way to give up and back out unless the program was written to allow it.
Here is the same situation in code. Thread 1 takes lock A and then lock B. Thread 2 takes B and then A. Each pauses for 0.1 s between its two locks, so that the unlucky timing is certain:
pthread_mutex_t A = PTHREAD_MUTEX_INITIALIZER, B = PTHREAD_MUTEX_INITIALIZER;
void *t1(void *x) { pthread_mutex_lock(&A); usleep(100000);
printf("T1 has A, wants B\n"); pthread_mutex_lock(&B); /* never returns */ ... }
void *t2(void *x) { pthread_mutex_lock(&B); usleep(100000);
printf("T2 has B, wants A\n"); pthread_mutex_lock(&A); /* never returns */ ... }
The main thread waits 2 s and then reports. The output was:
T1 has A, wants B
T2 has B, wants A
main: after 2 s, nothing finished
Neither "done" line ever appears. Both threads sleep on a lock that only the other one can release. No amount of waiting changes that. Compare this with a thread that is merely slow: a slow thread will finish if given enough time, while a deadlocked thread will not.
Deadlock
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.
Example: thread 1 holds lock A and waits for B, while thread 2 holds B and waits for A; the two form a deadlocked set.
Check yourself: 1. Why does the output stop after two lines, although both threads are still alive? 2. What is the difference between a deadlocked thread and a thread that is waiting a long time for a slow disk? 3. Why is the word "same set" important in the definition?