Operating System Design, 2nd Edition

Table of contents

1. Cover Page
2. Half Title Page
3. Title Page
4. Copyright Page
5. Dedication
6. Contents
7. Preface
8. About the Author
9. Chapter 1 Introduction And Overview
   1. 1.1 Operating Systems
   2. 1.2 Approach Used In The Text
   3. 1.3 A Hierarchical Design
   4. 1.4 The Xinu Operating System
   5. 1.5 What An Operating System Is Not
   6. 1.6 An Operating System Viewed From The Outside
   7. 1.7 Remainder of the Text
   8. 1.8 Perspective
   9. 1.9 Summary
   10. Exercises
10. Chapter 2 Concurrent Execution And Operating System Services
    1. 2.1 Introduction
    2. 2.2 Programming Models For Multiple Activities
    3. 2.3 Operating System Services
    4. 2.4 Concurrent Processing Concepts And Terminology
    5. 2.5 Distinction Between Sequential And Concurrent Programs
    6. 2.6 Multiple Processes Sharing A Single Piece of Code
    7. 2.7 Process Exit And Process Termination
    8. 2.8 Shared Memory, Race Conditions, And Synchronization
    9. 2.9 Semaphores And Mutual Exclusion
    10. 2.10 Type Names Used In Xinu
    11. 2.11 Operating System Debugging With Kputc And Kprintf
    12. 2.12 Perspective
    13. 2.13 Summary
    14. Exercises
11. Chapter 3 An Overview Of The Hardware And Runtime Environment
    1. 3.1 Introduction
    2. 3.2 Physical And Logical Organizations of A Platform
    3. 3.3 Instruction Sets
    4. 3.4 General-purpose Registers
       1. 3.4 .1Galileo (Intel)
       2. 3.4 .2BeagleBone Black (ARM)
    5. 3.5 I/O Buses And The Fetch-Store Paradigm
    6. 3.6 Direct Memory Access
    7. 3.7 The Bus Address Space
    8. 3.8 Bus Startup And Configuration
    9. 3.9 Calling Conventions And The Runtime Stack
       1. 3.9.1 Galileo (Intel)
       2. 3.9.2 BeagleBone Black (ARM)
    10. 3.10 Interrupts And Interrupt Processing
    11. 3.11 Vectored Interrupts
    12. 3.12 Exception Vectors And Exception Processing
    13. 3.13 Clock Hardware
    14. 3.14 Serial Communication
    15. 3.15 Polled vs. Interrupt-driven I/O
    16. 3.16 Storage Layout
    17. 3.17 Memory Protection
    18. 3.18 Hardware Details And A System On Chip Architecture
    19. 3.19 Perspective
    20. 3.20 Hardware References
    21. Exercises
12. Chapter 4 List And Queue Manipulation
    1. 4.1 Introduction
    2. 4.2 A Unified Structure for Linked Lists of Processes
    3. 4.3 A Compact List Data Structure
    4. 4.4 Implementation of the Queue Data Structure
    5. 4.5 Inline Queue Manipulation Functions
    6. 4.6 Basic Functions To Extract A Process From A List
    7. 4.7 FIFO Queue Manipulation
    8. 4.8 Manipulation of Priority Queues
    9. 4.9 List Initialization
    10. 4.10 Perspective
    11. 4.11 Summary
    12. Exercises
13. Chapter 5 Scheduling And Context Switching
    1. 5.1 Introduction
    2. 5.2 The Process Table
    3. 5.3 Process States
    4. 5.4 Ready And Current States
    5. 5.5 A Scheduling Policy
    6. 5.6 Implementation Of Scheduling
    7. 5.7 Deferred Rescheduling
    8. 5.8 Implementation Of Context Switching
    9. 5.9 State Saved In Memory
    10. 5.10 Context Switch Operation
        1. 5.10.1 Galileo (Intel)
        2. 5.10.2 BeagleBone Black (ARM)
    11. 5.11 An Address At Which To Restart A Process
    12. 5.12 Concurrent Execution And A Null Process
    13. 5.13 Making A Process Ready And The Scheduling Invariant
    14. 5.14 Other Process Scheduling Algorithms
    15. 5.15 Perspective
    16. 5.16 Summary
    17. Exercises
