Concepts of Concurrent Programming

1 C U R R I C U L U M M O D U L ESEI-CM-24 Carnegie Mellon UniversitySoftware Engineering InstituteConcepts ofConcurrentProgramming..David W. BustardUniversity of UlsterApril 1990 Approved for public of Concurrent ProgrammingiPrefaceA Concurrent program is one defining actions that may be performedsimultaneously. This module discusses the nature of such programsand provides an overview of the means by which they may beconstructed and executed. Emphasis is given to the terminology usedin this field and the underlying Concepts module is largely concerned with explicit concurrency, whereconcurrent behavior is specified by the program designer. Particularattention is paid to programs that can be considered inherentlyconcurrent, that is, programs that are constructed to control or modelphysical systems that involve parallel activity.

2 The module alsoincludes a brief introduction to performance-oriented concurrency,where concurrency is used to improve program performance by takingadvantage of hardware support for parallel module is divided into three sections. The first deals with basicconcepts in Concurrent Programming , covering characteristicattributes, formal properties, standard design problems, and executiondetails. The second section discusses the steps in constructingconcurrent programs from specification to coding. The final sectionbriefly examines concurrency from the point of view of some commonapplication module gives a foundation for a deeper study of specific topics inconcurrent Programming . It also provides the preparatory material fora study of the Concurrent aspects of application areas such as real-time(embedded) systems, database systems, operating systems, and manysimulation sequential program is really just a Concurrent program in which asingle activity is defined.

3 This is not a fanciful idea. In practice, mostsoftware design techniques yield program structures that are naturallyCapsuleDescriptionScopePhilosop hyiiConcepts of Concurrent ProgrammingSEI-CM-24concurrent, and developers need to go to some lengths to convert suchdesigns into a sequential form (for an example see [Sutcliffe88]).Traditionally, this avoidance of a Concurrent program representationhas occurred for two main reasons. One is the lack of a suitableimplementation language for the application concerned; the other is abelief that the concurrency concept is too difficult for the averageprogrammer. In the experience of practitioners [Brinch Hansen77,Gelernter88], the latter argument is unfounded. Language support hasindeed been a problem but is one that is diminishing rapidly for mostapplication areas [Wegner89].

4 At the current rate of progress it seemslikely that most Programming languages will support therepresentation of concurrency by the turn of the century. In that event,a study of the Concepts of Concurrent Programming will become anessential first step in understanding Programming in general. Thismodule is a contribution to that am very grateful to Gary Ford for his guidance and encouragementthrough every stage in the production of this module. Linda Pesantealso earns my sincere thanks for her infectious enthusiasm and herability to turn apparently neat phrases into much neater ones. I amalso indebted to Karola Fuchs, Sheila Rosenthal, and Andy Shimp, whoprovided an excellent library service that managed to be both efficientand technical content of the module has benefited significantly fromsuggestions made by Mark Ardis, Lionel Deimel, and Robert Firth.

5 Iam also grateful to Daniel Berry, who gathered some initial , I would like to thank Norm Gibbs for the opportunity to producethis module and for his concern that the experience should be was!Comments on this module are solicited, and may be sent to the SEIS oftware Engineering Curriculum Project or to the author:David W. BustardDepartment of Computing ScienceUniversity of UlsterColeraine BT52 1 SANorthern IrelandAcknowledge-mentsAuthor sAddressSEI-CM-24 Concepts of Concurrent Programming1 Concepts ofConcurrentProgramming1. Basic Nature of Concurrent and explicit and Concurrent programs: basic Concurrent , parallel, and Concurrent programs and in Concurrent mutual postponement (or starvation or lockout) of Concurrent Concurrent of of schedulingOutline2 Concepts of Concurrent ProgrammingSEI-CM-242.

6 Program A Requirements state flow A Design A Coding via shared by message Program Evaluation3. Common Operating Systems1. Basic ConceptsThis section provides introductory definitions and discussion of the mainconcepts and terms used in Concurrent Programming . Further explanations,with illustrations, may be found in any basic text in this area [Ben-Ari82,Bustard88, Schiper89, Whiddett87]. Concurrency Concepts are also covered inmost books on operating systems [Deitel84, Habermann76, Lister85] and intexts addressing the Concurrent aspects of specific Programming languages[Burns85, Gehani84, Gehani85, Holt83]. An introduction to distributed andparallel Programming may be found in [Critchlow88, Perrott87].

7 Nature of Concurrent and explicit concurrencyIn principle, most programs may be considered Concurrent in thatthey are likely to: contain independent processing steps (at the block, statement, orexpression level) that may be executed in parallel; or trigger device operations that may proceed in parallel with theexecution of the may be termed implicit concurrency. Explicit concurrency iswhere Concurrent behavior is specified by the program introduction to the detection of implicit concurrency in a programmay be found in [Perrott87]. A more detailed discussion is presentedin [Polychronopoulous88].AnnotatedOutlineSE I-CM-24 Concepts of Concurrent Programming3 Generally, the detection of concurrency implies the identification ofsequences of independent array or arithmetic operations that might beexecuted in parallel ( setting array elements to zero).

8 Suchanalysis is carried out to improve the performance of existingsequential code. Typical improvements are, however, only a fractionof the potential speed-up that might be achieved by restructuring theprograms remainder of this module is concerned with explicit and Concurrent programs: basic definitionsA sequential program specifies sequential execution of a list ofstatements; its execution is called a process. A Concurrent programspecifies two or more sequential programs that may be executedconcurrently as parallel processes [Andrews83]. In many languages,process is also the name of the construct used to describe processbehavior [Bustard88, Gehani89, Holt83]; one notable exception is Ada,which uses the name task for this purpose [Burns85].

9 Concurrent , parallel, and distributedprogramsIn the literature, a Concurrent program is commonly discussed in thesame context as parallel or distributed programs. Unfortunately, fewauthors give precise meanings to these terms and the meanings thatare offered tend to conflict. On balance, the following definitionsseem appropriate: A Concurrent program defines actions that may be performedsimultaneously. A parallel program is a Concurrent program that is designed forexecution on parallel hardware. A distributed program is a parallel program designed forexecution on a network of autonomous processors that do not sharemain memory [Bal89].Thus, Concurrent program is a generic term used to describe anyprogram involving actual or potential parallel behavior; parallel anddistributed programs are sub-classes of Concurrent program that aredesigned for execution in specific parallel processing it is known that a single processor will be used to execute aprogram expressed in a Concurrent form, the concurrency involved issometimes referred to as pseudoparallelism [Bal89, Schiper89].

10 Aquasiparallel program [Schiper89] is a pseudoparallel program inwhich processes execute cooperatively by transferring control to eachother using a coroutine mechanism. (This is the basis of theconcurrency model supported in the Programming language Modula-2[Ford86].) Concurrent programs and concurrentsystemsA Concurrent program is primarily a coherent unit of software. If twopieces of communicating software run concurrently, the result is aconcurrent program when the two pieces form a conceptual whole;otherwise, the situation is viewed as two programs communicatingthrough an agreed protocol. The communicating programs do,4 Concepts of Concurrent ProgrammingSEI-CM-24however, constitute a Concurrent system (or parallel system ordistributed system , as appropriate).