Ada Programming/Tasking

Tasks edit

A task unit is a program unit that is obeyed concurrently with the rest of an Ada program. The corresponding activity, a new locus of control, is called a task in Ada terminology, and is similar to a thread, for example in Java Threads. The execution of the main program is also a task, the anonymous environment task. A task unit has both a declaration and a body, which is mandatory. A task body may be compiled separately as a subunit, but a task may not be a library unit, nor may it be generic. Every task depends on a master, which is the immediately surrounding declarative region - a block, a subprogram, another task, or a package. The execution of a master does not complete until all its dependent tasks have terminated. The environment task is the master of all other tasks; it terminates only when all other tasks have terminated.

Task units are similar to packages in that a task declaration defines entities exported from the task, whereas its body contains local declarations and statements of the task.

A single task is declared as follows:

  task Single is
     declarations of exported identifiers
  end Single;
  ...
  task body Single is
     local declarations and statements
  end Single;

A task declaration can be simplified, if nothing is exported, thus:

  task No_Exports;

Ex. 1

  procedure Housekeeping is
  
     task Check_CPU;
     task Backup_Disk;
  
     task body Check_CPU is
        ...
     end Check_CPU;
  
     task body Backup_Disk is
        ...
     end Backup_Disk;
     -- the two tasks are automatically created and begin execution
  begin -- Housekeeping
     null;
     -- Housekeeping waits here for them to terminate
  end Housekeeping;

It is possible to declare task types, thus allowing task units to be created dynamically, and incorporated in data structures:

  task type T is
     ...
  end T;
  ...
  Task_1, Task_2 : T;
  ...
  task body T is
     ...
  end T;

Task types are limited, i.e. they are restricted in the same way as limited types, so assignment and comparison are not allowed.

Rendezvous edit

The only entities that a task may export are entries. An entry looks much like a procedure. It has an identifier and may have in, out or in out parameters. Ada supports communication from task to task by means of the entry call. Information passes between tasks through the actual parameters of the entry call. We can encapsulate data structures within tasks and operate on them by means of entry calls, in a way analogous to the use of packages for encapsulating variables. The main difference is that an entry is executed by the called task, not the calling task, which is suspended until the call completes. If the called task is not ready to service a call on an entry, the calling task waits in a (FIFO) queue associated with the entry. This interaction between calling task and called task is known as a rendezvous. The calling task requests rendezvous with a specific named task by calling one of its entries. A task accepts rendezvous with any caller of a specific entry by executing an accept statement for the entry. If no caller is waiting, it is held up. Thus entry call and accept statement behave symmetrically. (To be honest, optimized object code may reduce the number of context switches below the number implied by this poor description.)

There is, however, a big difference between a procedure and an entry. A procedure has exactly one body that is executed when called. There is no such relation between an entry and a corresponding accept statement. An entry may have more than one accept statement, and the code executed may be different each time. In fact, there even need not be an accept statement at all. (Calling such an entry leads to deadlock of the caller if not timed, of course.)

Ex. 2 The following task type implements a single-slot buffer, i.e. an encapsulated variable that can have values inserted and removed in strict alternation. Note that the buffer task has no need of state variables to implement the buffer protocol: the alternation of insertion and removal operations is directly enforced by the control structure in the body of Encapsulated_Buffer_Task_Type which is, as is typical, a loop.

  task type Encapsulated_Buffer_Task_Type is
     entry Insert (An_Item : in  Item);
     entry Remove (An_Item : out Item);
  end Encapsulated_Buffer_Task_Type;
  ...
  Buffer_Pool : array (0 .. 15) of Encapsulated_Buffer_Task_Type;
  This_Item   : Item;
  ...
  task body Encapsulated_Buffer_Task_Type is
     Datum : Item;
  begin
     loop
        accept Insert (An_Item : in  Item) do
           Datum := An_Item;
        end Insert;
        accept Remove (An_Item : out Item) do
           An_Item := Datum;
        end Remove;
     end loop;
  end Encapsulated_Buffer_Task_Type;
  ...
  Buffer_Pool(1).Remove (This_Item);
  Buffer_Pool(2).Insert (This_Item);

Selective Wait edit

To avoid being held up when it could be doing productive work, a server task often needs the freedom to accept a call on any one of a number of alternative entries. It does this by means of the selective wait statement, which allows a task to wait for a call on any of two or more entries.

