next up previous contents index
Next: Summary Up: Task Types and Objects Previous: Ada Tasks   Contents   Index

Subsections


GNAT Implementation

Although the GNAT run-time reuses most of the support provided by the low level Pthreads library, it needs to handle some additional information to provide the full Ada semantics: state of the Ada task (according to the Ada semantics), parent, activator, etc. This information is stored by the run-time in a per-task register called Ada Task Control Block (ATCB)2.1. In addition, some task specific information is also required to store the task discriminants (the task parameters). The compiler generates code which creates another register for such information. The ATCB is linked with this register and with the corresponding Threads Control Block (TCB) in the POSIX level (cf. Figure [*]).

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

When a task is created, the run-time dynamically generates a new ATCB and inserts it in a list (All Tasks List2.2). ATCBs are always inserted in LIFO order (as a stack). Therefore, the first ATCB in this list corresponds to the most recently created task.


GNAT Task States

GNAT considers four basic states during task life (indicated by the State ATCB field):

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

GNAT Masters Implementation

The master is a construct used to finalize local objects, including tasks (see section [*]). Each master handles the termination of an Ada scope to ensure the Ada tasks termination semantics (all dependent tasks must terminate before its master performs finalization on other objects that it created). It is associated with the scope being executed by the Parent when the task was created. The run-time is only concerned with masters for purposes of task termination.

GNAT associates one identifier to each master, and two values are associated with each task: the master of its Parent (Master_Of_Task) and its internal master nesting level (Master_Within).

Tasks created by an allocator do not necessarily depend on its activator; 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 can not terminate until all library-level tasks have terminated [BW98, chapter 4.3.2]. Given a task T, table [*] presents a summary of the basic concepts used by the run-time for handling Ada task termination.

