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.
No comments:
Post a Comment