Two processes, P1 and P2, need to access a critical section of code. Consider the following synchronization construct used by the processes:

/*  P1   */
while (true) {
    wants1 = true;
    while (wants2 == true);
    /* Critical Section */
    wants1 = false;
/* Remainder section */

/*  P2   */
while (true) {
    wants2 = true;
    while (wants1 == true);
    /* Critical Section */
/* Remainder section */

Here, wants1 and wants2 are shared variables, which are initialized to false.

What i have tried =>

Here, mutual exclusion is satisfied and deadlock is there, so no progress .

I am only having a doubt that bounded waiting can also be satisfied here as according to the definition, bound is here 0, so waiting is bounded here ?

Is my understanding correct ?


Bounded waiting is satisfied, the process $p_i$ will never be bypassed by $p_{1-i}$ after changing the value of $w_i$ (wants $i$) to $1$.

If $p_i$ set the value of $w_i$ to $1$, then in order to enter the critical section, $p_{1-i}$ must pass the while loop. This cannot happen until the value of $w_i$ is set to 0. The only place where $w_i$ is set to $0$, is after $p_i$ has finished, which means he will never be bypassed by $p_{1-i}$.

When in doubt, try to prove it yourself. If you agree that the number of times a process may be bypassed is at most $0$, then yes, bounded waiting holds.

| cite | improve this answer | |
  • $\begingroup$ Thanks, for a good explaination. I discussed same thing with you before. Now, i have understood the concept . $\endgroup$ – Garrick Sep 23 '16 at 17:16
  • $\begingroup$ In same kind of problems having deadlock, will there be any condition given about the protocol, that will not ensure bounded waiting. Suppose p1 always runs and never gives up the CPU , then surely bounded waiting is not satisfied ? How to know that condition $\endgroup$ – Garrick Sep 23 '16 at 17:21
  • $\begingroup$ From the examples you saw it is clear that bounded waiting is independent of deadlock freedom. I'm unaware of any meaningful property that together with lack of deadlock freedom will imply no bounded waiting. $\endgroup$ – Ariel Sep 23 '16 at 18:17
  • $\begingroup$ okk, but thanks for this one . I will soon ask the question having deadlock with no bounded waiting . $\endgroup$ – Garrick Sep 23 '16 at 19:02
  • $\begingroup$ I gave you such an example in your previous question. The terms are independent, you can have both bounded waiting/no bounded waiting in both cases of deadlock freedom/no deadlock freedom. $\endgroup$ – Ariel Sep 23 '16 at 19:11

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.