Basic question about select

Basic question about select

[John Wilkinson]

select
    	PID.Call;  --an entry call to task PID
    	Status := P;
then abort
    	delay 10.0;
    	Status := Q;
end select;

Is the above valid Ada code? It's been handed to me by someone, I 
don't really know much about Ada, and I'm supposed to understand 
what it does. I can't find any information on "abort" or even 
"then".

If it's valid, what does it do?

Re: Basic question about select

[Dmitry A. Kazakov]

On Wed, 28 Apr 2010 18:16:44 +0000 (UTC), John Wilkinson wrote:

> select
>     	PID.Call;  --an entry call to task PID
>     	Status := P;
> then abort
>     	delay 10.0;
>     	Status := Q;
> end select;
> 
> Is the above valid Ada code? It's been handed to me by someone, I 
> don't really know much about Ada, and I'm supposed to understand 
> what it does. I can't find any information on "abort" or even 
> "then".

See ARM 9.7.4 Asynchronous Transfer of Control

> If it's valid, what does it do?

It waits 10s and then assigns Q to Status. But if within these 10s + the
time needed to assign Status, the task PID accepts Call, then the sequence
introduced by "then abort" is aborted, Call is performed, and finally, P is
assigned to Status.

Note that the recommended way to do this is the timed entry call ARM 9.7.2:

select
   PID.Call;  -- call to task PID
   Status := P;
or delay 10.0; -- wait to longer than 10s
   Status := Q;
end select;

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

Re: Basic question about select

[Jeffrey R. Carter]

Dmitry A. Kazakov wrote:
> 
> It waits 10s and then assigns Q to Status. But if within these 10s + the
> time needed to assign Status, the task PID accepts Call, then the sequence
> introduced by "then abort" is aborted, Call is performed, and finally, P is
> assigned to Status.

That's a good explanation for the OP.

Technically, though, it isn't quite true: if the entry call *completes* then the 
abortable part (after "then abort") is aborted: "If the triggering_statement 
completes other than due to cancellation, the abortable_part is aborted". The 
abortable part only begins execution if the entry call is queued, either 
immediately or by requeue-with-abort.

If the abortable part completes, then it attempts to cancel the entry call, even 
if it has been "selected" (is no longer queued but has not completed).

For a timed entry call, no attempt is made to cancel the entry call if the entry 
has been "selected". This difference in semantics may be why this code uses 
asynchronous transfer of control rather than a timed entry call.

But I doubt it.

-- 
Jeff Carter
"From this day on, the official language of San Marcos will be Swedish."
Bananas
28

Re: Basic question about select

[Dmitry A. Kazakov]

On Wed, 28 Apr 2010 14:00:50 -0700, Jeffrey R. Carter wrote:

> Technically, though, it isn't quite true: if the entry call *completes* then the 
> abortable part (after "then abort") is aborted: "If the triggering_statement 
> completes other than due to cancellation, the abortable_part is aborted".

This is a very interesting question. I don't know if this wording indeed
requires the rendezvous and the abortable part to execute in parallel.
Otherwise, in effect, fetching the call from the queue must abort. I would
expect rather the latter, because the former would be quite difficult to
implement. The following example illustrates the case:

   protected Event is
      procedure Signal;
      entry Wait;
   private
      Signaled : Boolean := False;
   end Event;

   protected body Event is
      procedure Signal is
      begin
         Signaled := True;
      end Signal;
      entry Wait when Signaled is
      begin
         Signaled := False;
      end;
   end Event;
   
   task PID is
      entry Call;
   end PID;

   task body PID is
   begin
      accept Call do Event.Wait; end;
   end PID;

begin
  select
     PID.Call;  -- Blocked in the rendezvous
  then abort
     delay 2.0;
     Event.Signal; -- Releases the rendezvous after 2s
  end select;

If abort to happen after *completion* of the rendezvous then the above
shall not deadlock. (I checked this under GNAT/Windows, it deadlocks
there.)

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

