next up previous contents index
Next: Summary Up: The Rendezvous Previous: The Ada Rendezvous   Contents   Index


GNAT Implementation

Achieving rendezvous ordinarily requires that one of the two tasks wait until the other is ready. In the case that more than one task is waiting on the same entry of a task, Ada requires the calls be accepted in first-in-first-out order. An implementation must therefore maintain data structures to keep track of which tasks are waiting on entry calls, which entries they are calling, and in what order the calls on each entry of a task arrived [BR85, Section 6].

Entry Call and Parameters

GNAT associates a record to each entry call: the Entry Call Record3.1. It is used to group all the run-time information associated with the entry call. It includes the identifier of the called entry, the current state of the entry call, the links to the previous and next queued entry calls, etc.

The compiler generates one record with one field associated with each entry parameter: the Entry Parameters Record. The compiler also generates code which fills these fields with the address of the corresponding parameter. (In case of simple Ada types--Integer, Float, enumeration, etc.-- the compiler generates code which declares local variables, copies the real parameter in these variables and stores the address of these variables in the corresponding field of the Entry Parameters Record). The address of the Entry Parameters Record is then passed to the GNAT run-time. The run-time stores the address of the Entry Parameters Record in the Uninterpreted_Data3.2 field of the Entry Call Record.

As a summary, Figure [*] presents the GNAT run-time data structures used to handle an entry call to the entry E of the following task specification:

   task T is
      entry E (Number : in Integer; Text : in String);
   end T;

Figure 3.1: Entry Call.

Simple Mode Entry Call

Due to the similarity of the simple mode entry call and the procedure call, the compiler translates a simple mode entry call into a procedure call.

      P : Parms_Block := (Parm1, Parm2, ..., ParmN);
      GNARL.Call_Simple (Task_ID, Entry_ID, P'Address);
      [ Parm1 := P.Parm1; ]
      [ Parm2 := P.Parm2; ]
      [ ...               ]

P is an aggregate which saves the parameters (the Entry Parameters Record described in section [*]). The address of this aggregate is passed to the GNAT run-time, along with the identifiers of the called task and entry. The assignments after the call are present only in the case of in out or out parameters for elementary types, and are used to assign back the resulting values of such parameters. Let's see the actions performed by the run-time.

Conditional Entry Call

The efficient implementation of the conditional entry call requires to check if the called task is ready to accept the call. If the test fails, the GNAT run-time returns control immediately to the calling task. Otherwise, the actions are similar to those for the simple mode call [BR85]. The compiler translates the conditional entry call into the following code:

      P          : Parms_Block := (Parm1, Parm2, ..., ParmN);
      Successful : Boolean;
      GNARL.Task_Entry_Call (Task_ID,
      if Successful then
         [ Parm1 := P.Parm1; ]
         [ Parm2 := P.Parm2; ]
         [ ...               ]
         Statements; --  Statements after the entry call
         Statements; --  Statements in the "else" part
      end if;

In this case the code generated by the compiler calls the GNARL subprogram Task_Entry_Call3.9 with the same parameters of the simple mode entry call and one additional out mode parameter (Successful). If the entry call is immediately accepted this parameter is set to True by the run-time, and the statements after the entry call are executed. Otherwise, the statements in the else part are executed.

Entries and Queues

The GNAT compiler associates a positive number to each task entry: the Entry Identifier. This number corresponds with the position of the entry in the task type specification (starting with 1). Families of entries are handled like individual entries. For example, the following task has five entries: a single entry (Hello), a family of entries (Do_Work) and another single entry (Bye). Identifier 1 is assigned to Hello; identifiers 2 to 4 are assigned to the entry family Do_Work, and identifier 5 is assigned to Bye.

   task T is
      entry Hello (A : in Integer);
      --  Hello       Entry_Id = 1

      entry Do_Work(1..3) (B : in Integer);
      --  Do_Work (1) Entry_Id = 2
      --  Do_Work (2) Entry_Id = 3
      --  Do_Work (3) Entry_Id = 4
      entry Bye;
      --  Bye         Entry_Id = 5
   end T;

Each entry has one queue which stores all the pending entry calls. If the queue is nonempty, the next caller to be served is at the head of the queue. The GNARL implementation uses circular doubly linked lists so that checking, insertion and deletion are all constant-time operations.

The ATCB field Entry_Queues is an array indexed by the entry identifier. Each element of this array has two fields: the Head and the Tail of the queue.

Figure 3.2: Entry Queues.

Trivial Accept

The GNAT run-time classifies the Ada accept sentences into the following modes: Trivial (accept without parameters and without code which is used to synchronize Ada tasks), Simple (accept with parameters or code) and Selective (the Ada selective accept sentence). The trivial accept corresponds with the following Ada code:

   accept My_Entry;
The compiler translates this sentence into the following GNARL call:
   GNARL.Accept_Trivial (Entry_ID);

This GNARL procedure performs the following actions:

Accept Statement

When the accept has some code the GNAT run-time extracts the Entry Call Record from the entry queue and pushes it in an Accepted Entry Calls Stack. The top of this stack is referenced by the Call field of the acceptor's ATCB (cf. Figure [*]).The Entry Call Records in this stack are linked by means of the Acceptor_Prev_Call field. All the entry calls in this stack correspond to nested accept statements executed by the acceptor task.

Figure 3.3: Simple Accept.

The simple mode accept corresponds with the following Ada code:

   accept My_Entry ( . . . ) do
        << Entry_Body >>
   end My_Entry;
It is translated by the compiler to the following code:
      Params_Block_Address : Address;
      GNARL.Accept_Call (Entry_ID, Params_Block_Address);
      << Entry_Body >>
      when others =>
The local variable Params_Block_Address is used to store the address of the Entry Parameters Record. The user code is put by the compiler in middle of two calls to GNARL. The GNARL procedure Accept_Call carries out the following actions.

If no exception is raised during the execution of the user code the GNARL subprogram Complete_Rendezvous3.16 is called. This subprogram just calls Exceptional_Complete_Rendezvous notifying that no exception has been raised. If some exception is raised Exceptional_Complete_Rendezvous is called from the exception handler. This procedure performs the following actions.

Selective Accept

The special implementation problem introduced by the selective wait is that a task may at one instant be ready to accept a call on a set of several entries. From the viewpoint of the Ada run-time, this is really two problems, since it comes up in the processing of entry calls, as well as selective waits:

  1. Since a task may be waiting on more than one open accept alternative, processing an entry call requires checking whether the called entry corresponds to one of the open alternatives.

  2. Since there may be several open accept alternatives, processing the selective wait requires checking the set of pending entry calls against the set of open accept alternatives.

The need to be able to perform both of these operations efficiently strongly influences an implementation's choice of data structures. There are two obvious ways to perform the first operation, checking whether a called entry has a currently open accept alternative:

If the set of open accept alternatives is represented as a list, checking requires comparing the called entry against each of the entries in this list. We call this approach the use of an open entry list. It may be time consuming if there are many open entries.

An alternative is to use a vector representation for the set of open entries: the open accepts vector. This vector would have one component for each entry of the task. Each component would minimally indicate whether the corresponding entry is open.

Note that the accept vector or open entry list must be created at the time the selective wait statement is executed, once it is known which alternatives are open. The time needed to do this only depends on the number of alternatives in the selective wait statement.

With separate queues for each entry, it is necessary to check the queue corresponding to each open entry. This requires sequencing through the open entries. Alternatively, if the open entries are represented by an open entry list, this check can be performed more quickly, without looking at the non-open entries. This may be a good reason to keep both an open entry list and an accept vector, though this redundancy may cost more in overhead than it saves through faster execution of the check for pending calls.

GNAT uses the Open Accepts Vector. Each element of this vector has two fields: the entry identifier and a boolean which indicates if the accept statement has a null body. Each element of the accept vector corresponds to the accept alternatives of the select statement (in the same order; first element of the accept vector corresponds to the first alternative, second element corresponds to the second alternative, etc.). The entry identifier is set to 0 when the entry guard is closed. The reference to the accept vector is stored in the Open_Accepts ATCB field. For example, the following task has three entries ($P$, $Q$ and $R$). In the select statement the first two entries are open, but the third entry is closed. Additionally, the first and third entry have a null body.

   task T is
      entry P;  -- Entry Id = 1
      entry Q;  -- Entry Id = 2
      entry R;  -- Entry Id = 3
   end T;

   task body T is
         accept Q;
         accept P do
         end P;
         when False =>
         accept R;
      end select;
   end T;

Figure [*] has the corresponding Open Accepts Vector. The first accept alternative corresponds to the second entry (therefore, the Entry_Id field is set to ``2'') which is open and has a null body. The second alternative corresponds to the first entry, which is also open and has some user-defined code. Finally, the last alternative has the guarding condition closed and, therefore the Entry_Id in the Open Accepts Vector is set to ``0''.

Figure 3.4: Open Accepts Vector.

The GNAT compiler translates the selective accept to one scope where it declares three variables: the Open Accepts Vector, the Index of the selected alternative and the address of the Entry Parameters Record. Index value 0 is used by the run-time to indicate that the else alternative has been selected.

      Open_Accepts_Table   : GNARL.Open_Accepts_Table;
      Index                : Natural;
      Params_Block_Address : System.Address;
        (Open_Accepts_Table, GNARL.Select_Mode,
         Params_Block_Address, Index);
      case Index is
         when 0 =>
            --  else part
         when 1 =>
            --  user code of the first accept
         when 2 =>
            --  user code of the second accept
      end case;

The user code associated with each alternative is translated to local procedures. Below we have the general structure of these procedures.

   procedure Entry_Name is
      << User Code >>
      when others =>
   end Entry_Name;

The GNARL procedure Selective_Wait carries out the following actions:

The Count Attribute

The GNARL function Task_Count3.22 implements this attribute and returns the number of queued entry calls in the specified entry queue.


... Record3.1
... Check_Exception3.6
... Body3.8
... Head3.12
... Select_Task_Entry_Call3.19
... Setup_For_Rendezvous_With_Body3.20
... Make_Passive3.21

next up previous contents index
Next: Summary Up: The Rendezvous Previous: The Ada Rendezvous   Contents   Index
(c) Javier Miranda. Canary Islands (Spain), 2002. Version 1.0