next up previous contents index
Next: 15. The Rendezvous Up: IV. Fourth Part: Run-Time Previous: IV. Fourth Part: Run-Time   Contents   Index

Subsections


14. Tasking

Ada tasks semantics requires run-time support for storage allocation, task scheduling, and intertask communication. These functions are typically performed by the kernel of the operating system. Ada is so specific in its semantic requirements, however, that it is unlikely that a given existing operating system will make such services available in a form that can be directly used by the generated code. As a consequence, the compiler run-time must add routines that support Ada tasking semantics on top of OS primitives, or else provide a tasking kernel for applications that run on bare boards.

The GNAT run-time assumes that functionality equivalent to that of the POSIX threads library (pthreads) is available in the target system. The additional run-time information concerning each Ada task (task state, parent, activator, etc. [AAR95, Chapter 9]) is stored in a per-task record called the Ada Task Control Block (ATCB).


14.1 The Ada Task Control Block

The Ada Task Control Block (ATCB) is a discriminated record, whose discriminant is the number of task entries (a central component of the ATCB is the array of queues whose size is fixed by the discriminant). In order to support Ada95 task discriminants and some Ada task attributes, the front-end generates an additional record (described in detail in Section 9.4). When a task is created, the run-time generates a new ATCB and links the new ATCB with its corresponding high-level record and Threads Control Block (TCB) record in the POSIX level (cf. Figure 14.1). In addition, the GNAT run-time inserts the new ATCB in a linked list (All Tasks List). ATCBs are always inserted in LIFO order (as a stack). Therefore, the first ATCB in this list corresponds to the most recently created task.

Figure 14.1: Run-Time Information Associated with Each Task.
\begin{figure}\centerline{\psfig{figure=figures/tasks/02-atcb_tcb.eps,
width=13.0cm}}\end{figure}


14.2 Task States

GNAT considers four basic states over the lifetime of a task. The current state is indicated by the State ATCB field):

The sleep state is composed of the following sub-states:


14.3 Task Creation and Termination

According to Ada semantics, all tasks created by the elaboration of object declarations of a single declarative region (including subcomponents of declared objects) are activated together. Similarly, all tasks created by the evaluation of a single allocator are activated together [AAR95, Section 9.2(2)]. In addition, if an exception is raised in the elaboration of a declarative part, then any task T created during that elaboration becomes terminated and is never activated. As T itself cannot handle the exception, the language requires the parent (creator) task to deal with the situation: the predefined exception Tasking_Error is raised in the activating context.

In order to achieve this semantics, the GNAT run-time uses an auxiliary list: the Activation List. The front-end expands the object declaration by introducing a local variable in the current scope, that holds the activation list (cf. Sections 9.1 and 9.6), and splits the OS call to create the new thread into two separate calls to the GNAT run-time: (1) Create_Task, which creates and initializes the new ACTB, and inserts it into both the all-tasks and activation lists, and (2) Activate_Task, which traverses the activation list and activates the new threads.

With respect to task termination, the concept of a master [AAR95, Section 9.3] is fundamental to the semantics of the language. (cf. Section 9.2). Basically a master defines a scope at the end of which the run-time must wait for termination of dependent tasks, before finalization of other objects created on such a scope. To implement this behavior, the front-end generates calls to the run-time subprograms Enter_Master and Complete_Master at the beginning and termination of a master scope (or, in the case of tasks, via Create_Task and Complete_Task subprograms). ^oThe GNAT run-time associates one identifier to each master, and two master identifiers with each task: the master of its Parent (Master_Of_Task) and its internal master nesting level (Master_Within). The identification method of masters provides an ordering on them, so that a master that depends on another will always have associated an identifier higher than that of its own master.

Normally a task starts out with internal master nesting level one larger than external master nesting level. This value is incremented by Enter_Master, which is called if the task itself has dependent tasks. It is set to 1 for the environment task. The environment task is the operating system thread which initializes the run-time and executes the main Ada subprogram. Before calling the main procedure of the Ada program, the environment task elaborates all library units needed by the Ada main program. This elaboration causes library-level tasks to be created and activated before the main procedure starts execution. Master level 2 is reserved for server tasks of the run-time system (the so called "independent tasks"), and the level 3 is for the library level tasks.

