Quick: What is "deadlock"? How would you define it? One common answer is: "When two threads each try to take a lock the other already holds." Yes, we do indeed have a potential deadlock anytime two threads (or other concurrent tasks, such as work items running on a thread pool; for simplicity, I'll say "threads" for the purposes of this article) try to acquire the same two locks in opposite orders, and the threads might run concurrently. The potential deadlock will only manifest when the threads actually do run concurrently, and interleave in an appropriately bad way where each successfully takes its first lock and then waits forever on the other's, as in the execution A->B->C->D in the following example:
// Thread 1 mut1.lock(); // A mut2.lock(); // C: blocks // Thread 2 mut2.lock(); // B mut1.lock(); // D: blocks
That's the classic deadlock example from college. Of course, two isn't a magic number. An improved definition of deadlock is: "When N threads enter a locking cycle where each tries to take a lock the next already holds."
Deadlock Among Messages
"But wait," someone might say. "I once had a deadlock just like the code you just showed, but it didn't involve locks at all—it involved messages." For example, consider this code, which is similar to the lock-based deadlock example:
// Thread 1 mq1.receive(); // blocks mq2.send( x ); // Thread 2 mq2.receive(); // blocks mq1.send( y );
Now Thread 1 is blocked, waiting for a message that Thread 2 hasn't sent yet. Unfortunately, Thread 2 is also blocked, waiting in turn for a message that Thread 1 hasn't sent yet. The result: A deadlock that is qualitatively the same as the one that arose from locks. So, then, what is a complete definition of deadlock?
