PART ONE OVERVIEW Chapter 1 Introduction 1.1 What Operating Systems Do 4 1.2 Computer-System Organization 7 1.3 Computer-System Architecture 12 1.4 Operating-System Structure 19 1.5 Operating-System Operations 21 1.6 Process Management 24 1.7 Memory Management 25 1.8 Storage Management 26 1.9 Protection and Security 30 1.10 Kernel Data Structures 31 1.11 Computing Environments 35 1.12 Open-Source Operating Systems 43 1.13 Summary 47 Exercises 49 Bibliographical Notes 51 Chapter 2 System Structures 2.1 Operating-System Services 53 2.2 User and Operating-System Interface 56 2.3 System Calls 60 2.4 Types of System Calls 64 2.5 System Programs 72 2.6 Operating-System Design and Implementation 73 2.7 Operating-System Structure 76 2.8 Operating-System Debugging 84 2.9 Operating-System Generation 89 2.10 System Boot 90 2.11 Summary 91 Exercises 92 Bibliographical Notes 98 PART TWO PROCESS MANAGEMENT Chapter 3 Process Concept 3.1 Process Concept 103 3.2 Process Scheduling 108 3.3 Operations on Processes 113 3.4 Interprocess Communication 120 3.5 Examples of IPC Systems 128 3.6 Communication in Client Server Systems 134 3.7 Summary 145 Exercises 147 Bibliographical Notes 158 Chapter 4 Multithreaded Programming 4.1 Overview 161 4.2 Multicore Programming 164 4.3 Multithreading Models 167 4.4 Thread Libraries 169 4.5 Implicit Threading 175 4.6 Threading Issues 181 4.7 Operating-System Examples 186 4.8 Summary 189 Exercises 189 Bibliographical Notes 197 Chapter 5 Process Scheduling 5.1 Basic Concepts 201 5.2 Scheduling Criteria 205 5.3 Scheduling Algorithms 206 5.4 Thread Scheduling 217 5.5 Multiple-Processor Scheduling 218 5.6 Real-Time CPU Scheduling 223 5.7 Operating-System Examples 230 5.8 Algorithm Evaluation 240 5.9 Summary 244 Exercises 245 Bibliographical Notes 250 Chapter 6 Synchronization 6.1 Background 253 6.2 The Critical-Section Problem 256 6.3 Peterson s Solution 257 6.4 Synchronization Hardware 259 6.5 Mutex Locks 262 6.6 Semaphores 263 6.7 Classic Problems of Synchronization 269 6.8 Monitors 273 6.9 Synchronization Examples 282 6.10 Alternative Approaches 288 6.11 Summary 292 Exercises 292 Bibliographical Notes 307 Chapter 7 Deadlocks 7.1 System Model 311 7.2 Deadlock Characterization 313 7.3 Methods for Handling Deadlocks 318 7.4 Deadlock Prevention 319 7.5 Deadlock Avoidance 323 7.6 Deadlock Detection 329 7.7 Recovery from Deadlock 333 7.8 Summary 335 Exercises 335 Bibliographical Notes 340 PART THREE MEMORY MANAGEMENT Chapter 8 Memory-Management Strategies 8.1 Background 345 8.2 Swapping 352 8.3 Contiguous Memory Allocation 354 8.4 Segmentation 358 8.5 Paging 360 8.6 Structure of the Page Table 372 8.7 Example: Intel 32 and 64-bit Architectures 377 8.8 Example: ARM Architecture 382 8.9 Summary 383 Exercises 384 Bibliographical Notes 387 Chapter 9 Virtual-Memory Management 9.1 Background 389 9.2 Demand Paging 393 9.3 Copy-on-Write 400 9.4 Page Replacement 401 9.5 Allocation of Frames 413 9.6 Thrashing 417 9.7 Memory-Mapped Files 422 9.8 Allocating Kernel Memory 428 9.9 Other Considerations 431 9.10 Operating-System Examples 437 9.11 Summary 440 Exercises 441 Bibliographical Notes 450 PART FOUR STORAGE MANAGEMENT Chapter 10 File System 10.1 File Concept 455 10.2 Access Methods 465 10.3 Directory and Disk Structure 467 10.4 File-System Mounting 478 10.5 File Sharing 480 10.6 Protection 485 10.7 Summary 490 Exercises 491 Bibliographical Notes 492 Chapter 11 Implementing File-Systems 11.1 File-System Structure 495 11.2 File-System Implementation 498 11.3 Directory Implementation 504 11.4 Allocation Methods 505 11.5 Free-Space Management 513 11.6 Efficiency and Performance 516 11.7 Recovery 520 11.8 NFS 523 11.9 Example: The WAFL File System 529 11.10 Summary 532 Exercises 533 Bibliographical Notes 536 Chapter 12 Mass-Storage Structure 12.1 Overview of Mass-Storage Structure 539 12.2 Disk Structure 542 12.3 Disk Attachment 543 12.4 Disk Scheduling 544 12.5 Disk Management 550 12.6 Swap-Space Management 554 12.7 RAID Structure 556 12.8 Stable-Storage Implementation 566 12.9 Summary 568 Exercises 569 Bibliographical Notes 572 Chapter 13 I/O Systems 13.1 Overview 575 13.2 I/O Hardware 576 13.3 Application I/O Interface 585 13.4 Kernel I/O Subsystem 592 13.5 Transforming I/O Requests to Hardware Operations 599 13.6 STREAMS 601 13.7 Performance 603 13.8 Summary 606 Exercises 607 Bibliographical Notes 608 PART FIVE PROTECTION AND SECURITY Chapter 14 System Protection 14.1 Goals of Protection 611 14.2 Principles of Protection 612 14.3 Domain of Protection 613 14.4 Access Matrix 618 14.5 Implementation of the Access Matrix 622 14.6 Access Control 625 14.7 Revocation of Access Rights 626 14.8 Capability-Based Systems 627 14.9 Language-Based Protection 630 14.10 Summary 635 Exercises 636 Bibliographical Notes 637 Chapter 15 System Security 15.1 The Security Problem 641 15.2 Program Threats 645 15.3 System and Network Threats 653 15.4 Cryptography as a Security Tool 658 15.5 User Authentication 669 15.6 Implementing Security Defenses 673 15.7 Firewalling to Protect Systems and Networks 680 15.8 Computer-Security Classifications 682 15.9 An Example:Windows 7 683 15.10 Summary 685 Exercises 686 Bibliographical Notes 688 PART SIX CASE STUDIES Chapter 16 The Linux System 16.1 Linux History 695 16.2 Design Principles 700 16.3 Kernel Modules 703 16.4 Process Management 706 16.5 Scheduling 709 16.6 Memory Management 714 16.7 File Systems 723 16.8 Input and Output 729 16.9 Interprocess Communication 732 16.10 Network Structure 733 16.11 Security 735 16.12 Summary 738 Exercises 738 Bibliographical Notes 740 Chapter 17 Windows 7 17.1 History 741 17.2 Design Principles 743 17.3 System Components 750 17.4 Terminal Services and Fast User Switching 774 17.5 File System 775 17.6 Networking 781 17.7 Programmer Interface 786 17.8 Summary 795 Exercises 795 Bibliographical Notes 796 Chapter 18 Influential Operating Systems 18.1 Feature Migration 799 18.2 Early Systems 800 18.3 Atlas 807 18.4 XDS-940 808 18.5 THE 809 18.6 RC 4000 809 18.7 CTSS 810 18.8 MULTICS 811 18.9 IBM OS/360 811 18.10 TOPS-20 813 18.11 CP/M and MS/DOS 813 18.12 Macintosh Operating System and Windows 814 18.13 Mach 814 18.14 Other Systems 816 Exercises 816 Bibliographical Notes 816 APPENDICES (Online) Appendix A BSD UNIX 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 A36 A.10 Summary A40 Exercises A41 Bibliographical Notes A42 Appendix B The Mach System 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