Coupon Accepted Successfully!


Two – process solution

The processes share two variables:

boolean flag[2];
int turn;
Initially flag[0]=flag[1]= false and turn can be 0 or 1;
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
Critical section
flag[i] = false;
Remainder section



Multiple process solution

This algorithm is also called Bakery algorithm. The common data structures for n processes is
boolean 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
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


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;
waiting[j] = false;
Remainder section
} while(1);


Test Your Skills Now!
Take a Quiz now
Reviewer Name