* New student-focused pedagogy and a new two-color design to enhance the learning process.
PART ONE OVERVIEW
Chapter 1 Introduction
1.1 What Operating Systems Do 3
1.2 Computer-System Organization 6
1.3 Computer-System Architecture 12
1.4 Operating-System Structure 18
1.5 Operating-System Operations 20
1.6 Process Management 23
1.7 Memory Management 24
1.8 Storage Management 25
1.9 Protection and Security 29
1.10 Distributed Systems 30
1.11 Special-Purpose Systems 32
1.12 Computing Environments 34
1.13 Open-Source Operating Systems 37
1.14 Summary 40
Exercises 42
Bibliographical Notes 46
Chapter 2 Operating-System Structures
2.1 Operating-System Services 49
2.2 User Operating-System Interface 52
2.3 System Calls 55
2.4 Types of System Calls 58
2.5 System Programs 66
2.6 Operating-System Design and
Implementation 68
2.7 Operating-System Structure 70
2.8 Virtual Machines 76
2.9 Operating-System Debugging 84
2.10 Operating-System Generation 88
2.11 System Boot 89
2.12 Summary 90
Exercises 91
Bibliographical Notes 98
PART TWO PROCESS MANAGEMENT
Chapter 3 Processes
3.1 Process Concept 101
3.2 Process Scheduling 105
3.3 Operations on Processes 110
3.4 Interprocess Communication 116
3.5 Examples of IPC Systems 123
3.6 Communication in Client–
Server Systems 128
3.7 Summary 140
Exercises 141
Bibliographical Notes 152
xvii
xviii Contents
Chapter 4 Threads
4.1 Overview 153
4.2 Multithreading Models 157
4.3 Thread Libraries 159
4.4 Threading Issues 165
4.5 Operating-System Examples 171
4.6 Summary 174
Exercises 174
Bibliographical Notes 182
Chapter 5 CPU Scheduling
5.1 Basic Concepts 183
5.2 Scheduling Criteria 187
5.3 Scheduling Algorithms 188
5.4 Thread Scheduling 199
5.5 Multiple-Processor Scheduling 200
5.6 Operating System Examples 206
5.7 Algorithm Evaluation 213
5.8 Summary 217
Exercises 218
Bibliographical Notes 223
Chapter 6 Process Synchronization
6.1 Background 225
6.2 The Critical-Section Problem 227
6.3 Peterson’s Solution 229
6.4 Synchronization Hardware 231
6.5 Semaphores 234
6.6 Classic Problems of
Synchronization 239
6.7 Monitors 244
6.8 Synchronization Examples 252
6.9 Atomic Transactions 257
6.10 Summary 267
Exercises 267
Bibliographical Notes 280
Chapter 7 Deadlocks
7.1 System Model 283
7.2 Deadlock Characterization 285
7.3 Methods for Handling Deadlocks 290
7.4 Deadlock Prevention 291
7.5 Deadlock Avoidance 294
7.6 Deadlock Detection 301
7.7 Recovery from Deadlock 304
7.8 Summary 306
Exercises 307
Bibliographical Notes 311
PART THREE MEMORY MANAGEMENT
Chapter 8 Main Memory
8.1 Background 315
8.2 Swapping 322
8.3 Contiguous Memory Allocation 324
8.4 Paging 328
8.5 Structure of the Page Table 337
8.6 Segmentation 342
8.7 Example: The Intel Pentium 345
8.8 Summary 349
Exercises 350
Bibliographical Notes 354
Contents xix
Chapter 9 VirtualMemory
9.1 Background 357
9.2 Demand Paging 361
9.3 Copy-on-Write 367
9.4 Page Replacement 369
9.5 Allocation of Frames 382
9.6 Thrashing 386
9.7 Memory-Mapped Files 390
9.8 Allocating Kernel Memory 396
9.9 Other Considerations 399
9.10 Operating-System Examples 405
9.11 Summary 407
Exercises 409
Bibliographical Notes 417
PART FOUR STORAGE MANAGEMENT
Chapter 10 File-System Interface
10.1 File Concept 421
10.2 Access Methods 430
10.3 Directory and Disk Structure 433
10.4 File-System Mounting 444
10.5 File Sharing 446
10.6 Protection 451
10.7 Summary 456
Exercises 457
Bibliographical Notes 459
Chapter 11 File-System Implementation
11.1 File-System Structure 461
11.2 File-System Implementation 464
11.3 Directory Implementation 470
11.4 Allocation Methods 471
11.5 Free-Space Management 479
11.6 Efficiency and Performance 482
11.7 Recovery 486
11.8 NFS 490
11.9 Example: The WAFL File System 496
11.10 Summary 498
Exercises 499
Bibliographical Notes 502
Chapter 12 Mass-Storage Structure
12.1 Overview of Mass-Storage
Structure 505
12.2 Disk Structure 508
12.3 Disk Attachment 509
12.4 Disk Scheduling 510
12.5 Disk Management 516
12.6 Swap-Space Management 520
12.7 RAID Structure 522
12.8 Stable-Storage Implementation 533
12.9 Tertiary-Storage Structure 534
12.10 Summary 543
Exercises 545
Bibliographical Notes 552
Chapter 13 I/O Systems
13.1 Overview 555
13.2 I/O Hardware 556
13.3 Application I/O Interface 565
13.4 Kernel I/O Subsystem 571
13.5 Transforming I/O Requests to
Hardware Operations 578
13.6 STREAMS 580
13.7 Performance 582
13.8 Summary 585
Exercises 586
Bibliographical Notes 588
xx Contents
PART FIVE PROTECTION AND SECURITY
Chapter 14 Protection
14.1 Goals of Protection 591
14.2 Principles of Protection 592
14.3 Domain of Protection 593
14.4 Access Matrix 598
14.5 Implementation of Access Matrix 602
14.6 Access Control 605
14.7 Revocation of Access Rights 606
14.8 Capability-Based Systems 607
14.9 Language-Based Protection 610
14.10 Summary 615
Exercises 616
Bibliographical Notes 618
Chapter 15 Security
15.1 The Security Problem 621
15.2 Program Threats 625
15.3 System and Network Threats 633
15.4 Cryptography as a Security Tool 638
15.5 User Authentication 649
15.6 Implementing Security Defenses 654
15.7 Firewalling to Protect Systems and
Networks 661
15.8 Computer-Security
Classifications 662
15.9 An Example: Windows XP 664
15.10 Summary 665
Exercises 666
Bibliographical Notes 668
PART SIX DISTRIBUTED SYSTEMS
Chapter 16 Distributed System Structures
16.1 Motivation 673
16.2 Types of Networkbased
Operating Systems 675
16.3 Network Structure 679
16.4 Network Topology 683
16.5 Communication Structure 684
16.6 Communication Protocols 690
16.7 Robustness 694
16.8 Design Issues 697
16.9 An Example: Networking 699
16.10 Summary 701
Exercises 701
Bibliographical Notes 704
Chapter 17 Distributed File Systems
17.1 Background 705
17.2 Naming and Transparency 707
17.3 Remote File Access 710
17.4 Stateful Versus Stateless Service 715
17.5 File Replication 716
17.6 An Example: AFS 718
17.7 Summary 723
Exercises 724
Bibliographical Notes 725
Chapter 18 Distributed Coordination
18.1 Event Ordering 727
18.2 Mutual Exclusion 730
18.3 Atomicity 733
18.4 Concurrency Control 736
18.5 Deadlock Handling 740
18.6 Election Algorithms 747
18.7 Reaching Agreement 750
18.8 Summary 752
Exercises 753
Bibliographical Notes 755
Contents xxi
PART SEVEN SPECIAL -PURPOSE SYSTEMS
Chapter 19 Real-Time Systems
19.1 Overview 759
19.2 System Characteristics 760
19.3 Features of Real-Time Kernels 762
19.4 Implementing Real-Time Operating
Systems 764
19.5 Real-Time CPU Scheduling 768
19.6 An Example: VxWorks 5.x 774
19.7 Summary 776
Exercises 777
Bibliographical Notes 778
Chapter 20 Multimedia Systems
20.1 What Is Multimedia? 779
20.2 Compression 782
20.3 Requirements of Multimedia
Kernels 784
20.4 CPU Scheduling 786
20.5 Disk Scheduling 787
20.6 Network Management 789
20.7 An Example: CineBlitz 792
20.8 Summary 795
Exercises 795
Bibliographical Notes 797
PART EIGHT CASE STUDIES
Chapter 21 The Linux System
21.1 Linux History 801
21.2 Design Principles 806
21.3 Kernel Modules 809
21.4 Process Management 812
21.5 Scheduling 815
21.6 Memory Management 820
21.7 File Systems 828
21.8 Input and Output 834
21.9 Interprocess Communication 837
21.10 Network Structure 838
21.11 Security 840
21.12 Summary 843
Exercises 844
Bibliographical Notes 845
Chapter 22 Windows XP
22.1 History 847
22.2 Design Principles 849
22.3 System Components 851
22.4 Environmental Subsystems 874
22.5 File System 878
22.6 Networking 886
22.7 Programmer Interface 892
22.8 Summary 900
Exercises 900
Bibliographical Notes 901
Chapter 23 Influential Operating Systems
23.1 Feature Migration 903
23.2 Early Systems 904
23.3 Atlas 911
23.4 XDS-940 912
23.5 THE 913
23.6 RC 4000 913
23.7 CTSS 914
23.8 MULTICS 915
23.9 IBM OS/360 915
23.10 TOPS-20 917
23.11 CP/M and MS/DOS 917
23.12 Macintosh Operating System and
Windows 918
23.13 Mach 919
23.14 Other Systems 920
Exercises 921
xxii Contents
PART NINE APPENDICES
Appendix A BSD UNIX (contents online)
A.1 UNIX History A1
A.2 Design Principles A6
A.3 Programmer Interface A8
A.4 User Interface A15
A.5 Process Management A18
A.6 Memory Management A22
A.7 File System A24
A.8 I/O System A32
A.9 Interprocess Communication A35
A.10 Summary A40
Exercises A41
Bibliographical Notes A42
Appendix B TheMach System (contents online)
B.1 History of the Mach System B1
B.2 Design Principles B3
B.3 System Components B4
B.4 Process Management B7
B.5 Interprocess Communication B13
B.6 Memory Management B18
B.7 Programmer Interface B23
B.8 Summary B24
Exercises B25
Bibliographical Notes B26
Appendix C Windows 2000 (contents online)
C.1 History C1
C.2 Design Principles C2
C.3 System Components C3
C.4 Environmental Subsystems C19
C.5 File System C21
C.6 Networking C28
C.7 Programmer Interface C33
C.8 Summary C40
Exercises C40
Bibliographical Notes C41
Bibliography 923
Credits 955
Index 957