Re: Deadlock resolution

[Ole-Hjalmar Kristensen <ole-hjalmar.kristensen@substitute_employer_here.com>]

>>>>> "NR" == Nick Roberts <nick.roberts@acm.org> writes:

    NR> On 26 Jul 2004 09:46:48 +0200, Mark Lorenzen <mark.lorenzen@ofir.dk> wrote:
    >>> Does this software tend to have deadlock detection and/or
    >>> resolution mechanisms explicitly programmed in Ada, or is
    >>> it expected that deadlocks will be managed elsewhere (for
    >>> example, in the operating system or run time system or
    >>> RTMS or whatever)?
    >> 
    >> I would say that it should be managed elsewhere preferably
    >> by hardware.

    NR> I have never come across hardware that does deadlock
    NR> detection or resolution. Is there any information about this
    NR> on the Internet?

All DB systems do deadlock detection, as they have no control over
the sequence of locks set by user transactions, so arbitrary
transactions may deadlock. See for example "Transaction processing" by
Gray and Reuter, section 7.11.  For centralized systems you can either
construct a wait-for graph or use a timeout. For distributed systems,
the most common method is to use a timeout.  But by all means, if you
can possibly do it, always reserve resources in the same order and
release them at the end, thus avoiding the problem altogether.

    >>> Alternatively, have you ever come across software written
    >>> in Ada using techniques to eliminate deadlock (for example,
    >>> a lock ordering strategy)?
    >> 
    >> Use one of the normal analysis methods to analyse if your
    >> tasks always meet their deadlines f.x. the Rate Monotonic
    >> Analysis method (see "Meeting Deadlines in Hard Real-Time
    >> Systems" ISBN: 0-8186-7406-7) together with the Ravenscar
    >> Ada profile.

    NR> Although I did not mention it (sorry), I am not really
    NR> thinking about hard real time systems. The kind of systems I
    NR> am most interested in are soft real time (non-embedded
    NR> network server, technical workstation, office desktop).

    NR> Although many of the same basic principles apply, it is often
    NR> the case that the economics are slightly different. But
    NR> perhaps this doesn't matter?

    >>> Which approach do you think is best, in reality (handle in
    >>> Ada, handle elsewhere, eliminate altogether)?
    >> 
    >> Eliminate deadlocks in the first place is the best
    >> solution. Everything else is just a hack trying to fix a
    >> bad design.

    NR> That is quite true, but deadlock handling is a bit like
    NR> exception handling, in that it can form the braces of a belt-
    NR> and-braces approach. Is deadlock elimination realistic for
    NR> all kinds of software?

    >>> I would appreciate brief descriptions of how deadlock
    >>> detection and/or resolution is performed in real Ada
    >>> programs (where it is performed in Ada).
    >> 
    >> In some systems, a watchdog is monitoring the CPU to detect
    >> if it halts and then resets the system. But again, avoiding
    >> deadlocks is better than resetting the system.

    NR> Is it necessary for the watchdog to reset the whole system,
    NR> or just to kill one of the tasks/threads participating in the
    NR> cycle of deadlock?

    NR> -- 
    NR> Thanks again,
    NR> Nick Roberts

-- 
   C++: The power, elegance and simplicity of a hand grenade.