Table of Contents: Operating System Design Volume 1


Foreword

Preface

Contents

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 Xinu Small Machine Environment 4
1.4.2 Xinu Services 5
1.4.3 Concurrent Processing 6
1.4.4 The Distinction Between Programs And Processes 7
1.4.5 Process Exit 11
1.4.6 Shared Memory 12
1.4.7 Synchronization 13
1.4.8 Mutual Exclusion 15
1.5 An Operating System Viewed From The Inside 16
1.6 Summary 18
For Further Study 18
Exercises 19

Chapter 2 An Overview of the Machine and Run-Time Environment

2.1 The Machine 21
2.1.1 Physical Organization Of The 11/2 22
2.1.2 Logical Organization Of The 11/2 23
2.1.3 Registers In The LSI 11/2 23
2.1.4 The Address Space 24
2.1.5 Processor Status Word 25
2.1.6 Vectored Interrupts 26
2.1.7 Exceptional Conditions 27
2.1.8 Asynchronous Communication 27
2.1.9 LSI 11 Asynchronous Serial Line Hardware 28
2.1.10 Addressing A Serial Line Unit 28
2.1.11 Polled vs. Interrupt-Driven I/O 30
2.2 Disk Storage Organization 31
2.2.1 Disk Interface And Control Hardware 33
2.2.2 The Pieces Of Disk Hardware 33
2.2.3 Interface And Controller Request Formats 34
2.3 The C Run-Time Environment 35
2.4 Summary 38
For Further Study 39
Exercises 39

Chapter 3 List and Queue Manipulation

3.1 Linked Lists Of Processes 41
3.2 Implementation Of The Q Structure 43
3.2.1 In-Line Q Functions 45
3.2.2 FIFO Queue Manipulation 45
3.3 Priority Queue Manipulation 47
3.4 List Initialization 49
3.5 Summary 51
For Further Study 51
Exercises 51

Chapter 4 Scheduling and Context Switching

4.1 The Process Table 54
4.2 Process States 56
4.3 Selecting A Ready Process 56
4.4 The Null Process 61
4.5 Making A Process Ready 61
4.6 Summary 63
For Further Study 63
Exercises 63

Chapter 5 More Process Management

5.1 Process Suspension And Resumption 65
5.1.1 Implementation Of Resume 66
5.1.2 The Return Values SYSERR And OK 67
5.2 System Calls 68
5.2.1 Implementation of Suspend 68
5.2.2 Suspending The Current Process 69
5.3 Process Termination 70
5.4 Kernel Declarations 72
5.5 Process Creation 73
5.6 Utility Procedures 76
5.7 Summary 78
For Further Study 79
Exercises 79

Chapter 6 Process Coordination

6.1 Low-Level Coordination Techniques 82
6.2 Implementation Of High-Level Coordination Primitives 82
6.2.1 Semaphore Data Structures 83
6.3 Semaphore Creation and Deletion 87
6.4 Summary 90
For Further Study 90
Exercises 90

Chapter 7 Message Passing

7.1 Message Passing In Xinu 94
7.2 Implementation Of Send 95
7.3 Implementation Of Receive 96
7.4 Summary 98
For Further Study 98
Exercises 99

Chapter 8 Memory Management

8.1 Memory Management On The 11/2 102
8.2 Dynamic Memory Requirements In Xinu 102
8.3 Low-Level Memory Management Procedures 103
8.4 The Location Of Allocated Storage 104
8.5 The Implementation Of Xinu Memory Management 104
8.5.1 Allocating Heap Storage 105
8.5.2 Allocating Stack Storage 107
8.5.3 Releasing Storage 109
8.6 Summary 111
For Further Study 111
Exercises 112

Chapter 9 Interrupt Processing

9.1 Dispatching Interrupts 113
9.2 Input And Output Interrupt Dispatchers 114
9.3 The Rules For Interrupt Processing 118
9.4 Rescheduling While Processing An Interrupt 119
9.5 Summary 120
For Further Study 120
Exercises 121

