Software Systems Principles: A Survey

Table of Contents
Preface xix
1. Introduction
Prologue
What Are Software Systems?
1.2.1 General Characteristics
1.2.2 Common Technical Characteristics
Operating Systems —An Example
Basic Concepts
Assumed Background for the Study of Software Systems
1.5.1 Machine Organization
1.5.2 Memory Organization
1.5.3 Programming
1.5.4 Data Structures
How to Use This Book
Editorial Notes
UNIT I: HARDWARE 18
2. Computer Structures (prepared especially for this text
by Samuel H. Fuller) 19
2.1 Prologue 19
2.2 Computer Structures and the PMS Notation 21
2.3 Data Representations 27
2.4 Computer Architecture 31
2.4.1 The Processor and Memory States 31
2.4.2 Instruction Sets 34
2.4.3 Memory Structures and Protection Mechanisms 44
2.4.4 Input/Output and Interrupt Structures 47
2.5 Important Implementation Concepts 52
2.5.1 Instruction Overlap and Pipelining 53
2.5.2 Interleaved Memories 57
2.5.3 Caches and Other Buffer Memories 58
2.6 Epilogue 62
2.7 Exercises 62
Microprogramming 65
3.1 Prologue 65
3.1.1 Processor Organization 65
3.1.2 Control Implementation 67
3.2 "Microprogramming Concepts" (prepared especially for this
text by Michael J. Flynn) 70
3.3 "System Design of a Dynamic Microprocessor" (reprinted
paper by Robert W. Cook and Michael J. Flynn) 85
3.4 Epilogue 99
3.5 Exercises 100
UNIT II: OPERATING SYSTEMS TECHNOLOGY 102
4. Process Management 111
4.1 Prologue 111
4.2 Fundamentals 112
4.2.1 Notation 113
4.2.2 States 115
4.3 Realization of Processes 117
4.4 Process Control Problems 119
4.4.1 Mutual Exclusion 120
4.4.2 Synchronization 121
4.4.3 Deadlock 122
4.4.4 Communication 123
4.5 Mutual Exclusion and Synchronization 123
4.5.1 An Illustrative Example 123
4.5.2 Synchronization Primitives 128
4.5.3 Synchronization Primitive Implementation 131
4.6 Communication 132
4.6.1 "The Multics Interprocess Communication Facility"
(reprinted paper by Michael J. Spier and Elliott I.
Organic k) 133
4.7 Deadlocks 153
4.7.1 "System Deadlocks" (reprinted paper by E. G.
Coffman, Jr., M. J. Elphick, and A. Shoshani) 153
4.8 Epilogue 167
4.9 Exercises 167
5. Input/Output Systems 169
5.1 Prologue 169
5.2 An Illustrative Example and Two Conceptualizations 171
5.2.1 An Example 171
5.2.2 I/O System Organization 178
5.3 Primary Functions of I/O Systems 180
5.3.1 Transferring Information 180
5.3.2 Matching Logical and Physical Characteristics 182
5.3.3 I/O Resource Sharing 183
5.3.4 Error Handling and Recovery 184
5.4 Important Mechanisms Used in I/O Systems 185
5.4.1 Interrupts, Interrupt Handlers, and Polling 185
5.4.2 Physical Device Descriptions 188
5.4.3 Pseudo and Virtual I/O Devices 189
5.5 Examples of I/O Systems 190
5.5.1 I/O in a Fortran System 190
5.5.2 The Multics I/O System 193
5.6 Epilogue 197
5.7 Exercises 198
6. Primary Memory Management 199
6.1 Prologue 199
6.1.1 Memory Management Problems 200
6.1.2 Dynamic Relocation 202
6.1.3 Advanced Techniques 203
6.2 "Virtual Memory" (reprinted paper by Peter J. Denning) 204
6.3 Recent Developments 257
6.3.1 Hardware Support 257
6.3.2 Measurement of Program Characteristics 258
6.3.3 Program Structuring 258
6.4 Epilogue 259
6.5 Exercises 260
7. General Resource Allocation 262
7.1 Prologue 262
7.2 Fundamentals 263
7.2.1 Policy Questions 264
7.2.2 Mechanisms 265
7.2.3 Connections to Other Allocation Problems 266
7.3 Typical Organization for Processor Allocation 266
7.4 Scheduling and Resource Allocation in Computer Systems
(prepared especially for this text by R. R. Muntz) 269
7.4.1 Introduction to Queueing Models 271
7.4.2 Scheduling Disciplines 274
7.4.3 Batch System Scheduling 292
7.4.4 Scheduling in Interactive Systems 296
7.4.5 CPU and I/O Scheduling 302
7.5 Epilogue 304
7.6 Exercises 305
UNIT III: INFORMATION STORAGE AND PROTECTION 308
8. File and Data Management Fundamentals 309
8.1 Prologue 309
8.2 Some Initial Concepts 311
8.2.1 Terminology 311
8.2.2 Logical Versus Physical Organization 312
8.3 "Elements of Data Management Systems" (reprinted paper
by George G. Dodd) 314
8.4 Additional Concepts 334
8.4.1 Directories 334
8.4.2 Backup and Recovery 336
8.5 Epilogue 336
8.6 Exercises 337
9. File and Data Management System Structures 338
9.1 Prologue 338
9.2 "A Modular Approach to File System Design" (reprinted
paper by Stuart E. Madnick and Joseph W. Alsop, II) 340
9.3 Data Structures and Accessing in Data Base Systems 361
9.3.1 Evolution of Information Systems 362
9.3.2 Information Organization 364
9.3.3 Data Representation and the DIAM 367
9.3.4 Comments on the Use of Data Models 368
9.4 Epilogue 369
9.5 Exercises 369
10. Information Protection 370
10.1 Prologue 370
10.2 "Computers and Privacy: A Survey" (reprinted paper by
Lance J. Hoffman) 373
10.3 Additional Protection Mechanisms 390
10.3.1 Protection Rings 390
10.3.2 Hardware and Software Structures 390
10.3.3 Data Base Security 391
10.4 Epilogue 391
10.5 Exercises 392
UNIT IV: LANGUAGES AND THEIR PROCESSORS 393
11. Survey of Computer Languages 394
11.1 Prologue 394
11.2 Language Types and Characteristics 395
11.3 Feature Survey of Common Programming Languages 398
11.3.1 Fortran 399
11.3.2 Algol 401
11.3.3 Basic 405
11.3.4 APL 406
11.3.5 Cobol 410
11.3.6 PL/I 412
11.4 Job Control and Terminal Command Languages 415
11.4.1 Functions of a Control Language 415
11.4.2 Pragmatic Considerations 417
11.5 Query and Other Nonprogramming Languages 417
11.6 Language Pragmatics and Software Systems 419
11.6.1 Language Design Issues 419
11.6.2 Some Desired Language Properties 420
11.6.3 Structured Programming 421
11.6.4 The Pragmatics of Programming Environments 422
11.7 Underlying Structural Issues 423
11.7.1 Information Binding 423
11.7.2 Control Structures 429
11.8 Epilogue 431
11.9 Exercises 431
12. Processors for Programming Languages 433
12.1 Prologue 433
12.2 Language Description 434
12.2.1 Syntax 435
12.2.2 Semantics 436
12.3 Functional Models of Important Processors 437
12.3.1 Assemblers 437
12 3.2 Compilers 441
12.3.3 Interpreters 443
12.4 The Technology of Translators 445
12.4.1 Lexical Analysis 445
12.4.2 Syntax Analysis 450
12.4.3 Semantic Analysis 459
12.4.4 Code Generation 460
12.4.5 Optimization 461
12.4.6 Run-Time Support 462
12.5 A Complete Compiler 463
12.6 Compiler Construction 466
12.7 Loading and Linking 468
12.7.1 Loading 469
12.7.2 Linking 471
12.8 Epilogue 475
12.9 Exercises 475
UNIT V: SOFTWARE ENGINEERING 476
13. Methods and Tools for System Creation 477
13.1 Prologue 477
13.2 Creation Methodologies 478
13.2.1 Design in Other Areas 479
132.2 Construction Steps Oriented Toward Software 479
13.2.3 Coherent Creation Methodologies 484
13.3 Tools and Techniques for System Construction 485
13.3.1 System-Implementation Languages 485
13.3.2 Structured Programming 487
133.3 Modular Programming 490
13.3.4 Chief Programmer Teams for Production
Programming 491
13.3.5 Programming Tools and Environments 493
13.3.6 Documentation 495
13.4 Future Developments 498
13.4.1 Software Engineering Techniques 498
13.4.2 Program Validation 500
13.4.3 Automatic Programming 502
13.5 Epilogue 504
13.6 Exercises 504
14. Performance Measurement and Evaluation 506
14.1 Prologue 506
14.2 "Performance Evaluation and Monitoring" (reprinted paper
by Henry C. Lucas, Jr.) 509
14.3 "The Instrumentation of Multics" (reprinted paper by
Jerome H. Saltier and John W. Gintell) 524
14.4 Epilogue 536
14.5 Exercises 536
UNIT VI: CASE STUDIES 538
15. Paradigmatic Systems 540
15.1 Prologue 540
15.2 "The Design of the Venus Operating System" (reprinted
paper by Barbara H. Liskov) 542
15.3 Exercises 553
16. General-Purpose Operating Systems 554
16.1 Prologue 554
16.2 "Multics — The First Seven Years" (reprinted paper by
F. J. Corbato, J. H. Saltier, and C. T. Clingen) 556
16.3 Exercises 578
17. Special-Purpose Operating Systems 579
17.1 Prologue 579
17.2 "RTOS - Extending OS/360 for Real-Time Spaceflight
Control" (reprinted paper by J. L. Johnstone) 580
17.3 Exercises 602
18. Virtual Machine Systems 603
18.1 Prologue 603
18.2 "A Virtual Machine Time-Sharing System" (reprinted
paper by R. A. Meyer and L. W. Seawright) 604
18.3 Exercises 622
References for Further Study 623
Bibliography 628
Index 653