The Rendezvous is the basic mechanism for synchronization and communication of Ada tasks. The model of Ada is based on a client/server model of interaction. One task, the server, declares a set of services that it is prepared to offer to other tasks (the clients). It does this by declaring one or more public entries in its task specification. A rendezvous is requested by one task making an entry call on an entry of another task. For the rendezvous to take place the called task must accept this entry call. During the rendezvous the calling task waits while the accepting task executes. When the accepting task ends the rendezvous both tasks are freed to continue their execution. 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. The run-time must 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.
A conditional entry call differs from an unconditional entry call in that the calling task need not wait unless the call can be accepted immediately. If the called task is ready to accept, execution proceeds as for an unconditional call. Otherwise, the calling task resumes execution without completion of a rendezvous. The syntax provides for execution to resume at different places, depending on whether any rendezvous took place. The efficient implementation of the conditional entry-call requires a simple test for whether the called task is ready to accept. This can be done in constant time if the run-time maintains an accept vector for each task, telling on which entries, if any, the task is ready to accept a call (See the expansion of this vector in Section 10.4.2). If the test fails, the run-time may return control immediately to the calling task. Otherwise, the actions are similar to those for the unconditional call.
The contents of this chapter are structured as follows: Section 15.1 presents the entry call record; Section 15.2 presents the implementation of the entry queues; Section 15.3 presents the stack required to give support to nested accept statements; Section 15.4 presents the run-time support for the selective accept statement. Finally, Section 15.5 describes the sequence of actions carried out by the GNARL subprograms that give support for entry-calls and for the accept-statements.
The GNAT run-time associates a record to each entry call: the
Entry Call Record. 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. If the entry has parameters, the front-end groups all the
parameters in a contiguous block
(cf. Section 10.2.1, and the run-time
saves the base address of this block in the Uninterpreted_Data
field of the Entry Call Record. Figure 15.1 presents the GNAT
run-time data structures used to handle an entry call to the entry
E of the following task specification:
An entry-call can be in one of the following states:
Each entry has one queue which stores all the pending entry calls [AAR95, Section 9.1(16)]. If the queue is nonempty, the next caller to be served is at the head of the queue. The cost of checking whether there are any calls queued for a given entry depends on the data structure chosen for the entry queues. The GNARL run-time 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 (the front-end associates an unique identifier to each entry queue, cf. Section 10.1). Each element of this array has two fields: the Head and the Tail of the queue (cf. Figure 15.2).
Because Ada allows the use of nested accept-statements, when an entry-call is accepted the GNAT run-time extracts the entry-call record from the corresponding entry-queue and pushes its address in an stack. The top of this stack is referenced by the Call field of the acceptor's ATCB (cf. Figure 15.3). The Acceptor_Prev_Call field links all the stack elements.
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 (cf. Section 10.4.2). 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 run-time returns 0 when the entry guard is closed.
Chapter 10 presents the expansion of the entry-call and accept statements. The following sections describe the actions carried out by the GNAT run-time subprograms called by the expanded code.
The run-time subprogram Call_Simple simply delegates the work to other run-time subprogram called Call_Synchronous.
The run-time subprogram Call_Synchronous carries out the following actions:
The subprogram Task_Do_Or_Queue carries out the following actions:
If the entry-call can be immediately accepted Task_Entry_Call carries out the same actions of the simple-mode entry-call and sets one out-mode parameter to True (Successful) to indicate this to the expanded code (cf. Section 10.2.2). Otherwise it sets this parameter to False. The expanded code uses this parameter to select the part of the user-code which must be executed after the call. Note that in the call is never enqueued; a conditional entry-call is only enqueued if the acceptor requeues it not-abortably (by means of a requeue-statement).
GNARL.Accept_Trivial performs the following actions:
The GNARL procedure Accept_Call carries out the following actions.
If no exception is raised during the execution of an accept body the subprogram Complete_Rendezvous is called is called by the expanded code. This subprogram just calls the subprogram Exceptional_Complete_Rendezvous notifying it that no exception was raised.
If an exception was raised during the execution of the code associated with the entry call, the exception must be also propagated on the caller and on the acceptor task [AAR95, Section 9.5.2]. For this purpose the subprogram Exceptional_Complete_Rendezvous carries out the following actions:
The GNARL subprogram Selective_Wait performs the following actions:
The function Task_Count gives support to the 'Count attribute. It returns the number of queued entry calls in the specified entry queue.
The Rendezvous is the basic mechanism for synchronization and communication of Ada tasks. In this chapter, the main aspects of the GNAT implementation have been described. In summary: