Composing tasks and protected objects

Composing tasks and protected objects

[Florian Weimer]

Suppose I want to write a selective accept which reads messages from a
queue, and also support a special entry call to reload the
configuration.

Conceptually, this would look like this:

   task Server is
      entry Reload_Configuration (Config : Config_Template);
      entry Shut_DOwn;
   end Server;

   task body Server is
      Current_Message : Message;

   begin
      loop
         select
            Get (Queue, Current_Message);
            Process_Message (Current_Message);

         or
            accept Reload_Configuration (Config : Config_Template) do
               Process_Reload (Config);
            end Reload_Configuration;

         or
            accept Shut_Down;
            exit;       -- Premature shut down requested

         or
            terminate;  -- Normal shutdown at end of scope
         end select;
      end loop;
   end Server;

In short, I want to perform protected entry calls and selective accept
in parallel.

Is this possible at all, without writing lots of stupid wrappers?  If
not, what was the justification for not integrating the two language
features (protected objects/tasks) in this way?

Re: Composing tasks and protected objects

[Robert A Duff]

Florian Weimer <fw@deneb.enyo.de> writes:

> Suppose I want to write a selective accept which reads messages from a
> queue, and also support a special entry call to reload the
> configuration.
> 
> Conceptually, this would look like this:
> 
>    task Server is
>       entry Reload_Configuration (Config : Config_Template);
>       entry Shut_DOwn;
>    end Server;
> 
>    task body Server is
>       Current_Message : Message;
> 
>    begin
>       loop
>          select
>             Get (Queue, Current_Message);
>             Process_Message (Current_Message);
> 
>          or
>             accept Reload_Configuration (Config : Config_Template) do
>                Process_Reload (Config);
>             end Reload_Configuration;
> 
>          or
>             accept Shut_Down;
>             exit;       -- Premature shut down requested
> 
>          or
>             terminate;  -- Normal shutdown at end of scope
>          end select;
>       end loop;
>    end Server;
> 
> In short, I want to perform protected entry calls and selective accept
> in parallel.
> 
> Is this possible at all, without writing lots of stupid wrappers?

No.  You cannot mix entry calls and accepts in the same select
statement.  You can't mix entry calls with "terminate", either.

The original Ada 9X design proposed to allow multiple entry calls in a
select, which would solve your main problem, which is waiting on
multiple events.  Your two entries would then become entries of a
protected object, and the above select would call them.  Whoever calls
those two entries would instead call protected procedures that trigger
those entries.

You would have to eliminate the terminate alternative, and use the
Shut_Down mechanism instead.  Or abort the task.

The multi-way call feature was rejected primarily due to perceived
difficulty of implementation, or perceived difficulty of *efficient*
implementation.  I did not agree with that argument.

One workaround is to change the call to Get into an accept
-- i.e. make Get be an entry of this task, and arrange for it
to be called as appropriate.

Another workaround is to implement something like multi-way call
yourself.  Several entries can be shunted through a single entry, with a
bit-mask saying which entry is intended.  Or something like that.  You
could probably create a general-purpose feature by wrapping that mess in
generics.

>...If
> not, what was the justification for not integrating the two language
> features (protected objects/tasks) in this way?

As far as I know, mixing calls and accepts was not considered,
perhaps because protected objects were intended to be a very lightweight
mechanism (compared to task entries and accept statements).

I don't think terminates mixed with calls was considered, either.  It's
not clear what it should mean.  Normally, "terminate" means the task
terminates when there is no possibility that anybody might want to call
the entries the task is waiting on.  This doesn't work in the case of
interrupt entries, but in all other cases, various language rules ensure
that it's true (e.g., a task can only accept its own entries).  But for
calls, the same reasoning doesn't work.

I'd be interested if anybody can give some rules that make sense for
mixing terminate with calls.

- Bob

Re: Composing tasks and protected objects

[Florian Weimer]

* Robert A. Duff:

>> In short, I want to perform protected entry calls and selective accept
>> in parallel.
>> 
>> Is this possible at all, without writing lots of stupid wrappers?
>
> No.  You cannot mix entry calls and accepts in the same select
> statement.  You can't mix entry calls with "terminate", either.

Yes, of course the code does not compile.  I thought that I might have
missed something obvious and this syntax was left out on the grounds
of orthogonality of language features or something like that.

> The original Ada 9X design proposed to allow multiple entry calls in a
> select, which would solve your main problem, which is waiting on
> multiple events.