Chapter 10 Real-Time Clock Management

10.1 The Real-Time Clock Mechanism 123
10.2 Optimization Of Clock Interrupt Processing 124
10.3 The Use Of A Real-Time Clock 125
10.4 Delta List Processing 126
10.5 Putting A Process To Sleep 127
10.6 Delays Measured In Seconds 131
10.7 Awakening Sleeping Processes 132
10.8 Deferred Clock Processing 133
10.8.1 Procedures For Changing To And From Deferred Mode 133
10.9 Clock Interrupt Processing 135
10.10 Clock Initialization 137
10.11 Summary 137
For Further Study 138
Exercises 138

Chapter 11 Device Independent Input and Output

11.1 Properties Of The Input And Output Interface 142
11.2 Abstract Operations 142
11.3 Binding Abstract Operations To Real Devices 143
11.4 Binding I/O Calls To Device Drivers At Run-Time 144
11.5 The Implementation Of High-Level I/O Operations 147
11.6 Opening And Closing Devices 151
11.7 Null And Error Entries In Devtab 152
11.8 Initialization Of The I/O System 153
11.9 Interrupt Vector Initialization 156
11.10 Summary 157
For Further Study 158
Exercises 158

Chapter 12 An Example Device Driver

12.1 The Device Type Tty 159
12.2 Upper And Lower Halves Of The Device Driver 160
12.3 Synchronization Of The Upper And Lower Halves 162
12.4 Control Block And Buffer Declarations 162
12.5 Upper-Half Tty Input Routines 165
12.6 Upper-Half Tty Output Routines 169
12.7 Lower-Half Tty Driver Routines 173
12.7.1 Watermarks And Delayed Signals 175
12.7.2 Lower-Half Input Processing 176
12.7.3 Cooked Mode And Cbreak Mode Processing 180
12.8 Tty Control Block Initialization 181
12.9 Device Driver Control 183
12.10 Summary 185
For Further Study 186
Exercises 186

Chapter 13 System Initialization

13.1 Starting From Scratch 190
13.2 Booting Xinu 191
13.3 System Startup 192
13.4 Finding The Size Of Memory 192
13.5 Initializing System Data Structures 194
13.6 Transforming The Program Into A Process 198
13.7 The Map Of Low Core 199
13.8 Summary 201
For Further Study 201
Exercises 201

Chapter 14 A Data Link Communication Driver

14.1 The Difficult Problem Of Communication 204
14.2 Nomenclature For The Network Software Layers 204
14.3 A Dlc Driver Design 205
14.3.1 Transmission Paradigm 206
14.3.2 High-Level I/O Operations With Dlc Devices 207
14.3.3 Acknowledgement Traffic 207
14.3.4 Optimizing With Deferred Processing 208
14.3.5 Efficient Error Correction 209
14.4 The Important Details Of Dlc 210
14.4.1 Escaped Characters 212
14.5 Dlc Finite State Output Machine 212
14.6 Deferred Input And Stalled Output 213
14.7 Implementation Of The Dlc Driver 215
14.8 Upper-Half Dlc Driver Routines 216
14.9 Lower-Half Dlc Driver Routines 220
14.9.1 The Lower-Half Of The Output Driver 220
14.9.2 The Lower-Half Of The Input Driver 223
14.10 Dlc Driver Initialization 226
14.11 Control Over Non-Blockmode Reception 227
14.12 Summary 228
For Further Study 229
Exercises 229

Chapter 15 High-Level Memory Management and Message Passing

15.1 Self-Initializing Modules 232
15.1.1 Specifying Initialization 232
15.1.2 Automatic Initialization 232
15.2 Memory Marking 233
15.3 Implementation Of Memory Marking 233
15.4 Partitioned Space Allocation 235
15.5 Buffer Pools 236
15.6 Returning Buffers To The Buffer Pool 239
15.7 Creating A Buffer Pool 240
15.8 Initializing The Buffer Pool Table 241
15.9 Communication Ports 242
15.10 The Implementation Of Ports 243
15.11 Other Operations On Ports 251
15.12 Summary 255
For Further Study 255
Exercises 255

