# Two â€“ process solution

boolean flag[2];

int turn;

Initially flag[0]=flag[1]= false and turn can be 0 or 1;

do

{

flag[i] = true;

turn = j;

while (flag[j] && turn == j);

Critical section

flag[i] = false;

Remainder section

}while(1);

Â

Â

# Multiple process solution

This algorithm is also called Bakery algorithm. The common data structures for n processes isboolean choosing: array [n];

int: array [n];

Initially, these data structures are initialized to false and 0, respectively. For convenience, the following notation is used in the solution:

(a, b) < (c, d) if a < c or if a== c and b < d.

Â

max(a0,a1..., an-1) is a number, k, such that k >= a ; for i = 0,..., n â€” 1

do

{

choosing[i] := true;

number[i] := max(number[Q], number^}, ..,, number[n â€” 1]) + 1;

choosing[i] := false;

for(j=0; j

{

while ( choosing [j] );

while ( (number[j]!=0) && (number[j], j)< (number[i], i) );

}

critical section

number[i] :=0;

remainder section

}while(1)

Â

*;*Â

Â

# Hardware solution for critical section problem

Features of the hardware can make the programming task easier and improve system efficiency. The critical-section problem could be solved simply in a uniprocessor environment if we could disallow interrupts to occur while a shared variable is being modified. Unfortunately, this solution is not feasible in a multiprocessor environment.

Many machines provide special hardware instructions that allow us either to test and modify the content of a word, or to swap the contents of two words, atomically.

Â

Â

The most common instructions provided by hardware are TestAndSet instruction and the Swap instruction.

The

Â

*Test-and-Set*instruction can be defined asÂ

boolean TestAndSet (boolean &target)

{

{

boolean rv = target;

target = true;

return rv;

}

Â

The solution which satisfies all requirements of critical section problem is the following algorithm. Following data structures are common with processes.Â

boolean waiting[n];

boolean lock;

In addition each process has a local boolean variable key.

Â

Â

Initially these data structures have value set to false.

Â

do {

waiting[i] = true;

key = true;

while (waiting [i] && key)

key = TestAndSet (lock);

waiting[i] = false;

Critical section

j = (i+1) % n;

while ((j!=i) && !waiting[j])

j = (j+1) % n;

if ( j == i)

lock = false;

else

waiting[j] = false;

Remainder section

} while(1);

Â

Â

Â