×

Principles of concurrent programming. (English) Zbl 0534.68005

Englewood Cliffs, New Jersey etc.: Prentice-Hall, Inc. XV, 172 p. $ 17.95 (1982).
This is an elegant textbook treating - ”within the overall context of writing correct software” - ”the single, but extremely important technical point of synchronization and communication in concurrent programming”. There are 7 Chapters: 1. What is concurrent programming? 2. The concurrent programming abstraction. 3. The mutual exclusion problem. 4. Semaphores. 5. Monitors. 6. The Ada rendezvous. 7. The dining philosophers. - and an Appendix (Implementation kit). The book is for advanced undergraduate students or practicing programmers - actually, maturity in computer science is the only prerequisite. In presenting the material, the author stresses that ”formal verification seems indispensable” - as ’usual’ debugging is impossible in concurrent programming. Therefore the concurrent programs presented are verified using precise, though informal, arguments; this verification is based on non-interference and uses an operational approach (the axiomatic approach is mentioned only in a comment to the reference list).
The author emphasizes that ”implementation of parallelism... is essentially independent of concurrent programming”, and such an abstraction-oriented approach is the correct one in presenting this important and nontrivial topic. The presentation is very clear and concise throughout (sometimes, maybe, too concise - the 7 Chapters occupy only 118 pages!). The primitives are introduced in a ”historical” manner - from Dekker’s algorithm to Ada rendezvous, and the author often succeeds in conveying his enthusiasm to the reader. Moreover, the author correctly justifies more powerful, higher level primitives showing how the use of low-level primitives leads to correct, but unnecessarily complex solutions. The reader will clearly appreciate the simplicity and elegance of solutions which use more powerful primitives like monitors, conditional critical regions, or Ada rendezvous. However, the presentation is often centered around semaphores - a rather low-level primitive - probably because they can be simulated very simply, using the author’s ”implementation kit” - the complete text of an (extended and simplified) Pascal-S compiler and its stack-machine object code interpreter. Namely, N. Wirth’s ETH compiler was simplified and augmented by the author (adding the semaphore and cobegin-coend constructs) and successfully used for class exercises ”to demonstrate (the hard way) to students the difficulties of concurrent programming”. Many of the exercises use semaphores and ask the student to ”study and test the programs and show that...” these programs are more difficult to comprehend than the monitor or critical region solutions to the same problems (which are also given in the book and which use primitives that, unlike semaphores, ”contribute to the clarity and reliability of the resulting system”). One has only to agree with the author about the hard way of such a presentation that must be used by an instructor who ”does not have access to one of the more serious systems” and so must use the implementation kit. (Answers to at least some of the exercises would have been helpful, but they are not given). The analogy between semaphores and goto statements suggests itself, but, unfortunately, is not mentioned.
The program design considerations actually shown in the book are absent in the exercise programs, and the ”ex post facto proof methods” (C. Jones) used by the author seem to be not the best ones possible. For some alternatives, see, e.g., the presentation in [A. N. Habermann, Operating System Structures, Math. Cent. Tracts 63, 89-118 (1975; Zbl 0351.68009)] showing programs ”correct by construction”, and also the important paper [E. W. Dijkstra, A personal summary of the Gries- Owicki theory (EWD554), in: E.W.Dijkstra, Selected writings on computing: A personal perspective (Berlin 1982; Zbl 0497.68001)]. Nevertheless, the author does introduce such important notions as an invariant of a computation (discussing semaphores) and an abstract data type approach (discussing monitors). Moreover, in demonstrating the sleeping barber solution of the producer-consumer problem the author clearly shows how the separation of concerns principle works: the efficiency concern improves the ”obvious” solution obtained using only the correctness concern. The author provides a very good annotated reference list to which this reviewer can add only the papers already mentioned as well as the recent, more ”modern”, survey [G.R. Andrews, and F. B. Schneider, Comput. Surv. 15, 3-43 (1983; Zbl 0515.68025)]. These references as well as the ones listed by the author share one characteristic: they are usually very well-written, as is the book under review. Summing up, despite the shortcomings this book does present a good and adequate introduction to the nontrivial subject of concurrent programming and may be highly recommended as a textbook.
Reviewer: H.Kilov

MSC:

68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68N99 Theory of software
68N25 Theory of operating systems