14. Chapter 6 More Process Management
    1. 6.1 Introduction
    2. 6.2 Process Suspension And Resumption
    3. 6.3 Self–suspension And Information Hiding
    4. 6.4 The Concept Of A System Call
    5. 6.5 Interrupt Control With Disable And Restore
    6. 6.6 A System Call Template
    7. 6.7 System Call Return Values SYSERR And OK
    8. 6.8 Implementation of Suspend
    9. 6.9 Suspending The Current Process
    10. 6.10 The Value Returned By Suspend
    11. 6.11 Process Termination And Process Exit
    12. 6.12 Process Creation
    13. 6.13 Other Process Manager Functions
    14. 6.14 Summary
    15. Exercises
15. Chapter 7 Coordination Of Concurrent Processes
    1. 7.1 Introduction
    2. 7.2 The Need for Synchronization
    3. 7.3 A Conceptual View of Counting Semaphores
    4. 7.4 Avoidance of Busy Waiting
    5. 7.5 Semaphore Policy And Process Selection
    6. 7.6 The Waiting State
    7. 7.7 Semaphore Data Structures
    8. 7.8 The Wait System Call
    9. 7.9 The Signal System Call
    10. 7.10 Static And Dynamic Semaphore Allocation
    11. 7.11 Example Implementation of Dynamic Semaphores
    12. 7.12 Semaphore Deletion
    13. 7.13 Semaphore Reset
    14. 7.14 Coordination Across Parallel Processors (Multicore)
    15. 7.15 Perspective
    16. 7.16 Summary
    17. Exercises
16. Chapter 8 Message Passing
    1. 8.1 Introduction
    2. 8.2 Two Types of Message Passing Services
    3. 8.3 Limits On Resources Used By Messages
    4. 8.4 Message Passing Functions And State Transitions
    5. 8.5 Implementation of Send
    6. 8.6 Implementation of Receive
    7. 8.7 Implementation Of Non-Blocking Message Reception
    8. 8.8 Perspective
    9. 8.9 Summary
    10. Exercises
17. Chapter 9 Basic Memory Management
    1. 9.1 Introduction
    2. 9.2 Types of Memory
    3. 9.3 Definition of A Heavyweight Process
    4. 9.4 Memory Management In Our Example System
    5. 9.5 Program Segments And Regions of Memory
    6. 9.6 Dynamic Memory Allocation
    7. 9.7 Design Of The Low–level Memory Manager
    8. 9.8 Allocation Strategy And Memory Persistence
    9. 9.9 Keeping Track of Free Memory
    10. 9.10 Implementation Of Low–level Memory Management
    11. 9.11 Data Structure Definitions Used With Free Memory
    12. 9.12 Allocating Heap Storage
    13. 9.13 Allocating Stack Storage
    14. 9.14 Releasing Heap And Stack Storage
    15. 9.15 Perspective
    16. 9.16 Summary
    17. Exercises
18. Chapter 10 High-level Memory Management And Virtual Memory
    1. 10.1 Introduction
    2. 10.2 Partitioned Space Allocation
    3. 10.3 Buffer Pools
    4. 10.4 Allocating A Buffer
    5. 10.5 Returning Buffers To the Buffer Pool
    6. 10.6 Creating A Buffer Pool
    7. 10.7 Initializing the Buffer Pool Table
    8. 10.8 Virtual Memory And Memory Multiplexing
    9. 10.9 Real And Virtual Address Spaces
    10. 10.10 Hardware for Demand Paging
    11. 10.11 Address Translation With A Page Table
    12. 10.12 Metadata In A Page Table Entry
    13. 10.13 Demand Paging And Design Questions
    14. 10.14 Page Replacement And Global Clock
    15. 10.15 Perspective
    16. 10.16 Summary
    17. Exercises
