You are previewing Operating System Concepts, Seventh Edition.
O'Reilly logo
Operating System Concepts, Seventh Edition

Book Description

Another defining moment in the evolution of operating systems

Small footprint operating systems, such as those driving the handheld devices that the baby dinosaurs are using on the cover, are just one of the cutting-edge applications you'll find in Silberschatz, Galvin, and Gagne's Operating System Concepts, Seventh Edition.

By staying current, remaining relevant, and adapting to emerging course needs, this market-leading text has continued to define the operating systems course. This Seventh Edition not only presents the latest and most relevant systems, it also digs deeper to uncover those fundamental concepts that have remained constant throughout the evolution of today's operation systems. With this strong conceptual foundation in place, students can more easily understand the details related to specific systems.

New Adaptations

  • Increased coverage of user perspective in Chapter 1.

  • Increased coverage of OS design throughout.

  • A new chapter on real-time and embedded systems (Chapter 19).

  • A new chapter on multimedia (Chapter 20).

  • Additional coverage of security and protection.

  • Additional coverage of distributed programming.

  • New exercises at the end of each chapter.

  • New programming exercises and projects at the end of each chapter.

  • New student-focused pedagogy and a new two-color design to enhance the learning process.

Table of Contents

  1. Copyright
  2. Preface
    1. Organization of This Book
    2. Content of This Book
    3. Operating-System Environments
    4. The Seventh Edition
    5. Programming Exercises and Projects
    6. Teaching Supplements and Web Page
    7. Mailing List
    8. Suggestions
    9. Acknowledgments
  3. I. Overview
    1. 1. Introduction
      1. 1.1. What Operating Systems Do
        1. 1.1.1. User View
        2. 1.1.2. System View
        3. 1.1.3. Defining Operating Systems
      2. 1.2. Computer-System Organization
        1. 1.2.1. Computer-System Operation
        2. 1.2.2. Storage Structure
        3. 1.2.3. I/O Structure
      3. 1.3. Computer-System Architecture
        1. 1.3.1. Single-Processor Systems
        2. 1.3.2. Multiprocessor Systems
        3. 1.3.3. Clustered Systems
      4. 1.4. Operating-System Structure
      5. 1.5. Operating-System Operations
        1. 1.5.1. Dual-Mode Operation
        2. 1.5.2. Timer
      6. 1.6. Process Management
      7. 1.7. Memory Management
      8. 1.8. Storage Management
        1. 1.8.1. File-System Management
        2. 1.8.2. Mass-Storage Management
        3. 1.8.3. Caching
        4. 1.8.4. I/O Systems
      9. 1.9. Protection and Security
      10. 1.10. Distributed Systems
      11. 1.11. Special-Purpose Systems
        1. 1.11.1. Real-Time Embedded Systems
        2. 1.11.2. Multimedia Systems
        3. 1.11.3. Handheld Systems
      12. 1.12. Computing Environments
        1. 1.12.1. Traditional Computing
        2. 1.12.2. Client–Server Computing
        3. 1.12.3. Peer-to-Peer Computing
        4. 1.12.4. Web-Based Computing
      13. 1.13. Summary
      14. 1.14. Exercises
      15. 1.15. Bibliographical Notes
    2. 2. Operating-System Structures
      1. 2.1. Operating-System Services
      2. 2.2. User Operating-System Interface
        1. 2.2.1. Command Interpreter
        2. 2.2.2. Graphical User Interfaces
      3. 2.3. System Calls
      4. 2.4. Types of System Calls
        1. 2.4.1. Process Control
        2. 2.4.2. File Management
        3. 2.4.3. Device Management
        4. 2.4.4. Information Maintenance
        5. 2.4.5. Communication
      5. 2.5. System Programs
      6. 2.6. Operating-System Design and Implementation
        1. 2.6.1. Design Goals
        2. 2.6.2. Mechanisms and Policies
        3. 2.6.3. Implementation
      7. 2.7. Operating-System Structure
        1. 2.7.1. Simple Structure
        2. 2.7.2. Layered Approach
        3. 2.7.3. Microkernels
        4. 2.7.4. Modules
      8. 2.8. Virtual Machines
        1. 2.8.1. Implementation
        2. 2.8.2. Benefits
        3. 2.8.3. Examples
          1. 2.8.3.1. VMware
          2. 2.8.3.2. The Java Virtual Machine
      9. 2.9. Operating-System Generation
      10. 2.10. System Boot
      11. 2.11. Summary
      12. 2.12. Exercises
      13. 2.13. Project—Adding a System Call to the Linux Kernel
        1. 2.13.1.
          1. 2.13.1.1. Getting Started
          2. 2.13.1.2. Building a New Kernel
          3. 2.13.1.3. Extending Kernel Source
          4. 2.13.1.4. Adding a System Call to the Kernel
          5. 2.13.1.5. Using the System Call From a User Program
      14. 2.14. Bibliographical Notes
  4. II. Process Management
    1. 3. Processes
      1. 3.1. Process Concept
        1. 3.1.1. The Process
        2. 3.1.2. Process State
        3. 3.1.3. Process Control Block
        4. 3.1.4. Threads
      2. 3.2. Process Scheduling
        1. 3.2.1. Scheduling Queues
        2. 3.2.2. Schedulers
        3. 3.2.3. Context Switch
      3. 3.3. Operations on Processes
        1. 3.3.1. Process Creation
        2. 3.3.2. Process Termination
      4. 3.4. Interprocess Communication
        1. 3.4.1. Shared-Memory Systems
        2. 3.4.2. Message-Passing Systems
          1. 3.4.2.1. Naming
          2. 3.4.2.2. Synchronization
          3. 3.4.2.3. Buffering
      5. 3.5. Examples of IPC Systems
        1. 3.5.1. An Example: POSIX Shared Memory
        2. 3.5.2. An Example: Mach
        3. 3.5.3. An Example: Windows XP
      6. 3.6. Communication in Client-Server Systems
        1. 3.6.1. Sockets
        2. 3.6.2. Remote Procedure Calls
        3. 3.6.3. Remote Method Invocation
      7. 3.7. Summary
      8. 3.8. Exercises
      9. 3.9. Project—UNIX Shell and History Feature
        1. 3.9.1.
          1. 3.9.1.1. Simple Shell
          2. 3.9.1.2. Creating a Child Process
          3. 3.9.1.3. Creating a History Feature
      10. 3.10. Bibliographical Notes
    2. 4. Threads
      1. 4.1. Overview
        1. 4.1.1. Motivation
        2. 4.1.2. Benefits
      2. 4.2. Multithreading Models
        1. 4.2.1. Many-to-One Model
        2. 4.2.2. One-to-One Model
        3. 4.2.3. Many-to-Many Model
      3. 4.3. Thread Libraries
        1. 4.3.1. Pthreads
        2. 4.3.2. Win32 Threads
        3. 4.3.3. Java Threads
      4. 4.4. Threading Issues
        1. 4.4.1. The fork() and exec() System Calls
        2. 4.4.2. Cancellation
        3. 4.4.3. Signal Handling
        4. 4.4.4. Thread Pools
        5. 4.4.5. Thread-Specific Data
        6. 4.4.6. Scheduler Activations
      5. 4.5. Operating-System Examples
        1. 4.5.1. Windows XP Threads
        2. 4.5.2. Linux Threads
      6. 4.6. Summary
      7. 4.7. Exercises
      8. 4.8. Project—Matrix Multiplication
        1. 4.8.1.
          1. 4.8.1.1. Passing Parameters to Each Thread
          2. 4.8.1.2. Waiting for Threads to Complete
      9. 4.9. Bibliographical Notes
    3. 5. CPU Scheduling
      1. 5.1. Basic Concepts
        1. 5.1.1. CPU-I/O Burst Cycle
        2. 5.1.2. CPU Scheduler
        3. 5.1.3. Preemptive Scheduling
        4. 5.1.4. Dispatcher
      2. 5.2. Scheduling Criteria
      3. 5.3. Scheduling Algorithms
        1. 5.3.1. First-Come, First-Served Scheduling
        2. 5.3.2. Shortest-Job-First Scheduling
        3. 5.3.3. Priority Scheduling
        4. 5.3.4. Round-Robin Scheduling
        5. 5.3.5. Multilevel Queue Scheduling
        6. 5.3.6. Multilevel Feedback-Queue Scheduling
      4. 5.4. Multiple-Processor Scheduling
        1. 5.4.1. Approaches to Multiple-Processor Scheduling
        2. 5.4.2. Processor Affinity
        3. 5.4.3. Load Balancing
        4. 5.4.4. Symmetric Multithreading
      5. 5.5. Thread Scheduling
        1. 5.5.1. Contention Scope
        2. 5.5.2. Pthread Scheduling
      6. 5.6. Operating System Examples
        1. 5.6.1. Example: Solaris Scheduling
        2. 5.6.2. Example: Windows XP Scheduling
        3. 5.6.3. Example: Linux Scheduling
      7. 5.7. Algorithm Evaluation
        1. 5.7.1. Deterministic Modeling
        2. 5.7.2. Queueing Models
        3. 5.7.3. Simulations
        4. 5.7.4. Implementation
      8. 5.8. Summary
      9. 5.9. Exercises
      10. 5.10. Bibliographical Notes
    4. 6. Process Synchronization
      1. 6.1. Background
      2. 6.2. The Critical-Section Problem
      3. 6.3. Peterson's Solution
      4. 6.4. Synchronization Hardware
      5. 6.5. Semaphores
        1. 6.5.1. Usage
        2. 6.5.2. Implementation
        3. 6.5.3. Deadlocks and Starvation
      6. 6.6. Classic Problems of Synchronization
        1. 6.6.1. The Bounded-Buffer Problem
        2. 6.6.2. The Readers-Writers Problem
        3. 6.6.3. The Dining-Philosophers Problem
      7. 6.7. Monitors
        1. 6.7.1. Usage
        2. 6.7.2. Dining-Philosophers Solution Using Monitors
        3. 6.7.3. Implementing a Monitor Using Semaphores
        4. 6.7.4. Resuming Processes Within a Monitor
      8. 6.8. Synchronization Examples
        1. 6.8.1. Synchronization in Solaris
        2. 6.8.2. Synchronization in Windows XP
        3. 6.8.3. Synchronization in Linux
        4. 6.8.4. Synchronization in Pthreads
      9. 6.9. Atomic Transactions
        1. 6.9.1. System Model
        2. 6.9.2. Log-Based Recovery
        3. 6.9.3. Checkpoints
        4. 6.9.4. Concurrent Atomic Transactions
          1. 6.9.4.1. Serializability
          2. 6.9.4.2. Locking Protocol
          3. 6.9.4.3. Timestamp-Based Protocols
      10. 6.10. Summary
      11. 6.11. Exercises
      12. 6.12. Project: Producer-Consumer Problem
        1. 6.12.1.
          1. 6.12.1.1. The Buffer
          2. 6.12.1.2. Producer and Consumer Threads
          3. 6.12.1.3. Pthreads Thread Creation
          4. 6.12.1.4. Pthreads Mutex Locks
          5. 6.12.1.5. Pthreads Semaphores
          6. 6.12.1.6. Win32
          7. 6.12.1.7. Win32 Mutex Locks
          8. 6.12.1.8. Win32 Semaphores
      13. 6.13. Bibliographical Notes
    5. 7. Deadlocks
      1. 7.1. System Model
      2. 7.2. Deadlock Characterization
        1. 7.2.1. Necessary Conditions
        2. 7.2.2. Resource-Allocation Graph
      3. 7.3. Methods for Handling Deadlocks
      4. 7.4. Deadlock Prevention
        1. 7.4.1. Mutual Exclusion
        2. 7.4.2. Hold and Wait
        3. 7.4.3. No Preemption
        4. 7.4.4. Circular Wait
      5. 7.5. Deadlock Avoidance
        1. 7.5.1. Safe State
        2. 7.5.2. Resource-Allocation-Graph Algorithm
        3. 7.5.3. Banker's Algorithm
          1. 7.5.3.1. Safety Algorithm
          2. 7.5.3.2. Resource-Request Algorithm
          3. 7.5.3.3. An Illustrative Example
      6. 7.6. Deadlock Detection
        1. 7.6.1. Single Instance of Each Resource Type
        2. 7.6.2. Several Instances of a Resource Type
        3. 7.6.3. Detection-Algorithm Usage
      7. 7.7. Recovery From Deadlock
        1. 7.7.1. Process Termination
        2. 7.7.2. Resource Preemption
      8. 7.8. Summary
      9. 7.9. Exercises
      10. 7.10. Bibliographical Notes
  5. III. Memory Management
    1. 8. Main Memory
      1. 8.1. Background
        1. 8.1.1. Basic Hardware
        2. 8.1.2. Address Binding
        3. 8.1.3. Logical Versus Physical Address Space
        4. 8.1.4. Dynamic Loading
        5. 8.1.5. Dynamic Linking and Shared Libraries
      2. 8.2. Swapping
      3. 8.3. Contiguous Memory Allocation
        1. 8.3.1. Memory Mapping and Protection
        2. 8.3.2. Memory Allocation
        3. 8.3.3. Fragmentation
      4. 8.4. Paging
        1. 8.4.1. Basic Method
        2. 8.4.2. Hardware Support
        3. 8.4.3. Protection
        4. 8.4.4. Shared Pages
      5. 8.5. Structure of the Page Table
        1. 8.5.1. Hierarchical Paging
        2. 8.5.2. Hashed Page Tables
        3. 8.5.3. Inverted Page Tables
      6. 8.6. Segmentation
        1. 8.6.1. Basic Method
        2. 8.6.2. Hardware
      7. 8.7. Example: The Intel Pentium
        1. 8.7.1. Pentium Segmentation
        2. 8.7.2. Pentium Paging
        3. 8.7.3. Linux on Pentium Systems
      8. 8.8. Summary
      9. 8.9. Exercises
      10. 8.10. Bibliographical Notes
    2. 9. Virtual Memory
      1. 9.1. Background
      2. 9.2. Demand Paging
        1. 9.2.1. Basic Concepts
        2. 9.2.2. Performance of Demand Paging
      3. 9.3. Copy-on-Write
      4. 9.4. Page Replacement
        1. 9.4.1. Basic Page Replacement
        2. 9.4.2. FIFO Page Replacement
        3. 9.4.3. Optimal Page Replacement
        4. 9.4.4. LRU Page Replacement
        5. 9.4.5. LRU-Approximation Page Replacement
          1. 9.4.5.1. Additional-Reference-Bits Algorithm
          2. 9.4.5.2. Second-Chance Algorithm
          3. 9.4.5.3. Enhanced Second-Chance Algorithm
        6. 9.4.6. Counting-Based Page Replacement
        7. 9.4.7. Page-Buffering Algorithms
        8. 9.4.8. Applications and Page Replacement
      5. 9.5. Allocation of Frames
        1. 9.5.1. Minimum Number of Frames
        2. 9.5.2. Allocation Algorithms
        3. 9.5.3. Global versus Local Allocation
      6. 9.6. Thrashing
        1. 9.6.1. Cause of Thrashing
        2. 9.6.2. Working-Set Model
        3. 9.6.3. Page-Fault Frequency
      7. 9.7. Memory-Mapped Files
        1. 9.7.1. Basic Mechanism
        2. 9.7.2. Shared Memory in the Win32 API
        3. 9.7.3. Memory-Mapped I/O
      8. 9.8. Allocating Kernel Memory
        1. 9.8.1. Buddy System
        2. 9.8.2. Slab Allocation
      9. 9.9. Other Considerations
        1. 9.9.1. Prepaging
        2. 9.9.2. Page Size
        3. 9.9.3. TLB Reach
        4. 9.9.4. Inverted Page Tables
        5. 9.9.5. Program Structure
        6. 9.9.6. I/O Interlock
      10. 9.10. Operating-System Examples
        1. 9.10.1. Windows XP
        2. 9.10.2. Solaris
      11. 9.11. Summary
      12. 9.12. Exercises
      13. 9.13. Bibliographical Notes
  6. IV. Storage Management
    1. 10. File-System Interface
      1. 10.1. File Concept
        1. 10.1.1. File Attributes
        2. 10.1.2. File Operations
        3. 10.1.3. File Types
        4. 10.1.4. File Structure
        5. 10.1.5. Internal File Structure
      2. 10.2. Access Methods
        1. 10.2.1. Sequential Access
        2. 10.2.2. Direct Access
        3. 10.2.3. Other Access Methods
      3. 10.3. Directory Structure
        1. 10.3.1. Storage Structure
        2. 10.3.2. Directory Overview
        3. 10.3.3. Single-Level Directory
        4. 10.3.4. Two-Level Directory
        5. 10.3.5. Tree-Structured Directories
        6. 10.3.6. Acyclic-Graph Directories
        7. 10.3.7. General Graph Directory
      4. 10.4. File-System Mounting
      5. 10.5. File Sharing
        1. 10.5.1. Multiple Users
        2. 10.5.2. Remote File Systems
          1. 10.5.2.1. The Client–Server Model
          2. 10.5.2.2. Distributed Information Systems
          3. 10.5.2.3. Failure Modes
        3. 10.5.3. Consistency Semantics
          1. 10.5.3.1. UNIX Semantics
          2. 10.5.3.2. Session Semantics
          3. 10.5.3.3. Immutable-Shared-Files Semantics
      6. 10.6. Protection
        1. 10.6.1. Types of Access
        2. 10.6.2. Access Control
        3. 10.6.3. Other Protection Approaches
      7. 10.7. Summary
      8. 10.8. Exercises
      9. 10.9. Bibliographical Notes
    2. 11. File-System Implementation
      1. 11.1. File-System Structure
      2. 11.2. File-System Implementation
        1. 11.2.1. Overview
        2. 11.2.2. Partitions and Mounting
        3. 11.2.3. Virtual File Systems
      3. 11.3. Directory Implementation
        1. 11.3.1. Linear List
        2. 11.3.2. Hash Table
      4. 11.4. Allocation Methods
        1. 11.4.1. Contiguous Allocation
        2. 11.4.2. Linked Allocation
        3. 11.4.3. Indexed Allocation
        4. 11.4.4. Performance
      5. 11.5. Free-Space Management
        1. 11.5.1. Bit Vector
        2. 11.5.2. Linked List
        3. 11.5.3. Grouping
        4. 11.5.4. Counting
      6. 11.6. Efficiency and Performance
        1. 11.6.1. Efficiency
        2. 11.6.2. Performance
      7. 11.7. Recovery
        1. 11.7.1. Consistency Checking
        2. 11.7.2. Backup and Restore
      8. 11.8. Log-Structured File Systems
      9. 11.9. NFS
        1. 11.9.1. Overview
        2. 11.9.2. The Mount Protocol
        3. 11.9.3. The NFS Protocol
        4. 11.9.4. Path-Name Translation
        5. 11.9.5. Remote Operations
      10. 11.10. Example: The WAFL File System
      11. 11.11. Summary
      12. 11.12. Exercises
      13. 11.13. Bibliographical Notes
    3. 12. Mass-Storage Structure
      1. 12.1. Overview of Mass-Storage Structure
        1. 12.1.1. Magnetic Disks
        2. 12.1.2. Magnetic Tapes
      2. 12.2. Disk Structure
      3. 12.3. Disk Attachment
        1. 12.3.1. Host-Attached Storage
        2. 12.3.2. Network-Attached Storage
        3. 12.3.3. Storage-Area Network
      4. 12.4. Disk Scheduling
        1. 12.4.1. FCFS Scheduling
        2. 12.4.2. SSTF Scheduling
        3. 12.4.3. SCAN Scheduling
        4. 12.4.4. C-SCAN Scheduling
        5. 12.4.5. LOOK Scheduling
        6. 12.4.6. Selection of a Disk-Scheduling Algorithm
      5. 12.5. Disk Management
        1. 12.5.1. Disk Formatting
        2. 12.5.2. Boot Block
        3. 12.5.3. Bad Blocks
      6. 12.6. Swap-Space Management
        1. 12.6.1. Swap-Space Use
        2. 12.6.2. Swap-Space Location
        3. 12.6.3. Swap-Space Management: An Example
      7. 12.7. RAID Structure
        1. 12.7.1. Improvement of Reliability via Redundancy
        2. 12.7.2. Improvement in Performance via Parallelism
        3. 12.7.3. RAID Levels
        4. 12.7.4. Selecting a RAID Level
        5. 12.7.5. Extensions
        6. 12.7.6. Problems with RAID
      8. 12.8. Stable-Storage Implementation
      9. 12.9. Tertiary-Storage Structure
        1. 12.9.1. Tertiary-Storage Devices
          1. 12.9.1.1. Removable Disks
          2. 12.9.1.2. Tapes
          3. 12.9.1.3. Future Technology
        2. 12.9.2. Operating-System Support
          1. 12.9.2.1. Application Interface
          2. 12.9.2.2. File Naming
          3. 12.9.2.3. Hierarchical Storage Management
        3. 12.9.3. Performance Issues
          1. 12.9.3.1. Speed
          2. 12.9.3.2. Reliability
          3. 12.9.3.3. Cost
      10. 12.10. Summary
      11. 12.11. Exercises
      12. 12.12. Bibliographical Notes
    4. 13. I/O Systems
      1. 13.1. Overview
      2. 13.2. I/O Hardware
        1. 13.2.1. Polling
        2. 13.2.2. Interrupts
        3. 13.2.3. Direct Memory Access
        4. 13.2.4. I/O Hardware Summary
      3. 13.3. Application I/O Interface
        1. 13.3.1. Block and Character Devices
        2. 13.3.2. Network Devices
        3. 13.3.3. Clocks and Timers
        4. 13.3.4. Blocking and Nonblocking IO
      4. 13.4. Kernel I/O Subsystem
        1. 13.4.1. I/O Scheduling
        2. 13.4.2. Buffering
        3. 13.4.3. Caching
        4. 13.4.4. Spooling and Device Reservation
        5. 13.4.5. Error Handling
        6. 13.4.6. I/O Protection
        7. 13.4.7. Kernel Data Structures
        8. 13.4.8. Kernel I/O Subsystem Summary
      5. 13.5. Transforming I/O Requests to Hardware Operations
      6. 13.6. STREAMS
      7. 13.7. Performance
      8. 13.8. Summary
      9. 13.9. Exercises
      10. 13.10. Bibliographical Notes
  7. V. Protection and Security
    1. 14. Protection
      1. 14.1. Goals of Protection
      2. 14.2. Principles of Protection
      3. 14.3. Domain of Protection
        1. 14.3.1. Domain Structure
        2. 14.3.2. An Example: UNIX
        3. 14.3.3. An Example: MULTICS
      4. 14.4. Access Matrix
      5. 14.5. Implementation of Access Matrix
        1. 14.5.1. Global Table
        2. 14.5.2. Access Lists for Objects
        3. 14.5.3. Capability Lists for Domains
        4. 14.5.4. A Lock–Key Mechanism
        5. 14.5.5. Comparison
      6. 14.6. Access Control
      7. 14.7. Revocation of Access Rights
      8. 14.8. Capability-Based Systems
        1. 14.8.1. An Example: Hydra
        2. 14.8.2. An Example: Cambridge CAP System
      9. 14.9. Language-Based Protection
        1. 14.9.1. Compiler-Based Enforcement
        2. 14.9.2. Protection in Java
      10. 14.10. Summary
      11. 14.11. Exercises
      12. 14.12. Bibliographical Notes
    2. 15. Security
      1. 15.1. The Security Problem
      2. 15.2. Program Threats
        1. 15.2.1. Trojan Horse
        2. 15.2.2. Trap Door
        3. 15.2.3. Logic Bomb
        4. 15.2.4. Stack and Buffer Overflow
        5. 15.2.5. Viruses
      3. 15.3. System and Network Threats
        1. 15.3.1. Worms
        2. 15.3.2. Port Scanning
        3. 15.3.3. Denial of Service
      4. 15.4. Cryptography as a Security Tool
        1. 15.4.1. Encryption
          1. 15.4.1.1. Symmetric Encryption
          2. 15.4.1.2. Asymmetric Encryption
          3. 15.4.1.3. Authentication
          4. 15.4.1.4. Key Distribution
        2. 15.4.2. Implementation of Cryptography
        3. 15.4.3. An Example: SSL
      5. 15.5. User Authentication
        1. 15.5.1. Passwords
        2. 15.5.2. Password Vulnerabilities
        3. 15.5.3. Encrypted Passwords
        4. 15.5.4. One-Time Passwords
        5. 15.5.5. Biometrics
      6. 15.6. Implementing Security Defenses
        1. 15.6.1. Security Policy
        2. 15.6.2. Vulnerability Assessment
        3. 15.6.3. Intrusion Detection
        4. 15.6.4. Virus Protection
        5. 15.6.5. Auditing, Accounting, and Logging
      7. 15.7. Firewalling to Protect Systems and Networks
      8. 15.8. Computer-Security Classifications
      9. 15.9. An Example: Windows XP
      10. 15.10. Summary
      11. 15.11. Exercises
      12. 15.12. Bibliographical Notes
  8. VI. Distributed Systems
    1. 16. Distributed System Structures
      1. 16.1. Motivation
        1. 16.1.1. Resource Sharing
        2. 16.1.2. Computation Speedup
        3. 16.1.3. Reliability
        4. 16.1.4. Communication
      2. 16.2. Types of Distributed Operating Systems
        1. 16.2.1. Network Operating Systems
          1. 16.2.1.1. Remote Login
          2. 16.2.1.2. Remote File Transfer
        2. 16.2.2. Distributed Operating Systems
          1. 16.2.2.1. Data Migration
          2. 16.2.2.2. Computation Migration
          3. 16.2.2.3. Process Migration
      3. 16.3. Network Structure
        1. 16.3.1. Local-Area Networks
        2. 16.3.2. Wide-Area Networks
      4. 16.4. Network Topology
      5. 16.5. Communication Structure
        1. 16.5.1. Naming and Name Resolution
        2. 16.5.2. Routing Strategies
        3. 16.5.3. Packet Strategies
        4. 16.5.4. Connection Strategies
        5. 16.5.5. Contention
      6. 16.6. Communication Protocols
      7. 16.7. Robustness
        1. 16.7.1. Failure Detection
        2. 16.7.2. Reconfiguration
        3. 16.7.3. Recovery from Failure
      8. 16.8. Design Issues
      9. 16.9. An Example: Networking
      10. 16.10. Summary
      11. 16.11. Exercises
      12. 16.12. Bibliographical Notes
    2. 17. Distributed File Systems
      1. 17.1. Background
      2. 17.2. Naming and Transparency
        1. 17.2.1. Naming Structures
        2. 17.2.2. Naming Schemes
        3. 17.2.3. Implementation Techniques
      3. 17.3. Remote File Access
        1. 17.3.1. Basic Caching Scheme
        2. 17.3.2. Cache Location
        3. 17.3.3. Cache-Update Policy
        4. 17.3.4. Consistency
        5. 17.3.5. A Comparison of Caching and Remote Service
      4. 17.4. Stateful Versus Stateless Service
      5. 17.5. File Replication
      6. 17.6. An Example: AFS
        1. 17.6.1. Overview
        2. 17.6.2. The Shared Name Space
        3. 17.6.3. File Operations and Consistency Semantics
        4. 17.6.4. Implementation
      7. 17.7. Summary
      8. 17.8. Exercises
      9. 17.9. Bibliographical Notes
    3. 18. Distributed Coordination
      1. 18.1. Event Ordering
        1. 18.1.1. The Happened-Before Relation
        2. 18.1.2. Implementation
      2. 18.2. Mutual Exclusion
        1. 18.2.1. Centralized Approach
        2. 18.2.2. Fully Distributed Approach
        3. 18.2.3. Token-Passing Approach
      3. 18.3. Atomicity
        1. 18.3.1. The Two-Phase Commit Protocol
        2. 18.3.2. Failure Handling in 2PC
          1. 18.3.2.1. Failure of a Participating Site
          2. 18.3.2.2. Failure of the Coordinator
          3. 18.3.2.3. Failure of the Network
      4. 18.4. Concurrency Control
        1. 18.4.1. Locking Protocols
          1. 18.4.1.1. Nonreplicated Scheme
          2. 18.4.1.2. Single-Coordinator Approach
          3. 18.4.1.3. Majority Protocol
          4. 18.4.1.4. Biased Protocol
          5. 18.4.1.5. Primary Copy
        2. 18.4.2. Timestamping
          1. 18.4.2.1. Generation of Unique Timestamps
          2. 18.4.2.2. Timestamp-Ordering Scheme
      5. 18.5. Deadlock Handling
        1. 18.5.1. Deadlock Prevention and Avoidance
        2. 18.5.2. Deadlock Detection
          1. 18.5.2.1. Centralized Approach
          2. 18.5.2.2. Fully Distributed Approach
      6. 18.6. Election Algorithms
        1. 18.6.1. The Bully Algorithm
        2. 18.6.2. The Ring Algorithm
      7. 18.7. Reaching Agreement
        1. 18.7.1. Unreliable Communications
        2. 18.7.2. Faulty Processes
      8. 18.8. Summary
      9. 18.9. Exercises
      10. 18.10. Bibliographical Notes
  9. VII. Special-Purpose Systems
    1. 19. Real-Time Systems
      1. 19.1. Overview
      2. 19.2. System Characteristics
      3. 19.3. Features of Real-Time Kernels
      4. 19.4. Implementing Real-Time Operating Systems
        1. 19.4.1. Priority-Based Scheduling
        2. 19.4.2. Preemptive Kernels
        3. 19.4.3. Minimizing Latency
      5. 19.5. Real-Time CPU Scheduling
        1. 19.5.1. Rate-Monotonic Scheduling
        2. 19.5.2. Earliest-Deadline-First Scheduling
        3. 19.5.3. Proportional Share Scheduling
        4. 19.5.4. Pthread Scheduling
      6. 19.6. VxWorks 5.x
      7. 19.7. Summary
      8. 19.8. Exercises
      9. 19.9. Bibliographical Notes
    2. 20. Multimedia Systems
      1. 20.1. What Is Multimedia?
        1. 20.1.1. Media Delivery
        2. 20.1.2. Characteristics of Multimedia Systems
        3. 20.1.3. Operating-System Issues
      2. 20.2. Compression
      3. 20.3. Requirements of Multimedia Kernels
      4. 20.4. CPU Scheduling
      5. 20.5. Disk Scheduling
        1. 20.5.1. Earliest-Deadline-First Scheduling
        2. 20.5.2. SCAN-EDF Scheduling
      6. 20.6. Network Management
        1. 20.6.1. Unicasting and Multicasting
        2. 20.6.2. Real-Time Streaming Protocol
      7. 20.7. An Example: CineBlitz
        1. 20.7.1. Disk Scheduling
        2. 20.7.2. Admission Control
      8. 20.8. Summary
      9. 20.9. Exercises
      10. 20.10. Bibliographical Notes
  10. VIII. Case Studies
    1. 21. The Linux System
      1. 21.1. Linux History
        1. 21.1.1. The Linux Kernel
        2. 21.1.2. The Linux System
        3. 21.1.3. Linux Distributions
        4. 21.1.4. Linux Licensing
      2. 21.2. Design Principles
        1. 21.2.1. Components of a Linux System
      3. 21.3. Kernel Modules
        1. 21.3.1. Module Management
        2. 21.3.2. Driver Registration
        3. 21.3.3. Conflict Resolution
      4. 21.4. Process Management
        1. 21.4.1. The fork() and exec() Process Model
          1. 21.4.1.1. Process Identity
          2. 21.4.1.2. Process Environment
          3. 21.4.1.3. Process Context
        2. 21.4.2. Processes and Threads
      5. 21.5. Scheduling
        1. 21.5.1. Process Scheduling
        2. 21.5.2. Kernel Synchronization
        3. 21.5.3. Symmetric Multiprocessing
      6. 21.6. Memory Management
        1. 21.6.1. Management of Physical Memory
        2. 21.6.2. Virtual Memory
          1. 21.6.2.1. Virtual Memory Regions
          2. 21.6.2.2. Lifetime of a Virtual Address Space
          3. 21.6.2.3. Swapping and Paging
          4. 21.6.2.4. Kernel Virtual Memory
        3. 21.6.3. Execution and Loading of User Programs
          1. 21.6.3.1. Mapping of Programs into Memory
          2. 21.6.3.2. Static and Dynamic Linking
      7. 21.7. File Systems
        1. 21.7.1. The Virtual File System
        2. 21.7.2. The Linux ext2fs File System
        3. 21.7.3. Journaling
        4. 21.7.4. The Linux proc File System
      8. 21.8. Input and Output
        1. 21.8.1. Block Devices
        2. 21.8.2. Character Devices
      9. 21.9. Interprocess Communication
        1. 21.9.1. Synchronization and Signals
        2. 21.9.2. Passing of Data Among Processes
      10. 21.10. Network Structure
      11. 21.11. Security
        1. 21.11.1. Authentication
        2. 21.11.2. Access Control
      12. 21.12. Summary
      13. 21.13. Exercises
      14. 21.14. Bibliographical Notes
    2. 22. Windows XP
      1. 22.1. History
      2. 22.2. Design Principles
        1. 22.2.1. Security
        2. 22.2.2. Reliability
        3. 22.2.3. Windows and POSIX Application Compatibility
        4. 22.2.4. High Performance
        5. 22.2.5. Extensibility
        6. 22.2.6. Portability
        7. 22.2.7. International Support
      3. 22.3. System Components
        1. 22.3.1. Hardware-Abstraction Layer
        2. 22.3.2. Kernel
          1. 22.3.2.1. Kernel Dispatcher
          2. 22.3.2.2. Threads and Scheduling
          3. 22.3.2.3. Implementation of Synchronization Primitives
          4. 22.3.2.4. Software Interrupts: Asynchronous and Deferred Procedure Calls
          5. 22.3.2.5. Exceptions and Interrupts
        3. 22.3.3. Executive
          1. 22.3.3.1. Object Manager
          2. 22.3.3.2. Virtual Memory Manager
          3. 22.3.3.3. Process Manager
          4. 22.3.3.4. Local Procedure Call Facility
          5. 22.3.3.5. I/O Manager
          6. 22.3.3.6. Cache Manager
          7. 22.3.3.7. Security Reference Monitor
          8. 22.3.3.8. Plug-and-Play and Power Managers
          9. 22.3.3.9. Registry
          10. 22.3.3.10. Booting
      4. 22.4. Environmental Subsystems
        1. 22.4.1. MS-DOS Environment
        2. 22.4.2. 16-Bit Windows Environment
        3. 22.4.3. 32-Bit Windows Environment on IA64
        4. 22.4.4. Win32 Environment
        5. 22.4.5. POSIX Subsystem
        6. 22.4.6. Logon and Security Subsystems
      5. 22.5. File System
        1. 22.5.1. NTFS Internal Layout
          1. 22.5.1.1. NTFS B+ Tree
          2. 22.5.1.2. NTFS Metadata
        2. 22.5.2. Recovery
        3. 22.5.3. Security
        4. 22.5.4. Volume Management and Fault Tolerance
          1. 22.5.4.1. Volume Set
          2. 22.5.4.2. Stripe Set
          3. 22.5.4.3. Stripe Set with Parity
          4. 22.5.4.4. Disk Mirroring
          5. 22.5.4.5. Sector Sparing and Cluster Remapping
        5. 22.5.5. Compression and Encryption
        6. 22.5.6. Mount Points
        7. 22.5.7. Change Journal
        8. 22.5.8. Volume Shadow Copies
      6. 22.6. Networking
        1. 22.6.1. Network Interfaces
        2. 22.6.2. Protocols
          1. 22.6.2.1. Server-Message Block
          2. 22.6.2.2. Network Basic Input/Output System
          3. 22.6.2.3. NetBIOS Extended User Interface
          4. 22.6.2.4. Transmission Control Protocol/Internet Protocol
          5. 22.6.2.5. Point-to-Point Tunneling Protocol
          6. 22.6.2.6. Novell NetWare Protocols
          7. 22.6.2.7. Web Distributed Authoring and Versioning Protocol
          8. 22.6.2.8. AppleTalk Protocol
        3. 22.6.3. Distributed-Processing Mechanisms
          1. 22.6.3.1. NetBIOS
          2. 22.6.3.2. Named Pipes
          3. 22.6.3.3. Mailslots
          4. 22.6.3.4. Winsock
          5. 22.6.3.5. Remote Procedure Calls
          6. 22.6.3.6. Microsoft Interface Definition Language
          7. 22.6.3.7. Component Object Model
        4. 22.6.4. Redirectors and Servers
          1. 22.6.4.1. Distributed File System
          2. 22.6.4.2. Folder Redirection and Client-Side Caching
        5. 22.6.5. Domains
          1. 22.6.5.1. Domain Trees and Forests
          2. 22.6.5.2. Trust Relationships
        6. 22.6.6. Active Directory
        7. 22.6.7. Name Resolution in TCP/IP Networks
      7. 22.7. Programmer Interface
        1. 22.7.1. Access to Kernel Objects
        2. 22.7.2. Sharing Objects Between Processes
        3. 22.7.3. Process Management
          1. 22.7.3.1. Instance Handles
          2. 22.7.3.2. Scheduling Rule
          3. 22.7.3.3. Thread Priorities
          4. 22.7.3.4. Thread Synchronization
          5. 22.7.3.5. Fibers
          6. 22.7.3.6. Thread Pool
        4. 22.7.4. Interprocess Communication
        5. 22.7.5. Memory Management
          1. 22.7.5.1. Virtual Memory
          2. 22.7.5.2. Memory-Mapping Files
          3. 22.7.5.3. Heaps
          4. 22.7.5.4. Thread-Local Storage
      8. 22.8. Summary
      9. 22.9. Exercises
      10. 22.10. Bibliographical Notes
    3. 23. Influential Operating Systems
      1. 23.1. Early Systems
        1. 23.1.1. Dedicated Computer Systems
        2. 23.1.2. Shared Computer Systems
        3. 23.1.3. Overlapped I/O
      2. 23.2. Atlas
      3. 23.3. XDS-940
      4. 23.4. THE
      5. 23.5. RC 4000
      6. 23.6. CTSS
      7. 23.7. MULTICS
      8. 23.8. IBM OS/360
      9. 23.9. Mach
      10. 23.10. Other Systems
      11. 23.11. Exercises
    4. Bibliography
    5. Credits