You are previewing Operating Systems.
O'Reilly logo
Operating Systems

Book Description

Operating Systems is designed to meet the needs of undergraduate computer science students, and follows the principle of top-down design and bottom-up development. It offers platform-independent, in-depth discussion of fundamental concepts; two detailed technological case studies, on Linux 2.6 and Microsoft Windows XP.

Table of Contents

  1. Cover
  2. Title page
  3. Brief Contents
  4. Contents
  5. About the Authors
  6. Preface
  7. Chapter 1: Overview
    1. 1.1 Introduction
    2. 1.2 Basic Terminology
    3. 1.2.1 Hardware
    4. 1.2.2 Primitive Data and Operation
    5. 1.2.3 RAM
    6. 1.2.4 ROM
    7. 1.2.5 Execution Flow
    8. 1.2.6 Program, Programming Language, and Computation
    9. 1.2.7 Application Programs
    10. 1.2.8 Operating System
    11. 1.3 The Computer System
    12. 1.4 I/O Device Operation
    13. 1.5 Process Abstraction
    14. 1.5.1 Resource Allocation
    15. 1.5.2 Process Address Space
    16. 1.6 Processor Operating Mode
    17. 1.7 System Call, Interrupt, Exception, and Kernel Path
    18. 1.8 Interprocess Communication and Process Synchronization
    19. 1.9 Protection and Security
    20. 1.10 Execution Semantics
    21. 1.11 Classification of Operating Systems
    22. 1.11.1 Multiprocessor Systems
    23. 1.11.2 Multiuser Systems
    24. 1.11.3 Multiprogram Systems
    25. 1.11.4 Multiprocess Systems
    26. 1.11.5 Time-sharing Systems
    27. 1.11.6 Multithread Systems
    28. 1.11.7 Preemptive Systems
    29. 1.11.8 Reentrant Kernels
    30. 1.11.9 Monolithic Kernels and Microkernel Systems
    31. 1.12 Designing Operating Systems
  8. Chapter 2: Hardware Platforms
    1. 2.1 Introduction
    2. 2.2 The Main Hardware Components
    3. 2.2.1 Bus
    4. 2.2.2 Main Memory
    5. RAM
    6. ROM
    7. 2.2.3 Processor
    8. Central Processing Unit
    9. Memory Management Unit
    10. Hardware Cache
    11. Timer Devices
    12. Protection Hardware
    13. Multiprocessor vs Multithreaded Processor
    14. Interrupt Controller
    15. 2.2.4 I/O Devices
    16. I/O Controller
    17. Disks
    18. Tapes
    19. Network Interface Cards
    20. 2.3 Hardware Layout
  9. Chapter 3: Software Platforms
    1. 3.1 Introduction
    2. 3.2 Different Views of Operating Systems
    3. 3.3 Bottom-Layer Subsystems
    4. 3.3.1 CPU Management
    5. 3.3.2 Memory Management
    6. 3.3.3 I/O-device Management
    7. 3.4 Middle-Layer Subsystems
    8. 3.4.1 Process Management
    9. 3.4.2 Virtual-memory Management
    10. 3.4.3 File-management System
    11. 3.4.4 Communication System
    12. 3.4.5 Virtual File System
    13. 3.5 Top-Layer Subsystems
    14. 3.5.1 Interrupt, System Call, and Exception
    15. 3.5.2 Utilities
    16. 3.5.3 Command Interpreter or Shell
    17. 3.5.4 System Libraries
    18. 3.6 Other Subsystems
    19. 3.6.1 Bootstrap
    20. 3.6.2 Time Management
    21. 3.6.3 Protection and Security
    22. 3.6.4 Module Management
  10. Chapter 4: Processes and Threads
    1. 4.1 Introduction
    2. 4.2 Process Abstraction
    3. 4.3 Programs vs Processes
    4. 4.4 Process Context and Process Descriptor
    5. 4.5 Process Address Space
    6. 4.5.1 Process Address Space Structure
    7. 4.5.2 Kernel Address Space
    8. 4.6 Process Execution Mode
    9. 4.7 Process Identification Information
    10. 4.7.1 User Identifier
    11. 4.7.2 Process Group Identifier
    12. 4.8 Interprocess Relationship
    13. 4.9 Process State
    14. 4.10 Process State Transition
    15. 4.11 Process Management
    16. 4.12 Threads and Their Management
    17. 4.12.1 Concurrency Granularity and Thread Abstraction
    18. 4.12.2 Thread and Process Relationship
    19. 4.12.3 The Benefits of Threads
    20. 4.12.4 Thread Synchronization
    21. 4.12.5 Thread Management
    22. Thread Library
    23. Multithread Kernel
    24. A Mixed System
    25. 4.12.6 A Typical Multithreaded Application
    26. 4.12.7 Issues with Multithreading
  11. Chapter 5: CPU Management
    1. 5.1 Introduction
    2. 5.2 Scheduling Objectives
    3. 5.3 Performance Metrics
    4. 5.4 A System Model
    5. 5.5 Two Broad Scheduling Classes: Preemptive vs Non-Preemptive
    6. 5.6 The Context Switch
    7. 5.7 Scheduling Schemes
    8. 5.7.1 First-come First-serve (FCFS) Scheduling
    9. 5.7.2 Shortest-job-first (SJF) Scheduling
    10. 5.7.3 Shortest-remaining-time-next (SRTN) Scheduling
    11. 5.7.4 Priority-based Scheduling
    12. Priority Implementation
    13. Priority Aging
    14. 5.7.5 Round-robin (RR) Scheduling
    15. The Effect of Time Quanta
    16. Variations of Round-rabin Scheduling
    17. 5.7.6 Fair-share Scheduling
    18. 5.7.7 Multilevel or Multiple-queue-based Scheduling
    19. 5.7.8 Multiprocessor Scheduling
    20. 5.7.9 Thread Scheduling
  12. Chapter 6: Interprocess Communications
    1. 6.1 Introduction
    2. 6.2 Interprocess Communications
    3. 6.3 Interprocess Communication Models
    4. 6.3.1 Message-passing Model
    5. 6.3.2 Shared-memory Model
    6. 6.3.3 Data Representation
    7. 6.4 Interprocess Communication Schemes
    8. 6.4.1 Signal System
    9. 6.4.2 Shared Memory Region
    10. 6.4.3 Message Queue
    11. 6.4.4 Pipe
    12. 6.4.5 FIFO
    13. 6.4.6 Socket
  13. Chapter 7: Process Synchronization
    1. 7.1 Introduction
    2. 7.2 Process Synchronization
    3. 7.3 Atypical Synchronization Problem
    4. 7.4 Classical Synchronization Problems
    5. 7.4.1 The Mutual Exclusion Problem
    6. 7.4.2 The Producer-Consumer Problem
    7. 7.4.3 The Readers-Writers Problem
    8. 7.4.4 The Dining-philosophers Problem
    9. 7.4.5 The Sleeping-barber Problem
    10. 7.5 Synchronization Solutions
    11. 7.5.1 Basic Progress Assumptions
    12. 7.5.2 Solution Characteristics
    13. 7.5.3 Solutions to the Mutual Exclusion Problem Using Atomic Variables
    14. A Naive Two-process Solution
    15. The Dekker Solution
    16. The Peterson Solution
    17. The Lamport Solution
    18. A Solution Using test-and-set Operation
    19. A Solution Using Swap Operation
    20. 7.5.4 Interrupt Disabling
    21. 7.5.5 Non-preemptive Kernels
    22. 7.5.6 Semaphores
    23. A Solution to the Mutual Exclusion Problem
    24. A Solution to the Producer-Consumer Problem
    25. A Solution to the Readers-Writers Problem
    26. A Solution to the Dining-philosophers Problem
    27. A Solution to the Sleeping-barber Problem
    28. 7.5.7 Spinlock
    29. 7.5.8 Critical Region
    30. 7.5.9 Conditional Critical Region
    31. A Solution to the Producer-Consumer Problem
    32. A Solution to the Readers-Writers Problem
    33. 7.5.10 Monitor
    34. 7.5.11 Comparison of Synchronization Primitives
    35. 7.6 Deadlock
    36. 7.6.1 Deadlock Prevention
    37. 7.6.2 Deadlock Avoidance
    38. Banker Algorithm
    39. Examples of the Banker Algorithm
    40. 7.6.3 Detection and Recovery
    41. 7.7 The Real Challenge
  14. Chapter 8: Memory Management
    1. 8.1 Introduction
    2. 8.2 Memory-Management System
    3. 8.3 Memory Hardware
    4. 8.4 Address Spaces and Address Translation
    5. 8.4.1 Memory-address Space
    6. 8.4.2 Program-identifier Space
    7. 8.4.3 Address Translation
    8. Address Binding
    9. Translation Utilities
    10. 8.4.4 Address-translation Schemes
    11. Compile Time Address Translation
    12. Load Time Address Translation
    13. Runtime Address Translation
    14. 8.4.5 Logical Address Space
    15. 8.4.6 Runtime Address-translation Schemes
    16. 8.5 Segmentation
    17. 8.5.1 Segment and Segment Block
    18. 8.5.2 Segment Table and Address Translation
    19. 8.5.3 Address Translation Overhead and Its Remedy
    20. 8.5.4 Memory Allocation
    21. Static Blocking
    22. Dynamic Blocking
    23. 8.5.5 Memory Fragmentation and Space Overhead
    24. 8.5.6 Segment Relocation
    25. 8.5.7 Memory Protection
    26. 8.5.8 Memory Sharing
    27. 8.6 Paging
    28. 8.6.1 Page and Frame
    29. 8.6.2 Page Table and Address Translation
    30. 8.6.3 Address Translation Overhead and Its Remedy
    31. 8.6.4 Memory Allocation
    32. 8.6.5 Memory Fragmentation and Space Overhead
    33. 8.6.6 Memory Relocation
    34. 8.6.7 Memory Protection
    35. 8.6.8 Memory Sharing
    36. 8.7 Paged Segmentation
    37. 8.7.1 Address Translation
    38. 8.7.2 Address Translation Overhead and Its Remedy
    39. 8.7.3 Memory Allocation
    40. 8.7.4 Memory Fragmentation and Space Overhead
    41. 8.7.5 Relocation
    42. 8.7.6 Memory Protection
    43. 8.7.7 Memory Sharing
  15. Chapter 9: Virtual Memory
    1. 9.1 Introduction
    2. 9.2 Virtual Memory
    3. 9.3 Memory Organization
    4. 9.4 Virtual-Memory Implementation
    5. 9.5 Demand Fetching
    6. 9.6 Demand Paging
    7. 9.6.1 Address Translation
    8. 9.6.2 The Effect of Page Fault
    9. 9.6.3 Execution Restart upon Page Fault
    10. 9.6.4 Frame Allocation
    11. 9.6.5 Page Replacement Algorithms
    12. FIFO Replacement Algorithm
    13. Second-chance Replacement Algorithm
    14. Least-recently-used Replacement Algorithm
    15. 9.6.6 The Constraints on Page-replacement Algorithms
    16. 9.6.7 Page-transfer Management
    17. 9.6.8 Thrashing and Its Remedy
    18. Reference String
    19. Reference Locality
    20. Working Set
    21. 9.7 Demand Segmentation
    22. 9.8 The Real Illusion
  16. Chapter 10: I/O Device Management
    1. 10.1 Introduction
    2. 10.2 I/O Devices
    3. 10.2.1 I/O Controllers
    4. 10.2.2 DMA Mode Data Transfer
    5. 10.2.3 SCSI Host Bus Adapter
    6. 10.3 Device Drivers
    7. 10.3.1 Driver Initialization
    8. 10.3.2 Software-Hardware Interactions
    9. Polling
    10. Interrupt Service Routines
    11. 10.4 I/O Subsystem
    12. 10.4.1 Device Types
    13. 10.4.2 Device Categories
    14. 10.4.3 I/O Subsystem Functionalities
    15. Device Status
    16. I/O Request Scheduling
    17. Data Cache
    18. 10.5 Disk Storage
    19. 10.5.1 Disk Geometry
    20. 10.5.2 Disk Drive
    21. 10.5.3 Disk-space Organization
    22. Sector Size
    23. Sector Address
    24. 10.5.4 Disk Formatting
    25. Physical Formatting
    26. Partitioning
    27. Logical Formatting
    28. 10.5.5 Disk Access
    29. 10.5.6 Disk Scheduling
    30. FCFS Scheduling
    31. Shortest-seek-time-first (SSTF) Scheduling
    32. Scan, C-scan, and Elevator Scheduling
    33. Scheduling in Hardware
    34. 10.5.7 Redundant Array of Inexpensive/Independent Disks (RAID)
    35. 10.6 The Network Interface Card
    36. 10.6.1 Ethernet Packet Format
    37. 10.6.2 Packet Descriptor
    38. 10.6.3 Software-Hardware Interaction
    39. 10.7 User Interface to Devices
  17. Chapter 11: File Systems
    1. 11.1 Introduction
    2. 11.2 File Systems
    3. 11.3 File Attributes
    4. 11.4 File Types
    5. 11.5 Operations
    6. 11.5.1 File Operations
    7. Create
    8. Delete
    9. Open/Close
    10. Reposition
    11. Read
    12. Write
    13. Truncate
    14. Memory Map
    15. 11.5.2 File-system Operations
    16. Initialize
    17. Mount
    18. Unmount
    19. 11.5.3 Extended Operations
    20. Hardlink
    21. Symbolic Link
    22. Dynamic Link
    23. 11.6 File Organization
    24. 11.6.1 File Tree
    25. 11.6.2 Directory Management
    26. 11.7 Device File
    27. 11.8 File Protection
    28. 11.9 Concurrency Control
    29. 11.10 File-System Implementation
    30. 11.10.1 Physical Organization
    31. 11.10.2 Space Allocation
    32. Contiguous Allocation
    33. Linked Allocation
    34. Extent Allocation
    35. Indexed Allocation
    36. UNIX File-space Allocation
    37. 11.10.3 Free-space Management
    38. Bit Map
    39. Trunked Free List
    40. 11.10.4 File-system Layout
    41. 11.10.5 File-system Journaling
    42. 11.11 Virtual File Systems
    43. 11.12 Runtime Structures
  18. Chapter 12: System Call, Interrupt, and Exception
    1. 12.1 Introduction
    2. 12.2 System Call
    3. 12.2.1 Address Space Switch
    4. 12.2.2 System-call Handler
    5. 12.2.3 Information Exchange
    6. 12.2.4 System-call Framework
    7. 12.2.5 System Library Support
    8. 12.3 Interrupt
    9. 12.3.1 Address Space Switch
    10. 12.3.2 Nested Interrupt
    11. 12.3.3 Interrupt Priority
    12. 12.3.4 Interrupt Coalescing
    13. 12.4 Exception
    14. 12.5 Programmable Interrupt Controller
    15. 12.6 Interrupt, Exception, and System Call Handlers
  19. Chapter 13: Protection and Security
    1. 13.1 Introduction
    2. 13.2 The Need for Security
    3. 13.3 Secure Software Systems
    4. 13.3.1 Need for Cost-effective Security
    5. 13.3.2 The Trinity of Troubles
    6. 13.4 Security Environments
    7. 13.4.1 Software Security vs Application Security
    8. 13.4.2 Internal Security vs Boundary Security
    9. 13.4.3 Malicious vs Incidental
    10. 13.4.4 Hardware vs Software
    11. 13.4.5 Unauthorized Use vs Denial of Service
    12. 13.4.6 Inside Attack vs Outside Attack
    13. 13.4.7 Security Attackers
    14. 13.5 Security Vulnerabilities
    15. 13.5.1 Buffer Overflow
    16. 13.5.2 Trap Doors or Back Doors
    17. 13.5.3 Cache Poisoning
    18. 13.5.4 Other Vulnerabilities
    19. 13.6 Access-Control-Based Security Systems
    20. 13.6.1 Object, Subject, and Access Control
    21. 13.6.2 Access-control Models
    22. 13.6.3 Discretionary Access-control Model
    23. Protection Domain
    24. Domain Switch
    25. 13.6.4 Implementing the Access-control Matrix
    26. Access-control List
    27. Capability List
    28. Merits and Demerits, and Composite Systems
    29. 13.7 Authentication
    30. 13.7.1 Password-based Authentication
    31. 13.7.2 Password Maintenance
    32. 13.8 Secure Communication
    33. 13.9 Application Security
    34. 13.9.1 Subversive Codes
    35. 13.9.2 Attack Types
    36. Trial and Error
    37. Spoofing
    38. 13.10 VIRUS
    39. 13.10.1 Droppers
    40. 13.10.2 Payloads
    41. 13.10.3 Detection and Counter Measures
    42. 13.11 Application Security Approaches
    43. 13.11.1 Firewall and Pop-up Blockers
    44. 13.11.2 Anti-virus and Anti-spam Software
    45. 13.11.3 Sandboxing
    46. 13.11.4 Software Updates/Patching
    47. 13.11.5 Honeypot Systems
  20. Chapter 14: Storage Hierarchy and Caching
    1. 14.1 Introduction
    2. 14.2 Storage Hierarchy
    3. 14.3 Data Cache
    4. 14.4 Cache Organization
    5. 14.5 Cache Access
    6. 14.6 Cache Populating: Demand Fetch vs Prefetch
    7. 14.7 Cache Management
    8. 14.8 Cache Replacement
    9. 14.8.1 The Optimal Replacement Scheme
    10. 14.8.2 The First-in First-out Scheme
    11. 14.8.3 The Least-recently-used Scheme
    12. 14.8.4 The Least-frequently-used Scheme
    13. 14.8.5 The Clock Scheme
    14. 14.9 Cache Concurrency
    15. 14.10 Cache Coherence
    16. 14.10.1 Data Consistency Semantics
    17. 14.10.2 Cache Coherence Protocol
    18. Snoopy Coherence
    19. Directory-based Coherence
    20. 14.11 Major Challenges
  21. Chapter 15: Real-time and Embedded Operating Systems
    1. 15.1 Introduction
    2. 15.2 The Characteristics of an RE System
    3. 15.3 The Hardware Elements of Real-Time Systems
    4. 15.3.1 Processing Elements
    5. 15.3.2 Memory Elements
    6. 15.3.3 Special I/O Devices
    7. 15.3.4 Communication and Other Elements
    8. 15.3.5 Real-time Embedded Hardware Systems
    9. 15.4 Operating Systems for RE Systems
    10. 15.5 The Structure of REOS
    11. 15.5.1 A Basic Interrupt-driven Task Model
    12. 15.5.2 The Nanokernel-based Model
    13. 15.5.3 The Microkernel-based Model
    14. 15.5.4 The Monolithic-kernel-based Model
    15. 15.6 CPU Scheduling
    16. 15.6.1 Scheduling Periodic Tasks
    17. Priority Scheduling Algorithm
    18. Rate Monotonic Scheduling Algorithm
    19. Earliest-deadline-first Scheduling Algorithm
    20. RM vs EDF
    21. Activation Adjusted Scheduling Algorithm
    22. 15.6.2 Scheduling Aperiodic and Sporadic Tasks
    23. Background Approach
    24. Polling Approach
    25. Variations
    26. 15.6.3 Energy Aware CPU Scheduling
    27. 15.7 Task Synchronization
    28. 15.7.1 Resource Sharing and the Priority-inversion Problem
    29. 15.7.2 Solutions to the Priority-inversion Problem
    30. 15.8 Memory Management
    31. 15.8.1 Static Memory Allocation
    32. 15.8.2 Dynamic Memory Allocation
    33. 15.9 File Systems
  22. Chapter 16: Distributed Operating Systems
    1. 16.1 Introduction
    2. 16.2 Distributed Systems
    3. 16.3 Goals and Challenges
    4. 16.3.1 Resource Sharing
    5. 16.3.2 Load Balancing
    6. 16.3.3 Computation Speedup
    7. 16.3.4 Electronic Communications
    8. 16.3.5 Availability and Fault tolerance
    9. 16.3.6 Design and Development Challenges
    10. 16.4 Computer Networks
    11. 16.4.1 Hardware Requirements
    12. 16.4.2 Network Topology
    13. Local-area Networks
    14. Wide-area Networks
    15. 16.5 Interprocess Communication
    16. 16.5.1 Communication Primitives
    17. 16.5.2 Sockets
    18. 16.5.3 Remote Procedure Call
    19. 16.6 System Environment
    20. 16.6.1 Network Operating Systems
    21. 16.6.2 Distributed Operating Systems
    22. 16.7 Distributed Applications
    23. 16.7.1 A Simple Model
    24. 16.7.2 Logical Clock
    25. 16.7.3 Mutual Exclusion
    26. Centralized Solution
    27. Decentralized Solution
    28. 16.7.4 Consensus
    29. 16.7.5 Leader Election
    30. 16.7.6 Termination Detection
    31. 16.7.7 Distributed File Systems
    32. 16.7.8 Deadlock Detection
    33. 16.7.9 Load Balancing
    34. 16.8 Fault Tolerance
    35. 16.8.1 Redundancy
    36. 16.8.2 Detection and Recovery
  23. Chapter 17: The Linux Operating System
    1. 17.1 An Overview of Linux
    2. 17.2 The Hardware Platform
    3. 17.2.1 CPU Registers
    4. 17.2.2 Memory-management Registers
    5. Segment Registers
    6. Page Registers
    7. 17.2.3 Other Registers
    8. 17.2.4 Processor Operating Modes
    9. 17.3 The Components of Linux
    10. 17.3.1 Bootstrap
    11. 17.3.2 Time Management
    12. 17.3.3 Kernel Module
    13. 17.4 Processes and Threads
    14. 17.4.1 Process Descriptor
    15. Process States
    16. Process Relationships
    17. Process Identification
    18. Process Group
    19. Process Owner Identification
    20. Process Priority
    21. The Working Directory
    22. 17.4.2 Setting up a Process Address Space
    23. 17.4.3 Setting up a Thread Address Space
    24. 17.4.4 Kernal Thread
    25. 17.5 CPU Management
    26. 17.5.1 CPU Scheduling
    27. 17.5.2 Context Switch
    28. 17.6 Interprocess Communications
    29. 17.6.1 Signals
    30. Signal Handler Execution
    31. Signal Restriction
    32. 17.6.2 Pipes and FIFO
    33. Pipe Implementation
    34. FIFO
    35. 17.6.3 User Semaphores
    36. 17.6.4 Message Queues
    37. 17.6.5 Shared Memory
    38. 17.7 Synchronization
    39. 17.7.1 Atomic Operations
    40. 17.7.2 Interrupt Disabling
    41. 17.7.3 Kernel Semaphore
    42. 17.7.4 Spinlock
    43. 17.7.5 Seqlock
    44. 17.7.6 Disabling Kernel Preemption
    45. 17.7.7 Kernel Path Synchronization
    46. 17.7.8 Deadlock Handling
    47. 17.8 Memory Management
    48. 17.8.1 Address Translation
    49. Segmentation
    50. Paging
    51. 17.8.2 Address Space Setup
    52. Process Address Space
    53. Kernel Space
    54. 17.8.3 Memory Allocation
    55. Contiguous Memory Allocator
    56. Allocation Priority
    57. Non-contiguous Memory Allocator
    58. 17.9 Virtual Memory
    59. 17.9.1 Memory Sharing
    60. 17.9.2 Memory Protection
    61. 17.9.3 Page-fault Handler
    62. 17.9.4 Page Reclamation
    63. 17.9.5 Process Creation
    64. 17.9.6 LWP Creation
    65. 17.10 I/O Subsystem and Device Management
    66. 17.11 File System
    67. 17.11.1 Virtual File System
    68. 17.11.2 Ext2 File System
    69. File Types
    70. File Organization
    71. File Attributes
    72. File Operations
    73. File Protection
    74. 17.11.3 File System Mount
    75. 17.11.4 Device File
    76. 17.11.5 Very Special Devices
    77. 17.11.6 File Lock
    78. 17.12 Interrupt, Exception, and System Call
    79. 17.12.1 Interrupt Handling
    80. 17.12.2 Exception Handling
    81. 17.12.3 System Call Handling
    82. 17.13 Protection and Security
    83. 17.14 Data Cache
    84. 17.15 Real-Time System Support
    85. 17.16 Networking
  24. Chapter 18: Windows XP
    1. 18.1 Windows XP Overview
    2. 18.2 The Hardware Platform
    3. 18.3 The Components of Windows XP
    4. 18.4 Process, Thread, Fiber, and Job
    5. 18.5 CPU Management
    6. 18.6 Interrupt, Exception, and System Call
    7. 18.7 Interprocess Communications
    8. 18.8 Synchronization
    9. 18.9 Memory Management
    10. 18.10 Virtual Memory
    11. 18.11 I/O Subsystem and Device Management
    12. 18.12 File System
    13. 18.13 Security
    14. 18.14 Data Cache
    15. 18.15 Networking
  25. Bibliography
  26. Notes
  27. Glossary
  28. Acknowledgements
  29. Copyright