Tuesday, January 28, 2020

Ada Concurrency - Avoiding Race Conditions


Race conditions

Concurrent tasks are commonly scheduled by the operating system. The result is that the programmer cannot predict the order of execution of tasks. For example, if two tasks increment a shared variable the result may not be what was expected.

Num : Integer := 100; -- shared variable
Procedure Increment is
Begin
   Num := Num + 1;
End Increment;

If two tasks simultaneously call the Increment procedure the following interaction is possible

Num := 100 + 1;

Each task reads the initial value of Num as 100, then adds one to the value and stores 101 into the variable Num. The trouble we see is the Increment function has been executed twice but the value stored in Num is only increased by 1 from the original value.
The race condition happens when two or more tasks perform overlapping writes to the same variable.
The following program illustrates this problem.

with Ada.Text_IO; use Ada.Text_IO;

procedure non_deterministic is
   Num : Integer := 0;
  
   procedure Increment is
   begin
      Num := Num + 1;
   end Increment;
  
   task type Adder;
  
   task body Adder is
   begin
      for I in 1..100_000 loop
         Increment;
      end loop;
   end Adder;
  
begin
   declare
      A1, A2 : Adder;
   begin
      null;
   end;
   Put_Line(Num'Image);
end non_deterministic;

The shared variable Num is initialized to 0. Two tasks are created. Each task calls Increment 100,000 times. If there are no race conditions the value of Num after both tasks complete should be 200,000. Instead successive executions of the program produce unexpected results:

196996
112584
124100
94783

Avoiding race conditions

The 1995 version of the Ada language added Protected Objects to the language. Ada protected objects are protected against race conditions and deadlocks.
A protected object is a passive element of concurrency while a task is an active element of concurrency. Protected objects are allowed to have three kinds of operations; procedures, entries, and functions. Protected procedures are allowed to read and write data in the protected object. Each protected object is granted an exclusive read/write lock on the protected object so that no other protected operation can be performed while the procedure is executing. Protected entries are similar to a protected procedure with the only difference that the protected entry has a guard condition which must be satisfied. If the guard condition evaluates to TRUE the calling task is allowed to execute the entry. While the guard condition evaluates to FALSE all calling tasks are suspended in an entry queue for that entry, waiting to execute when the guard condition evaluates to TRUE. Protected entries acquire a read/write lock just like protected procedures. Protected functions acquire a shared read-only lock. Protected entries are not allowed to modify the value or state of the protected object. They can only return values.
The previous example can be implemented using a protected object as shown below.

with Ada.Text_IO; use Ada.Text_IO;

procedure deterministic is
   protected Num is
      procedure Increment;
      function report return Integer;
   private
      Value : Integer := 0;
   end Num;

   protected body Num is
      procedure Increment is
      begin
         Value := Value + 1;
      end Increment;

      function report return Integer is
      begin
         return Value;
      end report;
   end Num;

   task type Adder;

   task body Adder is
   begin
      for I in 1 .. 100_000 loop
         Num.Increment;
      end loop;
   end Adder;

begin
   declare
      A1, A2 : Adder;
   begin
      null;
   end;
   Put_Line (Integer'Image (Num.report));
end deterministic;

The value output by this program is always

200000

Interleaving task access to a shared object

The problem of non-deterministic behavior is compounded when tasks must interleave their behaviors. Consider a problem with two bank accounts and two tasks. Each task transfers money from one account to the other.

with Ada.Text_IO; use Ada.Text_IO;

procedure banking is
   protected type Account is
      procedure Deposit(Amt : Positive);
      procedure Withdraw(Amt : Positive);
      function Report return Integer;
   private
      Balance : Integer := 0;
   end Account;
  
   protected body Account is
      procedure Deposit (Amt : Positive) is
      begin
         Balance := Balance + Amt;
      end Deposit;
     
      procedure Withdraw(Amt : Positive) is
      begin
         Balance := Balance - Amt;
      end Withdraw;
     
      function Report return Integer is
      begin
         return Balance;
      end Report;
   end Account;
  
   type Acct_Idx is (Joe, Bob);
  
   Accounts : array(Acct_Idx) of Account;
  
   procedure Print (Label : String) is
   begin
      New_Line;
      Put_Line(Label);
      for I in Accounts'Range loop
         Put_Line(I'Image & " balance:" &
                    Integer'Image(Accounts(I).Report));
      end loop;
   end Print;
  
  
   task type Transfer (Amt : Positive; From : Acct_Idx; To : Acct_Idx);
  
   task body Transfer is
   begin
      for I in 1..100_000 loop
         Accounts(From).Withdraw(Amt);
         Accounts(To).Deposit(Amt);
      end loop;
   end Transfer;
  
begin
   Accounts(Joe).Deposit(200_000);
   Accounts(Bob).Deposit(300_000);
  
   Print("Beginning balances:");
  
   declare
      T1 : Transfer(Amt => 2, From => Joe, To => Bob);
      T2 : Transfer(Amt => 1, From => Bob, To => Joe);
   begin
      null;
   end;
  
   print("Ending balances:");
  
end banking;

The output of this program is:

Beginning balances:
JOE balance: 200000
BOB balance: 300000

Ending balances:
JOE balance: 100000
BOB balance: 400000

If there had been any deadlock the program would have frozen at some point in its execution. Deadlocks will occur when each of the two tasks above holds a lock on a protected object and tries to simultaneously obtain a lock on the other object. Neither task can make any progress because each is waiting for the other task to release its lock.
As you can see from the example above, Ada protected objects manage locks in a manner which prevents deadlocks.

Comparison of three algorithms for summing an array of integers

This article shares a comparison of the time taken to sum an array of integers. This article tests three algorithms for summing the array. •...