Re: Deadlock resolution

[Mark Lorenzen <mark.lorenzen@ofir.dk>]

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

> 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.
> 
> I have never come across hardware that does deadlock
> detection or resolution. Is there any information about this
> on the Internet?

Martin Dowie mentioned something about an FPGA watchdog in another
response. You could also measure the electrical power consumption of
the CPU and if it is too low for too long, the CPU has probably
halted. But observe that these techniques does not guarantee that a
deadlock has occurred, just that "something" didn't happen on time.

> 
> >> 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.
> 
> Although I did not mention it (sorry), I am not really
> thinking about hard real time systems. The kind of systems I
> am most interested in are soft real time (non-embedded
> network server, technical workstation, office desktop).
> 
> Although many of the same basic principles apply, it is often
> the case that the economics are slightly different. But
> perhaps this doesn't matter?

You are right that economics differ - in soft real-time systems we are
often more interested in f.x. throughput than response time.

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

Good question. Is it actually possible to detect a deadlock in all
situations?

> 
> >> 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.
> 
> Is it necessary for the watchdog to reset the whole system,
> or just to kill one of the tasks/threads participating in the
> cycle of deadlock?

I was thinking of small embedded systems and there it is often
feasible to just reset the complete board. But in large systems, it
can be necessary to handle such incidents more gracefully. The
Ericsson AXE10 telephony switch can f.x. perform two kinds of restart
- a small and a large. A large restart is the fastest as it is simply
a "normal" restart of the system. A small restart on the other hand,
is much more complex as this involves tracing of all the ongoing calls
and only release the calls that have not yet reached a stable state
(such as two-way speach connection). The trick is to make sure that
all "tasks" (really co-routines in the AXE10) are able to receive a
special trace message at all times, evaluate it and send it to the
next entity in the call chain. It is thus the responsibility of the
co-routines to act on a small restart - they must reset themselves if
they are not in a stable stage.

But this does not solve the deadlock problem. It just ensure that in
such a case the RTS simply notes that a co-routine haven't given up
the CPU within a specific amount of time and then initiates a restart
(small I think) and if the problem persists the RTS will initiate a
large restart.

Maybe it is too overkill for your application though.

> 
> -- 
> Thanks again,
> Nick Roberts

Regards,
- Mark Lorenzen