Principles of Concurrent and Distributed Programming - Preface and Table of Contents

Preface

The field of concurrent programming has seen an explosive expansion since the publication of my previous book Principles of Concurrent Programming . Two factors have dictated the need for an entirely new text: the increasing importance of distributed programming and the routine use in industry of languages containing primitives for concurrency such as Ada and occam. The aim of the book remains unchanged: it is an introductory textbook on concurrent programming that focuses on general principles and not on specific systems. The student who masters the material will be prepared not only to read the research literature, but also to evaluate systems, algorithms and languages from a broad perspective.

The intended audience includes advanced undergraduate and beginning graduate students, as well as practicing software engineers interested in obtaining a scientific background in this field. The book assumes a high level of `computer maturity', such as would be achieved by 2-3 years of a computer science major or practical experience. At the very least, courses in data structures, programming languages and computer architecture should be required prerequisites. The scope of the material has been limited to concurrent execution of processes, exclusing the very low-grained concurrency of large parallel computers and at the other extreme the very high-grained concurrency of computer networks. Within this scope, the choice of material has been guided by pedagogical considerations. An algorithm, language or system is described because it demonstrates some fundamental concept or unusual behavior. Pointers to the current state of the art are given in the references.

The book is divided into three parts and a set of appendices. Part I covers classical concurrent programming similar to the treatment in Principles of Concurrent Programming, though there is more use of formal notation. Part II covers distributed programming. Three very different languages are described and compared: Ada, occam and Linda. This is followed by several chapters on distributed algorithms. Part III discusses principles of the implementation of concurrency. A unique feature is the treatment of concurrent programming in real-time systems.

The Ada programming language is used uniformly throughout the book. Ada is probably the only language with embedded concurrent primitives for which high-quality implementations are available on a wide range of computers from mainframes through workstations and down to personal computers. The appendices provide an overview of Ada, as well as code to emulate other primitives (semaphores, monitors, occam, Linda) in Ada. The program fragments in the text have been expanded into complete executable Ada programs. The source code is available on diskette. Also on diskette is a very simple concurrency simulator called AdaS written in Turbo Pascal for a personal computer. AdaS can be used to demonstrate the pathological behavior of the examples in Chapter 3 which a true Ada compiler may not be able to show because it does not let the user precisely control the scheduler.

When teaching the course, the instructor can choose from three difference types of exercises:

  • Solving the theoretical questions appended to the chapters in Parts I and II.
  • Experimenting with the Ada examples and with AdaS.
  • Writing a concurrent program.

A list of suggested problems is given in Section 1.6.

This book was written during a sabbatical year at Brandeis University. I would like to thank the faculty and staff of the university for their support and encouragement. I would also like to thank the Digital Equipment Corporation for the loan of their Ada compiler. Finally, I am indebted to my students both at the Technion and at Brandeis for their patience with me during my experiments with the choice of material and the form of presentation.

Table of Contents

Chapter 1 What is Concurrent Programming? 9
1.1 Introduction 9
1.2 Overlapped I/O and Computation 10
1.3 Multi-programming 11
1.4 Multi-tasking 13
1.5 An Outline of the Book 16
1.6 Concurrent Programming Problems 17
1.7 Further Reading 20
1.8 Exercises 20

Chapter 2 The Concurrent Programming Abstraction 21
2.1 Introduction 21
2.2 Interleaving 23
2.3 Atomic Instructions 27
2.4 Correctness 30
2.5 Inductive Proofs of Correctness 33
2.6 Liveness proofs 36
2.7 Further Reading 37
2.8 Exercises 38

Chapter 3 The Mutual Exclusion Problem 39
3.1 Introduction 39
3.2 First Attempt 41
3.3 Second Attempt 44
3.4 Third Attempt 46
3.5 Fourth Attempt 49
3.6 Dekker's Algorithm 52
3.7 Mutual Exclusion for N Processes 56
3.8 Hardware-Assisted Mutual Exclusion 62
3.9 Further Reading 62
3.10 Exercises 64

Chapter 4 Semaphores 69
4.1 Introduction 69
4.2 Semaphore Invariants 70
4.3 Mutual Exclusion 70
4.4 Semaphore Definitions 73
4.5 Producer-Consumer Problem 76
4.6 Infinite Buffers 77
4.7 Bounded Buffers 80
4.8 Producer-Consumer with Binary Semaphores 83
4.9 Further Reading 85
4.10 Exercises 85

Chapter 5 Monitors 87
5.1 Introduction 87
5.2 Producer-Consumer Problem 88
5.3 Emulation of Semaphores by Monitors 93
5.4 Emulation of Monitors by Semaphores 94
5.5 The Problem of the Readers and the Writers 96
5.6 Correctness proofs 99
5.7 Further Reading 102
5.8 Exercises 103

Chapter 6 The Problem of the Dining Philosophers 105
6.1 Introduction 105
6.2 Solutions using Semaphores 106
6.3 Monitor Solutions to the Dining Philosophers 109
6.4 Further Reading 112
6.5 Exercises 113

Chapter 7 Distributed Programming Models 117
7.1 Introduction 117
7.2 Synchronous or Asynchronous Communication 118
7.3 Process Identification 119
7.4 Data Flow 120
7.5 Process Creation 121
7.6 Further Reading 122

Chapter 8 Ada 123
8.1 Introduction 123
8.2 Rendezvous 124
8.3 The Select Statement 127
8.4 Programming with the Rendezvous 131
8.5 Select in the Calling Task 134
8.6 Dynamic Task Creation 136
8.7 Priorities and Entry Families 139
8.8 Further Reading 140

Chapter 9 occam 143
9.1 Introduction 143
9.2 Concurrent Programming in occam 143
9.3 Matrix Multiplication in occam 146
9.4 occam Syntax 148
9.5 Further Reading 151

Chapter 10 Linda 153
10.1 Introduction 153
10.2 Matrix Multiplication in Linda 157
10.3 Further Reading 159

Chapter 11 Distributed Mutual Exclusion 161
11.1 Introduction 161
11.2 Outline of the algorithm 162
11.3 Details of the Algorithm 164
11.4 Correctness of the Algorithm 169
11.5 Further Reading 171
11.6 Exercises 172

Chapter 12 Distributed Termination 173
12.1 Introduction 173
12.2 The Dijkstra-Scholten Algorithm 176
12.3 Termination using Markers 181
12.4 Snapshots 184
12.5 Further Reading 189
12.6 Exercises 189

Chapter 13 The Byzantine Generals Problem 191
13.1 Introduction 191
13.2 Description of the Problem 192
13.3 Algorithm for Four Generals 194
13.4 Impossibility for Three Generals 195
13.5 Further Reading 196
13.6 Exercises 196

Chapter 14 Single Processor Implementation 201
14.1 Introduction 201
14.2 Memory allocation 202
14.3 Process control blocks 205
14.4 Priorities 206
14.5 The Ada Rendezvous 207
14.6 Further Reading 210

Chapter 15 Multi-processor Implementation 211
15.1 Introduction 211
15.2 occam on the Transputer 212
15.3 Implementations of Linda 214
15.4 Ada on Distributed Systems 216
15.5 Further Reading 218

Chapter 16 Real-Time Programming 219
16.1 Introduction 219
16.2 Synchronous and Asynchronous Systems 220
16.3 Interrupts and Polling 225
16.4 Interrupt Handlers and Software Processes 226
16.5 Nested Interrupts 230
16.6 Scheduling Algorithms for Real-Time 230
16.7 Priority Inversion in Ada 232
16.8 Further Reading 233

Appendix A Ada Overview 235
A.1 Introduction 235
A.2 Types and Statements 236
A.3 Packages 239
A.4 Further Reading 243

Appendix B Concurrent programs in Ada 245
B.1 Introduction 245
B.2 Common memory 247
B.3 Semaphores 249
B.4 Monitors 253

Appendix C Implementation of the Ada emulations 259
C.1 Introduction 259
C.2 occam 259
C.3 Linda 269

Appendix D Distributed Algorithms in Ada 285
D.1 Introduction 285
D.2 The TM algorithm 285
D.3 The Ricart-Agrawala algorithm 294
D.4 The Dijkstra-Scholten algorithm 294
D.5 Snapshots 294