On Programming Dependences Between Parallel Processes

Abstract

In order to study the problems of synchronization between concurrent processes, a distinction is made between the level of the formal models, the level of programming tools, and the level of the implementation practicalities. The model is seen as the semantics of the programming tools, and the implementation as the realization of the semantics at a lower level of abstraction. Different classes of problems of synchronization are distinguished (e. g. exclusions, cooperations) and formal rules are defined to characterize them (the rules of dependence). The different classes are defined upon a common root of basic concepts and hypotheses, in order to be able to draw comparisons between them. An important part of the work is dedicated to a formal treatment of the deadlock problem for the class of problems of exclusions between critical sections. An attempt is made to give an answer to the question of understanding what characterizes a problem of synchronization, how it is related to the choice of programming primitives, and what are the effects of the imp1ementation design.