Chapter 16 Frame-Level Network Communication

16.1 Operation Of The Frame Manager 258
16.2 Details Of The Frame-Level Protocol 258
16.3 The Xinu Ring Network 259
16.4 Messages, Packets, Frames, Blocks, And The Network Layers 260
16.5 An Example Of Packet Transfer Across An Internet 261
16.6 Frame-Level Processing 264
16.7 The Frame Format 265
16.8 The Interface Between The Frame And Internet Layers 267
16.9 The Frame-Level Input Process 269
16.10 The Frame-Level Output Process 272
16.11 Using The Acknowledgement Timer 275
16.12 Implementation Of The Timer 276
16.13 Initialization Of The Frame Layer 277
16.14 Optimizing The Transfer Of Datagrams To Frames 279
16.15 Summary 279
For Further Study 280
Exercises 280

Chapter 17 A Disk Driver

17.1 Operations Supplied By The Disk Driver 283
17.2 Controller Request And Interface Register Descriptions 284
17.3 The List Of Pending Disk Requests 286
17.4 Enqueuing Disk Requests 288
17.5 Optimizing the Request Queue 291
17.6 Starting A Disk Operation 293
17.7 Driver Initialization 295
17.8 The Upper-Half Read Routine 297
17.9 The Upper-Half Output Routine 298
17.10 Implementation Of The Upper-Half Output Routine 299
17.11 The Upper-Half Seek Routine 300
17.12 The Lower-Half Of The Disk Driver 301
17.13 Flushing Pending Requests 303
17.14 Summary 306
For Further Study 306
Exercises 306

Chapter 18 File Systems

18.1 What Is A File System? 309
18.2 Disk And File Servers 311
18.3 A Local File System 311
18.4 Data Structures For The File System 312
18.5 Implementation Of The Index Manager 313
18.6 Operations On I-Blocks 315
18.6.1 Clearing An I-Block 315
18.6.2 Reading An I-Block 315
18.6.3 Writing An I-Block 316
18.6.4 Allocating I-Blocks From The Free List 318
18.6.5 Returning I-Blocks To The Free List 319
18.7 The Directory Structure 321
18.8 Using The Device Switch Table For Files 322
18.9 Establishing A Pseudo-Device 325
18.10 Pseudo-Device Driver Routines 331
18.10.1 Index Management Routines 333
18.10.2 The Pseudo-Device Seek Routine 336
18.10.3 The Pseudo-Device Getc Routine 337
18.10.4 The Pseudo-Device Putc Routine 339
18.10.5 The Pseudo-Device Read Routine 341
18.10.6 The Pseudo-Device Write Routine 342
18.10.7 The Pseudo-Device Close Routine 342
18.10.8 The Pseudo-Device Initialization Routine 344
18.11 Summary 345
For Further Study 345
Exercises 345

Chapter 19 Exception Handling and Support Routines

19.1 Exceptions, Traps, And Illegal Interrupts. 347
19.2 Initialization Of Interrupt Vectors 348
19.3 Implementation Of Panic 348
19.4 Formatted Output 353
19.4.1 Printf And Fprintf 361
19.4.2 Kprintf 362
19.5 Summary 364
For Further Study 365
Exercises 365

Chapter 20 System Configuration

20.1 The Need For Multiple Configurations 367
20.2 Static vs. Dynamic Configuration 368
20.3 The Details Of Configuration In Xinu 368
20.3.1 Input To Config 371
20.3.2 Computation Of Minor Device Numbers 372
20.4 Configuring A Xinu System 373
20.4.1 Counting Devices 374
20.5 System Calls And Procedures 374
20.6 Summary 375
For Further Study 375
Exercises 376

Bibliography

Index



Return to list of Comer's OS books



Return to Comer's homepage