TIFR CSE 2010 | Part B | Question: 32

Question

Consider the following solution (expressed in Dijkstra's guarded command notation) to the mutual exclusion problem.

process P1 is   
begin      
    loop
        Non_critical_section;
        while not (Turn=1) do skip od;
        Critical_section_1;
        Turn:=2;
    end loop
end

 

process P2 is  
begin
    loop
        Non_critical_section;
        while not (Turn=2) do skip od;
        Critical_section_2;
        Turn:=1;
    end loop
end

Initially, Turn$=1$, Assume that the two process run forever and that no process stays in its critical and non-critical section infinitely. A mutual exclusion program is correct if it satisfies the following requirements.

1. Only one process can be in a critical region at a time.
2. Program is a dead-lock free, i.e., if both processes are trying to enter the critical region then at least one of them does enter the critical region.
3. Program is starvation-free; i.e, a process trying to enter the critical region eventually manages to do so.

The above mutual exclusion solution.

• A. Does not satisfy the requirement (1).
• B. Satisfy the requirement (1) but does not satisfy the requirement (2).
• C. Satisfies the requirements (1) and (2), but does not satisfies the requirement (3).
• D. Satisfies the requirement (1) and (3), but does not satisfies the requirement (2).
• E. Satisfies all the requirement (1), (2), and (3).

Comments

From Wikipedia:

"Skip is the empty instruction: do nothing. It is used in the program itself, when the syntax requires a statement, but the programmer does not want the machine to change states."

As a request can someone write an equivalent program to this in a C-like syntax?

---

Mutual exclusion is guaranteed just because only one process will be able to enter critical section ?? As i can see 1 will never execute only 2 will execute does this guaranteed mutual exclusion when only 1 process can execute??

---

I think selected answer is Wrong

Answer should be : E

It is starvation free( because there is a strict alternation ) and it is also mentioned in the question

Assume that the two process run forever and that no process stays in its critical and non-critical section infinitely

Answer 1

Process P1 code can be realized as

begin      
    loop
    Non_critical_section;
    while (Turn!=1) do{
        skip od;}
        Critical_section_1;
        Turn=2;
    end loop
end

Process P2 code is

begin
    loop
    Non_critical_section;
    while (turn!=2) do{
        skip od;}
        Critical_section_2;
        Turn=1;
    end loop
end

 

Given assumption

Assume that the two process run forever and that no process stays in its critical and non-critical section infinitely.

This means that a process will execute its non-critical section for a finite amount of time and it will execute the critical section for a finite amount of time. But will a process get to execute its critical section in the finite amount of time? let's find out.!!

Initially Turn=1.

Only one process will be in critical region at any point of time: How? : The process which gets to execute CS must have completed its while loop. For process P1, this will be true when turn=1 and for process P2 it will be true when turn =2. However, the turn variable can be only 1 or 2 at a time but not both, means one of the processes among P1 and P2 must be waiting in while loop, while another one will get to execute CS. So Mutual Exclusion is ensured.

Yes, the program is deadlock free, for the program to be in a deadlock, both the processes should have been executing in their while loop continuously which is possible only when turn=1 and turn =2 both at the same time which is impossible!!.

Now we need to check whether

Program is starvation-free; i.e, a process trying to enter the critical region eventually manages to do so.

Focus on the word eventually in the definition of "starvation free". A process eventually manages to enter CS. After how long does it get to execute CS, it is not told but it is told it will do so. So, starvation-freedom does not ensure bounded waiting but bounded waiting does ensure starvation freedom because a process will then "eventually" gets to execute CS (it is mentioned in question that no process stays in CS forever).

Suppose that turn=2. Process P1 will keep waiting in while loop. Process P2 will get to execute CS and it is given in assumption that CS will be executed for a finite amount of time. Means after a "finite amount of time" process P2 will come out of CS and set turn=1. This will give chance to process P1. Hence the entry of P1 into CS, it bounded by 1 entry of process P2 into CS.

The same reasoning goes when turn =1.

So, bounded waiting is being ensured. $\rightarrow$ "starvation free".

---

Is Progress being satisfied?

Assume turn=2. Process P2 is not ready to enter CS. Process P1 wants to enter CS, but it will keep looping in it's while loop.

So, a process which is requesting to enter CS while no process is executing in CS is not being allowed to enter CS.

Progress is not Satisfied. Why?  Process P2 is running outside it's CS is blocking process P1 to enter CS and P1 can only enter CS, once P2 has executed it's CS and set turn=1. and this is what the term progress means. No process which wants to enter CS, should be blocked by the process which are not executing in CS.

Final Verdict: (E)

Comments

@Ayush Upadhyaya 

This is the answer i was searching for. Exact explanation what question actually needed. Thanx.

---

As per me, Starvation and bounded waiting are independent on each other.

This question is satisfying 3rd due to description in the question.

---

Can you give a scenario where bounded waiting is satisfied but starvation freedom is not?

---

sir, let in this question,

no process stays in its critical and non-critical section infinitely.

removed and

while(1) present in the Critical section.

then Process which is in the CS never going to be terminated, isn't it starve the another another process ?

---

https://csedoubts.gateoverflow.in/6125/there-any-relation-between-starvation-and-bounded-waiting

---

Yes you are correct. But you should be open to the interpretation in question. Bounded waiting can refer to "finite waiting time" as per many standard resources. And when no process execute for infinite time in CS, bounded waiting does imply no starvation.

Answer 2

Process $P1$ while loop says : while NOT (turn $= 1$) do.. so, it will not enter the while loop until Turn $= 2$ which will make Turn$=1$ false and thus NOT (Turn $=1$) as true.

Process $P2$ for the same reason will enter the while loop.

As process $P2$ has statement Turn $= 1$ at the end of the while loop so the value of Turn will always remain $1$. So, process $P1$ will never enter the while loop and so, this will result in starvation of Process $P1$.

Hence, answer is (C).

Comments

@`JEET

yes, I guess, question needs some editing as I commented.

@Satbir @Mk Utkarsh Can you please check it ?

---

Corrected !

---

@Shaik Masthan

Sir, Thank you. Can you please check the selected answer here. Same problem of indentation is here also and I think the selected answer is wrong.

Answer 3

This is simply another version of strict alternation problem..

So guarantee ME..and Deadlock free...and having starvation.... So option C..

And the confusing part of the code is

While not ( turn=1) do.. Is equivalent to

While ( turn !=1);...means here 1st  P1 will enter into CS(bcz turn=1 initially) then P2 ..now they run alternatively..

Hence Ans is C..

Answer 4

satisfies requirement 1 and 2 but doesnot satisfies the requirement 3.Since Process P1 after executing the CS making Turn=2 ..If  P1 again wants to enter CS, its possible only when P2 will enter CS and make turn =1.But P2 may not want to enter CS that time so Turn will not become 1.So P1 will be Starved. So option is C

Comments

" Assume that the two process run forever and that no process stays in its critical and non-critical section infinitely." as per this statement 2 process runs forever therefore if p1 makes the turn =2 and p2 does not want to execute eventually but p1 do want to run again then p1 will wait till p2 execute its turn .there is strict alteration and violation of progress but we cannot assume that p2 will never execute and p1 has to wait forever viz leads to starvation ...i think ans should be (e) .