Preface 1
To the Student 1
To the Instructor 6
Chapter1 Introduction 1
1.1 Computers and Software 2
1.1.1 General System Software 2
1.1.2 Resource Abstraction 4
* IN THE HANGAR: A Disk Device Abstraction 5
1.1.3 Resource Sharing 6
1.1.4 Computers Without System Software 7
1.2 Operating System Strategies 8
* PERFORMANCE TUNING: Multiprogramming Systems 10
1.2.1 Batch Systems 10
* IN THE HANGAR: Batch Files 13
1.2.2 Timesharing Systems 14
1.2.3 Personal Computers and Workstations 16
1.2.4 Process Control and Real-time Systems 18
1.2.5 Networks 19
1.2.6 The Genesis of Modern Operating Systems 20
* IN THE HANGAR: The Evolution of Linux 21
* IN THE HANGAR: The Microsoft Windows Family of Operating Systems 23
1.3 Summary 25
1.4 Exercises 26
Chapter2 Using The Operating System 29
2.1 The Abstract Model of Computing 30
2.2 Resources 30
2.2.1 Files 30
* IN THE HANGAR: POSIX Files 31
* IN THE HANGAR: Windows Files 33
2.2.2 Other Resources 36
2.3 Processes 37
2.3.1 Creating Processes 39
* IN THE HANGAR: Using FORK, JOIN, and QUIT 40
* IN THE HANGAR: Creating Processes in UNIX 41
* IN THE HANGAR: Creating Processes in Windows 44
2.4 Threads 46
* IN THE HANGAR: C Threads 48
2.5 Objects 49
2.6 Summary 50
2.7 Exercises 50
* LABORATORY EXERCISE: A Shell Program 53
·Background 53
·Attacking the Problem 58
* LABORATORY EXERCISE: A Multithreaded Windows Console Application 61
·Background 61
·Attacking the Problem 65
Chapter3 Operating System Organization 71
3.1 Factors in OS Design 72
3.1.1 Performance 72
3.1.2 Protection and Security 73
3.1.3 Correctness 74
3.1.4 Maintainability 74
3.1.5 Commercial Influence on Operating Systems 74
3.1.6 Standards and Open Systems 75
3.2 Basic Functions 76
3.2.1 Device Management 77
3.2.2 Process and Resource Management 77
3.2.3 Memory Management 78
3.2.4 File Management 78
3.2.5 Functional Organization 79
3.3 Basic Implementation Considerations 80
3.3.1 Processor Modes 80
3.3.2 Kernels 81
3.3.3 Requesting Services from the Operating Systems 82
3.4 Summary 83
3.5 Exercises 84
Chapter4 Computer Organization 85
4.1 The von Neumann Architecture 86
4.2 The Central Processing Unit 88
4.2.1 The Arithmetical-Logical Unit 88
4.2.2 The Control Unit 89
4.3 Memory 91
* PERFORMANCE TUNING: Speeding up the Machine 92
* PERFORMANCE TUNING: Parallel Processors 94
4.4 Devices 95
4.4.1 General Device Characteristics 96
4.4.2 Device Controllers 97
* IN THE HANGAR: Asynchronous Serial Devices 98
4.4.3 Device Drivers 99
4.5 Interrupts 100
4.6 The Mode Bit Revisited: The Trap Instruction 103
4.7 Summary 104
4.8 Exercises 105
* LABORATORY EXERCISE: Kernel Timers 109
·Background 109
·Attacking the Problem 113
Chapter5 Device Management 119
5.1 Device Management Approaches 120
5.1.1 I/O System Organization 120
5.1.2 Direct I/O with Polling 121
5.1.3 Interrupt-driven I/O 123
* PERFORMANCE TUNING: Interrupts Versus Polling 126
5.1.4 Memory-mapped I/O 127
5.1.5 Direct Memory Access 128
* PERFORMANCE TUNING: I/O-Processor Overlap 129
5.2 Buffering 130
5.3 Device Drivers 134
5.3.1 The Device Driver Interface 134
5.3.2 CPU-device Interactions 137
5.3.3 I/O Optimization 138
5.4 Some Device Management Scenarios 138
5.4.1 Serial Communications 138
* IN THE HANGAR: UNIX Device Drivers 139
5.4.2 Sequentially Accessed Storage Devices 141
5.4.3 Randomly Accessed Devices 142
* PERFORMANCE TUNING: Optimizing Access on Rotating Devices 144
5.5 Summary 149
5.6 Exercises 150
* LABORATORY EXERCISE: A Floppy Disk Driver 153
·Background 154
·Attacking the Problem 158
Chapter6 Process Management 161
6.1 The System View of Process and Resources 162
6.1.1 Implementing the Process Model 163
6.1.2 Implementing the Resource Model 164
6.2 Initializing the Operating System 165
6.3 Process Address Spaces 166
6.3.1 Creating the Address Space 167
6.3.2 Loading the Program 168
6.3.3 Maintaining Consistency in the Address Space 168
6.4 The Process Abstraction 170
6.4.1 Process Descriptors 170
6.4.2 Process State Diagram 172
6.5 The Resource Abstraction 173
6.6 Process Hierarchy 174
6.6.1 Refining the Process Manager 176
6.6.2 Specializing Resource Allocation Strategies 177
6.7 Summary 178
6.8 Exercises 179
* LABORATORY EXERCISE: Observing OS Behavior 181
·Background 182
·Attacking the Problem 187
Chapter7 Scheduling 189
7.1 Scheduling Mechanisms 190
7.1.1 The Process Scheduler Organization 190
7.1.2 Saving the Process Context 192
7.1.3 Voluntary CPU Sharing 192
7.1.4 Involuntary CPU Sharing 194
7.1.5 Performance 195
7.2 Strategy Selection 196
7.2.1 Partitioning a Process into Small Processes 199
7.3 Nonpreemptive Strategies 200
7.3.1 First-Come-First-Served 200
* PERFORMANCE TUNING: Approximating System Load 201
7.3.2 Shortest Job Next 202
* PERFORMANCE TUNING: Predicting Wait Times for FCFS 203
7.3.3 Priority Scheduling 204
7.3.4 Deadline Scheduling 206
7.4 Preemptive Strategies 207
7.4.1 Round Robin 207
7.4.2 Multiple-level Queues 210
7.5 Summary 212
7.6 Exercises 213
Chapter8 Basic Synchronization Principles 217
8.1 Interacting Processes 218
* IN THE HANGAR: Solving a System of Linear Equation 219
8.1.1 Critical Sections 220
8.1.2 Deadlock 224
8.2 Coordinating Processes 226
8.3 Semaphores 228
8.3.1 Principles of Operation 229
* IN THE HANGAR: Examples Using Semaphore 231
8.3.2 Practical Considerations 237
8.4 Shared Memory Multiprocessors 241
8.5 Summary 242
8.6 Exercises 242
* LABORATORY EXERCISE: Bounded Buffer Problem 249
·Background 249
·Attacking the Problem 255
Chapter9 High-level Synchronization 257
9.1 Alternative Synchronization Primitives 258
9.1.1 AND Synchronization 258
9.1.2 Events 259
* IN THE HANGAR: Using Events 260
* IN THE HANGAR: UNIX Signals 261
* IN THE HANGAR: Windows 2000 Dispatcher Objects 263
9.2 Monitors 264
9.2.1 Principles of Operation 264
9.2.2 Condition Variables 266
* IN THE HANGAR: Examples Using Monitors 269
9.2.3 Some Practical Aspects of Using Monitors 273
9.3 Interprocess Communication 273
9.3.1 Mailboxes 274
9.3.2 Message Protocols 276
9.3.3 Using the send and receive Operations 276
* IN THE HANGAR: Synchronized IPC 278
9.3.4 Deferred Message Copying 278
9.4 Explicitly Ordering Event Execution 279
9.5 Summary 281
9.6 Exercises 281
* LABORATORY EXERCISE: Refining the Shell 285
·Background 285
·Attacking the Problem 290
Chapter10 Deadlock 291
10.1 Background 292
10.1.1 Prevention 294
10.1.2 Avoidance 295
10.1.3 Detection and Recovery 295
10.1.4 Manual Deadlock Management 295
10.2 A System Deadlock Model 296
* IN THE HANGAR: Single Resource Type 297
10.3 Prevention 299
10.3.1 Hold and Wait 299
10.3.2 Circular Wait 301
10.3.3 Allowing Preemption 303
10.4 Avoidance 304
10.4.1 The Banker's Algorithm 306
* IN THE HANGAR: Using The Banker's Algorithm 307
10.5 Detection and Recovery 309
10.5.1 Serially Reusable Resources 310
10.5.2 Consumable Resources 316
10.5.3 General Resource Systems 320
10.5.4 Recovery 321
10.6 Summary 321
10.7 Exercises 322
Chapter11 Memory Management 325
11.1 The Basics 326
11.1.1 Requirements on Primary Memory 326
11.1.2 Mapping the Address Space to Primary Memory 327
* PERFORMANCE TUNING: Using Memory Hierarchies to Reduce Access Time 328
* IN THE HANGAR: The Address Binding Procedure 330
11.1.3 Dynamic Memory for Data Structures 333
11.2 Memory Allocation 335
11.2.1 Fixed-partition Memory Strategies 336
11.2.2 Variable-partition Memory Strategies 337
11.2.3 Contemporary Allocation Strategies 340
* PERFORMANCE TUNING: The Cost of Moving Programs 341
11.3 Dynamic Address Relocation 342
11.3.1 Runtime Bound Checking 346
* IN THE HANGAR: Expanding Small Address Spaces 347
11.4 Memory Manager Strategies 348
11.4.1 Swapping 348
11.4.2 Virtual Memory 352
11.4.3 Shared-memory Multiprocessors 352
* PERFORMANCE TUNING: Using Cache Memory 535
11.5 Summary 357
11.6 Exercises 357
Chapter12 Virtual Memory 361
12.1 Address Translation 362
12.1.1 Address Space Mapping 362
12.1.2 Segmentation and Paging 364
12.2 Paging 365
12.2.1 Virtual Address Translation 367
* PERFORMANCE TUNING: Page Table Implementations 370
12.3 Static Paging Algorithms 371
12.3.1 The Fetch Policy 372
12.3.2 Demand Paging Algorithms 372
12.3.3 Stack Algorithms 376
12.3.4 Implementing LRU 378
* PERFORMANCE TUNING: Paging Performance 379
12.4 Dynamic Paging Algorithms 381
12.4.1 The Working Set Algorithm 381
* IN THE HANGAR: Working Set Algorithm Example 383
12.4.2 Implementing the Working Set Algorithm 385
* PERFORMANCE TUNING: Taking Advantage of Pages with IPC 387
* IN THE HANGAR: Windows 2000 Virtual Memory 388
* IN THE HANGAR: Linux Virtual Memory 392
12.5 Segmentation 393
12.5.1 Address Translation 394
12.5.2 Implementation 396
* IN THE HANGAR: The Multics Segmentation System 399
12.6 Summary 401
12.7 Exercises 402
Chapter13 File Management 405
13.1 Files 406
13.1.1 Low-level Files 408
13.1.2 Structured Files 412
13.1.3 Database Management Systems 418
13.1.4 Multimedia Storage 418
13.2 Low-level File Implementations 419
13.2.1 open and close Operations 420
* IN THE HANGAR: UNIX open and close 420
13.2.2 Block Management 422
* IN THE HANGAR: UNIX File Structure 425
13.2.3 Reading and Writing the Byte Stream 430
13.3 Supporting Other Storage Abstractions 431
13.3.1 Structured Sequential Files 431
13.3.2 Indexed Sequential Files 431
13.3.3 Database Management Systems 432
13.3.4 Multimedia Documents 432
13.4 Memory-Mapped Files 433
* IN THE HANGAR: Memory-mapped Files in Windows 2000 434
13.5 Directories 435
13.5.1 Directory Structures 436
* IN THE HANGAR: Some Directory Examples 437
13.6 Directory Implementation 439
13.6.1 Device Directories 439
13.6.2 File Directory 440
13.6.3 Opening a File in a Hierarchical Directory 440
13.6.4 Mounting Removable File Systems 441
13.7 Summary 442
13.8 Exercises 442
* LABORATORY EXERCISE: A Simple File Manager 445
·Background 446
·Attacking the Problem 449
Chapter14 Protection and Security 453
14.1 Fundamentals 454
14.1.1 Policy and Mechanism 454
14.1.2 Implementing Policy and Mechanism 456
14.1.3 Authentication Mechanism 456
14.1.4 Authorization Mechanisms 457
14.1.5 Encryption 458
14.2 Authentication 458
14.2.1 User Authentication 459
14.2.2 Authentication in Networks 459
* IN THE HANGAR: Kerberos Network Authentication 461
14.3 Internal Access Authorization 463
14.3.1 A Model for Resource Protection 464
14.3.2 Changing the Protection State 466
14.3.3 The Cost of Protection Mechanisms 468
14.4 Implementing Internal Authorization 469
14.4.1 Protection Domains 469
14.4.2 Implementing the Access Matrix 471
14.5 Cryptography 476
14.6 Summary 477
14.7 Exercises 478
Chapter15 Networks 481
15.1 From Computer Communications to Networks 482
15.1.1 Communication Subnetworks 483
15.1.2 Network Communication Protocols 484
15.2 The ISO OSI Network Architecture Model 485
15.2.1 The Evolution of Network Protocols 484
15.2.2 The ISO OSI Model 487
15.3 Low-level Protocols 490
15.3.1 The Physical Layer 491
* PERFORMANCE TUNING: Fast Physical Layers 492
15.3.2 The Data Link Layer 493
15.3.3 Contemporary Networks 494
15.4 The Network Layer 496
15.4.1 Addressing 498
15.4.2 Routing 499
15.4.3 Using the Network Layer 501
15.5 The Transport Layer 502
15.5.1 Communication Ports 502
15.5.2 Data Types 503
15.5.3 Reliable Communication 504
* PERFORMANCE TUNING: Datagrams and Virtual Circuits 505
15.6 Using the Transport Layer 506
15.6.1 Naming 506
* IN THE HANGAR: The Domain Name System 508
15.6.2 The Client-server Model 509
15.7 Summary 511
15.8 Exercises 512
* LABORATORY EXERCISE: Using TCP/IP 515
·Background 515
·Attacking the Problem 523
Chapter16 Remote Files 525
16.1 Sharing Information Across the Network 526
16.1.1 Explicit File Copying Systems 527
16.1.2 Implicit File Sharing 528
16.1.3 The Remote Storage Interface 530
16.1.4 Distributing the Work 531
16.2 Remote Disk Systems 533
16.2.1 The Remote Disk Operation 534
16.2.2 Performance Considerations 535
16.2.3 Reliability 536
16.2.4 The Future of Remote Disks 539
16.3 Remote File Systems 539
16.3.1 The General Architecture 540
16.3.2 Block Caching 542
16.3.3 Crash Recovery 544
16.4 File-level Caching 548
* IN THE HANGAR: The Andrew File System 548
* IN THE HANGAR: The LOCUS File System 549
16.5 Directory Systems and Their Implementations 551
16.5.1 Filenames 552
16.5.2 Opening a File 554
16.6 Summary 555
16.7 Exercises 556
Chapter17 Distributed Computing 559
17.1 Distributing Process Management 560
17.1.1 Partitioning the Work 560
17.1.2 Supporting Partitioned Computation 562
17.1.3 General Process Management 563
17.1.4 Scheduling 563
* PERFORMANCE TUNING: Process Migration and Load Balancing 564
17.1.5 Coordinating Processes 565
17.2 Message Passing 568
17.2.1 Message-Passing Interfaces 570
17.2.2 Computing Paradigms 572
17.3 Remote Procedure Call 573
17.3.1 How Does RPC Work? 573
17.3.2 Implementing RPC 575
17.4 Distributed-memory Management 579
17.4.1 Remote Memory 583
* IN THE HANGAR: Examples of Distributed Memory 583
17.4.2 Distributed Virtual Memory 586
17.4.3 Distributed Objects 588
17.5 Summary 589
17.6 Exercises 589
Chapter18 Strategies and Examples 591
18.1 OS Components and Relationships 592
18.2 General Organizational Issues 593
18.2.1 Software Organization 594
18.2.2 Managing Distributed Hardware 599
18.3 The Traditional UNIX Kernel 601
18.3.1 The Kernel 602
18.3.2 The Monolithic Organization 603
18.3.3 Conclusion 604
18.4 The Linux Kernel 604
18.4.1 Kernel Organization 604
18.4.2 Process and Resource Management 609
18.4.3 Memory Manager 615
18.4.4 File Management 616
18.5 Choices: An Object-oriented OS 618
18.5.1 Frameworks 618
18.5.2 Using a Framework for the Memory Manager 618
18.5.3 Conclusion 620
18.6 Microsoft Windows NT 621
18.6.1 General Architecture 621
18.6.2 The Hardware Abstraction Layer (HAL) 624
18.6.3 The NT Kernel 624
18.6.4 The NT Executive 626
18.6.5 NT Subsystems 631
18.7 The Mach Operating System 632
18.7.1 Process Management 633
18.7.2 Message Passing 635
18.7.3 Memory Management 638
18.7.4 Conclusion 640
18.8 The CHORUS Operating System 640
18.8.1 Process Management 642
18.8.2 Interprocess Communication 643
18.8.3 Memory Management 643
18.8.4 Conclusion 644
18.9 Summary 644
18.10 Exercises 644
Glossary 647
Bibliography 659
Index 663