Ada Concurrency

Sequential Programming

Traditional programs are sequential, performing actions in a specified sequence. The classical pattern for sequential program execution is described as Input, Process, Output. This pattern may be performed once or it may be performed many times using either iteration or recursion. This pattern is very effective at doing one thing at a time for one user. The pattern exhibits serious limitations when dealing with multiple events overlapping in time, or with multiple users.

For instance, the following sequential program calculates the sum of the digits in an integer. The program supports one user who enters a single number.

1  Simple Sequential Program

----------------------------------------------------------------------- -- calculate the sum of the digits of a positive integer ----------------------------------------------------------------------- with Ada.Text_IO; use Ada.Text_Io; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Sum_Digits is    Num : Natural;    Sum : Integer := 0; begin    Put("Enter a positive integer: ");    Get(Num);    Put_Line("Given number ="& Num'Image);    while Num > 0 loop       Sum := Sum + (Num mod 10);       Num := Num / 10;    end loop;    Put_Line("Sum of the digits =" & Sum'Image); end Sum_Digits;

Concurrent Programming

Computer designers soon realized that some problems required more than one program to run at a time and some business needs required more than one person at a time to use computing resources. The first solution for this problem was called time sharing. Operating systems were developed that allowed several programs to take turns interleaving their sequential processing so that each program could make some progress in its sequential actions during a given time period. This provided the illusion of concurrent behavior and also more efficiently used computer resources. Using the Input, Process, Output model each program would have periods of low activity while waiting for input or output data or resources. Other programs could be allowed to execute during these “waiting” periods.

These early solutions still only used a single central processor since computers of the time only had a single central processor. The time sharing approach allowed multiple users to run many different programs or many instances of the same program simultaneously, but performance was noticeably impacted as the number of simultaneous users increased. Some systems could support a dozen users while others could support 50 to 100 users before performance became bothersome.

Operating systems such as Unix implemented concepts of pipes and filters allowing many programs to chain input and output to perform complex processing. Unix pipes were I/O channels within the computer providing guaranteed delivery of data from one program to another.

For example, if a user wanted to count the number of files in a directory the user could combine two Unix filters or programs. The “ls” program lists the files in a directory. The “wc” program counts words or lines read from its input and outputs the count. The user would simply write

ls | wc –l

The “|” symbol was used to implement a pipe between ls and wc. The output of the ls command is written to the pipe and that output is sent to the input of the wc command. The concept was thought of as plumbing data from one program to another through a “pipe”. The command wc –l caused the wc program to count only lines, not words or characters. The ls command output the list of files in the directory with one file name per line of output. The pipe concept was very sophisticated for its time. The pipe actually caused the two programs to synchronize their processing. If the pipe was empty the reading program would be suspended until data arrived. If the pipe was full the writing program would be suspended until data was consumed by the reading program.

The first attempts to increase performance through hardware involved locating two or more computer motherboards in the same computer chassis. Sequential programs could then be distributed across the two or more central processors to provide increased processing capability to programs and users. One of the problems of this early approach is that pipes did not initially work across computer boundaries. A program executing on one motherboard could not pipe data to a program executing on the other motherboard. Networking was needed to communicate data between motherboards.

Eventually multi-core processors were developed along with multi-tasking cores, allowing parallel tasks to be executed on the same central processor. Those tasks can communicate directly or through shared memory without the complexities and delays of networking.

Tasks

The commonly used term for separately executing sub-processes is threads, while the academic term for has long been tasks. The Ada language has supported the creation of tasks since its first language standard in 1983, long before the term “threads” became popular for sub-processes.

Every Ada program executes at least one task, which is commonly called the main task. Additional tasks can be created. The example below shows a main task which creates a child task. Both the child task and the main task run at the same time.

2 Simple Task

with Ada.Text_IO; use Ada.Text_IO; procedure Simple_Task_Main is    task Hello_Task;       task body Hello_Task is    begin       for I in 1..10 loop          Put_Line("=== Hello from the child task.===");       end loop;    end Hello_Task; begin    for I in 1..11 loop       Put_Line("Hello from the main task.");    end loop; end Simple_Task_Main;

