ME,BW,Progress

Question

while(1) 
{ 
    flag[i] = true; 
    while(flag[j]); 
    /* Critical section */ 
    flag[i] = false; 
    /*Remainder section */ 
    
}

Let flag is declared as Boolean flag[2] and P_i denote one process while P_j denotes other process and i = 1-j. Both processes execute concurrently, then in the above case

A) Mutual Exclusion is satisfied only

B) Mutual Exclusion and Bounded Waiting is satisfied only

C) Progress is satisfied only

D) Mutual Exclusion and Progress is satisfied only

Comments

According to me Mutual Exclusion and Bounded Waiting are satisfied but

Progress is not satisfied as there can be a Deadlock.

---

So, according to you every 2 process solution satisfy BW??

---

Actually DeadLock exists in this situation and you can see following link:

https://cs.stackexchange.com/questions/63730/how-to-satisfy-bounded-waiting-in-case-of-deadlock

---

The discussion given in the below link is very helpful:

https://gateoverflow.in/143607/does-this-satisfy-bounded-wait

This problem has:

1. Livelock (a kind of deadlock)

2. Mutual Exclusion

3. No Progress

4. Bounded waiting

Answer 1

Mutual exclusion and Bounding waiting is satisfied here, progress not.

Mutual exclusion because no two processes can enter critical section at the same time. If one process is in the critical section, then other has to wait.

Bounding waiting because when a process shows the interest to go into the critical section then there is bound on the number of time other processes can go into the critical section and that is 1. (Process is already in the critical section).

Progress is not satisfied here because when both the process execute Flag[i] = true and got preempted then both the processes waiting for each other to release the flag. Which is not going to happen without entering the critical section. So They will wait for indefinite time, No progress. This situation is called "Deadlock".

Comments

I know this code can get into the deadlock. But can we say it does not ensure progress? Galvin's book says nothing about deadlock in the definition of "Progress". Here is the screenshot of Galvin's book with definition of the Progress highlighted: