operating system design the xinu approachPDF电子书下载

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