Tasks created by an allocator do not necessarily depend on their activator, but rather on the master that created the access type; in such case the activator's termination may precede the termination of the newly created task [AAR95, Section 9.2(5a)]. Therefore, the master of a task created by the evaluation of an allocator is the declarative region which contains the access type definition. Tasks declared in library-level packages have the main program as their master. That is, the main program cannot terminate until all library-level tasks have terminated [BW98, Chapter 4.3.2]. Figure 14.2 summarizes the basic concepts used by the run-time for handling Ada task termination.

Figure 14.2: Definition of Parent, Activator, Master of Task and Master Within.
\begin{figure}\small\begin{center}
\begin{tabular}{\vert l\vert l\vert}
\hline
{...
...ng level of T's dependent tasks.\\
\hline
\end{tabular}\end{center}\end{figure}



Example

In order to understand these concepts better, let's apply them to the following example:

\begin{figure}\begin{lstlisting}{}
procedure P is
-- P: Parent = Environment Ta...
... end T3;
begin
null;
end T1;
begin
null;
end P;
\end{lstlisting}\end{figure}

Parent and activator do not coincide for T6 because the task is created by means of an allocator, and in this case the parent of the new task is the task where the access type is declared, while the activator is the task that executes the allocator. In all other cases above, parent and activator coincide.

The abort statement is intended for use in response to those error conditions where recovery by the errant task is deemed to be impossible. The language defines some operations in which abortion must be deferred [BW98, Section 10.2.1]. In addition, the execution of some critical points of the run-time must be also deferred to keep its state stable. For this purpose the GNAT run-time uses a pair of subprograms (Abort_Defer, Abort_Undefer) that are called by the code expanded by the front-end to bracket unabortable operations involving task termination, (cf. Section 9.5), rendezvous statements (cf. Chapter 10), and protected objects (cf. Chapter 11). The implementation of these primitives will be discussed in detail in Chapter 20.


14.4 Run-Time Subprograms for Task Creation and Termination

Section 9.6 discussed the sequence of calls to the run-time issued by the expanded code at the point of tasks creation and finalization. Figure 14.3 represents this sequence. Each rectangle represents a subprogram; the rhombus represents the new task.

Figure 14.3: GNARL Subprograms Called During the Task Life-Cycle
\begin{figure}\centerline{\psfig{figure=figures/tasks/03-Task_Steps.eps,
width=13.0cm}}\end{figure}

The whole sequence is as follows:

1.
 Enter_Master is called in the Ada scope where a task or an allocator designating objects containing tasks is declared.

2.
Create_Task is called to create the ATCBs of the new tasks and to insert them in the all tasks list and in the activation chain (see section 14.4.3).

3.
Activate_Tasks is called to create new threads and to associate them with the new ATCBs on the activation chain. When all the threads have been created the activator becomes blocked until they complete the elaboration of their declarative part.

The thread associated with the new task executes a task-wrapper procedure. This procedure has some locally declared objects that serve as per-task run-time local data. The task-wrapper calls the Task Body Procedure (the procedure generated by the compiler which has the task user code) which elaborates the declarations within the task declarative part, to set up the local environment in which it will later execute its sequence of statements. Note that if these declarations also have task objects, then there is a chained activation: this task becomes the activator of dependent task objects and cannot start the execution of its user code until all dependent tasks complete their own activation.

4.
Complete_Activation is called when the new thread completes the elaboration of all the task declarations, but before executing the first statetement in the task body. This call is used to signal to the activator that it need no longer wait for this task to finish activation. If this is the last task on the activation list to complete its activation, the activator becomes unblocked.

From here on the activator and the new tasks proceed concurrently and their execution is controlled by the POSIX scheduler. Afterward, any of them can terminate its execution and therefore the following two steps can be interchanged.

5.
Complete_Task is called when a task terminates its execution. This may happen as a result of reaching the end of its sequence of statements, or by other means, such as an exception or an abort statement (cf. Chapter 20). Even though a completed task cannot execute any more, it is not yet safe to deallocate its working storage at this point because some reference may still be made to the task. In particular, it is possible for other tasks to still attempt entry calls to a terminated task, to abort it, and to interrogate its status via the 'Terminated and 'Callable attributes. Nevertheless, completion of a task does requires action by the run-time. The task must be removed from any queues on which it may happen to be, and must be marked as completed. A check must be made for pending calls on entries of the completed task, and the exception Tasking_Error must be raised in any such calling tasks [BR85, Section 4].

6.
Complete_Master is called by the activator when it finishes the execution of its statements. At this point the activator waits until all its dependent tasks either complete their execution (and call Complete_Task) or are blocked in a Terminate alternative. Alive dependent tasks in a terminate alternative are then forced to terminate.

In general this is the earliest point at which it is completely safe to discard all storage associated with dependent tasks (because it is at this point that execution leaves the scope of the task's declaration, and it is no longer possible for any dependent task to be awakened again by a call).

In the following sections we give more a detailed description of the work done by the following run-time subprograms: Enter_Master, Create_Task, Activate_Tasks, Complete_Activation, Complete_Task, and Complete_Master, which implement the most important aspects of tasking.


14.4.1 GNARL.Enter_Master

Enter_Master increments the current value of Master_Within in the activator.


14.4.2 GNARL.Create_Task

Create_Task carries out the following actions:

1.
If no priority was specified for the new task then assign to it the base priority of the activator. When no priority is specified, the priority of a task is the priority at which it is created, that is, the priority of the activator at the point it calls Create_Task.

2.
Traverse the parents list of the activator to locate the parent of the new task via the master level (the Parent Master is lower than the master of the new task).

3.
Defer abortion.

4.
Request dynamic memory for the new ATCB (New_ATCB).

5.
Lock All_Tasks_List because this lock is used by Abort_Dependents and Abort_Tasks and, up to this point, it is possible for the new task is to be part of a family of tasks that is being aborted.

6.
Lock the Activator's ATCB.

7.
If the Activator has been aborted then unlock the previous locks (All_Tasks_Lists and its ATCB), undefer the abortion and raise the Abort_Signal internal exception.

8.
Initialize all the fields of the new ATCB: Callable set to True; Wait_Count, Alive_Count and Awake_Count set to 0 (cf. System.Tasking.Initialize_ATCB).

9.
Unlock the Activator's ATCB.

10.
Unlock All_Tasks_List.

11.
Add some data to the new ATCB to manage exceptions (cf. System.Soft_Links.Create_TSD).

12.
Insert the new ATCB in the activation chain.

13.
Initialize the structures associated with the task attributes.

14.
Undefer the abortion.

From this point the new task becomes callable. When the call to this run-time subprogram returns, the code generated by the compiler sets to True the variable which indicates that the task has been elaborated.


14.4.3 GNARL.Activate_Tasks

With respect to task activation the Ada Reference Manual says that all tasks created by the elaboration of object_declarations of a single declarative region (including subcomponents of the declared objects) are activated together. Similarly, all tasks created by the evaluation of a single allocator are activated together [AAR95, Section 9.2(2)].

GNAT uses an auxiliary list (the Activation List) to achieve this semantics. In a first stage all the ATCBs are created and inserted in the two lists (All Tasks and Activation lists); in a second stage the Activation List is traversed and new threads of control are created and associated with the new ATCBs. Although ATCBs are inserted in both lists in LIFO order all activated tasks synchronize on the activators lock before they start their activation in priority order. The activation chain is not preserved once all its tasks have been activated.

Activate_Tasks performs the following actions:

  1. Defer abortion.

  2. Lock All_Tasks_List to prevent activated tasks from racing ahead before we finish activating all tasks in the Activation Chain.

  3. Check that all task bodies have been elaborated. Raise Program_Error otherwise.

    For the activation of a task, the activator checks that the task_body is already elaborated. If two or more tasks are being activated together (see ARM 9.2), as the result of the elaboration of a declarative_part or the initialization of the object created by an allocator, this check is done for all of them before activating any.

    Reason: As specified by AI-00149, the check is done by the activator, rather than by the task itself. If it were done by the task itself, it would be turned into a Tasking_Error in the activator, and the other tasks would still be activated [AAR95, Section 3.11(12)].

  4. Reverse the activation chain so that tasks are activated in the order they were declared. This is not needed if priority-based scheduling is supported, since activated tasks synchronize on the activators lock before they start activating and so they should start activating in priority order.

  5. For all tasks in the activation chain do the following actions:

    1. Lock the task's parent.

    2. Lock the task ATCB.

    3. If the base priority of the new task is lower than the activator priority, raise its priority to the activator priority, because a task being activated inherits the active priority of its activator [AAR95, Section D.1(21)].

    4. Create a new thread by means of GNARL call (cf. Create_Task) and associates it to the task wrapper. If the creation of the new thread fails, release the locks and set the caller ATCB field Activation_Failed to True.

    5. Set the state of the new task to Runnable.

    6. Initialize the counters of the new task (Await_Count and Alive_Count set to 1)

    7. Increment the parent counters (Await_Count and Alive_Count).

    8. If the parent is completing the master associated with this new task, increment the number of tasks that the master must wait for (Wait_Count).

    9. Unlock the task ATCB.

    10. Unlock the task's parent.

  6. Lock the caller ATCB.

  7. Set the activator state to Activator Sleep

  8. Close the entries of the tasks that failed thread creation, and count those that have not finished activation.

  9. Poll priority change and wait for the activated tasks to complete activation. While the caller is blocked POSIX releases the caller lock.

    Once all of these activations are complete, if the activation of any of the tasks has failed (typically due to the propagation of an exception), Tasking_Error is raised in the activator, at the place at which it initiated the activations. Otherwise, the activator proceeds with its execution normally. Any tasks aborted prior to completing their activation are ignored when determining whether to raise Tasking_Error [AAR95, Section 9.2(5)].

  10. Set the activator state to Runnable.

  11. Unlock the caller ATCB.

  12. Remove the Activation Chain.

  13. Undefer the abortion.

  14. If some tasks activation failed then raise Program_Error. Tasking_Error is raised only once, even if two or more of the tasks being activated fail their activation [AAR95, Section 9.2(5b)].


14.4.4 GNARL.Tasks_Wrapper

The task-wrapper is a GNARL procedure that has some local objects that serve as per-task local data.


14.4.5 GNARL.Complete_Activation

Complete_Activation is called by each task when it completes the elaboration of its declarative part. It carries out the following actions:

  1. Defer the abortion.
  2. Lock the activator ATCB.
  3. Lock self ATCB.
  4. Remove dangling reference to the activator (since a task may outline its activator).
  5. If the activator is in the Activator_Sleep State then decrement Wait_Count in the activator. If this is the last task to complete the activation in the Activation Chain, wake up the activator so it can check if all tasks have been activated.

  6. Set the priority to the base priority value.
  7. Undefer the abortion.


14.4.6 GNARL.Complete_Task

The Complete_Task subprogram performs the following single action:

  1. Cancel queued entry calls.

From this point the task becomes not callable.


14.4.7 GNARL.Complete_Master

The run-time subprogram Complete_Master carries out the following actions:

  1. Traverse all ATCBs counting how many active dependent tasks does this master currently have (and terminate all the still unactivated tasks). Store this value in Wait_Count.

  2. Set the current state of the activator to Master_Completion_Sleep.

  3. Wait until dependent tasks are all terminated or ready to terminate.

  4. Set the current state of the activator to Runnable.

  5. Force those tasks on terminate alternatives to terminate (by aborting them).

  6. Count how many active dependent tasks does this master currently have. Store this value in Wait_Count.

  7. Set the current state of the activator to Master_Phase_2_Sleep_State.

  8. Wait for all counted tasks to terminate themselves.

  9. Set the current state of the activator to Runnable.

  10. Remove terminated tasks from the list of dependents and free their ATCB.

  11. Decrement Master_Within

14.5 Summary

In this chapter we have examined the basic data structures used by the GNAT run-time to support Ada tasks, the task states used by GNARL, some of the compiler-generated code that invokes run-time actions, and the subprograms called by this generated code. To summarize again:

  1. Each task has an associated Ada Task Control Block (ATCB).

  2. THe (All Tasks List) holds the ATCBs of all tasks in the program

  3. One auxiliary list is used to activate task objects created in the same Ada scope at the same time.

  4. A construct that declares tasks is a Master for these tasks. A task can itself be a Master. The presence of Masters determines all actions relating to task finalization.

  5. A task declaration is translated by the compiler into a limited record which is part of the ATCB; the Ada task body is translated into a procedure with intermixed calls to the RTS to manage the task body creation, activation, communication and finalization.

  6. The environment task is responsible for initialization of the RTS and the execution the main subprogram. As a consequence, the environment task is also the activator of all library-level tasks.


next up previous contents index
Next: 15. The Rendezvous Up: IV. Fourth Part: Run-Time Previous: IV. Fourth Part: Run-Time   Contents   Index
(C) Javier Miranda and Edmond Schonberg, 2004