edited by
1,207 views
15 votes
15 votes

One of your classmates has suggested the following modified version of a standard scheme for solving the $2$-process critical section problem (CSP).

shared char want[2] = {0,0};
shared int turn = 0;
1.  P_i()
2.  { while (1) {
3.      turn = j;
4.      want[i] = 1;
5.      while (want[j] && turn!=i);
6.      critical_section();
7.      want[i] = 0;
8.      remainder_section();
9.      }
10. }

Show that the above scheme does not guarantee mutual exclusion by constructing an appropriate interleaved sequence of instructions executed by two processes $P_0$ and $P_1$.
Modify the above scheme so that it becomes a correct solution to the $2$-process CSP.

edited by

2 Answers

Best answer
14 votes
14 votes

let process $p1$ enters it executed $3$ line i.e turn=j means it made turn $=0$ (as $p1$ entered so, $i=1$ $j=0$ ) now assume $p1$ got preempted

now process $p0$ enterted it executed $3$ line made turn $=1$ (as $p0$ entered so, $i=0 \ j=1$) 

after that $p0$ executed $4$ line made want$[0]=1$

next $p0$ executed $5$ line while($0$ &&true ) which is false so, it entered critical section

now $p1$ resumed and executed $4$ line made want$[1]=1$

next $p1$ executed $5$ line while($1$ &&false) which is false so, it entered critical section

now, both process $p0$ & $p1$ are in CS at same time so, above solution is wrong

the correct solution is as follows:

just interchange line $3$ & line $4$, than solution becomes correct

shared char want[2] = {0,0};
shared int turn = 0;
1.  P_i()
2.  { while (1) {
3.      want[i] =1;
4.      turn = j:
5.      while (want[j] && turn!=i);
6.      critical_section();
7.      want[i] = 0;
8.      remainder_section();
9.      }
10. }
edited by
0 votes
0 votes
There are two processes Pi and Pj

Order of execution

1. Process Pi -> turn=j;

 // turn=j , want[i]=want[j]=0

2. Process Pj -> turn=i;

 // turn=i, want[i]=want[j]=0

3. Pj-> want[j]=1;

 // turn=i, want[i]=0, want[j]=1

4. Pj-> while(0 && 1) --- False

// Process Pj in critical section

5. Pi-> want[i]=1;

 // turn=i, want[i]=want[j]=1;

6. Pi-> while (1 && 0) ---- False

// Process Pi in critical section


Modification:

Just swap the two statements

turn=j;
wants[i]=1;

To

wants[i]=1;
turn=j;

That's it!
Just by swapping these two lines the code becomes correct.

Related questions

4 votes
4 votes
0 answers
1
17 votes
17 votes
4 answers
3
2 votes
2 votes
2 answers
4
go_editor asked Jun 3, 2016
723 views
Consider relations $R(A, B)$ and $S(B, C)$. Find a propositional formula $\phi$ such that the following two relational algebra expressions produce the same answer.$\pi_{A...