The interleaving of the outputs from the two tasks will vary from one execution to another. Following is an output of this program.

3 Simple Task Output

=== Hello from the child task.=== Hello from the main task. === Hello from the child task.=== Hello from the main task. === Hello from the child task.=== Hello from the main task. === Hello from the child task.=== Hello from the main task. === Hello from the child task.=== Hello from the main task. === Hello from the child task.=== Hello from the main task. === Hello from the child task.=== Hello from the main task. === Hello from the child task.=== Hello from the main task. === Hello from the child task.=== Hello from the main task. === Hello from the child task.=== Hello from the main task. Hello from the main task.

The child task automatically starts when execution of the main task reaches the “begin” statement in the main task.

Task Interactions

The two tasks shown above do not share any data. Most useful concurrent programs need to share data among the tasks. Ada provides two approaches for sharing data. The Ada Rendezvous mechanism allows two tasks to pass data from one to another in a synchronous manner. Ada Protected Objects allow data to be shared asynchronously through a shared buffer.

Rendezvous

A task may provide entries. Entries may be called by other tasks to pass data between the called task and the calling task. The two tasks synchronize at the calling/called points. If the caller gets to the entry interface first the caller waits for the called task. If the called task gets to the entry interface point first the called task waits for the calling task.

The following example demonstrates the use of tasks to perform parallel addition of the elements of an array. The calling task passes the first half of an array to one task and the second half of the same array to another task. Each task totals the elements in its portion of the array and passes back the sum. The calling task then retrieves the two sums, and calculates the final sum of array elements. This example also calculates the time required to perform the parallel sum and displays that timing as well as the result.

The parallel sum routine is provided in a separate Ada package. The package specification identifies the data types and function interface required to call the parallel addition routine. The package body defines the executable code for the parallel addition routine. Finally, a main procedure is defined to test the parallel addition and record execution times.

4 Parallel Addition Specification

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;

The package specification defines two data types. Data_Array is an unconstrained array of Integer. Data_Access is an access type referencing Data_Array. Access types are roughly equivalent to references in C++.

The function Sum takes a non-null instance of Data_Access as an input parameter and returns an Integer; Use of an access type as the parameter allows the program to handle very large arrays of integer very efficiently.

5 Parallel Addition Body

