Fairness in parallel programs: the transformational approach

Abstract

Program transformations are proposed as a means of providing fair parallelism semantics for parallel programs with shared variables. The transformations are developed in two steps. First, abstract schedulers that implement the various fairness policies are introduced. These schedulers use random assignments z := ? to represent the unbounded nondeterminism induced by fairness. Concrete schedulers are derived by suitably refining the ?. The transformations are then obtained by embedding the abstract schedulers into the parallel programs. This embedding is proved correct on the basis of a simple transition semantics. Since the parallel structure of the original program is preserved, the transformations also provide a basis for syntax-directed proofs of total correctness under the fairness assumption. These proofs make use of infinite ordinals.