Chapter 1 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
Chapter 2 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
Chapter 3 Operating System Organization 71
3.1 Factorsin 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.2 Process and Resource Management 77
3.2.1 Device 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
Chapter 4 Computer Organization 85
4.1 The von Neumann Architecture 86
4.2.1 The Arithmetical-Logical Unit 88
4.2 The Central Processing 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
Chapter 5 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
Chapter 6 Process Management 161
6.1 The System View of Processes 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.1 Process Descriptors 170
6.4 The Process Abstraction 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
Chapter 7 Scheduling 189
7.1.1 The Process Scheduler Organization 190
7.1 Scheduling Mechanisms 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
Chapter 8 Basic Synchronization Principles 217
8.1 Interacting Processes 218
IN THE HANGAR:Solving a System of Linear Equations 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
Chapter 9 High-lever Synchronization 257
9.1 Alternative Synchronization Primitiyes 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.6 Exercises 281
9.5 Summary 281
LABORATORY EXERCISE:Refining the Shell 285
Background 285
Attacking the Problem 290
Chapter 10 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.1 Hold and Wait 299
10.3 Prevention 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
Chapter 11 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 353
11.5 Summary 357
11.6 Exercises 357
Chapter 12 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
Chapter 13 File Management 405
13.1 Files 406
13.1.1 Low-level Files 408
13.1.2 Structured Files 412
13.1.4 Multimedia Storage 418
13.1.3 Database Management Systems 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
Chapter 14 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 Mechanisms 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
Chapter 15 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 485
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
Chapter 16 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
IN THE HANGAR:The Andrew File System 548
16.4 File-level Caching 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
Chapter 17 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.6 Exercises 589
17.5 Summary 589
Chapter 18 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