semantics question about SELECT statement

semantics question about SELECT statement

[cis.ohio-state.edu!zaphod.mps.ohio-state.edu!cs.utexas.edu!sun-barr!news2]

Hello Netters,

I have a question about guard evaluation in select statements.
Let us consider the piece of code below, excerpt from Ada Rationale,
section 13.2.11.

Let us assume this select is nested into a loop. Let us assume that at
some time all the guards of the select statement are opened, but no
rendez-vous is possible. Then, according to Reference Manual, section
9.7.1, the task waits on the open alternatives for a rendez-vous.

Let us assume now that two requests arrive at the same time but with
different priorities (e.g. URGENT and MEDIUM).

The question is: WHICH ONE OF THE TWO CLIENTS WILL BE SERVICED FIRST?
>From the Reference Manual, it seems to me that the clients **in that
case** are serviced in an arbitrary order (because the guards are not
reevaluated). 

It seems to me that the example below is OK only if the rendez-vous
are serviced in the textual order, i.e. the callers on the entry
REQUEST(URGENT) are serviced before the callers on the entry
REQUEST(MEDIUM), and so on, even when all the guards are opened and
several rendez-vous are possible on different entries.

Am I right, or am I missing something ?

----------------------------------------------------------------
   type LEVEL is (URGENT, MEDIUM, LOW);

   
   task CONTROL is
     entry REQUEST(LEVEL)(D :  DATA);
   end;
   
   task body CONTROL is
     ...
     select
       accept REQUEST(URGENT)(D :  DATA) do
         ...
       end;
     or when REQUEST(URGENT)'COUNT = 0 =>
       accept REQUEST(MEDIUM)(D :  DATA) do
         ...
       end;
     or when REQUEST(URGENT)'COUNT = 0
       and   REQUEST(MEDIUM)'COUNT = 0 =>
       accept REQUEST(LOW)(D :  DATA) do
         ...
       end;
     end select;
     ...
   end CONTROL;
----------------------------------------------------------------


--
Miguel ALABAU
Universite BORDEAUX I - LaBRI
351, cours de la Liberation   33405 TALENCE CEDEX (FRANCE)      
phone: (33) 56-84-69-35 / fax: (33) 56-84-66-69
e-mail: alabau@geocub.greco-prog.fr / alabau@labri.u-bordeaux.fr

Re: semantics question about SELECT statement (typos fixed)

[Alex Blakemore]

In article <1993Mar5.145221.23827@greco-prog.fr> alabau@geocub.greco-prog.fr writes:
> Let us assume now that two requests arrive at the same time but with
> different priorities (e.g. URGENT and MEDIUM).

most methods for reasoning about concurrent processes would say they
CANNOT arrive at exactly the same time, one must preceed the other.
there are other semantic foundations, but you can reason quite successfully
about concurrent processing under the "interleaving semantics" assumption where
you must consider all possible interleavings of concurrent events.

they both could arrive before the called task was eligible to run again,
which would have a similar effect.

> The question is: WHICH ONE OF THE TWO CLIENTS WILL BE SERVICED FIRST?
> From the Reference Manual, it seems to me that the clients **in that
> case** are serviced in an arbitrary order (because the guards are not
> reevaluated). 

if they called the same entry they would be served in FIFO order by Ada83 rules.
you are correct, if they call different open entries, the language
does not define the order.

>    type LEVEL is (URGENT, MEDIUM, LOW);
>    task CONTROL is
>      entry REQUEST(LEVEL)(D :  DATA);
>    end;
    
>    task body CONTROL is
>      select
>        accept REQUEST(URGENT)(D :  DATA) do
>          ...
>        end;
>      or when REQUEST(URGENT)'COUNT = 0 =>
>        accept REQUEST(MEDIUM)(D :  DATA) do
>          ...
>        end;
>      or when REQUEST(URGENT)'COUNT = 0
>        and   REQUEST(MEDIUM)'COUNT = 0 =>
>        accept REQUEST(LOW)(D :  DATA) do
>          ...
>        end;
>      end select;
>    end CONTROL;

> It seems to me that the example below [now above] is OK only if the rendez-vous
> are serviced in the textual order.

there are even worse problems with this example.
for example, consider the case where all entry queues are empty,
task control evaluates all guards and then blocks waiting for
calls to request(low) ONLY (the other guards evaluated to false)

then even if hundreds of high and medium level requests arrive,
not a single one will be served until a low level request arrives
and is served so that the guards can be reevaluated (after the
presumably missing loop around the select stmt is executed).

this is another example of 'count getting you in trouble 
(even without timed or conditional entries)

here's a version that avoids the problem.

      select
        -- check for urgent requests
        accept REQUEST(URGENT)(D :  DATA) do
          ...
        end;
      else
        -- no urgent requests, check for medium ones
        select
          accept REQUEST(URGENT)(D :  DATA) do -- could probably remove this one
            ...
          end;
        or 
          accept REQUEST(MEDIUM)(D :  DATA) do
            ...
          end;
        else
          -- no medium ones either, handle a low request if one is waiting
          -- or the first one that arrives of any priority
          select
            accept REQUEST(URGENT)(D :  DATA) do
              ...
            end;
          or 
            accept REQUEST(MEDIUM)(D :  DATA) do
              ...
            end;
          or
            accept REQUEST(LOW)(D :  DATA) do
            ...
            end;
          end select;
        end select;
      end select;
    end CONTROL;

I believe this guarantees that at most one lower priority request
can be served before a higher one after the arrival of the
higher priority request -- for example if a low priority task is
being served at the instant a higher one arrives, it will complete its
rendezvous but no more low priority requests will be served until
the high priority queue is empty.
Presumably, this is what you want.
-- 
---------------------------------------------------
Alex Blakemore alex@cs.umd.edu   NeXT mail accepted

Re: semantics question about SELECT statement

[Robert I. Eachus]

In article <1993Mar5.145221.23827@greco-prog.fr> alabau@labri.greco-prog.fr (Miguel ALABAU) writes:

  > From the Reference Manual, it seems to me that the clients **in that
  > case** are serviced in an arbitrary order (because the guards are not
  > reevaluated). 

  > It seems to me that the example below is OK only if the rendez-vous
  > are serviced in the textual order, i.e. the callers on the entry
  > REQUEST(URGENT) are serviced before the callers on the entry
  > REQUEST(MEDIUM), and so on, even when all the guards are opened and
  > several rendez-vous are possible on different entries.

  > Am I right, or am I missing something ?

    You are missing something.  What will happen is that one or the
other rendezvous attempt will occur first and that rendezvous will
immediately occur.  Even in a "true" multiprocessor environment there
will be some hardware mechanism used to serialize two attempts to
rendezvous with a single task, so in effect the hardware will
guarentee the rendezvous attempts do not occur simultaneously.

   Also, since the rendezvous occurs at the higher of the two
priorities of the tasks involved and one of those two tasks must be
running when it becomes possible to complete the rendezvous, the
rendezvous can always be completed immediately.  This is a very subtle
point, but is crucial to understanding the Ada tasking model--the
rendezvous always IMMEDIATELY follows the arrival of the second of the
two parties at the rendezvous.  So there are complex models for
determining which task should be accepted when the called task is not
the first to arrive, but when things happen in the other order only
one rendezvous is possible.
--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...