THE ORIGIN OF
CONCURRENT PROGRAMMING
From Semaphores to Remote Procedure CaUs
Springer Science+Business Media, LLC
THE ORIGIN OF
CONCURRENT PROGRAMMING
From Semaphores to Remote Procedure Calls
Edited by PER BRINCH HANSEN
Springer
Per Brinch Hansen
Center for Science and Technology
Syracuse University
Syracuse, NY 13244
USA
[email protected]
Library of Congress Cataloging-in-Publication Data
The origin of concurrent programming: from semaphores to remote procedure calls/
editor, Per Brinch Hansen.
p. cm.
Includes bibliographie al references.
1. Parallel programming (Computer science) 1. Brinch Hansen, Per, 1938-
QA 76.642.075 2002
005.2'.75-dc21
2002016002
Printed on acid-free paper
Ada is a trademark of the United States Government. IBM is a trademark of IBM. Java is a
trademark of Sun Microsystems, Inc. occam and Transputer are trademarks of Inmos, Ltd. PDP-
11 is a trademark of Digital Equipment Corporation. Unix is a trademark of X/Open Company,
Ltd.
ISBN 978-1-4419-2986-0 ISBN 978-1-4757-3472-0 (eBook)
DOI 10.1007/978-1-4757-3472-0
2002 Springer Science+Business Media New York
Originally published by Springer-Verlag New York, Inc. in 2002.
Softcover reprint ofthe hardcover 1st edition 2002
All rights reserved. This work may not be translated or copied in whole or in part without the
written permission of the publisher Springer Science+Business Media, LLC,
except for brief excerpts in connection with reviews or scholarly analysis. Use
in connection with any form of information storage and retrieval, electronic adaption, computer
software, or by similar or dissimilar methodology now known or hereafter developed is forbidden.
The use in this publication of trade names, trademarks, service marks, and similar terms, even if
they are not identified as such, is not to be taken as an expression of opinion as to whether or not
they are subject to proprietary rights.
9 8 7 6 543 2 1 SPIN 10860478
www.springer-ny.com
FOR JONATHAN GREENFIELD
PREFACE
If you want to discover new ideas in computing, textbooks won't help you.
You need to find out how the masters of the field did it. You need to read
their original papers!
That's why I put twenty-four papers together in a previous volume called
Classic Operating Systems: Fmm Batch Pmcessing to Distributed Systems
(Springer-Verlag, 2001).
But there is another side to this story. You cannot build (or understand)
a modern operating system unless you know the principles of concurrent
programming. The classic papers in the present book cover the major break-
throughs in concurrent programming fmm the mid 1960s to the la te 1970s.
These pioneering contributions have remained the foundation of concurrent
programming in operating systems and parallel computing.
All the papers were written by the computer scientists who invented these
ideas. Apart from a brief summary, I let the papers speak for themselves.
This book is for programmers, researchers, and students of electrical engi-
neering and computer science. I assume that you are familiar with operating
system principles.
I thank the copyright owners for permission to reprint these papers. A
footnote on the title page of each paper gives fuH credit to the publication in
wh ich the work first appeared, including the name of the copyright holder.
PER BRINCH HANSEN
Syracuse University
vii
CONTENTS
OVERVIEW
The Invention of Concurrent Programming 3
PER BRINCH HANSEN (2001)
PART I CONCEPTUAL INNOVATION
1 Cooperating Sequential Processes 65
EDSCER W. DIJKSTRA (1965)
2 The Structure of the THE Multiprogramming System 139
EDSCER W. DIJKSTRA (1968)
3 RC 4000 Software: Multiprogramming System 153
PER BRINCH HANSEN (1969)
4 Hierarchical Ordering of Sequential Processes 198
EDSCER W. DIJKSTRA (1971)
PART II PROGRAMMING LANGUAGE CONCEPTS
5 Towards a Theory of Parallel Programming 231
C. A. R. HOARE (1971)
6 An Outline of a Course on Operating System Principles 245
PER BRINCH HANSEN (1971)
7 Structured Multiprogramming 255
PER BRINCH HANSEN (1972)
8 Shared Classes 265
PER BRINCH HANSEN (1973)
9 Monitors: An Operating System Structuring Concept 272
C. A. R. HOARE (1974)
PART III CONCURRENT PROGRAMMING LANGUAGES
10 The Programming Language Concurrent Pascal 297
PER BRINCH HANSEN (1975)
IX
x CONTENTS
PART IV MODEL OPERATING SYSTEMS
11 The Solo Operating System: A Concurrent Pascal
Program 321
PER BRINCH HANSEN (1976)
12 The Solo Operating System: Processes, Monitors
and Classes 334
PER BRINCH HANSEN (1976)
13 Design Principles 382
PER BRINCH HANSEN (1977)
PART V DISTRIBUTED COMPUTING
14 A Synthesis Emerging? 397
EDSGER W. DIJKSTRA (1975)
15 Communicating Sequential Processes 413
C. A. R. HOARE (1978)
16 Distributed Processes: A Concurrent Programming
Concept 444
PER BRINCH HANSEN (1978)
17 Joyce-A Programming Language for Distributed
Systems 464
PER BRINCH HANSEN (1987)
PART VI IMPLEMENTATION ISSUES
18 SuperPascal: A Publication Language
for Parallel Scientific Computing 495
PER BRINCH HANSEN (1994)
19 Efficient Parallel Recursion 525
PER BRINCH HANSEN (1995)
