Is bounded waiting satisfied in the 2 Process Solution?

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 ?

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.

• 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. Dec 12, 2016 at 11:58
• @Garrick In this specific execution, it is not. Dec 12, 2016 at 12:00
• 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 .... Dec 12, 2016 at 14:33
• @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. Dec 12, 2016 at 14:51
• @Garrick OK. I will have a look at it when I am not that busy. Dec 14, 2016 at 10:52