package body Parallel_Addition is    ---------    -- Sum --    ---------    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;          First : Integer;          Last  : Integer;       begin          accept Set (Min : Integer; Max : Integer) do             First := Min;             Last  := Max;          end Set;          for I in First .. Last loop             Total := Total + Item (I);          end loop;          accept Report (Value : out Integer) do             Value := Total;          end Report;       end Adder;       A1  : Adder;       A2  : Adder;       R1  : Integer;       R2  : Integer;       Mid : constant Integer := (Item'Length / 2) + Item'First;    begin       A1.Set (Min => Item'First, Max => Mid);       A2.Set (Min => Mid + 1, Max => Item'Last);       A1.Report (R1);       A2.Report (R2);       return R1 + R2;    end Sum; end Parallel_Addition;

The package body for Parallel_Addition contains the implementation of the function Sum. Inside the function Sum a task type named Adder is defined. First the interface for Adder declares that it has two entries. The entry named Set reads in two parameters Min and Max, which are the array indices an instance of Adder will use to access elements of the array pointed to by the parameter Item passed into function Sum. The entry named Report passes a single integer out to the calling task of the Adder instance.

The task body of the Adder task type accepts the Set entry, reading the Min and Max values and assigning them to the local variables First and Last. The task then sums all the values from index First to index Last. Finally, the Adder task accepts the Report entry and passes its total to the calling task.

The calling task in this case is the task that calls the Sum function.

Two instances of the Adder task, named A1 and A2, are created. Both instances start executing when the Sum function reaches its “begin” statement. Both tasks suspend at the accept statement for the Set entry, waiting for some task to call them. The executable part of the Sum function then calls the Set entry for each task instance, passing in the appropriate Min and Max values. The Sum function then calls the Report entries of each task. The Sum function waits for the tasks to execute the Accept call for the Report entry, then adds the two reported values and returns that final total.

The main procedure for this example is:

6 Parallel Addition Test Main Procedure

with Parallel_Addition; use Parallel_Addition; with Ada.Text_IO;       use Ada.Text_IO; with Ada.Calendar;      use Ada.Calendar; procedure Parallel_Addition_Test is    The_Data : Data_Access := new Data_Array (1 .. Integer'Last / 5);    Start    : Time;    Stop     : Time;    The_Sum  : Integer; begin    The_Data.all := (others => 1);    Start        := Clock;    The_Sum      := Sum (The_Data);    Stop         := Clock;    Put_Line ("The sum is: " & Integer'Image (The_Sum));    Put_Line      ("Addition elapsed time is " &       Duration'Image (Stop - Start) &         " seconds.");    Put_Line      ("Time per addition operation is " &         Float'Image(Float(Stop - Start) / Float(The_Data'Length)) &         " seconds."); end Parallel_Addition_Test;

The test procedure dynamically allocates an instance of Data_Array containing 429496729 integers and assigns the value 1 to each element. A start time of the Sum function is assigned to the variable Start, the Sum function is called, and a stop time of the Sum function is assigned to the variable Stop. Finally the sum, the total execution time of the function, and the average time per addition are displayed.

7 Parallel Addition Test Output

The sum is:  429496729 Addition elapsed time is  1.147519700 seconds. Time per addition operation is  2.67178E-09 seconds.

A common programming pattern for concurrency is the Producer-Consumer pattern. This is the pattern used for Unix pipes and filters, and variations on this pattern continue to be used in many programs. The simplest producer-consumer pattern employs a single producing task and a single consuming task. This simple producer-consumer is easily implemented using the Ada Rendezvous mechanism.

8 Producer Consumer Rendezvous

----------------------------------------------------------------------- -- Producer Consumer implemented using the Ada Rendezvous ----------------------------------------------------------------------- with Ada.Text_IO; use Ada.Text_Io; procedure rendezvous_pc is    task producer;    task consumer is       entry Put(Item : in Integer);    end consumer;    task body producer is    begin       for I in 0..15 loop          Consumer.Put(I);       end loop;    end Producer;    task body consumer is       Num : Integer;    begin       loop          select             accept Put(Item : in Integer) do                Num := Item;             end Put;             Put_Line("Consumed" & Num'Image);          or             terminate;          end select;       end loop;    end consumer; begin    null; end rendezvous_pc;

Program 9 Producer Consumer Rendezvous Output

Consumed 0 Consumed 1 Consumed 2 Consumed 3 Consumed 4 Consumed 5 Consumed 6 Consumed 7 Consumed 8 Consumed 9 Consumed 10 Consumed 11 Consumed 12 Consumed 13 Consumed 14 Consumed 15

In this example the main task only starts up the producer and consumer and then waits for them to complete. The producer generates 16 integer values from 0 through 15 then stops. The consumer reads each value produced by the producer and quits after the producer quits.

Protected Objects

The Rendezvous can be very useful in synchronous communication between tasks, but is very clumsy when developing asynchronous task communication solutions. Ada’s solution is the Protected Object.

Ada protected objects are shared data buffers protected from race conditions between tasks. Protected objects have three kinds of interfaces to tasks.

Protected Operation	Description
Function	Protected functions provide shared read-only access to the protected object. Multiple tasks can simultaneously call protected functions of a protected object. Functions implement a read lock on the protected object preventing any task from changing the object while it is being read.
Procedure	Protected procedures provide unconditional read/write access to a protected object. Protected procedures employ an exclusive read/write lock ensuring only one task at a time has access to the object during execution of the procedure.
Entries	Protected entries provide conditional read/write access to a protected object. Protected entries employ an exclusive read/write lock ensuring only one task at a time has access to the object during execution of the entry. Tasks calling a protected entry while the controlling condition is false are automatically suspended in an entry queue. Tasks in an entry queue are activated and released from the queue when the controlling condition evaluates to TRUE. The order in which tasks are released from the entry queue depends upon the chosen queuing policy. The default queuing policy is First In First Out.

Following is a simple producer-consumer example using a protected object.

10 Generic Protected Object Specification

generic    type Element_Type is private; package Protected_Buffer is    Capacity : constant := 10;    type Index_T is mod Capacity;    type Internal_Buffer is array(Index_T) of Element_Type;    protected type Buffer_T is       entry Add(Item : in Element_Type);       entry Get(Item : out Element_Type);    private       Buf : Internal_Buffer;       Add_Idx : Index_T := Index_T'First;       Get_Idx : Index_T := Index_T'First;       Count   : Natural := 0;    end Buffer_T; end Protected_Buffer;

This protected object provides two operations. The Add entry and the Get entry allow a task to write to the protected object and to read from the protected object.

The Internal_Buffer type is an array indexed by a modular type. The valid index values for this array are 0 through 9. Modular types provide modular arithmetic. In this case 9 + 1 results in 0. Modular types are very useful for implementing circular buffers.

The implementation of the protected type is:

11 Protected Object Implementation

package body Protected_Buffer is    --------------    -- Buffer_T --    --------------    protected body Buffer_T is       ---------       -- Add --       ---------       entry Add (Item : in Element_Type) when Count < Capacity is       begin          Buf(Add_Idx) := Item;          Add_Idx := Add_Idx + 1;          Count := Count + 1;       end Add;       ---------       -- Get --       ---------       entry Get (Item : out Element_Type) when Count > 0 is       begin          Item := Buf(Get_Idx);          Get_Idx := Get_Idx + 1;          Count := Count - 1;       end Get;    end Buffer_T; end Protected_Buffer;

The protected body reveals the conditions associated with each protected entry. The Add entry is only open to execution when Count is less than Capacity. The Get entry is only open to execution when Count is greater than 0.

This implementation of a protected object is designed to ensure that every value written to the protected object can be read from the protected object. As we will see later, other behaviors are possible.

12 Protected Producer Consumer Main

with Ada.Text_IO; use Ada.Text_IO; with Protected_Buffer; procedure Main is    package Int_Buf is new Protected_Buffer(Integer);    use Int_Buf;    Shared_Buf : Buffer_T;    task producer;    task body producer is    begin       for I in 0..15 loop          Shared_Buf.Add(I);       end loop;    end producer;    task consumer;    task body consumer is       Num : Integer;    begin       loop          select             Shared_Buf.Get(Num);             Put_Line("Consumed" & Num'Image);          or             delay 0.001;             exit;          end select;       end loop;    end consumer; begin    null; end Main;

13 Protected Main Output

Consumed 0 Consumed 1 Consumed 2 Consumed 3 Consumed 4 Consumed 5 Consumed 6 Consumed 7 Consumed 8 Consumed 9 Consumed 10 Consumed 11 Consumed 12 Consumed 13 Consumed 14 Consumed 15

In this example the producer and consumer tasks never directly communicate with each other. Instead, the two tasks only communicate with the protected object. The producer task adds values to the protected object and the consumer task gets values from the protected object.

Notice that all the lock manipulation is handled automatically.

There are many variations on the producer-consumer model. For instance, it is possible to have a producer that produces data faster than the consumer can consume data. If one uses the protected object implementation shown above the producer will be slowed down to the rate of the consumer because the buffer will eventually fill. While this behavior may be desirable under some circumstances, it may be unacceptable under other circumstances.

Some problem domains may require that the producer work at full speed, completely uninhibited by the consumer. The result is that the consumer must under-sample the data produced by the producer.

14 Undersampling Example

with Ada.Text_IO; use Ada.Text_IO; procedure Undersampling is    protected Buffer is       procedure Add(Item : Integer);       entry Get(Item : out Integer);    private       Value : Integer;       Is_New : Boolean := False;    end Buffer;       protected body Buffer is             procedure Add(Item : Integer) is       begin          Value := Item;          Is_New := True;       end Add;             entry Get(Item : out Integer) when Is_New is       begin          Item := Value;          Is_New := False;       end Get;    end Buffer;       task Producer is       Entry Stop;    end Producer;       task Consumer is       Entry Stop;    end Consumer;       task body Producer is       Num : Natural := 0;    begin       loop          select             Accept Stop;             Exit;          else             Buffer.Add(Num);             Num := Num + 1;          end select;       end loop;    end Producer;       task body Consumer is       Num : Natural;    begin       loop          select             accept Stop;             exit;          else             select                Buffer.Get(Num);                Put_Line("Consumed:" & Num'Image);             else                null;             end select;          end select;       end loop;    end Consumer;               begin    delay 0.0001; -- wait 0.0001 second    Producer.Stop;    Consumer.Stop; end Undersampling;

 15 Undersampling output

Consumed: 173 Consumed: 174 Consumed: 195 Consumed: 209 Consumed: 224 Consumed: 238 Consumed: 253 Consumed: 271 Consumed: 286 Consumed: 300 Consumed: 314 Consumed: 328 Consumed: 343 Consumed: 356 Consumed: 372 Consumed: 386 Consumed: 402 Consumed: 416 Consumed: 430 Consumed: 444 Consumed: 459 Consumed: 475 Consumed: 489 Consumed: 503 Consumed: 517 Consumed: 530 Consumed: 545

The main task calls the Stop entries for the producer and consumer to coordinate the shutdown of the program. Failure to do this will result in an eventual integer overflow and the corresponding run time exception.

It is also possible that the consumer may consume data faster than the data is produced. In this case either the consumer can be slowed down to wait for the producer, or the consumer can oversample the values. The following example demonstrates oversampling by the consumer.

16 Oversampling Example

with Ada.Text_IO; use Ada.Text_IO; procedure Oversampling is    protected Buffer is       procedure Add(Item : Integer);       function Get return Integer;    private       Value : Integer := Integer'First;    end Buffer;    protected body Buffer is       procedure Add(Item : Integer) is       begin          Value := Item;       end Add;       function Get return Integer is       begin          return Value;       end Get;    end Buffer;    task Producer is       entry Stop;    end Producer;    task Consumer is       entry Stop;    end Consumer;    task body Producer is       Num : Natural := 0;    begin       Put_Line("Starting Producer");       loop          select             accept Stop;             exit;          else             Buffer.Add(Num);             Num := Num + 1;             delay 0.005;          end select;       end loop;    end Producer;    task body Consumer is       Num : Natural;    begin       Put_Line("Starting Consumer");       loop          select             accept Stop;             exit;          else             Num := Buffer.Get;             Put_Line("Consumed:" & Num'Image);             Delay 0.001;          end select;       end loop;    end consumer; begin    delay 0.1;    Producer.Stop;    Consumer.Stop; end Oversampling;

17 Oversampling Output

Starting Producer Starting Consumer Consumed: 0 Consumed: 0 Consumed: 0 Consumed: 0 Consumed: 1 Consumed: 1 Consumed: 1 Consumed: 1 Consumed: 2 Consumed: 2 Consumed: 2 Consumed: 2 Consumed: 2 Consumed: 2 Consumed: 3 Consumed: 3 Consumed: 4 Consumed: 4 Consumed: 4 Consumed: 4 Consumed: 5 Consumed: 5 Consumed: 5 Consumed: 5 Consumed: 5 Consumed: 6 Consumed: 6 Consumed: 6 Consumed: 6 Consumed: 7 Consumed: 7 Consumed: 7 Consumed: 7 Consumed: 8 Consumed: 8 Consumed: 8 Consumed: 9 Consumed: 9 Consumed: 9 Consumed: 9 Consumed: 10 Consumed: 10 Consumed: 10 Consumed: 10 Consumed: 11 Consumed: 11 Consumed: 11 Consumed: 11 Consumed: 12 Consumed: 12 Consumed: 12 Consumed: 12 Consumed: 13 Consumed: 13 Consumed: 13 Consumed: 13 Consumed: 14 Consumed: 14 Consumed: 14 Consumed: 14 Consumed: 15 Consumed: 15 Consumed: 15 Consumed: 16 Consumed: 16 Consumed: 16 Consumed: 16 Consumed: 17 Consumed: 17 Consumed: 17