Fairness

There is one exception to the requirement that any arbitrary interleaving is a valid execution of a concurrent program. Recall that the concurrent programming ab- straction is intended to represent a collection of independent computers whose in- structions are interleaved. While we clearly stated that we did not wish to assume anything about the absolute speeds at which the various processors are executing, it does not make sense to assume that statements from any specific process are never selected in the interleaving.

Definition 2.6 A scenario is (weakly) fair if at any state in the scenario, a statement that is continually enabled eventually appears in the scenario.

If after constructing a scenario up to the ith state \( s_0, s_1, \dots, s_i\), the control pointer of a process p points to a statement pj that is continually enabled, then \(p_j\) will appear in the scenario as \( s_k \), for \( k > i \). Assignment and control statements are continually enabled. Later we will encounter statements that may be disabled, as well as other (stronger) forms of fairness.

Consider the following algorithm:

Let us ask the question: does this algorithm necessarily halt? That is, does the algorithm halt for all scenarios? Clearly, the answer is no, because one scenario is \( p_1, p_2, p_1, p_2 \dots\), in which p1 and then p2 are always chosen, and q1 is never chosen. Of course this is not what was intended. Process q is continually ready to run because there is no impediment to executing the assignment to flag, so the non-terminating scenario is not fair. If we allow only fair scenarios, then eventually an execution of q1 must be included in every scenario. This causes process q to terminate immediately, and process p to terminate after executing at most two more statements. We will say that under the assumption of weak fairness, the algorithm is correct with respect to the claim that it always terminates.