1,089 views
0 votes
0 votes
Assume that 2 processes P0 and P1 share one global boolean array flag[] and integer variable 'turn'. Initially flag[0] and flag[1] are zero.Consider the following code executed by processes Pi where i=0 or 1:

while(true)

{

flag[i]=true;

while(flag[i])

{

if(turn==j)

{

flag[i]=false;

while(turn==j);

flag[i]=true;

}

}

<critical section>

turn=j;

flag[i]=false;

<remainder section>

}

If current process is Pi then other process is Pj where j=1-i.

The above solution satisfies:

a Mutual Exclusion

b Mutual exclusion and progress

c Mutual exclusion, progress and bounded waiting

d None of these

 

The answer key says c but please explain how is there bounded waiting.

1 Answer

1 votes
1 votes

First of all, the above code is a standard PETERSON'S SOLUTION FOR SYNCHRONIZATION OF TWO PROCESSES.

Now lets move to your question: How is bounded waiting satisfied here?

BOUNDED WAITING: After a limited number of attempts, the interested process must be allowed to enter the critical section.

Flow of above code:

  1. Process 'i' declares itself as interested to enter the CS by marking its flag=true.
  2. Now, while 'i' is interested, it checks whether the turn is given to 'j'?
  3. If it is process j turn now, then it marks itself as not interested to enter CS by setting flag=false.
  4. Process 'i' keeps on checking if process j turn has ended or not in the next while loop (while(turn==j);)
  5. Process i will break out of while loop only when process j makes turn = i.
  6. After this, the process i will mark itself interested by setting flag=true.
  7. Then , it will enter CS, and again will give turn to process j by setting turn=j just before leaving CS.

In this way, the two processes will keep alternating.

The main thing to note here is that, a process a will have finite statements in its CS to execute, that eventually means that the statement "turn=j" will be executed by each process surely.

I know why you got this doubt.The statement turn=j made you think that everytime, the turn is given to process j. But the question mentions that, if current process is Pi then the other process is Pj where j=1-i.

So if i=0,then j=1 and if i=1, then j=0...

I recommend you to watch this:https://youtu.be/XAsAAJSotA4

Happy Learning

Related questions

1 votes
1 votes
2 answers
1