Tasking and the Ada Rendezvous
Multiprocessing has been a part of the Ada programming
language since the language was first standardized in 1983. The original
version of Ada provided active concurrency objects called tasks. Today tasks
are commonly implement by Ada compilers as operating system threads, but the
Ada language does not depend on operating system threading to implement tasks.
The execution of an Ada program consists of the execution of
one or more tasks. Each
task represents a separate thread of control that proceeds independently and
concurrently between the points where it interacts with other
tasks. The various forms of task interaction are described in this clause, and
include:
·
the activation and termination of a task;
·
a call on a protected subprogram of a protected
object, providing exclusive read-write access, or concurrent read-only
access to shared data;
·
a call on an entry, either of another task,
allowing for synchronous communication with that task, or of a protected
object, allowing for asynchronous communication with one or more other tasks
using that same protected object;
·
a timed operation, including a simple delay
statement, a timed entry call or accept, or a timed asynchronous select
statement (see next item);
·
an asynchronous transfer of control as part of
an asynchronous select statement, where a task stops what it is doing and
begins execution at a different point in response to the completion of an entry
call or the expiration of a delay;
·
an abort statement, allowing one task to cause
the termination of another task.
Tasks can be implemented as a task type, allowing multiple
identical instances of a task to be created, or as single task entities defined
as members of an anonymous task type.
Definition of a task type includes declaration of all
interfaces to the task type. Task interfaces, or calling points, are called
task entries. Each task entry allow another task to call an instance of the
task type, possibly passing data to or from the task type instance.
Rendezvous
When one task calls an entry of another task the two task
synchronize to allow data to be passed from one task to the other. If task A
calls an entry named set_id declared in task B with the purpose of passing an
id value from task A to task B the two tasks synchronize to allow direct
communication between the tasks. Task A calls the Task B entry. Task B accepts
the entry call. Synchronization happens when both task are ready to process the
entry. If task A calls the entry before task B accepts the entry call then task
A suspends until task B is ready. Similarly, if task B accepts the entry before
any task calls the entry then task B suspends until the entry is called. An
entry is allowed to transfer data to or from the task calling the entry.
Table 1 Task Type Example
|
task type Counter is |
The task type in the example above is named Counter. Task
type Counter has one entry. A task type may have multiple entries or it may
have no entries.
The single entry in this example is named Set_Num. Set_Num
requires a single parameter of type Integer. The “in” mode designation causes
the value to be passed from the calling task to the called instance of Counter.
Each task or task type declaration must be completed with a
task body. The task or task type declaration contains the declaration of the
name of the task or task type as well as the declaration of all entries
associated with the task or task type. The task body contains the logic
implemented by the task. The task body must have the same name as its
corresponding task or task type declaration.
Table 2 Task Body Example
|
task body Counter is delay Duration (Random (Seed) * 0.01); Put_Line (Num'Image); end Counter; |
The structure of a task body is very similar to the structure
of an Ada procedure. Local variables are declared between the “is” reserved
word and the “begin” reserved word. The “accept” statement performs the task’s
interaction with the entry call. In this case the parameter “Val” contains the
value passed from the task calling the entry. That value is copied into the local
variable “Num”. The accept operation ends when the code reaches “end Set_Num”.
Upon completion of the accept operation the synchronization of this task with
its calling task completes and both tasks resume asynchronous execution.
Calling a Task Entry
The following example demonstrates how one task calls the
entry of another task.
Table 3 Calling a Task Entry
|
with
Ada.Text_IO; use Ada.Text_IO; with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random; procedure Main is task type Counter is task body Counter is begin Reset (Seed); accept Set_Num (Val : in Integer) do delay Duration (Random (Seed) *
0.01); Put_Line
(Num'Image); end Counter; subtype Index is Integer range 0 .. 9; Counters : array (Index) of Counter; begin for I in
Counters'Range loop end Main; |
The purpose of this simple program is to use tasks to print
the digits 0 through 9 in random order. The task type counter is designed to
receive a single integer value through its Set_Num entry, delay execution for a
random time (in this case the time is a random fraction of milliseconds between
9 milliseconds and 1 millisecond) and then output the value of its local
variable named Num. Upon completing the output operation the instance of
Counter completes.
An array of Counter objects is created. The name of that
array is Counters. The array is indexed by the values 0 through 9, which causes
the array to have 10 instances of task type Counter. Those tasks start automatically
when program execution reaches the “begin” statement of the Main procedure.
Looking back at the task body for Counter we see that the
first action of the task is to call the Reset procedure for random generator,
setting the random number seed to a unique value based upon the current
computer clock. After resetting the random number seed the task calls the
accept operator for the Set_Num entry. The task then suspends until its Set_Num
entry is called.
The “for” loop in the Main procedure iterates through the
array of Counter tasks, calling each one in order and passing its array index
value as the number it will output. Keep in mind that the Main procedure
executes in a task separate from the ten Counter tasks.
Another example of the Ada Rendezvous is shown below. This
example defines an Ada package implementing parallel addition of an array of
integer values. The example is implemented in three files.
Table 4 Parallel_Addition.ads
|
package Parallel_Addition is type Data_Array is
array(Integer range <>) of Integer; type Data_Access is
access all Data_Array; function Sum(Item : in
not null Data_Access) return Integer; end Parallel_Addition; |
This package specification declares an unconstrained array
type named Data_Array. Data_Array arrays are indexed by some set of values
within the valid set of Integer values. Each element contains an Integer. An
unconstrained array allows the user to pass an array of any size permitted by
the computer hardware.
The type Data_Access is a reference to Data_Array.
The function Sum takes a parameter of type Data_Access so
that very large arrays created on the heap may be passed to the function. The
function returns a single Integer which is the sum of all the elements in the
array passed to the function.
Table 5 Parallel_Addition.adb
|
package body Parallel_Addition is --------- function Sum (Item :
in not null Data_Access) return Integer is task type Adder is entry Set (Min : Integer; Max :
Integer); entry Report
(Value : out Integer); end Adder; task body Adder is Total : Integer
:= 0; begin accept Set (Min
: Integer; Max : Integer) do for I in First
.. Last loop accept Report
(Value : out Integer) do end Adder; A1 : Adder; begin A1.Set (Min =>
Item'First, Max => Mid); A1.Report (R1); return R1 + R2; end Sum; end Parallel_Addition; |
The package body for Parallel_Addition contains the
implementation of the Sum function declared in the Parallel_Addition package
specification.
Within the Sum function we find the declaration of a task
type name Adder. Instances of Adder will perform the parallel addition. The
task type declaration for Adder includes two entries named Set and Report. The
Set entry sets the minimum and maximum index values to be used by the task. The
Report entry passes the total calculate by the task back to the entry’s calling
task.
Two instances of Adder are created. One is named A1 and the
other is named A2. Similarly two integer variables intended to hold the results
of the additions are created. Those variables are named R1 and R2.
The Sum function calculated a middle value for the index
values in the array passed to it as Item.
The Adder tasks begin execution when program execution
reaches the “begin” of the Sum function.
The Sum function calls the Set entry for Adder A1 passing it
the index values for the first index of Item and the Mid value. Similarly, the
set entry for Adder A2 is passed the index value of Mid + 1 and the last index
value of Item.
The Sum function immediately calls the Adder A1 Report entry
to receive the value for R1, followed by calling the Adder A2 report entry to
receive the value for R2. The Sum function will suspend until A1 accepts its
Report entry. It will then suspend again if necessary until A2 accepts its
Repot entry.
Sum returns the sum of R1 and R2.
Table 6 Parallel_Addition_Test.adb
|
with Parallel_Addition; use Parallel_Addition; procedure Parallel_Addition_Test is The_Data : Data_Access
:= new Data_Array (1 .. Integer'Last); Start : Time; The_Sum : Integer; begin The_Data.all :=
(others => 1); end Parallel_Addition_Test; |
The program Parallel Addition Test creates an array
containing 2,147,483,647 elements. The object of this test is to calculate an
average time for each addition operation using the Parallel_Addition package. A
large array provides a statistically solid number for the average time.
In this case all the elements of the array are initialized
to 1 so that the addition will not result in an integer overflow. This also
gives a good check of the addition, since the correct result is 2,147,483,647.
The program captures the clock time in the variable Start,
calls the Sum function, then captures the time in the variable Stop. The
difference between the two times is the approximate time used to sum the array.
The addition result along with the elapsed time and the
average time per addition operation are reported.
The result of an example run is:
Table 7 Example Parallel_Addition_Test Output
|
The sum is: 2147483647 |