Test by Bikram | Operating Systems | Test 2 | Question: 14

Question

Consider the $2$ – process solution to the Critical Section problem (here i refers to the current process and j is the other process )

Process Pi

repeat
flag[i] = true;
while ( flag[j] ) do no-op;
< critical - section >
flag[i] = false;
< remainder - section >
until false;

Which of the following statement is true?

• A. Mutual exclusion and Bounded waiting are satisfied
• B. Only mutual exclusion is satisfied
• C. Mutual exclusion is violated
• D. Mutual exclusion and progress requirements are met

Comments

Discussion thread in FB:

https://www.facebook.com/groups/gateoverflow/permalink/652351738303373/

Answer 1

The solution is for process P_i

flag [i] = true means Pi ready to enter its critical section .

• It satisfies Mutual Exclusion :  Mutual exclusion is ensured through the use of the flag and turn variables. Process P_i  set it's flag to true, so only this process will succeed . The waiting process P_j can only enter its critical section when the other process P_i updates the value of turn.

In this code snippet there is no such scope for process P_j .

• Progress is not satisfied : if a process wishes to access their critical section, it can set their flag variable to true and enter their critical section. It sets turn to the value of the other process only upon exiting its critical section. If this process wishes to enter its critical section again before the other process it repeats the process of entering its critical section and setting turn to the other process upon exiting. 

 But in this code section we can see  it is possible only P_i is executing and there is no turn for P_j hence no progress .

That means there deadlock  is possible. If p1 process stop after flag[1] = true, then p2 can't go into CS. After flag[2] = true, process p1 can't go into the CS. This satisfy ME condition too .

• Bounded wait is satisfied :  

   there are 2 way we can define BW :

• in terms of time ( indefinite waiting , that the CMU link is talking about [1])
• in terms of number of other process in CS ( what we need to follow and given in book like Galvin )

1. For first case , you see deadlock is there so BW is not satisfy as there is indefinite waiting.
2. For 2nd case we just need to check for each process before it enter how many other process can enter into CS ( this is rather more simple way to check , here we don't consider that the system is in deadlock or no progress possible ..etc , we just check when a process request and before that request granted how many other process enter into CS ) .

when we check BW is satisfied or not for 2 process CS problem, we always check how many times other process can enter into CS before our requesting process enter. 

That's the only point we need to consider. And no need to check if deadlock exist or not while considering BW , as per Galvin definition.

This does guarantee mutual exclusion, and bounded wait. 

Hence the correct option is A .

For more clarity , see below reference link , check  Slide # 9, Algorithm 2

Reference : [ click here ]  < slide from galvin >

[1] http://www.cs.cmu.edu/~gkesden/412-18/fall01/ln/lecture6.html 

Comments

@AnilGoudar

As you said "as even Pj can also start execution like Pi. How is the turn of Pj restricted by Pi ? " 

There is deadlock so no progress.

ME is satisfied.

Bounded Waiting is satisfied.

https://www.facebook.com/groups/gateoverflow/permalink/652351738303373/

---

The Galvin slides link clearly mentions that progress is "If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely." then I don't understand why the above method does not satisfy progress because one process cannot prevent another process from entering into critical segment if the critical segment is not accessed by any other process.

So why is the solution not D?

---

i think the solution is d bcoz suppose if at a time both processes comes and start executing make flag[process]=true.

now both flag value is true so they both wait for each other to make flag value false.. i.e deadlock occurs..

and in case of deadlock there is no bounded waiting

Answer 2

Mutual Exclusion is satisfied. Because when a process detects other's flag to be TRUE, it waits.

---

Now the bigger question that remains is what else is satisfied — Bounded Wait or Progress?

Check this from Galvin.

»»» Progress is when a process that doesn't wish to enter its Critical Section poses no problems for a process that wishes to enter.

Here, if a process doesn't wish to enter CS, it won't execute the entry section => its flag won't be set to TRUE.

So Progress is satisfied.

But wait.

Suppose $P_i$ got preempted right after making its flag = TRUE.

Then $P_j$ started to execute, and it put its flag = TRUE as well.

Now they're in a deadlock.

When there's deadlock, there's no progress.

 

»»» Bounded Wait is violated when there's no upper limit to the number of times a process enters its Critical Section before it gives another process a chance to enter.

Here, if both the processes want to enter — they'll set their flags to TRUE. And this 

while ( flag[j] ) do no-op;

will prevent $P_i$ to keep entering its Critical Section without giving $P_j$ its turn. Vice versa.

Bounded Wait is satisfied.

 

Option A