19. Chapter 11 High-level Message Passing
    1. 11.1 Introduction
    2. 11.2 Inter–process Communication Ports
    3. 11.3 The Implementation of Ports
    4. 11.4 Port Table Initialization
    5. 11.5 Port Creation
    6. 11.6 Sending A Message To A Port
    7. 11.7 Receiving A Message From A Port
    8. 11.8 Port Deletion And Reset
    9. 11.9 Perspective
    10. 11.10 Summary
    11. Exercises
20. Chapter 12 Interrupt Processing
    1. 12.1 Introduction
    2. 12.2 The Advantage of Interrupts
    3. 12.3 Interrupt Processing
    4. 12.4 Vectored Interrupts
    5. 12.5 Integration of Interrupts and Exceptions
       1. 12.5.1 Galileo (Intel)
       2. 12.5.2 BeagleBone Black (ARM)
    6. 12.6 ARM Exception Vectors Using Code
    7. 12.7 Assignment Of Device Interrupt Vector Numbers
    8. 12.8 Interrupt Dispatching
    9. 12.9 The Structure Of Interrupt Software
       1. 12.9.1 Galileo (Intel)
       2. 12.9.2 BeagleBone Black (ARM)
    10. 12.10 Disabling Interrupts
    11. 12.11 Constraints On Functions That Interrupt Code Invokes
    12. 12.12 The Need To Reschedule During An Interrupt
    13. 12.13 Rescheduling During An Interrupt
    14. 12.14 Perspective
    15. 12.15 Summary
    16. Exercises
21. Chapter 13 Real-time Clock Management
    1. 13.1 Introduction
    2. 13.2 Timed Events
    3. 13.3 Real-time Clocks And Timer Hardware
    4. 13.4 Handling Real-time Clock Interrupts
    5. 13.5 Delay And Preemption
    6. 13.6 Implementation Of Preemption
    7. 13.7 Efficient Management of Delay With A Delta List
    8. 13.8 Delta List Implementation
    9. 13.9 Putting A Process To Sleep
    10. 13.10 Timed Message Reception
    11. 13.11 Awakening Sleeping Processes
    12. 13.12 Clock Interrupt Processing
    13. 13.13 Clock Initialization
    14. 13.14 Perspective
    15. 13.15 Summary
    16. Exercises
22. Chapter 14 Device–independent Input and Output
    1. 14.1 Introduction
    2. 14.2 Conceptual Organization of I/O and Device Drivers
    3. 14.3 Interface and Driver Abstractions
    4. 14.4 An Example I/O Interface
    5. 14.5 The Open-Read-Write-Close Paradigm
    6. 14.6 Bindings For I/O Operations And Device Names
    7. 14.7 Device Names In Xinu
    8. 14.8 The Concept Of A Device Switch Table
    9. 14.9 Multiple Copies Of A Device And Shared Drivers
    10. 14.10 The Implementation Of High–level I/O Operations
    11. 14.11 Other High–level I/O Functions
    12. 14.12 Open, Close, And Reference Counting
    13. 14.13 Null And Error Entries In Devtab
    14. 14.14 Initialization Of The I/O System
    15. 14.15 Perspective
    16. 14.16 Summary
    17. Exercises
23. Chapter 15 An Example Device Driver
    1. 15.1 Introduction
    2. 15.2 Serial Communication Using UART Hardware
    3. 15.3 The Tty Abstraction
    4. 15.4 Organization Of A Tty Device Driver
    5. 15.5 Request Queues And Buffers
    6. 15.6 Synchronization Of Upper Half And Lower Half
    7. 15.7 UART Hardware FIFOs And Driver Design
    8. 15.8 The Concept Of A Control Block
    9. 15.9 Tty Control Block And Data Declarations
    10. 15.10 Minor Device Numbers
    11. 15.11 Upper–half Tty Character Input (ttygetc)
    12. 15.12 Upper–half Tty Read Function (ttyread)
    13. 15.13 Upper–half Tty Character Output (ttyputc)
    14. 15.14 Starting Output (ttykickout)
    15. 15.15 Upper–half Tty Multiple Character Output (ttywrite)
    16. 15.16 Lower–half Tty Driver Function (ttyhandler)
    17. 15.17 Output Interrupt Processing (ttyhandle_out)
    18. 15.18 Tty Input Processing (ttyhandle_in)
        1. 15.18.1 Raw Mode Processing
        2. 15.18.2 Cbreak Mode Processing
        3. 15.18.3 Cooked Mode Processing
    19. 15.19 Tty Control Block Initialization (ttyinit)
    20. 15.20 Device Driver Control (ttycontrol)
    21. 15.21 Perspective
    22. 15.22 Summary
    23. Exercises
