What Actually Causes Deadlock
Date: 14 Dec 2006 21:33:59 -0800
Message-ID: <1166160839.536968.220270_at_80g2000cwy.googlegroups.com>
Over dinner and some excellent red wine, it occurred to me that the "folks at home" following some of the commentary on deadlock might not actually be fully up to speed on what causes deadlock, and might not be altogether following the ironic mode of speech in some of the posts, including my own. So I just want to put out there what really causes deadlock.
Deadlock is caused when there are *more than one* mutual exclusion entities, each possessed by a separate thread of computation, and the threads do not follow a consistent protocol for acquiring exclusive hold of these entities. Disk I/O has nothing to do with it; deadlock is entirely possible with two threads and two locks and no virtual memory or disk I/O of any kind.
Note that there has to be at least two, and there has to be inconsistent order in acquiring the locks. If either condition does not hold, deadlock is not possible. For example, if there is only one lock, then deadlock is impossible, no matter how many threads there are. If there are many locks but only one thread, then deadlock is impossible no matter how many locks there are. If there are many threads and many locks, but there also exists a canonical order to acquire the locks and every thread will only acquire locks in the canonical order, then deadlock is impossible.
The simplest example of deadlock possible:
Thread A has code that attempts to acquire lock 1 and if successful attempts to acquire lock 2. Thread B has code that attempts to acquire lock 2 and if successful attempts to acquire lock 1.
No simpler example of deadlock is possible.
When I was like, 18 years old it occurred to me that there was a simple lock discipline that would make deadlock impossible: give every lock a name, and only acquire locks in alphabetical order.
In any event, I hope this clears things up. Further questions will be handled when I'm fully sober.
For followup reading:
http://en.wikipedia.org/wiki/Deadlock
http://www.bvwines.com
Marshall Received on Fri Dec 15 2006 - 06:33:59 CET