Mutual Exclusion in Concurrent Programming

Atomic Operations

• Operations on shared data
• An update operation consists of a "read, update, write" sequence
• Hardware prevents two primitive operations (read/write) at once, but sequences of instructions must be synchronized to maintain atomic operation integrity
• Example: need for an atomic add to a variable (X+1)

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:

• Process 1

loop
Entry Protocol
  Critical Section
Exit Protocol
  Noncritical Section
end

• Process 2

loop
Entry Protocol
  Critical Section
Exit Protocol
  Noncritical Section
end

Peterson's Solution to the Mutual Exclusion Problem

Three shared variables are used:

• "enteri" is true when process Pi is executing its entry protocol or its critical section
• "turn" records the name of the next process to be granted entry into its own critical section; it is used when both processes execute their respective entry protocols at about the same time

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)

• process tests a variable
• if "set", then process just keeps testing until it is not "set"
• when not "set", set it and continue with next instruction

• Code Skeletons

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

• Each process calculates (a width of W of) the area under the curve using a trapezoid as an approximation.
• Each process then contributes its "localsum" to the globalsum representing the total area under the curve.
• Each process must synchronize (using a spinlock) while adding to the globalsum.
• MultiPascal Code from Lester's book

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

• Spinlocks let a process continue to use the processor (wasting CPU) when waiting for a critical region or resource to become available
• Semaphores release the processor from the currently executing process, save the state of this process, and call the dispatcher to scheduler another process on the processor
• A semaphore can be used to protect a critical region of code

Skeleton Code for Binary Semaphore

• wait(sem): if sem = 1 then sem:= 0; else place process in sem.queue;
• signal(sem): if sem.queue not empty

then remove a process from the queue and place in ready list

else sem :=1;

• A binary semaphore allows just one process in the critical region at a time (mutual exclusion)

Skeleton Code for Counting Semaphore

• Counting semaphore is initialized to "n"
• It then allows n processes into critical region or allocation of n resources
• wait(sem): s:=s-1; if s<0 place process on sem.queue
• signal(sem): s:=s+1; if s <= n then move process from sem.queue to ready list