Figure 2.3: Definition of Parent, Activator, Master of Task and Master Within.
\begin{figure}\small\begin{center}
\begin{tabular}{\vert l\vert l\vert}
\hline
{...
...ting level of T 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.


procedure P is     --  P:  Parent = Environment Task;
                   --      Activator = Environment
                   --      Master_Of_Task = 1; Master_Within = 2;

   task T1;                  --  T1: Parent = P; Activator = P
                             --      Master_Of_Task = 2; Master_Within = 3;
   task body T1 is

      task type TT;
      task body TT is
      begin
         null;
      end TT;

      type TTA is access TT;
      T2 : TT;               --  T2: Parent = T1; Activator = T1
                             --      Master_Of_Task = 3; Master_Within = 4;

      task T3;               --  T3: Parent = T1; Activator = T1
                             --      Master_Of_Task = 3; Master_Within = 4;
      task body T3 is
         task T4;            --  T4: Parent = T3; Activator = T3
                             --      Master_Of_Task = 4; Master_Within = 5;
         task body T4 is
         begin
            null;
         end T4;
         T5 : TT;            --  T5: Parent = T3; Activator = T3
                             --      Master_Of_Task = 4; Master_Within = 5;
         T6 : TTA := new TT; --  T6: Parent = T1; Activator = T3
                             --      Master_Of_Task = 2; Master_Within = 3;
      begin
         null;
      end T3;

   begin
     null;
   end T1;

begin
   null;
end P;

Parent and activator do not coincide in T6 because the task is created by means of an Ada allocator (an Ada expression in the form 'new ...'). In this case the parent of the new task is the task where the type is declared and the activator is the task which executes the allocator. In the other cases, parent and activator coincide.


Compiler Task Translation

In order to understand the run-time behavior we first present the task translation done by the compiler.



Task Specification

The Ada task type is translated by the compiler into a limited record with the same discriminants. For example, the following task specification:

   task type T_Task (Discriminant : DType) is
      ...
   end T_Task;
...is translated by the compiler into the following code:
   T_TaskE : aliased Boolean := False;
   T_TaskZ : Size_Type       := [ Unspecified_Size |
                               Size_Type (Size_Expression) ];
   type T_TaskV [ (Discriminant : DType) ] is
        limited record
           _Task_Id : System.Tasking.Task_Id;
           [ Entry_Family : array (Bounds) of Void; ]
           [ _Priority    : Integer        := Priority_Expression;    ]

           [ _Size        : Size_Type      := Size_Expression;        ]
           [ _Task_Info   : Task_Info_Type := Task_Info_Expression;   ]
           [ _Task_Name   : Task_Image_Type : new String'(Task_Name); ]
        end record;

The optional code (the code that it is not always generated by the compiler) has been put between square brackets ([...]). First, a boolean flag E is declared and initialized to false. It is set to True when the body of the task is elaborated. The Z variable holds the task stack size (either the default value, unspecified_size, or the value set by a pragma Storage_Size). Next the task type is translated by the compiler into a limited record V with Discriminants present only if the corresponding task type has discriminants. The first field contains the Task_ID2.3 value (an access to the corresponding ATCB). One Entry_Family component is present for each entry family in the task definition. The bounds correspond to the bounds of the entry family (which may depend on discriminants). Since the run-time only needs such information for determining the entry index the element type is void. The next three fields are present only if the corresponding pragma is present in the task definition: the Size field corresponds to Storage_Size pragma; Task_Info corresponds to Task_Info pragma, and Task_Name corresponds to Task_Name pragma. A reference to this record is stored in the Task_Arg2.4 ATCB field (cf. Figure [*]). This reference is used by the thread associated with the task to find the task discriminants.

Figure 2.4: Compiler-Generated Information Associated with Each Task.
\begin{figure}\centerline{\psfig{figure=figures/02-Tasks/02-atcb_tcb.eps,
width=14.0cm}}\end{figure}



Task body

The run-time needs an access to subprogram to call the task user code. Therefore the compiler translates the task body into a procedure. For example, the following task body:

   task body T_Task is
      <Declarations>
   begin
      <Statements>
   end T_Task;
...is translated by the compiler into the following code:
  1: procedure T_TaskB (_Task : access T_TaskV) is
  2:   Discriminant : Dtype renames _Task.Discriminant;
  3:
  4:   procedure _Clean is
  5:   begin
  6:      Abort_Defer;
  7:      GNARL.Complete_Task;
  8:      Abort_Undefer;
  9:   end _Clean;
 10:
 11:  begin
 12:     Abort_Undefer;
 13:     <Declarations>
 14:     [ Activate_Tasks ]
 15:     GNARL.Complete_Activation;
 16:     <Statements>
 17:  at end
 18:     _Clean;
 19:  end T_TaskB;

The call to Activate_Tasks2.5 (line 14) is only generated if the task body is an activator. The at end handler is a single point of task finalization that is called even in the presence of exceptions or task abortion [BG94, section 6.9.5].

Run-Time Subprograms for Task Creation and Termination

Figure [*] presents the sequence of calls to the run-time issued by the compiler generated code during the creation and finalization of a task. Each rectangle represents a subprogram.

Figure 2.5: GNARL Subprograms Called During the Task Life-Cycle
\begin{figure}\centerline{\psfig{figure=figures/02-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 the task or access type designating objects containing tasks is declared.

2.
Create_Task is called to create the ATCBs of the new tasks and to insert it in the all tasks list and in the activation chain (see section [*]).

3.
Activate_Tasks is called to create new threads and to associate them to the new ATCB (the ATCBs in 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, setting up the local environment in which it will later execute its sequence of statements. (In general the compiler must generate code for the elaboration of Ada declarations.) 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 can not start the execution of its user code until all dependent tasks complete their activation.

4.
Complete_Activation is called when the new thread completes the elaboration of all the task declarations, but before executing the first task body sentence. 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 which completes its activation, the activator becomes unblocked.

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

5.
Complete_Task is called when the task terminates its execution. 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 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 this scope. 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 forced to terminate.

In general this is the earliest point at which it is completely safe to discard all storage associated with its dependent tasks (because it is at this point that execution leaves the scope of the task's type declaration). This is so because reference to a task may be passed far from its point of creation, as via task access variables and functions returning task values [BR85, Section 4].

In the following sections we make 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.

1. Enter Master

Enter_Master2.6 just increments the current value of Master_Within in the activator.


2. Create Task

Create_Task2.7 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.

The priority of a task where no priority is specified is the priority at which it was created, that is, the activator priority at the time that it calls Create_Task [BG94, section 6.7.5]

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

3.
Defer the abortion.

4.
Request dynamic memory for the new ATCB2.8.

5.
Lock All_Tasks_List because this lock is used by Abort_Dependents and Abort_Tasks and, up to this point, it is possible that the new task is 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 ATCB2.9 (Callable set to True; Wait_Count, Alive_Count and Awake_Count set to 0).

9.
Unlock the Activator's ATCB.

10.
Unlock All_Tasks_List.

11.
Add some data to the new ATCB to manage exceptions2.10.

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 executes a sentence which sets to True the variable which reminds that the task has been elaborated (described in section [*]).


3. Activate Tasks

With respect to the tasks 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 (as a stack) all activated tasks synchronize on the activators lock before they start their activation in priority order. The activation chain is not outstanding when all its tasks have been activated.

Activate_Tasks2.11 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 for 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 the 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 GNULL call2.12 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 (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 task 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)].


4. Complete Activation

Complete_Activation2.13 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.


5. Complete Task

The Complete_Task2.14 subprogram performs the following single action:

  1. Cancel queued entry calls.

From this point the task becomes not callable.


6. Complete Master

The run-time subprogram Complete_Master2.15 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



Footnotes

... (ATCB)2.1
System.Tasking.Ada_Task_Control_Block
... List2.2
System.Tasking.All_Tasks_List
...Task_ID2.3
System.Tasking.Task_ID
...Task_Arg2.4
System.Tasking.Task_Arg
...Activate_Tasks2.5
System.Tasking.Stages.Activate_Tasks
...Enter\_Master2.6
System.Tasking.Stages.Enter_Master
...Create\_Task2.7
System.Tasking.Stages.Create_Task
... ATCB2.8
System.Task_Primitives.Operations.New_ATCB
... ATCB2.9
System.Tasking.Initialize_ATCB
... exceptions2.10
System.Soft_Links.Create_TSD
...Activate\_Tasks2.11
System.Tasking.Stages.Activate_Tasks
... call2.12
System.Task_Primitives.Operations.Create_Task
...Complete\_Activation2.13
System.Tasking.Stages.Complete_Activation
...Complete\_Task2.14
System.Tasking.Stages.Complete_Task.
...Complete\_Master2.15
System.Tasking.Stages.Complete_Master

next up previous contents index
Next: Summary Up: Task Types and Objects Previous: Ada Tasks   Contents   Index
(c) Javier Miranda. Canary Islands (Spain), 2002. Version 1.0