If only one of the alternatives in a selective wait statement has a pending entry call, then that one is accepted. If two or more alternatives have calls pending, the implementation is free to accept any one of them. For example, it could choose one at random. This introduces bounded non-determinism into the program. A sound Ada program should not depend on a particular method being used to choose between pending entry calls. (However, there are facilities to influence the method used, when that is necessary.)

Ex. 3

  task type Encapsulated_Variable_Task_Type is
     entry Store (An_Item : in  Item);
     entry Fetch (An_Item : out Item);
  end Encapsulated_Variable_Task_Type;
  ...
  task body Encapsulated_Variable_Task_Type is
     Datum : Item;
  begin
     accept Store (An_Item : in Item) do
        Datum := An_Item;
     end Store;
     loop
        select   
           accept Store (An_Item : in Item) do
              Datum := An_Item;
           end Store;
        or
           accept Fetch (An_Item : out Item) do
              An_Item := Datum;
           end Fetch;
        end select;
     end loop;
  end Encapsulated_Variable_Task_Type;

  x, y : Encapsulated_Variable_Task_Type;

creates two variables of type Encapsulated_Variable_Task_Type. They can be used thus:

  it : Item;
  ...
  x.Store(Some_Expression);
  ...
  x.Fetch (it);
  y.Store (it);

Again, note that the control structure of the body ensures that an Encapsulated_Variable_Task_Type must be given an initial value by a first Store operation before any Fetch operation can be accepted.

Guards edit

Depending on circumstances, a server task may not be able to accept calls for some of the entries that have accept alternatives in a selective wait statement. The acceptance of any alternative can be made conditional by using a guard, which is Boolean precondition for acceptance. This makes it easy to write monitor-like server tasks, with no need for an explicit signaling mechanism, nor for mutual exclusion. An alternative with a True guard is said to be open. It is an error if no alternative is open when the selective wait statement is executed, and this raises the Program_Error exception.

Ex. 4

  task Cyclic_Buffer_Task_Type is
     entry Insert (An_Item : in  Item);
     entry Remove (An_Item : out Item);
  end Cyclic_Buffer_Task_Type;
  ...
  task body Cyclic_Buffer_Task_Type is
     Q_Size : constant := 100;
     subtype Q_Range is Positive range 1 .. Q_Size;
     Length : Natural range 0 .. Q_Size := 0;
     Head, Tail : Q_Range := 1;
     Data : array (Q_Range) of Item;
  begin
     loop
        select
           when Length < Q_Size =>
              accept Insert (An_Item : in  Item) do
                 Data(Tail) := An_Item;
              end Insert;
              Tail := Tail mod Q_Size + 1;
              Length := Length + 1;
        or
           when Length > 0 =>
              accept Remove (An_Item : out Item) do
                 An_Item := Data(Head);
              end Remove;
              Head := Head mod Q_Size + 1;
              Length := Length - 1;
        end select;
     end loop;
  end Cyclic_Buffer_Task_Type;

Protected types edit

Tasks allow for encapsulation and safe usage of variable data without the need for any explicit mutual exclusion and signaling mechanisms. Ex. 4 shows how easy it is to write server tasks that safely manage locally-declared data on behalf of multiple clients. There is no need for mutual exclusion of access to the managed data, because it is never accessed concurrently. However, the overhead of creating a task merely to serve up some data may be excessive. For such applications, Ada 95 provides protected modules, based on the well-known computer science concept of a monitor. A protected module encapsulates a data structure and exports subprograms that operate on it under automatic mutual exclusion. It also provides automatic, implicit signaling of conditions between client tasks. Again, a protected module can be either a single protected object or a protected type, allowing many protected objects to be created.

A protected module can export only procedures, functions and entries, and its body may contain only the bodies of procedures, functions and entries. The protected data is declared after private in its specification, but is accessible only within the protected module's body. Protected procedures and entries may read and/or write its encapsulated data, and automatically exclude each other. Protected functions may only read the encapsulated data, so that multiple protected function calls can be concurrently executed in the same protected object, with complete safety; but protected procedure calls and entry calls exclude protected function calls, and vice versa. Exported entries and subprograms of a protected object are executed by its calling task, as a protected object has no independent locus of control. (To be honest, optimized object code may reduce the number of context switches below the number implied by this naive description.)

Similar to a task entry which optionally has a guard, a protected entry must have a barrier to control admission. This provides automatic signaling, and ensures that when a protected entry call is accepted, its barrier condition is True, so that a barrier provides a reliable precondition for the entry body. A barrier can statically be true, then the entry is always open.

