Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Software Patent Institute
Randal E. Bryant: AUTHOR [+4]
In this paper, the main approaches to constructing concurrent programs will be presented and compared. As a basis for comparison, two examples of systems incorporating- concurrent operations have been chosen, and programs for these examples will be presented using the different approaches to concurrent programming. Of particular interest are the semantic issues in language design, i.e. how the computation is expressed, rather than the detailed syntax of the languages. Hence, in the interest of uniformity, the example programs will be written in PASCAL , modified to include the necessary constructs. As will be seen, the different approaches to concurrent programming differ greatly in their expressive power, clarity of expression, and ease and efficiency of implementation.
THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.
Randal E. Bryant California Institute of Technology and Jack B. Dennis Massachusetts Institute of Technology
5027:TM:82 This paper will appear in "Operating Systems Engineering,"' M . Maekawa, ed. , Springer-Verlag, 1982 California Institute of Technology,, order in which the requests are received and processed. Nondeterminacy is essential in many concurrent systems.
The need for high level programming languages which can express the operation ` of a system of concurrent processes has led to the development of programming constructs with which one can express these communication and synchronization operations. Some of these approaches, such as semaphores  and monitors [6,7,19], suppose systems in which all processes have access to a single, shared memory. Others assume that processes communicate by sending messages to one another [4,20,24]. Languages based on actor semantics [15,16,17] carry the message-passing concept even further by considering all primitive operations to be carried out by separate, message-passing processes. Other approaches to concurrent programming have been developed which, instead of viewing a system as a number of communicating, sequential processes, view a program as an unordered set of instructions and permit an instruction to be executed any tithe its operands are ready. This form of program execution can potentially achieve a higher degree of concurrency than is possible with sequential processes. Languages based on this approach are called data flow languages [1,2,11,25,27].
Several issues must be considered when designing programming languages to support concurrent computation. Of primary importance is expressive power. The expressive power of a language, in the context of concurrent systems, means the forms of concurrent operations, and the types of communication, synchronization, and ' nondeterminacy which can be expressed in the language. A language which lacks expressive power will force the programmer to rely on a suitable set of operating system routines to implement desired behaviors. A properly designed language, on the other hand, should have sufficient richness to express these functions directly. Furthermore, if the language lacks expressive power, a programmer may need to resort to awkward or inefficient programming techniques to achieve desired results.
A second issue in the design of 'a language for concurrent programming is the clarity of programs written in the language, that is, how easily the effect of executing a program can be understood by looking at the program. A properly designed language can provide a programmer with the tools needed to write clear and concise programs. To meet this goal, the language must allow programs to be written in a modular fashion, so that the sections of the program can be viewed independently of one another. This property is critical in concurrent system desi...