Critical Section

Question

Consider the following code to solve the critical section problem for two processes P₀ and P₁. Initially flag [i] contain false for i = 0 and 1.

Assume i refers to the current process P_i and j refers the other process P_j. If two processes executing above code concurrently then which of the following satisfy the above solution?

A. Mutual exclusion and progress

B. Mutual exclusion and bounded wait

C. Progress

D. None of these

Comments

@Na462....can you explain what is the answer if u got the concept

---

No bro there is only one relationship we can we is that if there is deadlock then no progress...

and Mutual exclusion is not prymary codition for deadlock to be happen above post is proove for that in that there is deadlock and not satisfying tha mutual exclusion just because (p0,p2) or (p0,p3) 0r (p4,p3)  can be present at the same in critical section .

---

 see this   : https://gateoverflow.in/241432/self-evolve#c241460

Answer 1

in this example, When Both are interested, then DEADLOCK happens

Deadlock ===> Mutual Exclusion ( Restriction is that entry section of each process should be same )

 

What about PROGRESS ? ( Below image is from 192 page of GALVIN book )

If dead lock happens, then process selection postponed to indefinitely ===> PROGRESS doesn't satisfied.

 

What about Bounded Waiting ? ( Below image is from 192 page of GALVIN book )

That means if P_i request for CS then Before P_i request grant, there should be a bound on how many times P_j can enter into CS

if DEADLOCK happens, no processes enter into CS, ( even P_j also can not enter) then how we talk about Bounded waiting ?

DEADLOCK ===> we can't judge about Bounded waiting.

For checking Bounded waiting take the possibilities which doesn't lead to DEADLOCK.

in this example, Bounded Waiting is satisfied.

Comments

For a question there are so many possibilities... In this question
1)P0 interested, P1 doesn't interested
2)P0 doesn't interested, P1 doesn't interested
3)P0 doesn't interested, P1 interested
4)P0  interested, P1 interested -------------------- This only lead to deadlock

you can judge Bounded waiting only when there is a no deadlock possible case, take the remaining three cases and analyse it...

---------------------------------------------------------------------------------------------------------------------------------------------
let you and your Brother taking the chocolates from a box without knowing your mom .... ( just assume both are interested to take chocolates )

if you take 2 in one turn , your brother also takes 2
if you take 3  in one turn , your brother also takes 3........ this is Bounded waiting guarenteed

if you didn't take ( i mean not interested ), your brother can take any no.of chocolates.......  this is Bounded waiting guarenteed

if your mom present infront of Box, either you or your brother can't take chocolates ( situation of Deadlock ), then how you can say, your brother taken less no.of chocolates or huge no.of chocolates than you... you can't judge due to he is not able to take it ====> Deadlock present we can't say anything about Bounded waiting

---

1) Having Deadlock and Bounded Waiting ( https://gateoverflow.in/39719/gate2016-1-50 )

Consider the following proposed solution for the critical section problem. There are n processes : P0....Pn−1. In the code, function pmax returns an integer not smaller than any of its arguments .For all i,t[i]

is initialized to zero.

Code for Pi;

do {
    c[i]=1; t[i]= pmax (t[0],....,t[n-1])+1; c[i]=0;
    for every j != i in {0,....,n-1} {
        while (c[j]); 
        while (t[j] != 0 && t[j] <=t[i]);
    }
    Critical Section;
    t[i]=0;
    
    Remainder Section;
    
}  while (true);

 

2) No deadlock and Bounded waiting satisfied ( https://gateoverflow.in/228832/process-synchronisation-self-doubt-bakery-algorithms-code )

Consider the following proposed solution for the critical section problem. There are n processes : P0....Pn−1. In the code, function pmax returns an integer not smaller than any of its arguments .For all i,t[i]

is initialized to zero.

Code for Pi

;

do {
    c[i]=1; t[i]= pmax (t[0],....,t[n-1])+1; c[i]=0;
    for every j != i in {0,....,n-1} {
        while (c[j]); 
        while (t[j] != 0 && t[j] < t[i]);
    }
    Critical Section;
    t[i]=0;
    
    Remainder Section;
    
}  while (true);

 

3) Having Deadlock and Bounded waiting is not satisfied

Let there are three processes P0, P1 and P2

 

4) NO Deadlock and NO Bounded Waiting

LOCK variable Synchronizing Mechanism

---

@Shaik Masthan In the 3rd example, case 1 - it is not a deadlock, but bounded waiting is not satisfied, because process 0 and 2 can enter any number of times( hence no bound), but since, both flag[0] and flag[2] can be false, hence process 1 may finally enter, so it is neither deadlocked nor starved.

3rd e.g case 2 : All process are busy waiting, so it is a deadlock with bounded waiting( bound is 0).

1st example : If for all i,t[i] is initialized to zero, then we have a deadlock with bounded wait(bound is 0). 

Am I CORRECT?

---

The bounded wait will be for some specific conditions and not general(the case when both the process would like to enter the CS). So, can we conclude option D is correct? Also, the video at here provides a good explanation for why it holds mutual exclusion but not progress.

Answer 2

The correct answer is it ensures Mutual exclusion and Bounded Waiting, but Fails at ensuring Progress.

If both processes are able to execute the statement  $ flag[i] = true$ before any process is able to enter the critical section then both processes will be stuck in while loop and no one will be able to enter critical section.

The number of times some process is able to enter critical section after the other process has made its request for critical section is clearly bounded. For example Process 0 tries to enter CS second time but will fail as Process 1 has made $flag[1] = true$.

How mutual exclusion is ensured is easy to prove by contradiction.

Comments

Yes, it ensures ME and bounded wait  not progress for P0 and P1. But if it will not work for multiple process.

---

consider the situation when a process $P_{1}$ wants in critical section then it set flag 1=true now preempt it after that process $P_{2}$ will came and set the flag[2]=true now it goes into while loop but flag[1]=true so it will goes to deadlock.so there is deadlock in it.

---

Please elaborate on the bounded wait part ?

---

According to the definition of progress if one process is not interested in entering the CS then it should not stop the other process from entering it

But in this case when both Po and P1 set the flag to 1 that means both of them are interested in entering the CS but that is not progress

So the above solution provides progress as well.

Also there cannot be deadlock because there is pre-emption

Answer 3

above are providing only MUTUAL exclusion and BOUNDED waiting but failed to provide Progresss.