Ex. 5 The following is a simple protected type analogous to the Encapsulated_Buffer task in Ex. 2.

  protected type Protected_Buffer_Type is
     entry Insert (An_Item : in  Item);
     entry Remove (An_Item : out Item);
  private
     Buffer : Item;
     Empty  : Boolean := True;
  end Protected_Buffer_Type;
  ...
  protected body Protected_Buffer_Type is
     entry Insert (An_Item : in  Item)
        when Empty is
     begin
        Buffer := An_Item;
        Empty := False;
     end Insert;
     entry Remove (An_Item : out Item)
        when not Empty is
     begin
        An_Item := Buffer;
        Empty := True;
     end Remove;
  end Protected_Buffer_Type;

Note how the barriers, using the state variable Empty, ensure that messages are alternately inserted and removed, and that no attempt can be made to take data from an empty buffer. All this is achieved without explicit signaling or mutual exclusion constructs, whether in the calling task or in the protected type itself.

The notation for calling a protected entry or procedure is exactly the same as that for calling a task entry. This makes it easy to replace one implementation of the abstract type by the other, the calling code being unaffected.

Ex. 6 The following task type implements Dijkstra's semaphore ADT, with FIFO scheduling of resumed processes. The algorithm will accept calls to both Wait and Signal, so long as the semaphore invariant would not be violated. When that circumstance approaches, calls to Wait are ignored for the time being.

  task type Semaphore_Task_Type is
     entry Initialize (N : in Natural);
     entry Wait;
     entry Signal;
  end Semaphore_Task_Type;
  ...
  task body Semaphore_Task_Type is
     Count : Natural;
  begin
     accept Initialize (N : in Natural) do
        Count := N;
     end Initialize;
     loop
        select
           when Count > 0 =>
               accept Wait do
                  Count := Count - 1;
               end Wait;
        or
               accept Signal;
               Count := Count + 1;
        end select;
     end loop;
  end Semaphore_Task_Type;

This task could be used as follows:

  nr_Full, nr_Free : Semaphore_Task_Type;
  ...
  nr_Full.Initialize (0); nr_Free.Initialize (nr_Slots);
  ...
  nr_Free.Wait; nr_Full.Signal;

Alternatively, semaphore functionality can be provided by a protected object, with major efficiency gains.

Ex. 7 The Initialize and Signal operations of this protected type are unconditional, so they are implemented as protected procedures, but the Wait operation must be guarded and is therefore implemented as an entry.

  protected type Semaphore_Protected_Type is
     procedure Initialize (N : in Natural);
     entry Wait;
     procedure Signal;
  private
     Count : Natural := 0;
  end Semaphore_Protected_Type;
  ...
  protected body Semaphore_Protected_Type is
     procedure Initialize (N : in Natural) is
     begin
        Count := N;
     end Initialize;
     entry Wait
        when Count > 0 is
     begin
        Count := Count - 1;
     end Wait;
     procedure Signal is
     begin
        Count := Count + 1;
     end Signal;
  end Semaphore_Protected_Type;

Unlike the task type above, this does not ensure that Initialize is called before Wait or Signal, and Count is given a default initial value instead. Restoring this defensive feature of the task version is left as an exercise for the reader.

Entry families edit

Sometimes we need a group of related entries. Entry families, indexed by a discrete type, meet this need.

Ex. 8 This task provides a pool of several buffers.

  subtype Buffer_Id is Integer range 1 .. nr_Bufs;
  ...
  task Buffer_Pool_Task is
     entry Insert (Buffer_Id) (An_Item : in Item);
     entry Remove (Buffer_Id) (An_Item : out Item);
  end Buffer_Pool_Task;
  ...
  task body Buffer_Pool_Task is
     Data   : array (Buffer_Id) of Item;
     Filled : array (Buffer_Id) of Boolean  := (others => False);
  begin
    loop
      for I in Data'Range loop
        select
          when not Filled(I) =>
             accept Insert (I) (An_Item : in Item) do
                Data(I) := An_Item;
             end Insert;
             Filled(I) := True;
        or
          when Filled(I) =>
             accept Remove (I) (An_Item : out Item) do
                    An_Item := Data(I);
             end Remove;
             Filled(I) := False;
        else
          null; -- N.B. "polling" or "busy waiting"
        end select;
      end loop;
    end loop;   
  end Buffer_Pool_Task;
  ...
  Buffer_Pool_Task.Remove(K)(This_Item);