Indeed.

> Your two entries would then become entries of a protected object,
> and the above select would call them.  Whoever calls those two
> entries would instead call protected procedures that trigger those
> entries.

Yes, this would solve the main multiplexing problem.

> The multi-way call feature was rejected primarily due to perceived
> difficulty of implementation, or perceived difficulty of *efficient*
> implementation.  I did not agree with that argument.

I could understand that argument if this language feature caused
uniform overhead on all protected operations, even if it isn't used
anywhere in the program.  Is this really the case?

> One workaround is to change the call to Get into an accept
> -- i.e. make Get be an entry of this task, and arrange for it
> to be called as appropriate.

Yes, but this only half of the story.  In order to decouple the sender
from the receiver, I think I need some access-to-entry concept.  I can
only implement this using some wrapper.

It seems that the synchronous interfaces of Ada 2005 would make this
considerably easier.

>>...If
>> not, what was the justification for not integrating the two language
>> features (protected objects/tasks) in this way?
>
> As far as I know, mixing calls and accepts was not considered,
> perhaps because protected objects were intended to be a very lightweight
> mechanism (compared to task entries and accept statements).

Hmm.  It's still a bit strange that these language concepts are so far
away from each other.

> I don't think terminates mixed with calls was considered, either.  It's
> not clear what it should mean.  Normally, "terminate" means the task
> terminates when there is no possibility that anybody might want to call
> the entries the task is waiting on.

I think the alternative is also chosen if the master completes.
Wouldn't this lead to useful semantics in this case as well?

In the queue example, you'd give up your subscription to that queue,
but this would be handled by a controlled object declared in the task,
I think.

Re: Composing tasks and protected objects

[Robert A Duff]

Florian Weimer <fw@deneb.enyo.de> writes:

> * Robert A. Duff:
> > The multi-way call feature was rejected primarily due to perceived
> > difficulty of implementation, or perceived difficulty of *efficient*
> > implementation.  I did not agree with that argument.
> 
> I could understand that argument if this language feature caused
> uniform overhead on all protected operations, even if it isn't used
> anywhere in the program.  Is this really the case?

I think I could implement multi-ways calls in such a way that there is
zero or near-zero overhead for the currently-allowed features (plain
calls, timed/conditional calls).  But I have not proven that by doing
so!

