Table of Contents: PC version of Operating System Design
Preface To The PC Edition
Foreword To The First Edition
Preface To The First Edition
Chapter 1 Introduction and Overview
- 1.1 Operating Systems 1
- 1.2 Our Approach 2
- 1.3 What An Operating System Is Not 3
- 1.4 An Operating System Viewed From The Outside 4
- 1.4.1 The PC-Xinu Small Machine Environment 4
- 1.4.2 PC-Xinu Services 4
- 1.4.3 Concurrent Processing 5
- 1.4.4 The Distinction Between Programs And Processes 6
- 1.4.5 Process Exit 10
- 1.4.6 Shared Memory 10
- 1.4.7 Synchronization 12
- 1.4.8 Mutual Exclusion 14
- 1.5 An Operating System Viewed From The Inside 15
- 1.6 Summary 17
- For Further Study 18
- Exercises 18
Chapter 2 An Overview of the Machine and Run-Time Environment
- 2.1 The Machine 19
- 2.2 Physical Organization Of The PC 20
- 2.3 Logical Organization Of The PC 21
- 2.3.1 The Address Space 21
- 2.3.2 Registers In The 8088 23
- 2.3.3 FLAGS Word 24
- 2.3.4 Vectored Interrupts 25
- 2.3.5 Exceptional Conditions 26
- 2.3.6 Software Interrupts 27
- 2.3.7 The ROM BIOS 27
- 2.3.8 BIOS Interrupt Service Routines 28
- 2.3.9 Pseudo-device interrupts 29
- 2.3.10 Interrupt Vector Summary 29
- 2.4 Standard PC I/O Devices 29
- 2.4.1 Keyboard 30
- 2.4.2 Video Display 31
- 2.4.3 Floppy Disk 32
- 2.4.4 The Pieces Of Disk Hardware 34
- 2.4.5 Logical sector numbers 35
- 2.4.6 Real-Time Clock 36
- 2.5 The C Run-Time Environment 37
- 2.6 Assembly Language Interface 39
- 2.6.1 Low-Level Keyboard Input 40
- 2.6.2 Low-Level Video Display 44
- 2.6.3 Low-Level Disk Services 47
- 2.7 Summary 51
- For Further Study 52
- Exercises 52
Chapter 3 List and Queue Manipulation
- 3.1 Linked Lists Of Processes 55
- 3.2 Implementation Of The Q Structure 57
- 3.2.1 In-Line Q Functions 59
- 3.2.2 FIFO Queue Manipulation 59
- 3.3 Priority Queue Manipulation 61
- 3.4 List Initialization 63
- 3.5 Summary 65
- For Further Study 65
- Exercises 65
Chapter 4 Scheduling and Context Switching
- 4.1 The Process Table 67
- 4.2 Process States 69
- 4.3 Selecting A Ready Process 70
- 4.4 The Null Process 75
- 4.5 Making A Process Ready 76
- 4.6 Summary 77
- For Further Study 77
- Exercises 77
Chapter 5 More Process Management
- 5.1 Process Suspension And Resumption 79
- 5.1.1 Implementation Of Resume 80
- 5.1.2 The Return Values SYSERR And OK 82
- 5.2 System Calls 82
- 5.2.1 Disable and Restore 82
- 5.2.2 Implementation of Suspend 84
- 5.2.3 Suspending The Current Process 85
- 5.3 Process Termination 86
- 5.4 Kernel Declarations 88
- 5.5 Process Creation 90
- 5.6 Utility Procedures 94
- 5.7 Summary 96
- For Further Study 97
- Exercises 97
Chapter 6 Process Coordination
- 6.1 Low-Level Coordination Techniques 100
- 6.2 Implementation Of High-Level Coordination Primitives 100
- 6.2.1 Semaphore Data Structures 101
- 6.3 Semaphore Creation and Deletion 105
- 6.4 Returning The Semaphore Count 108
- 6.5 Other Semaphore Utilities 109
- 6.6 Summary 110
- For Further Study 111
- Exercises 111
Chapter 7 Message Passing
- 7.1 Message Passing In PC-Xinu 113
- 7.2 Implementation Of Send 114
- 7.3 Implementation Of Receive 118
- 7.4 Summary 120
- For Further Study 120
- Exercises 121
Chapter 8 Memory Management
- 8.1 Memory Management On The 8088 124
- 8.2 Dynamic Memory Requirements In PC-Xinu 124
- 8.3 Low-Level Memory Management Procedures 125
- 8.4 The Location Of Allocated Storage 125
- 8.5 The Implementation Of PC-Xinu Memory Management 126
- 8.5.1 Allocating Storage 127
- 8.5.2 Releasing Storage 129
- 8.6 Summary 131
- For Further Study 131
- Exercises 132
Chapter 9 Interrupt Processing
- 9.1 Dispatching Interrupts 133
- 9.2 The Interrupt Dispatcher 134
- 9.2.1 The Intmap table 134
- 9.2.2 Implementation of the Interrupt Dispatcher 140
- 9.2.3 Deferred Rescheduling 140
- 9.2.4 To BIOS or Not to BIOS 141
- 9.3 Process Control Of Deferred Rescheduling 141
- 9.4 The Rules For Interrupt Processing 144
- 9.5 Rescheduling While Processing An Interrupt 145
- 9.6 PC Interrupt Vectors 146
- 9.7 Summary 147
- For Further Study 147
- Exercises 148
Chapter 10 Real-Time Clock Management
- 10.1 The Real-Time Clock Mechanism 149
- 10.2 PC Real-Time Clock Interrupts 150
- 10.3 The Use Of A Real-Time Clock 151
- 10.4 Delta List Processing 152
- 10.5 Putting A Process To Sleep 154
- 10.6 Delays Measured In Seconds 156
- 10.7 Clock Interrupt Processing 158
- 10.8 Awakening Sleeping Processes 159
- 10.9 Deferred Clock Processing 160
- 10.9.1 Procedures For Changing To And From Deferred Mode 160
- 10.10 Clock Initialization 161
- 10.11 Summary 162
- For Further Study 162
- Exercises 163
Chapter 11 Device Independent Input and Output
- 11.1 Properties Of The Input And Output Interface 166
- 11.2 Abstract Operations 166
- 11.3 Binding Abstract Operations To Real Devices 167
- 11.4 Binding I/O Calls To Device Drivers At Run-Time 168
- 11.5 The Implementation Of High-Level I/O Operations 171
- 11.6 Translating Device Names Into Descriptors 175
- 11.7 Opening And Closing Devices 175
- 11.8 Null And Error Entries In Devtab 177
- 11.9 Initialization Of The I/O System 178
- 11.10 Interrupt Vector Initialization 182
- 11.11 Summary 184
- For Further Study 184
- Exercises 185
Chapter 12 An Example Device Driver
- 12.1 The Device Type Tty 187
- 12.2 Upper And Lower Halves Of The Device Driver 188
- 12.3 Synchronization Of The Upper And Lower Halves 190
- 12.4 Control Block And Buffer Declarations 190
- 12.5 Upper-Half Tty Input Routines 194
- 12.6 Upper-Half Tty Output Routines 198
- 12.7 Lower-Half Tty Driver Routines 202
- 12.7.1 Watermarks And Delayed Signals 205
- 12.7.2 Lower-Half Input Processing 205
- 12.7.3 Cooked Mode And Cbreak Mode Processing 211
- 12.8 Keyboard Interrupt Handling 212
- 12.9 Tty Control Block Initialization 212
- 12.10 Device Driver Control 214
- 12.11 Summary 216
- For Further Study 216
- Exercises 216
Chapter 13 System Initialization
- 13.1 Starting From Scratch 219
- 13.2 Booting PC-Xinu 220
- 13.3 System Startup 221
- 13.4 Transforming The Program Into A Process 228
- 13.5 Summary 231
- For Further Study 231
- Exercises 231
Chapter 14 Window Management
- 14.1 Windows As Pseudo-Devices 233
- 14.2 Window-Specific Fields In The tty Structure 234
- 14.2.1 The CURSOR Type 234
- 14.2.2 Relative Cursor Positions 235
- 14.2.3 Window Borders And Character Attributes 235
- 14.3 Opening A Window 236
- 14.4 Upper-Level Window Driver Routines 245
- 14.4.1 Window Output Operations 245
- 14.4.2 Window Input And Control Operations 249
- 14.4.3 Closing A Window 253
- 14.5 The Lower-Half Window Output Server Process 255
- 14.6 Low-Level PC Screen Operations 260
- 14.7 Window Keyboard Input 262
- 14.8 Window Driver Initialization 263
- 14.9 Summary 264
- For Further Study 265
- Exercises 265
Chapter 15 High-Level Memory Management and Message Passing
- 15.1 Self-Initializing Modules 268
- 15.1.1 Specifying Initialization 268
- 15.1.2 Automatic Initialization 268
- 15.2 Memory Marking 269
- 15.3 Implementation Of Memory Marking 269
- 15.4 Partitioned Space Allocation 271
- 15.5 Buffer Pools 272
- 15.6 Returning Buffers To The Buffer Pool 275
- 15.7 Creating A Buffer Pool 277
- 15.8 Initializing The Buffer Pool Table 278
- 15.9 Communication Ports 279
- 15.10 The Implementation Of Ports 279
- 15.10.1 Ports Initialization 281
- 15.10.2 Port Creation 283
- 15.10.3 Sending To Ports 285
- 15.10.4 Receiving From Ports 288
- 15.11 Other Operations On Ports 289
- 15.12 Summary 294
- For Further Study 294
- Exercises 294
Chapter 16 A Disk Driver
- 16.1 Operations Supplied By The Disk Driver 297
- 16.2 The List Of Pending Disk Requests 298
- 16.3 Enqueuing Disk Requests 300
- 16.4 Optimizing The Request Queue 303
- 16.5 Driver Initialization 305
- 16.6 The Upper-Half Read Routine 307
- 16.7 The Upper-Half Write Routine 309
- 16.8 Implementation Of The Upper-Half Write Routine 310
- 16.9 The Upper-Half Seek Routine 311
- 16.10 The Lower-Half Of The Disk Driver 313
- 16.11 Flushing Pending Requests 315
- 16.12 Summary 318
- For Further Study 318
- Exercises 319
Chapter 17 File Systems
- 17.1 What Is A File System? 321
- 17.2 Disk And File Servers 323
- 17.3 A Local File System 323
- 17.4 Data Structures For The File System 324
- 17.5 Implementation Of The Index Manager 325
- 17.6 Operations On I-Blocks 327
- 17.6.1 Clearing An I-Block 327
- 17.6.2 Reading An I-Block 327
- 17.6.3 Writing An I-Block 328
- 17.6.4 Allocating I-Blocks From The Free List 330
- 17.6.5 Returning I-Blocks To The Free List 331
- 17.7 The Directory Structure 333
- 17.8 Using The Device Switch Table For Files 334
- 17.9 Establishing A Pseudo-Device 337
- 17.10 Pseudo-Device Driver Routines 343
- 17.10.1 Index Management Routines 346
- 17.10.2 The Pseudo-Device Seek Routine 349
- 17.10.3 The Pseudo-Device Getc Routine 350
- 17.10.4 The Pseudo-Device Putc Routine 352
- 17.10.5 The Pseudo-Device Read Routine 353
- 17.10.6 The Pseudo-Device Write Routine 354
- 17.10.7 The Pseudo-Device Close Routine 355
- 17.10.8 The Pseudo-Device Initialization Routine 357
- 17.11 Summary 358
- For Further Study 358
- Exercises 358
Chapter 18 MS-DOS File Interface
- 18.1 File Operations Available Through MS-DOS 361
- 18.2 Using The Device Switch Table For MS-DOS Files 367
- 18.3 Establishing A Pseudo-Device 369
- 18.4 MS-DOS Pseudo-Device Driver Routines 373
- 18.4.1 MS-DOS File Input/Output And Seek Operations 375
- 18.4.2 Closing The Pseudo-Device 380
- 18.4.3 MS-DOS Pseudo-Device Initialization 381
- 18.5 MS-DOS File System Control Operations 382
- 18.6 Summary 383
- For Further Study 383
- Exercises 383
Chapter 19 Exception Handling and Support Routines
- 19.1 Exceptions, Traps, And Illegal Interrupts 385
- 19.2 Initialization Of Interrupt Vectors 386
- 19.3 Implementation Of Panic 386
- 19.4 Formatted Output 389
- 19.4.1 Printf And Fprintf 397
- 19.4.2 Kprintf 398
- 19.5 The Butler Process 399
- 19.5.1 The Ctrl-Break Event 401
- 19.5.2 System Snapshots 402
- 19.6 Summary 409
- For Further Study 409
- Exercises 410
Chapter 20 System Configuration
- 20.1 The Need For Multiple Configurations 411
- 20.2 Static vs. Dynamic Configuration 412
- 20.3 The Details Of Configuration In PC-Xinu 412
- 20.3.1 Input To Config 414
- 20.3.2 Computation Of Minor Device Numbers 416
- 20.4 Configuring A PC-Xinu System 417
- 20.4.1 Counting Devices 418
- 20.5 System Calls And Procedures 418
- 20.6 Summary 419
- For Further Study 419
- Exercises 419
Bibliography
Index