Note that the busy wait else null is necessary here to prevent the task from being suspended on some buffer when there was no call pending for it, because such suspension would delay serving requests for all the other buffers (perhaps indefinitely).

Termination edit

Server tasks often contain infinite loops to allow them to service an arbitrary number of calls in succession. But control cannot leave a task's master until the task terminates, so we need a way for a server to know when it should terminate. This is done by a terminate alternative in a selective wait.

Ex. 9

  task type Terminating_Buffer_Task_Type is
     entry Insert (An_Item : in  Item);
     entry Remove (An_Item : out Item);
  end Terminating_Buffer_Task_Type;
  ...
  task body Terminating_Buffer_Task_Type is
     Datum : Item;
  begin
     loop
        select
           accept Insert (An_Item : in  Item) do
              Datum := An_Item;
           end Insert;
        or
           terminate;
        end select;
        select
           accept Remove (An_Item : out Item) do
              An_Item := Datum;
           end Remove;
        or
           terminate;
        end select;
     end loop;
  end Terminating_Buffer_Task_Type;

The task terminates when:

at least one terminate alternative is open, and
there are no pending calls to its entries, and
all other tasks of the same master are in the same state (or already terminated), and
the task's master has completed (i.e. has run out of statements to execute).

Conditions (1) and (2) ensure that the task is in a fit state to stop. Conditions (3) and (4) ensure that stopping cannot have an adverse effect on the rest of the program, because no further calls that might change its state are possible.

Timeout edit

A task may need to avoid being held up by calling to a slow server. A timed entry call lets a client specify a maximum delay before achieving rendezvous, failing which the attempted entry call is withdrawn and an alternative sequence of statements is executed.

Ex. 10

  task Password_Server is
     entry Check (User, Pass : in String; Valid : out Boolean);
     entry Set (User, Pass : in  String);
  end Password_Server;
  ...
  User_Name, Password : String (1 .. 8);
  ...
  Put ("Please give your new password:");
  Get_Line (Password);
  select
     Password_Server.Set (User_Name, Password);
     Put_Line ("Done");
  or
     delay 10.0;
     Put_Line ("The system is busy now, please try again later.");
  end select;

To time out the functionality provided by a task, two distinct entries are needed: one to pass in arguments, and one to collect the result. Timing out on rendezvous with the latter achieves the desired effect.

Ex. 11

  task Process_Data is
     entry Input (D  : in  Datum);
     entry Output (D  : out Datum);
  end Process_Data;
  
  Input_Data, Output_Data : Datum;
  
  loop
     collect Input_Data from sensors;
     Process_Data.Input (Input_Data);
     select
        Process_Data.Output (Output_Data);
        pass Output_Data to display task;
     or
        delay 0.1;
        Log_Error ("Processing did not complete quickly enough.");
     end select;
  end loop;

Symmetrically, a delay alternative in a selective wait statement allows a server task to withdraw an offer to accept calls after a maximum delay in achieving rendezvous with any client.

Ex. 12

  task Resource_Lender is
     entry Get_Loan (Period : in Duration);
     entry Give_Back;
  end Resource_Lender;
  ...
  task body Resource_Lender is
     Period_Of_Loan : Duration;
  begin
     loop
        select
           accept Get_Loan (Period : in Duration) do
              Period_Of_Loan := Period;
           end Get_Loan;
           select
              accept Give_Back;
           or
              delay Period_Of_Loan;
              Log_Error ("Borrower did not give up loan soon enough.");
           end select;
        or
           terminate;
        end select;
     end loop;
  end Resource_Lender;

Conditional entry calls edit

An entry call can be made conditional, so that it is withdrawn if the rendezvous is not immediately achieved. This uses the select statement notation with an else part. Thus the constructs

  select
    Callee.Rendezvous;
  else
    Do_something_else;
  end select;

and

  select
    Callee.Rendezvous;
  or
    delay 0.0;
    Do_something_else;
  end select;

seem to be conceptually equivalent. However, the attempt to start the rendezvous may take some time, especially if the callee is on another processor, so the delay 0.0; may expire although the callee would be able to accept the rendezvous, whereas the else construct is safe.

Requeue statements edit

A requeue statement allows an accept statement or entry body to be completed while redirecting it to a different or the same entry queue, even to one of another task. The called entry has to share the same parameter list or be parameter-less. The caller of the original entry is not aware of the requeue and the entry call continues although now to possibly another entry of another task.

