Ada 9X and deadlocks

Ada 9X and deadlocks

[Craig Anderson]

Hi.
How does one write multi-tasking Ada 9X programs with any reasonable
assurance of freedom from deadlock?  Should we expect to see robust
static deadlock analysis programs?  Are code coverage tools available
that would help in designing test cases to find deadlocks?  How would
we go about specifying a static locking order -- would we want to? --
and perhaps why wasn't this included in Ada 9X?  I guess you can assume
that real-time support isn't available or that an MP platform is being
used.

Thanks,
-Craig
-- 
Craig Anderson (craig@abstract.co.nz)
Abstract Technologies New Zealand Limited
Ada 9X: the language for the 90's; finger or mail ada@abstract.co.nz for info

Re: Ada 9X and deadlocks

[Tucker Taft]

In article <3ab9ee$fhe@abstract.co.nz>,
Craig Anderson <craig@abstract.co.nz> wrote:

>How does one write multi-tasking Ada 9X programs with any reasonable
>assurance of freedom from deadlock?  

Avoid holding multiple locks at the same time, and when you
do, be sure you acquire them in a consistent order.

> ... Should we expect to see robust
>static deadlock analysis programs?  

Hopefully.  There are a number of research-y tools in this
area, and one would hope that at least one of them will progress
to production quality sometime soon.

> ... Are code coverage tools available
>that would help in designing test cases to find deadlocks?  

I don't know.

> ... How would
>we go about specifying a static locking order -- would we want to? --

Yes, you certainly want to establish a static locking order if
a task ever needs to hold multiple locks simultaneously.

>... and perhaps why wasn't this included in Ada 9X?  

We considered some primitives for acquiring multiple locks,
but they were complicated, and seemed well beyond what is
appropriate for a language-defined "primitive."

Even what a "lock" is depends on the application.  You might
only use the locking inherent in protected types (or
rendezvous, for that matter), in which case the only way
you ever hold multiple locks is if from within a protected
operation you call another protected operation (or for rendezvous,
do an entry call from an accept statement).  
The concept of ceiling priority already provides some
degree of deadlock avoidance, if each lock has its own
priority.  On a mono-processor, deadlock is impossible in Ada9X
if you restrict yourself to the locking inherent in protected types
(the proof is left as an exercise for the reader ;-).

Alternatively, a "lock" might be a higher-level abstraction you 
build using protected types (or rendezvous).   This would make
sense for longer-lived (or queued) locks.  Another alternative is to
provide preemptible locks, and thereby avoid deadlock by having
a lock back-out protocol.

The bottom line is that we concluded that management of multiple locks
was a "programming" problem, not a "language design" problem.

> ... I guess you can assume
>that real-time support isn't available or that an MP platform is being
>used.

I'm not sure what you mean by this last sentence...

>Thanks,
>-Craig
>-- 
>Craig Anderson (craig@abstract.co.nz)
>Abstract Technologies New Zealand Limited
>Ada 9X: the language for the 90's; finger or mail ada@abstract.co.nz for info

S. Tucker Taft    stt@inmet.com
Ada 9X Mapping/Revision Team
Intermetrics, Inc.
Cambridge, MA  02138