6
$\begingroup$

I have a doubt regarding bounded waiting.

Deadlock implies no Progress because the processes take indefinite time to decide who will enter the critical section .

But, Does deadlock implies no bounded waiting ?

I think No because bounded waiting is per process and deadlock is for the system.

Moreover, In a deadlock, bounded waiting conditon is not violated and bounded waiting is not with respect to time, but with respect to the number of times the processes enter the critical section before intended process enters the critical system .

Would anyone at least care to correct me or suggest what is right and not right?

Improve this question
$\endgroup$
3
  • $\begingroup$ Look up the term starvation, seems to be what you're looking for. $\endgroup$
    – Ariel
    Sep 21 '16 at 17:03
  • $\begingroup$ I know starvation. Deadlock implies starvation. Starvation is indefinite waiting. $\endgroup$
    – Garrick
    Sep 21 '16 at 17:05
  • $\begingroup$ @Garrick how you are saying deadlock implies starvation deadlock is no process using that resources , but starvation is like not giving chance to only that process so there is progress in starvation but not in deadlock. $\endgroup$
    – Pavan Kumar Munnam
    Dec 14 '16 at 9:22
6
$\begingroup$

You are correct.

Consider the simple synchronization algorithm which denies entry to all processes.

In this case we have both deadlock and bounded waiting, since any process $p$ is not bypassed by some process $p'$ before entering the critical section, so you could say bounded waiting is satisfied with the constant function $f=0$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ "since any process p is not bypassed by some process p′ before entering the critical section, so you could say bounded waiting is satisfied with the constant function f=0." can you plz elaborate this ? $\endgroup$
    – Garrick
    Sep 21 '16 at 18:54
  • 1
    $\begingroup$ It's important to have the precise definition in mind. Talking in the language of critical sections, the protocol satisfies bounded waiting if there exists some function $f$ such that after a process expresses his desire to enter the critical section, he will be bypassed at most $f\left(N\right)$ times, where $N$ is the number of processes. In this case, a process can never be bypassed, since no one enters the critical section. $\endgroup$
    – Ariel
    Sep 21 '16 at 19:00
  • $\begingroup$ Okk, now its clear to me . So, i can say in a deadlock , bounded waiting is satisfied , right ? $\endgroup$
    – Garrick
    Sep 21 '16 at 19:02
  • 2
    $\begingroup$ bounded waiting and deadlock freedom are properties of the protocol, and not of a current snapshot (you could point out a deadlock, but what indication on bounded waiting will sampling the system at some time $t$ provide?). Your original question was if lack of deadlock freedom implies no bounded waiting, which is, as you saw, not true (i took the liberty to rephrase your question a bit). You're now asking something different, does lack of deadlock freedom imply bounded waiting? (again, in light of the beginning of my comment i rephrased your question a bit). cont... $\endgroup$
    – Ariel
    Sep 21 '16 at 19:16
  • 2
    $\begingroup$ To answer this, consider the somewhat stupid protocol which denies entry from $p_1$, always allows $p_2$ in, and on the first occurrence of $p_3$ it flips and denies entry from everyone. This protocol is obviously not deadlock free, but also does not satisfy bounded waiting ($p_1$ may be bypassed by $p_2$ any number of times). $\endgroup$
    – Ariel
    Sep 21 '16 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.