Inefficiency is never a good reason to leave a feature out of a
language.  What matters is distributed overhead (i.e. when a feature
causes inefficiency when you *don't* use it).

There's also the issue that the implementation experiments done during
the Ada 9X process were done on *existing* implementations, which were
designed with the requirements of Ada 83 in mind.  Adding a feature to
an existing implementation is sometimes a lot harder than implementing
it in a from-scratch design where the designer knows the requirements.

> > As far as I know, mixing calls and accepts was not considered,
> > perhaps because protected objects were intended to be a very lightweight
> > mechanism (compared to task entries and accept statements).
> 
> Hmm.  It's still a bit strange that these language concepts are so far
> away from each other.

Well, if I were designing a language from scratch, I would have
something like protected object entries.  I would eliminate task entries
entirely, and beef up PO entries so that can do all the useful things
that task entries can do (such as waiting on multiple events).

Task entries cause an enormous amount of unnecessary complexity in the
language.  Task types and task bodies could be completely eliminated,
for example.

As I said, I'm not sure what to do about terminate alternatives.

> > I don't think terminates mixed with calls was considered, either.  It's
> > not clear what it should mean.  Normally, "terminate" means the task
> > terminates when there is no possibility that anybody might want to call
> > the entries the task is waiting on.
> 
> I think the alternative is also chosen if the master completes.
> Wouldn't this lead to useful semantics in this case as well?

A terminate alt is chosen if the master is complete, and all tasks
dependent upon that master (directly or indirectly) are terminated, or
are waiting at select-with-terminate statements.  Given these conditions
(and ignoring interrupts), the task's entries could never be called.

But the same conditions in the entry call case do not imply that the
called entry will never be triggered, because the called entry can be
essentially anywhere, without regard to scopes and whatnot.

> In the queue example, you'd give up your subscription to that queue,
> but this would be handled by a controlled object declared in the task,
> I think.

I don't understand what you mean here.

- Bob

Re: Composing tasks and protected objects

[Florian Weimer]

* Robert A. Duff:

> But the same conditions in the entry call case do not imply that the
> called entry will never be triggered, because the called entry can be
> essentially anywhere, without regard to scopes and whatnot.
> 
>> In the queue example, you'd give up your subscription to that queue,
>> but this would be handled by a controlled object declared in the task,
>> I think.
>
> I don't understand what you mean here.

As you wrote, you can't be sure that there won't be any further
messages in the queue when the terminate alternative is selected.  In
general, you have to inform the sender about this, otherwise the queue
will eventually get stuck.  Therefore, in general, you need to notify
the queue about the lack of receivers.  Doing this with a controlled
object seems to be a natural choice because it would also work in the
presence of exceptions.

(As always, there might be some nasty deadlock issues lurking
somwhere. 8-)

Re: Composing tasks and protected objects

[Jeffrey Carter]

Florian Weimer wrote:
> Suppose I want to write a selective accept which reads messages from a
> queue, and also support a special entry call to reload the
> configuration.

You need all calls to go the same way. Right now you're trying to do 
something like

+----------+          +----------+          +----------+
|          |          |          |          |          |
|     Q    |<--Get----|  Server  |<--Shut---|     ?    |
|          |          |          |   Down   |          |
|          |          |          |<--Reload-|          |
|          |          |          |          |          |
+----------+          +----------+          +----------+

where arrows indicate direction of call. This won't work, but it will 
work if you can turn that call to Get around. For this, you need a 
forwarder between the Queue and Server:

+----------+       +----------+       +----------+       +----------+
|          |       |          |       |          |       |          |
|     Q    |<-Get--| Forwarder|--Msg->|  Server  |<-Etc--|     ?    |
|          |       |          |       |          |       |          |
+----------+       +----------+       +----------+       +----------+

Now your task can look like

select
    accept Msg (Message : in ...) do
       Current_Message := Message;
    end Msg;

    Process_Message (Current_Message);
or
    ... -- as in your example
end select;

The only difficulty is terminating the Forwarder.

-- 
Jeff Carter
"Go and boil your bottoms."
Monty Python & the Holy Grail
01

Re: Composing tasks and protected objects

[Dmitry A. Kazakov]

On Fri, 05 Aug 2005 19:26:35 +0200, Florian Weimer wrote:

> Suppose I want to write a selective accept which reads messages from a
> queue, and also support a special entry call to reload the
> configuration.
> 
> Conceptually, this would look like this:
> 
>    task Server is
>       entry Reload_Configuration (Config : Config_Template);
>       entry Shut_DOwn;
>    end Server;
> 
>    task body Server is
>       Current_Message : Message;
> 
>    begin
>       loop
>          select
>             Get (Queue, Current_Message);
>             Process_Message (Current_Message);
> 
>          or
>             accept Reload_Configuration (Config : Config_Template) do
>                Process_Reload (Config);
>             end Reload_Configuration;
> 
>          or
>             accept Shut_Down;
>             exit;       -- Premature shut down requested
> 
>          or
>             terminate;  -- Normal shutdown at end of scope
>          end select;
>       end loop;
>    end Server;

You could make "Reload_Configuration" and "Shut_Down" messages rather than
entries. Of course only if you don't need to wait for their completion.
Otherwise you are going to mix synchronous calls with fire-and-forget
messaging. It is always difficult.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Composing tasks and protected objects

[Randy Brukardt]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wcchde4dyv4.fsf@shell01.TheWorld.com...
> Florian Weimer <fw@deneb.enyo.de> writes:
>
> > * Robert A. Duff:
> > > The multi-way call feature was rejected primarily due to perceived
> > > difficulty of implementation, or perceived difficulty of *efficient*
> > > implementation.  I did not agree with that argument.
> >
> > I could understand that argument if this language feature caused
> > uniform overhead on all protected operations, even if it isn't used
> > anywhere in the program.  Is this really the case?
>
> I think I could implement multi-ways calls in such a way that there is
> zero or near-zero overhead for the currently-allowed features (plain
> calls, timed/conditional calls).  But I have not proven that by doing
> so!

The UI teams of the Ada 9X effort were asked to write reports on this
feature. None of them came up with an efficient implementation. Their
reports are still around somewhere (use the search engine to look in the
AdaIC archives - archive.adaic.com).

> Inefficiency is never a good reason to leave a feature out of a
> language.  What matters is distributed overhead (i.e. when a feature
> causes inefficiency when you *don't* use it).

I think that most of the possible efficient implementations did so by having
distributed overhead. But it was a long, long time ago, so I don't remember
the details anymore.

But I do remember that one of the major issues was that the people who were
pushing for the feature were hard-real-time types with strict timing
requirements. No one had an implementation that could meet those sorts of
requirements (polling seemed to be required). Having a feature that cannot
be efficicient enough for the customers is silly.

> There's also the issue that the implementation experiments done during
> the Ada 9X process were done on *existing* implementations, which were
> designed with the requirements of Ada 83 in mind.  Adding a feature to
> an existing implementation is sometimes a lot harder than implementing
> it in a from-scratch design where the designer knows the requirements

Possibly. I have to wonder if there wouldn't be too many conflicting
requirements to make that possible. The "Bob" language without task entries
would clearly make it easier to allow other sorts of things (although I
can't quite figure out how it would work). A clear sheet of paper helps
things in every dimension -- but that isn't going to happen for Ada, as
compatibility is important.

                                Randy.

Re: Composing tasks and protected objects

[Florian Weimer]

* Jeffrey Carter:

> You need all calls to go the same way. Right now you're trying to do 
> something like
>
> +----------+          +----------+          +----------+
> |          |          |          |          |          |
> |     Q    |<--Get----|  Server  |<--Shut---|     ?    |
> |          |          |          |   Down   |          |
> |          |          |          |<--Reload-|          |
> |          |          |          |          |          |
> +----------+          +----------+          +----------+
>
> where arrows indicate direction of call. This won't work, but it will 
> work if you can turn that call to Get around. For this, you need a 
> forwarder between the Queue and Server:
>
> +----------+       +----------+       +----------+       +----------+
> |          |       |          |       |          |       |          |
> |     Q    |<-Get--| Forwarder|--Msg->|  Server  |<-Etc--|     ?    |
> |          |       |          |       |          |       |          |
> +----------+       +----------+       +----------+       +----------+

This introduces overhead in terms of an additional task, and the
Forwarder and Server are strongly coupled (unless you manually write
wrappers, because access-to-entry types are missing).

Re: Composing tasks and protected objects

[Randy Brukardt]

"Florian Weimer" <fw@deneb.enyo.de> wrote in message
news:87oe88bvse.fsf@mid.deneb.enyo.de...
....
> This introduces overhead in terms of an additional task, and the
> Forwarder and Server are strongly coupled (unless you manually write
> wrappers, because access-to-entry types are missing).

Yes, but an implementation of the proposed feature probably would have to
introduce that task anyway. It would end up costing about the same, yet it
would look cheap. That's generally bad language design.

                      Randy.

Re: Composing tasks and protected objects

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> "Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
> news:wcchde4dyv4.fsf@shell01.TheWorld.com...
> > Florian Weimer <fw@deneb.enyo.de> writes:
> >
> > > * Robert A. Duff:
> > > > The multi-way call feature was rejected primarily due to perceived
> > > > difficulty of implementation, or perceived difficulty of *efficient*
> > > > implementation.  I did not agree with that argument.
> > >
> > > I could understand that argument if this language feature caused
> > > uniform overhead on all protected operations, even if it isn't used
> > > anywhere in the program.  Is this really the case?
> >
> > I think I could implement multi-ways calls in such a way that there is
> > zero or near-zero overhead for the currently-allowed features (plain
> > calls, timed/conditional calls).  But I have not proven that by doing
> > so!
> 
> The UI teams of the Ada 9X effort were asked to write reports on this
> feature. None of them came up with an efficient implementation. Their
> reports are still around somewhere (use the search engine to look in the
> AdaIC archives - archive.adaic.com).

It's easy to believe that multi-way call is infeasible to implement in
an existing Ada 83 compiler.  And we certainly cannot blame an Ada 83
implementor for not taking into account language requirements that did
not exist until 10 years after they did their design!

And of course a language revision needs to take into account difficulty
of implementation on *existing* compilers.

For example, in Ada 83, one could assume that a task can only be on one
entry queue at a time.  And it was reasonable for Ada 83 implementers to
take advantage of that assumption by putting the queue links in the TCB.
For multi-way calls, you have to switch to thinking about each entry
call (represented by a stack-allocated object) being separately on an
entry queue, rather than the *task* itself being on the queue.  And that
might require a rather daunting rewrite of an existing Ada 83
implementation.

However, my claim was that it is possible to implement multi-way calls
with near-zero distributed overhead, in a *from scratch*
implementation.

Note that there may already be a tiny bit of distributed overhead:
simple entry calls pay some cost because of the mere existence of timed
entry calls, even if timed entry calls are not used, because you have to
worry about the potential race condition if the time-out happens at
nearly the same time as the entry being triggered.  I claim (without
proof ;-)) that the distributed overhead of multi-way calls can be
hidden in the same overhead necessary for timed calls.

> > Inefficiency is never a good reason to leave a feature out of a
> > language.  What matters is distributed overhead (i.e. when a feature
> > causes inefficiency when you *don't* use it).
> 
> I think that most of the possible efficient implementations did so by having
> distributed overhead. But it was a long, long time ago, so I don't remember
> the details anymore.
> 
> But I do remember that one of the major issues was that the people who were
> pushing for the feature were hard-real-time types with strict timing
> requirements. No one had an implementation that could meet those sorts of
> requirements (polling seemed to be required).

I don't think polling is required (in a from-scratch design, where the
designer knows the requirement for multi-way call ahead of time).

>... Having a feature that cannot
> be efficicient enough for the customers is silly.

I don't really buy that argument.  If the requirement is to wait upon
multiple entry calls, and that feature is not available, then
programmers will have to implement it themselves.  If it's inherently
inefficient, then so be it -- they need that functionality, and that's
that.  It's unlikely that programmers will be able to implement that
functionality more efficiently than Ada implementers.

> > There's also the issue that the implementation experiments done during
> > the Ada 9X process were done on *existing* implementations, which were
> > designed with the requirements of Ada 83 in mind.  Adding a feature to
> > an existing implementation is sometimes a lot harder than implementing
> > it in a from-scratch design where the designer knows the requirements
> 
> Possibly. I have to wonder if there wouldn't be too many conflicting
> requirements to make that possible. The "Bob" language without task entries
> would clearly make it easier to allow other sorts of things (although I
> can't quite figure out how it would work). A clear sheet of paper helps
> things in every dimension -- but that isn't going to happen for Ada, as
> compatibility is important.

Yes -- compatibility is important.

- Bob

Re: Composing tasks and protected objects

[Robert A Duff]

"Randy Brukardt" <randy@rrsoftware.com> writes:

> "Florian Weimer" <fw@deneb.enyo.de> wrote in message
> news:87oe88bvse.fsf@mid.deneb.enyo.de...
> ....
> > This introduces overhead in terms of an additional task, and the
> > Forwarder and Server are strongly coupled (unless you manually write
> > wrappers, because access-to-entry types are missing).
> 
> Yes, but an implementation of the proposed feature probably would have to
> introduce that task anyway.

Are we still talking about multi-way calls?  I certainly don't believe
that their implementation requires the implicit introduction of hidden
tasks, or anything near that cost!

>... It would end up costing about the same, yet it
> would look cheap. That's generally bad language design.

Well, I disagree about the cost, but I also disagree with that language
design principle -- the principle that says inefficient things should
*look* inefficient in the source code.  That principle is exactly the
*opposite* of what high level languages ought to be about.

In most cases, Ada does *not* follow that principle, and that's a Good
Thing.  In the few cases where Ada does follow it, it's a Bad Thing.

Consider:

    X := Y;

If the type is Integer, it takes approximately 1 machine instruction.
If the type is array-of-a-million-integers, it takes millions of
instructions.  If the type is controlled, it invokes Adjust, which could
do all kinds of user-defined task locking and heap management.

We don't use a different syntax for fast and slow assignments!
Surely that's good.  (Contrast with C, where the array case uses
"memcpy" instead of "=", and the Adjust case requires calling Adjust
explicitly.)

Another example: array indexing uses the same syntax whether the thing
is bit-packed or not.  Contrast with C, where the bit-packed case
requires explicit shifting and masking.  The extra cost of bit-packed
array indexing is more apparent from the source code in C, which is
certainly an advantage, but it's outweighed by the loss in abstraction.
For example, in Ada, you can easily experiment to determine whether bit
packing is an efficiency win.

An example where Ada *does* follow this misguided principle: unbounded
strings are a huge pain to use in Ada.  It would be much nicer if they
supported array-indexing syntax, slicing, literals, etc.  That would
hide the inefficiency of these strings.

I say, if you want to see efficiency properties clearly in the source
code, you must program in assembly.  In higher level languages, you lose
that capability.  You must determine efficiency by measurement, and by
experience (knowing which features are efficient in typical
implementations).

- Bob