Re: What Actually Causes Deadlock

Marshall wrote:
> 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
>

Back in the 1970's (and the 1960's too, I guess) every mainframe application programmer who used IBM CICS or IMS DC was aware of that terse bullet list in the wikipedia and were careful to order their accesses, whether they were to dbms, file, TP channel or abstact memory in some agreed-upon order. Similar must have been true of application programmers who used other hardware from the so-called "BUNCH". The big operating system developments of the 1960's had already recognized the problem and even the non-assembler, eg., Cobol, programmers of those days were to some extent programming the bare metal, as it were.

I remember several of us scratching our heads around fifteen years ago about a deadlock we had introduced in a multi-process access engine when another old-timer asked what were we playing at. We had become so enamoured with making high-level tools that we had forgotten the old stuff.

I suppose the intermittent re-discovery of old knowledge is inevitable as the trend to more and more specialization and componentization continues.

p Received on Fri Dec 15 2006 - 15:28:13 CET