Question

Consider the following program which provides a software approach to mutual exclusion:

Integer array control [1: N]; integer k

Where 1 ≤ k ≤ N, and each element of “control” is either 0, 1, Or 2. All elements of “control” are initially zero; the initial valueof k is immaterial.

The program of the ith process (1 ≤ i ≤ N) is

begin integer j;

L0: control [i] := l;

LI: for j:=k step l until N, l step l until k do

begin

if j = i then goto L2;

if control [j] ≠ 0 then goto L1

end;

L2: control [i] := 2;

for j := 1 step 1 until N do

if j ≠ i and control [j] = 2 then goto L0;

L3: if control [k] ≠ 0 and k ≠ i then goto L0;

L4: k := i;

critical section;

L5: for j := k step 1 until N, 1 step 1 until k do

if j ≠ k and control [j] ≠ 0 then

begin

k := j;

goto L6

end;

L6: control [i] := 0;

L7: remainder of cycle;

goto L0;

end

This is referred to as the Eisenberg-McGuire algorithm. Explain its operation and its key features.

 

Answer 1

This is a program that provides mutual exclusion for access to a critical resource among N processes, which can only use the resource one at a time. The unique feature of this algorithm is that a process need wait no more then N - 1 turns for access. The values of control[i] for process i are interpreted as follows: 0 = outside the critical section and not seeking entry; 1 = wants to access critical section; 2 = has claimed precedence for entering the critical section. The value of k reflects whose turn it is to enter the critical section. 

 

 

Entry algorithm: Process i expresses the intention to enter the critical section by setting control[i] = 1. If no other process between k and i (in circular order) has expressed a similar intention then process i claims its precedence for entering the critical section by setting control[i] = 2. If i is the only process to have made a claim, it enters the critical section by setting k = 1; if there is contention, i restarts the entry algorithm. 

 

 

Exit algorithm: Process i examines the array control in circular fashion beginning with entry i + 1. If process i finds a process with a nonzero control entry, then k is set to the identifier of that process. 

 

 

The original paper makes the following observations: First observe that no two processes can be simultaneously processing between their statements L3 and L6. Secondly, observe that the system cannot be blocked; for if none of the processes contending for access to its critical section has yet passed its statement L3, then after a point, the value of k will be constant, and the first contending process in the cyclic ordering (k, k + 1, ..., N, 1, ..., k – 1) will meet no resistance. Finally, observe that no single process can be blocked. Before any process having executed its critical section can exit the area protected from simultaneous processing, it must designate as its unique successor the first contending process in the cyclic ordering, assuring the choice of any individual contending process within N – 1 turns. 

it must designate as its unique successor the first contending process in the cyclic ordering, assuring the choice of any individual contending process within N – 1 turns.