Ada Programming/Tasking

From Wikibooks, open books for an open world
Jump to: navigation, search

Ada Lovelace 1838.jpg

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 private 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.)

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

Like a task entry, a protected entry can employ a guard to control admission. This provides automatic signaling, and ensures that when a protected entry call is accepted, its guard condition is True, so that a guard provides a reliable precondition for the entry body.

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 guards, 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.

  type 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:

  1. at least one terminate alternative is open, and
  2. there are no pending calls to its entries, and
  3. all other tasks of the same master are in the same state (or already terminated), and
  4. 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 to a different or the same entry queue. The called entry has to share the same parameter list or be parameter-less.

Scheduling[edit]

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

Interfaces[edit]

This language feature is only available in Ada 2005.

Task 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;

See also[edit]

Wikibook[edit]

Ada Reference Manual[edit]

Ada 95[edit]

Ada 2005[edit]

Ada Quality and Style Guide[edit]