Oracle FAQ Your Portal to the Oracle Knowledge Grid

Home -> Community -> Usenet -> comp.databases.theory -> Re: What Actually Causes Deadlock

Re: What Actually Causes Deadlock

From: Cimode <>
Date: 15 Dec 2006 08:18:16 -0800
Message-ID: <>

paul c wrote:
> 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:
> >
> >
> >
> >
> >
> > 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.

Not knowing history and repeating the same mistakes done 40 years ago certainly is a proof of the failure of the current American educational system today and on the past 30 years. Keep in mind that RM was not implemented because *good old people* refused to implement when there was a unique great opportunity to do it in the 70's.

> p
Received on Fri Dec 15 2006 - 10:18:16 CST

Original text of this message