Re: file locking in Ada

[bobduff@world.std.com (Robert A Duff)]

In article <dewar.859696916@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>How can you deadlock without doing a potentially blocking operation

I'm thinking about something like this: Protected objects This and That,
both with functions F and G.  Protected object This has a function F,
which calls That.F.  Protected object That has a function G which calls
This.G.  Both directions.  Now, if task 1 calls This.F, and task 2 calls
That.G, then is there a potential deadlock?  Suppose we have two
processors, and both happen at the same time, and This.F locks This, and
That.G locks That.  If those locks allow read-only access, then deadlock
is impossible.  But if the implementation converts those read-only locks
into "normal" read/write locks, then it is possible that task 1 holds
the lock on This, and task 2 holds the lock on That, and each is
contending for the lock on the other protected object -- hence deadlock.

Suppose This and That have the same ceiling.  Tasks 1 and 2 are both
running, since we have (at least) two processors (so we don't care what
priority they are).

My claim is that the RM says the above situation must not deadlock,
whereas, the intent of the language designers (including me!), was that
the above situation *might* deadlock.

>Yes, if protected objects were orthogonal abstraction mechanisms, one
>could certainly tell, but given the severe restrictions that are placed
>on them, I don't see how you could possibly tell with a functional test.

It seems to me that contending for locks on protected objects can cause
deadlock -- no need for entries, or other "potentially blocking ops".
After all, if F and G above were replaced with protected *procedures*,
then surely, deadlock is possible.

The two situations, "deadlock possible", and "deadlock impossible" are
semantically different.  (No need to produce a test where deadlock is
"inevitable", IMHO.)

- Bob