Chapter 1 Introduction and Overview 1
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.5 An Operating System Viewed From The Inside 16
1.6 Summary 18
Chapter 2 An Overview of the Machine and Run-Time Environment 21
2.1 The Machine 21
2.2 Disk Storage Organization 31
2.3 The C Run-Time Environment 35
2.4 Summary 38
Chapter 3 List and Queue Manipulation 41
3.1 Linked Lists Of Processes 41
3.2 Implementation Of The Q Structure 43
3.3 Priority Queue Manipulation 47
3.4 List Initialization 49
3.5 Summary 51
Chapter 4 Scheduling and Context Switching 53
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
Chapter 5 More Process Management 65
5.1 Process Suspension And Resumption 65
5.2 System Calls 68
5.3 Process Termination 70
5.4 Kernel Declarations 72
5.5 Process Creation 73
5.6 Utility Procedures 76
5.7 Summary 78
Chapter 6 Process Coordination 81
6.1 Low-Level Coordination Techniques 82
6.2 Implementation Of High-Level Coordination Primitives 82
6.3 Semaphore Creation and Deletion 87
6.4 Summary 90
Chapter 7 Message Passing 93
7.1 Message Passing In Xinu 94
7.2 Implementation Of Send 95
7.3 Implementation Of Receive 96
7.4 Summary 98
Chapter 8 Memory Management 101
8.1 Memory Management On The 11/02 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.6 Summary 111
Chapter 9 Interrupt Processing 113
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
Chapter 10 Real-Time Clock Management 123
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.9 Clock Interrupt Processing 135
10.10 Clock Initialization 137
10.11 Summary 137
Chapter 11 Device Independent Input and Output 141
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
Chapter 12 An Example Device Driver 159
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.8 Tty Control Block Initialization 181
12.9 Device Driver Control 183
12.10 Summary 185
Chapter 13 System Initialization 189
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
Chapter 14 A Data Link Communication Driver 203
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.4 The Important Details Of Dlc 210
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.10 Dlc Driver Initialization 226
14.11 Control Over Non-Blockmode Reception 227
14.12 Summary 228
Chapter 15 High-Level Memory Management and Message Passing 231
15.1 Self-Initializing Modules 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
Chapter 16 Frame-Level Network Communication 257
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
Chapter 17 A Disk Driver 283
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
Chapter 18 File Systems 309
18.1What Is A File System？ 309
18.2Disk And File Servers 311
18.3A Local File System 311
18.4Data Structures For The File System 312
18.5Implementation Of The Index Manager 313
18.6Operations On I-Blocks 315
18.7The 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.11 Summary 345
Chapter 19 Exception Handling and Support Routines 347
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.5 Summary 364
Chapter 20 System Configuration 367
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.4 Configuring A Xinu System 373
20.5 System Calls And Procedures 374
20.6 Summary 375
Appendix 1 A Quick Introduction to C 377
Appendix 2 Xinu Programmer’s Manual 385
Bibliography 469
Index 477