The Semantics of Shared Variables in Parallel Programming Languages

Candidate: Shulman,Norman Victor

Abstract

Chapter 1 surveys the status of shared variables in parallel programming languages, as well as pointing out the problems inherent in the use of shared variables and the importance of a semantic definition. Our approach to the semantics of shared variables is set forth, and used to highlight the deficiencies of shared variables in Ada. Chapter 2 presents a clear simple informal semantic model of shared variables based on the concepts of atomicity, uniqueness and independence. The model captures the relationships between these concepts so that it can be used to resolve questions regarding packing, mutual exclusion, and local copies of shared variables. Chapter 3 discusses the deficiencies of shared variables in Ada. An informal semantic model of shared variables in Ada is presented in terms of the concepts of atomicity, uniqueness and independence. This informal semantic model serves as the basis for proposing changes to the section of the Ada Reference Manual dealing with shared variables for incorporation in a future revision. Chapter 4 shows how the Ada definition can be modified so that execution of programs such as the on-the-fly garbage collector and the Laplace's equation solver mentioned in Chapter 1 will no longer be qualified as erroneous. New restrictions can be imposed to ensure the independence of operations on shared variables. The informal semantic model also serves as the basis for extending the applicability of the axiomatic techniques of Owicki to a wider class of programs subject to certain optimizations of time and space. Chapter 5 shows that it is possible to relax the restrictions on expressions, and to formulate conditions under which it is safe to keep local copies of shared variables and to pack shared structured objects, while preserving the assignment axiom.