24. Chapter 16 DMA Devices And Drivers (Ethernet)
    1. 16.1 Introduction
    2. 16.2 Direct Memory Access And Buffers
    3. 16.3 Multiple Buffers And Rings
    4. 16.4 An Example Ethernet Driver Using DMA
    5. 16.5 Device Hardware Definitions and Constants
    6. 16.6 Rings And Buffers In Memory
    7. 16.7 Definitions Of An Ethernet Control Block
    8. 16.8 Device And Driver Initialization
    9. 16.9 Reading From An Ethernet Device
    10. 16.10 Writing To An Ethernet Device
    11. 16.11 Handling Interrupts From An Ethernet Device
    12. 16.12 Ethernet Control Functions
    13. 16.13 Perspective
    14. 16.14 Summary
    15. Exercises
25. Chapter 17 A Minimal Internet Protocol Stack
    1. 17.1 Introduction
    2. 17.2 Required Functionality
    3. 17.3 Simultaneous Conversations, Timeouts, And Processes
    4. 17.4 A Consequence Of The Design
    5. 17.5 ARP Functions
    6. 17.6 Definition Of A Network Packet
    7. 17.7 The Network Input Process
    8. 17.8 Definitions For IP
    9. 17.9 IP Functions
    10. 17.10 Definition Of The UDP Table
    11. 17.11 UDP Functions
    12. 17.12 Internet Control Message Protocol
    13. 17.13 Dynamic Host Configuration Protocol
    14. 17.14 Perspective
    15. 17.15 Summary
    16. Exercises
26. Chapter 18 A Remote Disk Driver
    1. 18.1 Introduction
    2. 18.2 The Disk Abstraction
    3. 18.3 Operations A Disk Driver Supports
    4. 18.4 Block Transfer And High-level VO Functions
    5. 18.5 A Remote Disk Paradigm
    6. 18.6 The Important Concept Of Caching
    7. 18.7 Semantics Of Disk Operations
    8. 18.8 Definition Of Driver Data Structures
    9. 18.9 Driver Initialization (rdsinit)
    10. 18.10 The Upper-half Open Function (rdsopen)
    11. 18.11 The Remote Communication Function (rdscomm)
    12. 18.12 The Upper-half Write Function (rdswrite)
    13. 18.13 The Upper-half Read Function (rdsread)
    14. 18.14 Flushing Pending Requests
    15. 18.15 The Upper-half Control Function (rdscontrol)
    16. 18.16 Allocating A Disk Buffer (rdsbufalloc)
    17. 18.17 The Upper-half Close Function (rdsclose)
    18. 18.18 The Lower-half Communication Process (rdsprocess)
    19. 18.19 Perspective
    20. 18.20 Summary
    21. Exercises
