Synchronization | Self-Doubt

Question

1. Does starvation freedom imply bounded- waiting ?

2. Does bounded- waiting imply starvation freedom ?

Explain with example.

Comments

Both are NO.

---

Not Starvation free, say Starvation rt?

See Starvation not a cause of bounded waiting.

And , Bounded waiting is a cause of starvation

Because if there is bounded waiting we have to wait for that execution of that process, So starvation

---

Questions on page no 22 : https://www.csl.mtu.edu/cs3331.ck/common/05-Sync-Basics.pdf

Answer 1

A). Does starvation freedom imply bounded- waiting ?

Starvation and Deadlock both are w.r.t time and bounded waiting is w.r.t count of number of processes which can enter critical section .

So, what is starvation freedom ?

It says that process will sometime enter CS and that time is finite, But is it bounded ? Not always. (There is a difference between finite and bounded ) . Waiting time may not be bounded, it has no limit .

Hence, first part Answer is No.

B). Does bounded- waiting imply starvation freedom ?

Again, same thing, Bounded waiting does not says that one day process will enter CS . It only says that there is a limit within which it will enter . Starvation freedom says, that one day it will enter .

Instead, Progress + Bounded waiting --> Starvation freedom . How?

Consider a deadlock in a 2 process system . We can say progress is not satisfied . But, bounded waiting can still be satisfied in a 2 process system .

So, bounded waiting condition is not violated during a deadlock . 

Hence, Progress + Bounded waiting --> Starvation freedom and  bounded waiting alone doesn't ensure starvation free .

Comments

Yes, correct.

---

@Kapil,you mentioned in one comment

yes, if process is in a loop in CS, then P1 starves .

But, if P2 is done, surely P1 will run satisfying bounded waiting.

Bounded waiting says that there  should be a bound on number of times other processes can entry their Critical section once a process has requested for entry into critical section.SO here if P1 is in loop in CS,then P2 might not get chance so bounded waiting is not satisfied.Can you check once/?

---

Can you please give an instance where it is free from starvation but bounded waiting is not satisfied?