Doubt on progress , bounded waiting and deadlock

Question

 I like to ask you regarding progress, bounded waiting and deadlock

Progress -> No deadlock

Deadlock -> Starvation and no progress

Starvation -> No bounded waiting

 

I have made this after reading  a lot of discussion . Is it the right ?

Correct me if something wrong in it

Answer 1

Progress -> No deadlock

Deadlock -> Starvation and no progress

Starvation -> No bounded waiting

Progress -> No deadlock

Deadlock -> Starvation and no progress .... These Two conclusions are Correct.

---

Starvation -> No bounded waiting .... This is Not true.

There could be Starvation or  even Deadlock in the System, But still Bounded waiting could satisfy.

Many examples could be given but to find intuition about it, one is enough.

Consider this GATE Question : https://gateoverflow.in/1256/gate2007-58

In this Code, Deadlock is Possible and thus Starvation is Possible But Bounded Waiting is Satisfied. 

Informally Speaking, Bounded waiting is defined in the terms of "Number of times" whereas Deadlock or Starvation is defined in the terms of "time". 

 I have made this after reading  a lot of discussion . Is it the right ?

Read some Standard book like Galvin to get clarity in all concepts. 

Comments

oh sorry ! i didn’t notice...by the way i found something hope it helps 

http://www.csl.mtu.edu/cs3331.ck/common/05-Sync-Basics.pdf

check last slides

---

Progress doesn’t mean “No Deadlock”

Take this example ,

P1 :

t2 = 1;

while (t1);

CS

Exit Section;

 

P2 :

t1 = 1;

while(t2);

CS

Exit Section ;

 

Let’s say ,

Initially t1=t2=0

 

Progress basically means that entry of a willing process shouldn’t be under the influence of entry of other processes given that those processes are unwilling to enter CS . So , here let’s say P1 want’s to enter CS and it can do so freely without P2 bothering it and vice versa . But if you look closely it is deadlock prone. So you get my point hopefully . TY

---

Hi Abir,

I don’t know which definition of Progress you are using But I follow Galvin for OS and all my conclusions and answer are based on that. 

Definition of Progress according to Galvin(as it is) :

Progress : If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely.

Now, the example that you have given : 

P1 :

// Entry Section

t2 = 1;

while (t1);

// critical section

CS

// Exit Section;

// remainder section

 

P2 :

// Entry Section

t1 = 1;

while (t2);

// critical section

CS

// Exit Section;

// remainder section

 

Let’s say ,

Initially t1=t2=0

Now assume that there is No process inside CS. And both process show their “wish” to enter by executing their Entry section. P1 makes t2 = 1, P2 makes t1 = 1. Now, both are struck in their while loops. So, deadlock is possible.

But now in this situation, analyze the definition of Progress. 

If no process is executing in its critical section (Yes satisfied)

and some processes wish to enter their critical sections, (Yes, both P1,P2 do)

then only those processes that are not executing in their remainder sections can participate in deciding which will enter its critical section next, (Okay, no problem, satisfied)

and this selection cannot be postponed indefinitely. (This is NOT satisfied)

So, Progress is violated. 

That is the reason : Deadlock implies No progress. 

And every conditional statement is equivalent to its contrapositive so, 

Progress implies No deadlock.

 

If you have any doubt in the above explanation, then I would suggest you visit the following links :

https://pages.mtu.edu/~shene/FORUM/Taiwan-Forum/ComputerScience/004-Concurrency/WWW/SLIDES/05-Sync-Basics.pdf

https://stackoverflow.com/questions/33143779/what-is-progress-and-bounded-waiting-in-critical-section

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