Operating system concepts / by Abraham Silberschatz, Peter Baer Galvin and Creg Gagne

Includes bibliographical references and index.

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 21 1.6 Process Management 24 1.7 Memory Management 25 1.8 Storage Management 25 1.9 Protection and Security 30 1.10 Distributed Systems 31 1.11 Special-Purpose Systems 32 1.12 Computing Environments 35 1.13 Open Source Operating Systems 38 1.14 Summary 38 Exercises 39 Bibliographical Notes 43 Chapter 2 Operating-System Structures 2.1 Operating-System Services 45 2.2 User Operating-System Interface 48 2.3 System Calls 50 2.4 Types of System Calls 55 2.5 System Programs 63 2.6 Operating-System Design and Implementation 64 2.7 Operating-System Structure 67 2.8 Virtual Machines 73 2.9 Operating-System Generation 82 2.10 System Boot 83 2.11 System Debugging 84 2.12 Summary 84 Exercises 85 Bibliographical Notes 91 PART TWO PROCESS MANAGEMENT Chapter 3 Processes 3.1 Process Concept 95 3.2 Process Scheduling 99 3.3 Operations on Processes 104 3.4 Interprocess Communication 110 3.5 Examples of IPC Systems 117 3.6 Communication in Client- Server Systems 122 3.7 Summary 130 Exercises 131 Bibliographical Notes 139 xvii xviii Contents Chapter 4 Threads 4.1 Overview 149 4.2 Multithreading Models 151 4.3 Thread Libraries 153 4.4 Threading Issues 160 4.5 Operating-System Examples 165 4.6 Summary 168 Exercises 168 Bibliographical Notes 174 Chapter 5 CPU Scheduling 5.1 Basic Concepts 177 5.2 Scheduling Criteria 181 5.3 Scheduling Algorithms 182 5.4 Thread Scheduling 193 5.5 Multiple-Processor Scheduling 196 5.6 Operating System Examples 200 5.7 Algorithm Evaluation 207 5.8 Summary 212 Exercises 213 Bibliographical Notes 217 Chapter 6 Process Synchronization 6.1 Background 219 6.2 The Critical-Section Problem 221 6.3 Peterson's Solution 223 6.4 Synchronization Hardware 225 6.5 Semaphores 228 6.6 Classic Problems of Synchronization 234 6.7 Monitors 238 6.8 Synchronization Examples 246 6.9 Atomic Transactions 251 6.10 Summary 259 Exercises 260 Bibliographical Notes 272 Chapter 7 Deadlocks 7.1 System Model 275 7.2 Deadlock Characterization 277 7.3 Methods for Handling Deadlocks 282 7.4 Deadlock Prevention 283 7.5 Deadlock Avoidance 286 7.6 Deadlock Detection 292 7.7 Recovery From Deadlock 297 7.8 Summary 298 Exercises 299 Bibliographical Notes 303 PART THREE MEMORYMANAGEMENT Chapter 8 Main Memory 8.1 Background 307 8.2 Swapping 314 8.3 Contiguous Memory Allocation 316 8.4 Paging 321 8.5 Structure of the Page Table 330 8.6 Segmentation 335 8.7 Example: The Intel Pentium 338 8.8 Summary 342 Exercises 343 Bibliographical Notes 346 Contents xix Chapter 9 VirtualMemory 9.1 Background 349 9.2 Demand Paging 353 9.3 Copy-on-Write 359 9.4 Page Replacement 361 9.5 Allocation of Frames 374 9.6 Thrashing 378 9.7 Memory-Mapped Files 382 9.8 Allocating Kernel Memory 388 9.9 Other Considerations 391 9.10 Operating-System Examples 397 9.11 Summary 400 Exercises 401 Bibliographical Notes 407 PART FOUR STORAGE MANAGEMENT Chapter 10 File-System Interface 10.1 File Concept 373 10.2 Access Methods 382 10.3 Directory and Disk Structure 385 10.4 File-System Mounting 395 10.5 File Sharing 397 10.6 Protection 403 10.7 Summary 408 Exercises 408 Bibliographical Notes 410 Chapter 11 File-System Implementation 11.1 File-System Structure 413 11.2 File-System Implementation 416 11.3 Directory Implementation 422 11.4 Allocation Methods 423 11.5 Free-Space Management 431 11.6 Efficiency and Performance 434 11.7 Recovery 438 11.8 NFS 441 11.9 Example: The WAFL File System 447 11.10 Summary 449 Exercises 451 Bibliographical Notes 453 Chapter 12 Mass-Storage Structure 12.1 Overview of Mass-Storage Structure 451 12.2 Disk Structure 454 12.3 Disk Attachment 455 12.4 Disk Scheduling 456 12.5 Disk Management 462 12.6 Swap-Space Management 466 12.7 RAID Structure 468 12.8 Stable-Storage Implementation 477 12.9 Tertiary-Storage Structure 478 12.10 Summary 488 Exercises 489 Bibliographical Notes 496 Chapter 13 I/O Systems 13.1 Overview 499 13.2 I/O Hardware 500 13.3 Application I/O Interface 509 13.4 Kernel I/O Subsystem 515 13.5 Transforming I/O Requests to Hardware Operations 522 13.6 STREAMS 524 13.7 Performance 526 13.8 Summary 529 Exercises 530 Bibliographical Notes 532 xx Contents PART FIVE PROTECTION AND SECURITY Chapter 14 Protection 14.1 Goals of Protection 531 14.2 Principles of Protection 532 14.3 Domain of Protection 533 14.4 Access Matrix 538 14.5 Implementation of Access Matrix 542 14.6 Access Control 545 14.7 Revocation of Access Rights 546 14.8 Capability-Based Systems 547 14.9 Language-Based Protection 550 14.10 Summary 555 Exercises 556 Bibliographical Notes 558 Chapter 15 Security 15.1 The Security Problem 561 15.2 Program Threats 565 15.3 System and Network Threats 573 15.4 Cryptography as a Security Tool 578 15.5 User Authentication 589 15.6 Implementing Security Defenses 594 15.7 Firewalling to Protect Systems and Networks 601 15.8 Computer-Security Classifications 602 15.9 An Example: Windows XP 604 15.10 Summary 606 Exercises 606 Bibliographical Notes 608 PART SIX DISTRIBUTED SYSTEMS Chapter 16 Distributed System Structures 16.1 Motivation 613 16.2 Types of Network- based Operating Systems 615 16.3 Network Structure 619 16.4 Network Topology 622 16.5 Communication Structure 624 16.6 Communication Protocols 630 16.7 Robustness 634 16.8 Design Issues 635 16.9 An Example: Networking 638 16.10 Summary 639 Exercises 640 Bibliographical Notes 642 Chapter 17 Distributed File Systems 17.1 Background 645 17.2 Naming and Transparency 647 17.3 Remote File Access 650 17.4 Stateful Versus Stateless Service 655 17.5 File Replication 656 17.6 An Example: AFS 658 17.7 Summary 663 Exercises 664 Bibliographical Notes 665 Chapter 18 Distributed Coordination 18.1 Event Ordering 667 18.2 Mutual Exclusion 670 18.3 Atomicity 673 18.4 Concurrency Control 676 18.5 Deadlock Handling 680 18.6 Election Algorithms 687 18.7 Reaching Agreement 689 18.8 Summary 691 Exercises 692 Bibliographical Notes 694 Contents xxi PART SEVEN SPECIAL -PURPOSE SYSTEMS Chapter 19 Real-Time Systems 19.1 Overview 699 19.2 System Characteristics 700 19.3 Features of Real-Time Kernels 702 19.4 Implementing Real-Time Operating Systems 704 19.5 Real-Time CPU Scheduling 708 19.6 VxWorks 5.x 714 19.7 Summary 716 Exercises 717 Bibliographical Notes 717 Chapter 20 Multimedia Systems 20.1 What Is Multimedia? 719 20.2 Compression 722 20.3 Requirements of Multimedia Kernels 724 20.4 CPU Scheduling 726 20.5 Disk Scheduling 727 20.6 Network Management 729 20.7 An Example: CineBlitz 732 20.8 Summary 734 Exercises 735 Bibliographical Notes 736 PART EIGHT CASE STUDIES Chapter 21 The Linux System 21.1 Linux History 741 21.2 Design Principles 746 21.3 Kernel Modules 749 21.4 Process Management 752 21.5 Scheduling 755 21.6 Memory Management 760 21.7 File Systems 768 21.8 Input and Output 774 21.9 Interprocess Communication 777 21.10 Network Structure 778 21.11 Security 781 21.12 Summary 783 Exercises 784 Bibliographical Notes 785 Chapter 22 Windows XP 22.1 History 787 22.2 Design Principles 789 22.3 System Components 791 22.4 Environmental Subsystems 815 22.5 File System 818 22.6 Networking 826 22.7 Programmer Interface 833 22.8 Summary 840 Exercises 840 Bibliographical Notes 842 Chapter 23 Influential Operating Systems 23.1 Early Systems 843 23.2 Atlas 849 23.3 XDS-940 850 23.4 THE 851 23.5 RC 4000 852 23.6 CTSS 853 23.7 MULTICS 853 23.8 IBM OS/360 854 23.9 Mach 855 23.10 Other Systems 857 Exercises 857 xxii Contents Appendix A BSD UNIX A.1 UNIX History 859 A.2 Design Principles 864 A.3 Programmer Interface 866 A.4 User Interface 873 A.5 Process Management 876 A.6 Memory Management 880 A.7 File System 883 A.8 I/O System 890 A.9 Interprocess Communication 893 A.10 Summary 898 Exercises 899 Bibliographical Notes 900 Appendix B TheMach System B.1 History of the Mach System 901 B.2 Design Principles 903 B.3 System Components 904 B.4 Process Management 907 B.5 Interprocess Communication 913 B.6 Memory Management 918 B.7 Programmer Interface 923 B.8 Summary 924 Exercises 925 Bibliographical Notes 926 Credits 927 Appendix C Windows 2000 C.1 History 929 C.2 Design Principles 930 C.3 System Components 931 C.4 Environmental Subsystems 947 C.5 File System 950 C.6 Networking 956 C.7 Programmer Interface 961 C.8 Summary 968 Exercises 968 Bibliographical Notes 969 Bibliography 855 Credits 885 Index 929

This market-leading book provides developers with the latest and most relevant information on today's operating systems. In addition, it uncovers the fundamental concepts that have remained constant throughout the evolution of those systems. The eighth edition adds simulation content throughout the pages along with new programming projects.