Ada Programming/Tasking< Ada Programming
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:
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 types are limited, i.e. they are restricted in the same way as limited private types, so assignment and comparison are not allowed.
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);
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.)
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.
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.
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;
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.
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).
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.
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.
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.
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.
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.
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 callsEdit
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
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.
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 is completed 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.
FIFO, priority, priority inversion avoidance, ... to be completed.
This language feature is only available from Ada 2005 on.
Task and Protected types can also implement interfaces.