Re: Basic question about select

[Jeffrey R. Carter]

Dmitry A. Kazakov wrote:
> 
>    protected Event is
>       procedure Signal;
>       entry Wait;
>    private
>       Signaled : Boolean := False;
>    end Event;
> 
>    protected body Event is
>       procedure Signal is
>       begin
>          Signaled := True;
>       end Signal;
>       entry Wait when Signaled is
>       begin
>          Signaled := False;
>       end;
>    end Event;
>    
>    task PID is
>       entry Call;
>    end PID;
> 
>    task body PID is
>    begin
>       accept Call do Event.Wait; end;
>    end PID;
> 
> begin
>   select
>      PID.Call;  -- Blocked in the rendezvous
>   then abort
>      delay 2.0;
>      Event.Signal; -- Releases the rendezvous after 2s
>   end select;
> 
> If abort to happen after *completion* of the rendezvous then the above
> shall not deadlock. (I checked this under GNAT/Windows, it deadlocks
> there.)

Here the call to PID.Call is not queued, but is accepted immediately, and does 
not encounter an explicit requeue-with-abort. I guess that queuing on Event.Wait 
does not count as equivalent to requeue-with-abort (unless this is a compiler 
error; any language lawyers care to comment?). So the abortable part is never 
executed, leading to deadlock.

It will be interesting to add "delay 1.0;" to the task before the accept, and 
see if that changes the behavior. Then the call to PID.Call will queue, and the 
abortable part should execute.

-- 
Jeff Carter
"From this day on, the official language of San Marcos will be Swedish."
Bananas
28

Re: Basic question about select

[Adam Beneschan]

On Apr 28, 5:20 pm, "Jeffrey R. Carter"
<spam.jrcarter....@spam.acm.org> wrote:
> Dmitry A. Kazakov wrote:
>
> >    protected Event is
> >       procedure Signal;
> >       entry Wait;
> >    private
> >       Signaled : Boolean := False;
> >    end Event;
>
> >    protected body Event is
> >       procedure Signal is
> >       begin
> >          Signaled := True;
> >       end Signal;
> >       entry Wait when Signaled is
> >       begin
> >          Signaled := False;
> >       end;
> >    end Event;
>
> >    task PID is
> >       entry Call;
> >    end PID;
>
> >    task body PID is
> >    begin
> >       accept Call do Event.Wait; end;
> >    end PID;
>
> > begin
> >   select
> >      PID.Call;  -- Blocked in the rendezvous
> >   then abort
> >      delay 2.0;
> >      Event.Signal; -- Releases the rendezvous after 2s
> >   end select;
>
> > If abort to happen after *completion* of the rendezvous then the above
> > shall not deadlock. (I checked this under GNAT/Windows, it deadlocks
> > there.)
>
> Here the call to PID.Call is not queued, but is accepted immediately, and does
> not encounter an explicit requeue-with-abort.

