2
$\begingroup$

Suppose, There are $2$ processes $P1$ and $P2$.

It is given that Mutual Exclusion and Progress are satisfied by these $2$ processes.

Suppose, Programming protocol is designed such that CPU only executes $P1$ and $P2$ is never alloted the CPU, So, here $P2$ starves.


My Question :- Is Bounded Waiting satisfied here ?

I think BW is satisfied, as there exists a bound on the number of processes that may enter after process desires to enter CS. And, here that bound is only 1 as only $P1$ is getting executed and if suppose CPU stops executing $P1$ and then after that only $P2$ will be executed.

Please provide the reason that exactly what happens here ?

$\endgroup$

1 Answer 1

3
$\begingroup$

A little remark first: The bounded waiting (BW) property is defined with respect to algorithms, which is in turn defined as a set of concrete executions. Thus, we cannot conclude whether an algorithm satisfies BW if a specific execution does.


For your question: For the specific execution in which only $P_1$ takes steps, BW is satisfied. However, it is not because "there exists a bound on the number of processes that may enter after process desires to enter CS". Instead, BW is satisfied simply because $P_2$ does not desire to enter the critical section. See the following definition from Mutual Exclusion (wiki).

A $k$-bounded waiting property can provide a bounded waiting guarantee and it requires in every execution, a process can only enter the critical section at most $k$ times while another process is waiting to enter the critical section.

A more precise definition can be found in the Book: The Art of Multiprocessor Programming; Exercise 9 in Section 2.10:

Define $k$-bounded waiting for a given mutual exclusion algorithm to mean that if $D_A^j \to D_B^l$ then $CS_A^{j} \to CS_B^{l+k}$.

Here, $D_A^j$ means process $A$ finishes its doorway section for the $j$-th time, and $CS_A^j$ denotes the interval during which $A$ executes the critical section for the $j$-th time.

In the execution above, $D_{P_2}^j \to D_{P_1}^l$ does not hold because $P_2$ does not take any steps at all. Thus, BW is trivially satisfied.

Suppose that $P_2$ has finished its doorway section (i.e., $D_{P_2}^1$ holds) and then halts. If $P_1$ continues entering and exiting the critical section, then BW is broken.


A little remark again:

I think BW is satisfied, as there exists a bound on the number of processes that may enter after process desires to enter CS.

It seems that you have a misunderstanding about $k$-bounded waiting property. $K$ here is about the number of entering (and exiting) the critical section, instead of the number of processes.

$\endgroup$
8
  • $\begingroup$ Really Nicely explained. Just having a doubt "Can I say, It is not the case that starvation implies BW", as you said that it is trivially satisfied. $\endgroup$
    – Garrick
    Dec 12, 2016 at 11:58
  • $\begingroup$ @Garrick In this specific execution, it is not. $\endgroup$
    – hengxin
    Dec 12, 2016 at 12:00
  • $\begingroup$ Sorry, but I will trouble you just last time. Can you please check my question again. I've edited it with an example . I think If you provide some lines, how BW works in this example .Is BW satisfied for this example ? It will really help me to understand crystal clear . Thanks in Advance .... $\endgroup$
    – Garrick
    Dec 12, 2016 at 14:33
  • 1
    $\begingroup$ @Garrick You are welcome. However, I think you had better open another post, instead of editing the original one. And I will be back tomorrow (I have no time today) and have a look at it. $\endgroup$
    – hengxin
    Dec 12, 2016 at 14:51
  • 1
    $\begingroup$ @Garrick OK. I will have a look at it when I am not that busy. $\endgroup$
    – hengxin
    Dec 14, 2016 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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