Re: Distributed Computing in Ada

[Robert A Duff <bobduff@shell01.TheWorld.com>]

"Jeffrey R. Carter" <spam.jrcarter.not@spam.acm.org> writes:

> Robert A Duff wrote:
>> Well, sort of, but not in a practical way.  Ada tasks share memory, and
>> there's no way to tell which variables are shared.  "Distributed" means
>> no shared memory.
>
> Ada tasks /can/ share memory, but they don't have to.

The problem is that the compiler can't know which variables are shared.
Maybe no variables are shared, and all communication is via rendezvous,
but if the compiler doesn't know that, it's no help.

For example:

    package body P is
        Global : Integer := 0;
        
        procedure Q is
        begin
            Global := Global + 1;
        end Q;
    end P;

Is Global shared?  It depends on who calls it.  Elsewhere we might have:

    task type T is
        entry E;
    end T;

    task body T is
    begin
        loop
            select
                accept E do
                    P.Q; -- Read and write shared variable.

                ... --etc.
        end loop;
    end T;

    A : array (...) of T;

Now we have a bunch of tasks accessing shared variable Global,
all correctly synchronized by the rendezvous.  But the compiler
didn't know it was shared when it compiled package body P.
And when it compiled tasks T, it didn't know P.Q modifies
any variable.

You could do a whole-program / link-time analysis, but that doesn't
scale well (Ada was designed to support separate compilation for a
reason!).  And even that won't always work -- consider possibly-shared
variables in the heap, where the compiler can't know what points at
what (see halting problem).

All in all, in this regard, I'd say Ada 83 tasks are just like the
"threads" of various languages and operating systems (Posix threads,
Java threads...) -- all these are designed with the assumption
of a shared address space.  Ada 95 protected types are designed
with the same assumption.

>...The rendezvous
> seems like it would map nicely to message passing.

Yes, it is.  That's how we did it -- basically, an entry call sends a
message, and at the end of the accept, the called task sends a message
back to the caller.  It's tricky, though -- what happens if one of
the entry parameters points into the address space of the caller, either
via an explicit access value, or via implicit pass-by-reference?
That's bad -- the data really needs to get copied across the network.

Note that this was Ada 83, so it predated protected types.

>> I actually implemented such a system for Ada 83, where tasks could run
>> on different computers.  But there were some severe restrictions on
>> shared variables.  Terminate alternatives are "interesting" in that
>> context.
>
> Yes, there would have to be some mechanism to deal with shared
> variables; the simplest would be simply to outlaw access to non-local
> variables in tasks if you want to run your program on a distributed
> system.

Depends what you mean by "outlaw".  If you mean "illegal", so you get an
error message at compile time, that won't work.  You could give an error
message at "link time", but only by being overly conservative (that is,
outlawing perfectly-OK programs).  You could say it's erroneous to
access shared variables (so it leads to unpredictable behavior) -- that
works fine, but it's obviously not ideal.  Or you could implement
a distributed shared address space via message passing, but I fear that
would be prohibitively expensive.

Ada 95's Distributed Systems Annex solves all this mess, by allowing the
compiler to know which variables are shared.  The unit of distribution
is the "partition", not the "task".  Usually, no variables are shared
across partitions -- but it's important for the compiler to know when
that's the case.

- Bob