The requeue statement should normally be used to quickly check some precondition for the work proper. If these are fulfilled, the work proper is delegated to another task, hence the caller should nearly immediately be requeued.

Thus requeuing may have an effect on timed entry calls. To be a bit more specific, say the timed entry call is to T1.E1, the requeue within T1.E1 to T2.E2:

task body T1 is
  ...
  accept E1 do
    ...  --  Here quick check of preconditions.
    requeue T2.E2;  --  delegation
  end E1;
  ...
end T1;

Let Delta_T be the timeout of the timed entry call to T1.E1. There are now several possibilities:

1. Delta_T expires before T1.E1 is accepted.

The entry call is aborted, i.e. taken out of the queue.

2. Delta_T expires after T1.E1 is accepted.

T1.E1 has finished (its check of preconditions) and T2.E2 is to be accepted.

For the caller, who is unaware of the requeue, the entry call is still executing; it is completed only with the completion T2.E2.

Thus, although the original entry call may be postponed for a long time while T2.E2 is waiting to be accepted, the call is executing from the caller's point of view.

To avoid this behaviour, a call may be requeued with abort. This changes case 2 above:

2.a The call is requeued to T2.E2 before Delta_T expires.

2.a.1. T2.E2 is accepted before expiration, the call continues until T2.E2 is completed.

2.a.2. Delta_T expires before T2.E2 is accepted: The entry call is aborted, i.e. taken out of the queue of T2.E2.

2.b The call is requeued to T2.E2 after the expiration of Delta_T.

2.b.1. T2.E2 is immediately available (i.e. there is no requeue), T2.E2 continues to completion.

2.b.2. T2.E2 is queued: The entry call is aborted, i.e. taken out of the queue of T2.E2.

In short, for a requeue with abort, the entry call to T1.E1 is completed in cases 1, 2.a.1 and 2.b.1; it is aborted in 2.a.2 and 2.b.2.

So what is the difference between these three entries?

 accept E1 do
    ...  --  Here quick check of preconditions.
    requeue T2.E2 with abort;  --  delegation
  end E1;

  accept E2 do
    ...  --  Here quick check of preconditions.
    T2.E2;  --  delegation
  end E2;

  accept E3 do
    ...  --  Here quick check of preconditions.
  end E3;
  T2.E2;  --  delegation

E1 has just been discussed. After the requeue, its enclosing task is free for other work, while the caller is still suspended until its call is completed or aborted.

E2 also delegates, however via an entry call. Thus E2 completes only with the completion of T2.E2.

E3 first frees the caller, then delegates to T2.E2, i.e. the entry call is completed with E3.

Scheduling edit

FIFO, priority, priority inversion avoidance, ... to be completed.

Interfaces and polymorphism edit

This language feature is only available from Ada 2005 on.

Tasks and protected types can also implement interfaces.

type Printable is task interface;

procedure Input (D  : in  Printable);


task Process_Data is new Printable with
   entry Input  (D  : in  Datum);
   entry Output (D  : out Datum);
end Process_Data;

To allow delegation necessary to the polymorphism, the interface Printable shall be defined in its own package. It is then possible to define different task type implementing the Printable interface and use these implemetations polymorphically:

 with printable_package; use printable_package;  -- This package contains the definition of Printable
 procedure Printer is
    task type Print_Red  is new Printable with end;
    task type Print_Blue is new Printable with end;
 
    task body Print_Red is
    begin
       Ada.Text_IO.Put_Line ("Printing in Red");
    end Print_Red;
 
    task body Print_Blue is
    begin
       Ada.Text_IO.Put_Line ("Printing in Blue");
    end Print_Blue;
 
    printer_task : access Printable'Class;
 begin
    printer_task := new Print_Red;
    printer_task := new Print_Blue;  -- Beware, this leaks memory. Example only.
 end Printer;

This feature is also called synchronized interfaces.

Restrictions and Profiles edit

Ada tasking has too many features for some applications. Therefore there exist restrictions and profiles for certain, mostly safety or security critical applications. Restrictions and profiles are defined via pragmas. A restriction forbids the use of certain features, for instance the restriction No_Abort_Statements forbids the use of the abort statement. A profile (do not confuse with parameter profiles for subprograms) combines a set of restrictions.

See 13.12: Pragma Restrictions and Pragma Profile ^[Annotated]

Ada Quality and Style Guide edit

Chapter 4: Program Structure
- 4.1.9 Tasks
- 4.1.10 Protected Types
Chapter 6: Concurrency