Mutual
Exclusion in Concurrent Programming
Atomic Operations
Interleaving of the "write to X" operations of
process a and process b leave the value X in an
unexpected state. We must "read/add/write" as an uninterruptible
(atomic) operation.
Busy Waiting on Shared Variables
Entry/Exit Protocol:
loop
Entry
Protocol
Critical Section
Exit
Protocol
Noncritical Section
end
loop
Entry
Protocol
Critical Section
Exit
Protocol
Noncritical Section
end
Peterson's Solution to the Mutual
Exclusion Problem
Three shared variables are used:
Program Mutex_example;
var enter1, enter2: Boolean initial(false,false);
turn: integer initial("P1");
{or "P2"}
process P1;
loop
Entry_Protocol:
enter1:= true;
{announce intent to enter}
turn:=
"P2"; {set priority to other process}
while enter2 and turn = "P2"
doskip {wait if
other process is in and it is his turn}
Critical Section:
Exit_Protocol:
enter1:=false;
{renounce intent to enter}
Noncritical Section:
end
end;
process P2;
loop
Entry_Protocol:
enter2:= true;
{announce intent to enter}
turn:=
"P1"; {set priority to other process}
while enter1 and turn = "P1"
do
skip; {wait if other process is in
and it is his turn}
Critical Section;
Exit_Protocol:
enter2:= false;
{renounce intent to enter}
Noncritical Section:
end
end
end
Spin Locks (processor is busy testing variable until true)
implemented with "TestandSet" operation which returns the current value
of a memory cell and also sets the memory cell to "1"
Unlock(L): Write 0 into L;
Lock(L):
repeat
x := TestAndSet(L);
{read old state and set to "locked"}
until x = 0; {terminate loop if L was "unlocked"}
Example: Parallel
Numerical Integration
a
integral(f(t)dt)
b
If f(t) is velocity of an object, then this definite integral
gives the total distance the object has traveled from time "a" to
time "b". We approximate this integral numerically by sampling the
function f at the two endpoints "a" and "b", and n internal points, spaced w units apart. Using the standard trapezoid rule, we have the following formula
which approximates the definite integral:
w*[f(a)/2+f(a+w) + f(a + 2*w) + --- + f(a + n*w) + f(b)/2]
Parallel Numerical Integration Program in MultiPascal
program NumericalIntegration;
const numproc = 40; (*
number of processes*)
numpoints = 30; (* number of points per process*)
var a,b,w,globalsum,answer:
real;
i: integer; l spinlock;
function
f(t: real); (*function to be integrated*)
begin
- - - (* compute the value of f(t)*)
end;
procedure Integrate(myindex:
integer);
var
localsum, t: real; j: integer;
begin
t := a + myindex * (b - a) / numproc;
(*starting point for this process*)
for j := 1 to numpoints
do
begin
localsum := localsum +
f(t); (*add next sample point*)
t := t + w;
end;
localsum := w * localsum;
lock(w);
globalsum := globalsum + localsum; (*atomic update*)
unlock(w);
end;
begin
- - - (* initialize values of end points
"a" and "b"*)
w := (b-a)/ (numproc*numpoints); (*distance between points*)
forall i := 0 to numproc -
1 do (*create processes *)
integrate(i);
answer := globalsum
+ w/2 * (f(b) - f(a)); (*add end points*)
end.
Semaphores
Skeleton Code for Binary Semaphore
then remove a process from the queue and place in ready list
else sem :=1;
Skeleton
Code for Counting Semaphore