Bounded waiting and starvation free in critical section problem

Question

I have 4 questions regarding relation between starvation and bounded waiting.

1.Does starvation-freedom imply deadlock-freedom?

My Answer:

From here,

definition of starvation free is

Freedom from Starvation -:Every thread that attempts to acquire the lock eventually succeeds

Freedom from Deadlock -:for some thread attempts to acquire the lock, then some thread (not necessarily the thread referred to in the if statement; emphasis added) will succeed in acquiring the lock.

So, I can state that starvation-freedom imply deadlock-freedom

2.Does starvation-freedom imply bounded-waiting?

Approach-:

Starvation free implies that every thread that will attempt to acquire lock will succeed.

On the other hand

Bounded wait insures that there exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections after a process has made request to enter its critical section and before that request is granted.

Which implies that there must not be any starvation.

Am i correct? But the explanation is here confuses me.

Answer 1

No, starvation-free doesn't imply bounded waiting.

For instance, consider a procedure that never even attempts to acquire any lock; but the amount of time it takes is variable and can be arbitrarily long. Then there is no bound on the amount of time it might take to complete its operation.

Here is another example of how it can fail. Starvation-free means that every attempt to acquire the lock eventually succeeds -- but that says nothing about how long it might take. Maybe the amount of time it will take to acquire the lock is variable and can be arbitrarily long -- there is no upper bound on how long it takes to acquire the lock. Then a procedure that first attempts to acquire the lock before doing anything else won't satisfy bounded waiting.

Answer 2

so i can state that starvation-freedom imply deadlock-freedom

If you find this statement difficult, you can convert it to its contrapositive statement which is Deadlock implies starvation. It is easier to observe this statement is true. Hence starvation freedom implies deadlock freedom is also true.

For Bounded wait there must not be starvation

This statement is false. See this example:-

flag[0]=flag[1]=false;  
i=j-1;   
while(1){  
    flag[i]=true;  
    while(flag[j]);    
    //  critical section  
    flag[i]=false;  
    //  remainder section  
}

At line no. 5 both processes may get stuck forever causing deadlock( and hence starvation also). But bounded waiting will be ensured because maximum number of times process i can enter the critical section before process j is allowed to enter the critical section is zero.

Answer 3

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

1. Does starvation-freedom imply deadlock-freedom? Yes. Since starvation-freedom says a process will eventually enter its CS, all processes will enter their CS. So, no two processes are deadlocked.
2. Does starvation-freedom imply bounded-waiting? No. starvation-freedom does not put a bound. So, though each process will enter its CS, one process may get more than bounded turns to enter its CS before another process enters its CS, hence breaking the bounded-waiting requirement