LANGUAGE STUDY NOTE LSN-039-UI EVALUATION OF THE IMPLEMENTATION OF THE MULTI-WAY SELECT AND ASYNCHRONOUS TRANSFER OF CONTROL CONSTRUCTS TARTAN INC March 23, 1992 1 Introduction One of the tasks that Tartan is responsible for in the U/I demonstration program is the design of an implementation of the multi-way select statement and the asynchronous transfer of control structure. There are at least two approaches which can be taken to implement the asynchronous transfer of control construct and the multi-way select statement in Ada 9X. The first method will require a significant change to the runtime system. The second method has a high overhead associated with it which may not be worth the cost. The first method involves a redesign of the queue structures which are to be used to keep track of tasks waiting for a delay to expire or an entry to be accepted. The idea here is that a linked list will be maintained in the task's TCB which points to all of the queues on which the task is waiting. When one of the events which dequeues the task occurs, the runtime will be responsible for removing the task from all other queues in which it is currently waiting. In addition the runtime must mark the TCB for the task as currently executing in rendezvous with the acceptor or move the TCB to the appropriate "ready queue" (dispatch port) if a delay has expired. Simultaneously the runtime must abort the execution sequence of the "then abort" part of the asynchronous transfer of control. The alternative method is to have the task that is executing the asynchronous transfer of control or multi-way entry call to spawn child processes to wait on the appropriate queues. When any one of these task becomes 'runnable' this child task must abort its siblings. It must then inform its parent that the parent is to stop what it is doing and join the child. When the parent joins the child the child is aborted and the parent begins executing where the child was ready to begin. Our initial approach was to minimize the changes to our existing runtime system. We began to work out a solution using child processes. This led to a complex and awkward design. We decided to begin again with the new guideline that any component of the runtime system may be dramatically changed or redesigned to support these features. The result has been a complete redesign of the tasking and protected record subsystems of the runtime system. 2 Design Constraints 2.1 Queue Algorithms and Elements The first change occurred in the type of elements in the delay queue or entry queues. As we were working through the design using agent tasks we realized that runtime queues were now composed of heterogeneous elements. This is a result of the multi-way select statement, were a task may be waiting on several queues simultaneously. The management of queues with heterogeneous elements motivated us to reexamine our choice of using agent tasks. We decided to revise our approach. We converted our designs to use queue elements for all queuing within the runtime system. Hence, all of our queuing algorithms had to be modified to work with queue elements instead of task control blocks. Next, we investigated the effect of this decision on queue element storage management. On the target processors that have protected memory, the runtime system and its corresponding data structures are kept in the protected region. The entry queues, delay queues, queue elements and select headers are runtime data structures. These structures must be allocated and deallocated from the runtime storage area. In particular, the runtime system will allocate and deallocate queue elements as needed. This means that the runtime system will be responsible for the storage management of queue elements. The exception STORAGE_ERROR will be raised when the runtime system does not have sufficient resources to allocate a queue element. This introduces an interesting timing issue. Suppose that the queue elements used are initially allocated from the runtime heap. However, when these queue elements are deallocated they are put into a queue element pool instead of being returned to the heap. This means that the first allocations will come from the heap, but later allocations will come from the queue element pool. The result is different timing behaviors based upon when the queue element allocation occurs. Now one may suggest that the queue element pool be allocated at system start-up time. The problem here is two fold: a) if tasking and protected records are never used then there is no need to allocate the queue element pool; b) it may be difficult to know at system start-up time how large the queue element pool needs to be. This may lead to the need for heap allocation sometime later in the program execution. The compilation time allocation of queue elements and similar structures introduces a different interesting issue. The user may specify how much stack space should be allocated for each task in the system. The user must now allow for these data structures to be allocated from the task stack. In addition, runtime routines will be needed to initialize these structures. Similar storage management issues exist for task control blocks, protected record control blocks, and select headers. A task control block pool is allocated statically at link time. A protected record control block pool and a select header pool are created dynamically similar to the method used for queue elements. 2.2 Multi-Way Select Statement The next step was evaluate the various issues associated with implementing the multi-way select statement. These include select alternative guard evaluation, task entry call support, else-part resolution, and asynchronous transfer of control support. To determine which model to use with respect to the evaluation of select alternative guards, parameters, and expressions, we decided to keep as much of the existing runtime structure as possible. Hence, first we evaluate all of the alternative guards, constructing a list of those that are open (true). This open list will be used when sequencing through the alternatives looking for a call that is immediately accepted. Since an entry alternative in a multi-way select statement can be a task entry call or a protected entry call, the existing code for task entry calls must be modified to check for calls that are associated with a multi-way select -2- statement. This means that prior to a rendezvous the accepting task must determine if the call has been generated from a multi-way select statement. If so, the appropriate actions must be taken including: checking the select header to determine if this is the first entry call to be accepted, adjusting the select header when necessary to indicate that one of the select alternatives has been selected; canceling all other pending entry calls including protected entry dequeuing; initiating the abortion of the abortable final part when appropriate. Similarly, the protected entry code must include the multi-way select statement test and associated clean-up activities. Note that these tests will be part of the rendezvous and protected entry code regardless of whether the multi-way select statement is actually used. The addition of the else-part generates more design decisions. A major issue here is whether or not the queue element associated with a pending entry call is actually placed into the corresponding entry queue. If none of the entry calls can execute immediately, the else part is to be executed. By eliminating the entry queuing operation when there is an else-part, the else-part can begin execution without any dequeuing. If this model is chosen, the interface to the entry call code will include a flag that indicates whether this call is a branch in a select statement containing an else-part. The protected entry call code will then check this flag whenever the barrier evaluates to false to determine if the caller should be enqueued. Similarly, the task entry call will need to check this flag if the called task is not ready to accept the call. Note that these tests will become part of the entry call code regardless of whether the user ever uses a multi-way select statement. The alternative is to queue each entry call and then select the else-part. In this case, each pending entry call must be canceled prior to the execution of the else-part. The queue elements must be removed from the corresponding entry queue. Each dequeue from a protected entry queue is a protected operation, hence the protected record lock must be obtained (if one is used), the queue element dequeued, and some form of epilogue code must be executed prior to releasing the lock. This procedure must occur for each pending entry call prior to starting the execution of the else part. We believe that our users will be more willing to pay the price associated with not queuing an entry call when an else part exists. So, this is the mechanism that we will use. 2.3 Asynchronous Transfer of Control The primary issues here are determining where, when and what checks for abortion are needed. Additionally, what internal support is needed to make these checks. The task control block will be modified to include a field that indicates whether the task is suspendable and/or abortable, a field that contains the number of nested abortable regions (then-abort parts) that the task encounters, and a field to indicate the level to which an abort is effective. This information will be used to manage the abortion of either a sequence of statements or a complete task. The select header for each multi-way select statement will also need to include a field for the nested abortable regions. - 3 - The prologue and epilogue code for all protected operations will need to include support for asynchronous transfer of control and deferring abortion. The prologue will modify the TCB's suspendable/abortable field to indicate that a new protected region has been entered. The epilogue code will need to modify the TCB's suspendable/abortable field to indicate that a protected region has been exited. Additionally, the epilogue code will need to examine this field to determine if any deferred abortion can be serviced. If so, further action needs to be taken to determine if any deferred aborts need to be handled. The epilogue will initiate abortion including self-abortion. The suspendable/abortable field will also be modified when a task executes an accept statement and when a task enters and exits its finalization code. These checks will be done even if an asynchronous transfer of control statement is not used throughout the entire system. They are required to support the requeue with abort structure as well as the asynchronous transfer of control structure. When the execution of a task enters an abortable region it updates the nested abortable region field in the TCB and in the appropriate select header. Execution continues until one of the select-alternatives initiates the abortion of this sequence of statements or the sequence of statements completes. In the later case, all of the pending calls associated with the multi-way select must be canceled including delays. This includes dequeuing and deallocating all of the queue elements. Additionally, the select header will be deallocated. The TCB nested abortable region field will be adjusted to indicate that an abortable region has been exited. Some concern has also been raised about the impact of asynchronous transfer of control on the code generated by the compiler. In Ada-83, it is the case that a task context is left asynchronously either to be resumed (e.g., time-sliced scheduling) or never to be returned to (abort). With asynchronous transfer of control, code generation must be resilient to an asynchronous transfer of control within the same task context at any time. This means that the code generation protocol must not contain situations where an asynchronous transfer of control can corrupt the task context. Otherwise, the code generation protocol will disable asynchronous transfer of control for the duration of any temporary inconsistency. An example would be a temporarily "incorrect" stack pointer that is set to a correct value shortly thereafter (this is an implementation alternative to handle unconstrained function results). Another would be a temporary use of task-wide heap storage to be deallocated soon after its allocation. There is a fairly heavy cost associated with ascertaining that the code generation protocol does not contain any such situations, and, if it does, to eliminate them. 2.4 Delay Expiration The Ada 83 support for delay expiration only needs to be concerned with whether the delay has expired for a task that is executing a timed-entry call. With the introduction of the multi-way select statement and the asynchronous - 4 - transfer of control construct the complexity of the support for delay expiration increases. a check must be made to determine if the delay has expired for a task that is executing a multi-way select statement. does the multi-way select have an asynchronous part, and if so, can that part be terminated at this time? 3 cost of implementation 3.1 runtime system maturity a large amount of time and effort has been expended developing a runtime system that provides the necessary services efficiently. for example, one of the features of the current tartan runtime system is a rendezvous accelerator. under certain conditions, the time to execute a rendezvous can be reduced to one third. with the proposed changes to the runtime system, features like the rendezvous accelerator must be redesigned. until the necessary tuning of the 9x runtime is done, the state of the tasking subsystem will be similar to the 1983 version with addition of the protected record support system. 3.2 distributed overhead for every 9x feature that is incorporated into the runtime system, there are several additional tests that need to be made in the protected operation prologue and/or epilogue code and in several of the tasking operations. one or two little tests may be acceptable to some of our users, however, the number of tests introduced is not small and is not isolated to the introduced features. 3.3 non-deterministic time the selection of an accept alternative or an else part may require the cancellation of other entry calls. if it is a protected entry call, the corresponding queue element is to be removed from the protected entry queue. this is a protected operation and has protected epilogue associated with it. this may result in the dequeuing of all of the waiting callers, the number of these may be non-deterministic. 3.4 non-deterministic space the nesting of multi-way select statements together with the dynamic behavior of the entry calls leads to non-deterministic space requirements. 3.5 compilation costs the asynchronous transfer of control feature introduces complexity and cost in generating code. code generation must be resilient to an asynchronous transfer of control within the same task context at any time. this means that the code generation protocol must not contain situations where an asynchronous transfer of control can corrupt the task context. otherwise, it will disable asynchronous transfer of control for the duration of any temporary inconsistency. there is a fairly heavy cost associated with ascertaining that the code generation protocol does not contain any such situations, and, if it does, to eliminate them. - 5 - 3.6 hard real-time versus soft real-time the overhead associated with the structures examined here may be acceptable to a large portion of the soft real-time community. this group may be willing to pay the time and space costs for these expressive and portable solutions. however, the hard real-time community will not be in favor of the costs associated with these structures. hence, these features will not be used and the current special purpose capabilities provided by various vendors will continue to be used. - 6 -