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].
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
the following task specification:
task T is entry E (Number : in Integer; Text : in String); end T;
Due to the similarity of the simple mode entry call and the procedure
call, the compiler translates a simple mode entry call into a
declare P : Parms_Block := (Parm1, Parm2, ..., ParmN); begin GNARL.Call_Simple (Task_ID, Entry_ID, P'Address); [ Parm1 := P.Parm1; ] [ Parm2 := P.Parm2; ] [ ... ] end;
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.
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:
declare P : Parms_Block := (Parm1, Parm2, ..., ParmN); Successful : Boolean; begin GNARL.Task_Entry_Call (Task_ID, Entry_ID, P'Address, Successful); if Successful then [ Parm1 := P.Parm1; ] [ Parm2 := P.Parm2; ] [ ... ] Statements; -- Statements after the entry call else Statements; -- Statements in the "else" part end if; end;
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.
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.
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
accept My_Entry;The compiler translates this sentence into the following GNARL call:
This GNARL procedure performs the following actions:
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.
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:
declare Params_Block_Address : Address; begin GNARL.Accept_Call (Entry_ID, Params_Block_Address); << Entry_Body >> GNARL.Complete_Rendezvous; exception when others => GNARL.Exceptional\_Complete\_Rendezvous; end;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.
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:
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:
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
ATCB field. For example, the following task has three entries (,
and ). 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 begin select accept Q; or accept P do ... end P; or 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''.
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.
declare Open_Accepts_Table : GNARL.Open_Accepts_Table; Index : Natural; Params_Block_Address : System.Address; begin GNARL.Selective_Wait (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; end;
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 begin GNARL.Undefer_Abortion; << User Code >> GNARL.Complete_Rendezvous; exception when others => GNARL.Exceptional_Complete_Rendezvous; end Entry_Name;
The GNARL procedure Selective_Wait carries out the following actions:
The GNARL function Task_Count3.22 implements this attribute and returns the number of queued entry calls in the specified entry queue.