27. Chapter 19 File Systems
    1. 19.1 What Is A File System?
    2. 19.2 An Example Set Of File Operations
    3. 19.3 Design Of A Local File System
    4. 19.4 Data Structures For The Xinu File System
    5. 19.5 Implementation Of The Index Manager
    6. 19.6 Clearing An Index Block (Ifibclear)
    7. 19.7 Retrieving An Index Block (lfibget)
    8. 19.8 Storing An Index Block (lfibput)
    9. 19.9 Allocating An Index Block From The Free List (lfiballoc)
    10. 19.10 Allocating A Data Block From The Free List (lfdballoc)
    11. 19.11 Using The Device-Independent I/O Functions For Files
    12. 19.12 File System Device Configuration And Function Names
    13. 19.13 The Local File System Open Function (lfsopen)
    14. 19.14 Closing A File Pseudo-Device (lflclose)
    15. 19.15 Flushing Data To Disk (lfflush)
    16. 19.16 Bulk Transfer Functions For A File (lflwrite, lflread)
    17. 19.17 Seeking To A New Position In the File (lflseek)
    18. 19.18 Extracting One Byte From A File (lflgetc)
    19. 19.19 Changing One Byte In A File (lflputc)
    20. 19.20 Loading An Index Block And A Data Block (lfsetup)
    21. 19.21 Master File System Device Initialization (lfsinit)
    22. 19.22 Pseudo-Device Initialization (lflinit)
    23. 19.23 File Truncation (lftruncate)
    24. 19.24 Initial File System Creation (lfscreate)
    25. 19.25 Perspective
    26. 19.26 Summary
    27. Exercises
28. Chapter Chapter 20 A Remote File Mechanism
    1. 20.1 Introduction
    2. 20.2 Remote File Access
    3. 20.3 Remote File Semantics
    4. 20.4 Remote File Design And Messages
    5. 20.5 Remote File Server Communication (rfscomm)
    6. 20.6 Sending A Basic Message (rfsndmsg)
    7. 20.7 Network Byte Order
    8. 20.8 A Remote File System Using A Device Paradigm
    9. 20.9 Opening A Remote File (rfsopen)
    10. 20.10 Checking The File Mode (rfsgetmode)
    11. 20.11 Closing A Remote File (rflclose)
    12. 20.12 Reading From A Remote File (rflread)
    13. 20.13 Writing To A Remote File (rflwrite)
    14. 20.14 Seeking On A Remote File (rflseek)
    15. 20.15 Character I/O On A Remote File (rflgetc, rflputc)
    16. 20.16 Remote File System Control Functions (rfscontrol)
    17. 20.17 Initializing The Remote File System (rfsinit, rflinit)
    18. 20.18 Perspective
    19. 20.19 Summary
    20. Exercises
29. Chapter Chapter 21 A Syntactic Namespace
    1. 21.1 Introduction
    2. 21.2 Transparency And A Namespace Abstraction
    3. 21.3 Myriad Naming Schemes
       1. 21.3.1 Ms-Dos
       2. 21.3.2 Unix
       3. 21.3.3 V System
       4. 21.3.4 Ibis
    4. 21.4 Naming System Design Alternatives
    5. 21.5 Thinking About Names Syntactically
    6. 21.6 Patterns And Replacements
    7. 21.7 Prefix Patterns
    8. 21.8 Implementation Of A Namespace
    9. 21.9 Namespace Data Structures And Constants
    10. 21.10 Adding Mappings To The Namespace Prefix Table
    11. 21.11 Mapping Names With The Prefix Table
    12. 21.12 Opening A Named File
    13. 21.13 Namespace Initialization
    14. 21.14 Ordering Entries In The Prefix Table
    15. 21.15 Choosing A Logical Namespace
    16. 21.16 A Default Hierarchy And The Null Prefix
    17. 21.17 Additional Object Manipulation Functions
    18. 21.18 Advantages And Limits Of The Namespace Approach
    19. 21.19 Generalized Patterns
    20. 21.20 Perspective
    21. 21.21 Summary
    22. Exercises
30. Chapter 22 System Initialization
    1. 22.1 Introduction
    2. 22.2 Bootstrap: Starting From Scratch
    3. 22.3 An Example Of Booting Over A Network
    4. 22.4 Operating System Initialization
    5. 22.5 Xinu Initialization
    6. 22.6 Xinu System Startup
    7. 22.7 Transforming A Program Into A Process
    8. 22.8 Perspective
    9. 22.9 Summary
    10. Exercises
31. Chapter 23 Subsystem Initialization And Memory Marking
    1. 23.1 Introduction
    2. 23.2 Self-initializing Modules
    3. 23.3 Self-initializing Modules In A Concurrent System
    4. 23.4 Self-initialization In The Presence Of Reboot
    5. 23.5 Initialization Using Accession Numbers
    6. 23.6 A Generalized Memory Marking Scheme
    7. 23.7 Data Declarations For The Memory Marking System
    8. 23.8 Implementation Of Marking
    9. 23.9 Perspective
    10. 23.10 Summary
    11. Exercises