Is that necessarily the case?  Since there aren't any priorities
specified, I don't think it's defined whether the body of the main
procedure (assuming it's a procedure) starts running first, or the
body of PID (assuming a single processor).  Which means that the entry
call could be queued.  Actually, on second thought, I think that for
some dispatching policies the main procedure *will* be executed first,
which means that the SELECT is executed before the body of PID starts,
which means the call *is* queued.  Of course, it will be accepted
"almost" immediately; but since the call is briefly queued, the
language of 9.7.4 means that the abortable part is started.  Then,
during "delay 2.0", PID is started, the call is accepted, but it
doesn't complete.  Then the delay finishes and the Signal occurs; an
attempt is made to cancel the entry call PID.Call, but that has no
effect since cancellation only works when the call is on a queue
(9.5.3(20)).  Anyway, as soon as the Signal occurs, the Wait
completes, then the entry call to PID.Call completes, and then
everything is done.  At least that's how I understand things, but I
could be wrong.

In any event, though, writing code like this has to be horrible since
you can't tell whether it will deadlock or not.

                             -- Adam

Re: Basic question about select

[Jeffrey R. Carter]

Adam Beneschan wrote:
> 
> Is that necessarily the case?  Since there aren't any priorities
> specified, I don't think it's defined whether the body of the main
> procedure (assuming it's a procedure) starts running first, or the
> body of PID (assuming a single processor).

That's a big assumption, especially today. From pretty cheap systems on up, 
almost everything has at least 2 processors these days. Certainly that's the 
case for the system on which I tested it, and found that it deadlocks as 
originally written, but doesn't if "delay 1.0;" is added to the task before the 
accept.

-- 
Jeff Carter
"From this day on, the official language of San Marcos will be Swedish."
Bananas
28

Re: Basic question about select

[Adam Beneschan]

On Apr 28, 9:25 pm, "Jeffrey R. Carter"
<spam.jrcarter....@spam.acm.org> wrote:
> Adam Beneschan wrote:
>
> > Is that necessarily the case?  Since there aren't any priorities
> > specified, I don't think it's defined whether the body of the main
> > procedure (assuming it's a procedure) starts running first, or the
> > body of PID (assuming a single processor).
>
> That's a big assumption, especially today. From pretty cheap systems on up,
> almost everything has at least 2 processors these days. Certainly that's the
> case for the system on which I tested it, and found that it deadlocks as
> originally written, but doesn't if "delay 1.0;" is added to the task before the
> accept.

Hmmm... I haven't studied the dispatching rules enough to know how
multiple processors affect things---that's why I assumed a single
processor, for simplicity.  If there are more than one, however, and
if the body of PID will get assigned to run on a different processor
than the main thread, then I'd think that makes things worse---you
can't tell at all whether the SELECT or the ACCEPT will occur first,
and there isn't any reason that it should work the same every time you
run it.  Again, I haven't thoroughly studied the new Ada 2005 language
dealing with dispatching, and I don't know what assumptions or
defaults GNAT uses, so perhaps there's some predictable reason why the
ACCEPT would occur first.

                           -- Adam

Re: Basic question about select

[Jeffrey R. Carter]

Adam Beneschan wrote:
> 
> Hmmm... I haven't studied the dispatching rules enough to know how
> multiple processors affect things---that's why I assumed a single
> processor, for simplicity.  If there are more than one, however, and
> if the body of PID will get assigned to run on a different processor
> than the main thread, then I'd think that makes things worse---you
> can't tell at all whether the SELECT or the ACCEPT will occur first,
> and there isn't any reason that it should work the same every time you
> run it.

Sure. They might happen at the same time.

That's the nature of concurrency. If you want things to happen in a specific 
order, you need to make them all part of the same task.

-- 
Jeff Carter
"Now look, Col. Batguano, if that really is your name."
Dr. Strangelove
31

Re: Basic question about select

[Jeffrey R. Carter]

Dmitry A. Kazakov wrote:
> 
> If abort to happen after *completion* of the rendezvous then the above
> shall not deadlock. (I checked this under GNAT/Windows, it deadlocks
> there.)

Under Linux/GNAT-gcc 4.3, this deadlocks as given, but does not if a "delay 
1.0;" is included in the task before the accept.

-- 
Jeff Carter
"From this day on, the official language of San Marcos will be Swedish."
Bananas
28

Re: Basic question about select

[Dmitry A. Kazakov]

On Wed, 28 Apr 2010 17:47:02 -0700, Jeffrey R. Carter wrote:

> Dmitry A. Kazakov wrote:
>> 
>> If abort to happen after *completion* of the rendezvous then the above
>> shall not deadlock. (I checked this under GNAT/Windows, it deadlocks
>> there.)
> 
> Under Linux/GNAT-gcc 4.3, this deadlocks as given, but does not if a "delay 
> 1.0;" is included in the task before the accept.

You are right.

Much implementation burden just in order to achieve a race condition!

Luckily ATC is a no-no in my coding standard anyway.

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