Question about three requirements considering critical section problem

Recently i'm reading the book Operating System Concepts Chapter VI about critical section problem, in section 6.2, we know that an algorithm for solving synchronization problem must meet three requirements: 1. Mutual Exclusion 2.Progress 3.Bounded Waiting. Obviously, if an algorithm meets second requirement (Progress), it doesn't necessarily imply that this algorithm meet Bounded Waiting one because of the process speed or scheduling issue.

However, my question is that, if an algorithm meet Bounded Waiting requirement, can we imply from this that, this algorithm also meet Progress re开发者_高级运维quirement? If no, what's the condition? If yes, why don't we raise ONLY the third requirement and delete the second one since the third one can imply second one. BTW, can any one explain the relationship (and differences) between second one and third one?

---

Concepts of Progress and bounded waiting are totally different.

Bounded waiting means a process can eventually get the lock/mutex whatever. While progress condition means the process can complete its execution. There is a circumstance called live-lock(corresponding to deadlock), in which two or more processes are organized as a process group, all the processes can acquire or release lock, which satisfy Bounded waiting, but the process group cannot progress(or why we call it live-lock. :-)).

Good luck and Regards

---

The first requirement is crystal clear since the main goal of the Mutal Exclusion is ... Hum, to mutually exclude, right?

The second requirement (Progress) is, in a sense, a misnomer. Suppose that a given system has a bunch of processes running concurrently, say, P1, P2, P3, P4 and P5 and none of them are executing the critical section (CS). Eventually, at a given instant, processes P1, P2 and P3 become interested in executing the CS simultaneously. In this situation, the Progress requirement states that only P1, P2 and P3 have the right of choosing between themselves who will be the one that will enter the CS (by no means P4 and P5 will be allowed to influence such a decision). As an aside, this requirement also determines that such a decision can not take forever, therefore its name ("Progress requirement". I think this is a non-descriptive term; "closure requirement" fits better since only the interested processes are entitled to decide who will execute the CS). It's my understanding that this requirement is aimed to prevent live-locks (with all processes saying "please, execute, it is your turn" to each other).

The third requirement (Bounded Waiting) is closely related to the second one. While the Progress requirement says that a decision has to be taken in a finite time by the interested processes, the Bounded Waiting rules that no process will have to wait indefinitely, therefore preventing starvation: after Pn made a request to enter the CS, only a limited number of processes can bypass Pn. Given its definition and in opposition to the second one, this requirement is terrifically named (Bounded Waiting or, sometimes, Bounded Bypass as seen here). In case you understand Portuguese, here goes the definition I found here:

O primeiro requisito é óbvio, pois é o objetivo principal da solução. O segundo diz que se não há processo dentro de região crítica e existem processos desejando entrar, então apenas os processos que desejam entrar participam na decisão de quem entra e essa decisão não é postergada indefinidamente. O terceiro requisito diz que um processo que deseja entrar na região crítica não deve esperar indefinidamente por sua vez; isto é, quando existe algum processo esperando para entrar, deve haver um limite no número de vezes que outros processos entram e saem de suas regiões críticas.