32. Chapter 24 Exception Handling
    1. 24.1 Introduction
    2. 24.2 Terminology: Faults, Checks, Traps, And Exceptions
    3. 24.3 Vectored Exceptions And Maskable Interrupts
    4. 24.4 Types Of Exceptions
    5. 24.5 Handling Exceptions
    6. 24.6 Exception Vector Initialization
    7. 24.7 Panic In The Face Of Catastrophic Problems
    8. 24.8 Implementation Of Panic
    9. 24.9 Perspective
    10. 24.10 Summary
    11. Exercises
33. Chapter 25 System Configuration
    1. 25.1 Introduction
    2. 25.2 The Need For Multiple Configurations
    3. 25.3 Configuration In Xinu
    4. 25.4 Contents Of The Xinu Configuration File
       1. 25.4.1 Section 1: Type Declarations
       2. 25.4.2 Section 2: Device Specifications
       3. 25.4.3 Symbolic Constants
    5. 25.5 Computation Of Minor Device Numbers
    6. 25.6 Steps In Configuring A Xinu System
    7. 25.7 Perspective
    8. 25.8 Summary
    9. Exercises
34. Chapter 26 An Example User Interface: The Xinu Shell
    1. 26.1 Introduction
    2. 26.2 What Is A User Interface?
    3. 26.3 Commands And Design Principles
    4. 26.4 Design Decisions For A Simplified Shell
    5. 26.5 Shell Organization And Operation
    6. 26.6 The Definition Of Lexical Tokens
    7. 26.7 The Definition Of Command-Line Syntax
    8. 26.8 Implementation Of The Xinu Shell
    9. 26.9 Storage Of Tokens
    10. 26.10 Code For The Lexical Analyzer
    11. 26.11 The Heart Of The Command Interpreter
    12. 26.12 Command Name Lookup And Builtin Processing
    13. 26.13 Arguments Passed To Commands
    14. 26.14 Passing Arguments To A Non-builtin Command
    15. 26.15 I/O Redirection
    16. 26.16 An Example Command Function (sleep)
    17. 26.17 Perspective
    18. 26.18 Summary
    19. Exercises
35. Chapter Appendix 1: Porting An Operating System
    1. A1.1 Introduction
    2. A1.2 Motivation: Evolving Hardware
    3. A1.3 Steps Taken When Porting An Operating System
       1. A1.3.1 Learning About The Hardware
       2. A1.3.2 Build Cross-Development Tools
       3. A1.3.3 Learn The Compiler's Calling Conventions
       4. A1.3.4 Build A Bootstrap Mechanism
       5. A1.3.5 Devise A Basic Polled Output Function
       6. A1.3.6 Load And Run A Sequential Program
       7. A1.3.7 Port And Test The Basic Memory Manager
       8. A1.3.8 Port The Context Switch And Process Creation Functions
       9. A1.3.9 Port And Test The Remaining Process Manager Functions
       10. A1.3.10 Build An Interrupt Dispatcher
       11. A1.3.11 Port And Test The Real-Time Clock Functions
       12. A1.3.12 Port And Test A Tty Driver
       13. A1.3.13 Port Or Create Drivers For An Ethernet And Other Devices
       14. A1.3.14 Port The Network Stack, Including Internet Protocols
       15. A1.3.15 Port The Remote Disk And RAM Disk Modules
       16. A1.3.16 Port The Local And Remote File System Modules
       17. A1.3.17 Port The Xinu Shell And Other Applications
    4. A1.4 Programming To Accommodate Change
    5. A1.5 Summary
36. Chapter Appendix 2: Xinu Design Notes
    1. A2.1 Introduction
    2. A2.2 Overview
    3. A2.3 Xinu Characteristics
    4. A2.4 Xinu Implementation
    5. A2.5 Major Concepts And Implementation
37. Index