1 INTRODUCTION 1
1.1 WHAT IS AN OPERATING SYSTEM? 4
1.1.1 The Operating System as an Extended Machine 4
1.1.2 The Operating System as a Resource Manager 5
1.2 HISTORY OF OPERATING SYSTEMS 6
1.2.1 The First Generation（1945-55）Vacuum Tubes and Plugboards 7
1.2.2 The Second Generation（1955-65）Transistors and Batch Systems 7
1.2.3 The Third Generation（1965-1980）ICs and Multiprogramming 9
1.2.4 The Fourth Generation（1980-Present）Personal Computers 13
1.2.5 History of MINIX 3 14
1.3 OPERATING SYSTEM CONCEPTS 17
1.3.1 Processes 18
1.3.2 Files 20
1.3.3 The Shell 23
1.4 SYSTEM CALLS 24
1.4.1 System Calls for Process Management 25
1.4.2 System Calls for Signaling 29
1.4.3 System Calls for File Management 31
1.4.4 System Calls for Directory Management 36
1.4.5 System Calls for Protection 38
1.4.6 System Calls for Time Management 40
1.5 OPERATING SYSTEM STRUCTURE 40
1.5.1 Monolithic Systems 40
1.5.2 Layered Systems 43
1.5.3 Virtual Machines 44
1.5.4 Exokernels 47
1.5.5 Client-Server Model 47
1.6 OUTLINE OF THE REST OF THIS BOOK 49
1.7 SUMMARY 49
2 PROCESSES 53
2.1 INTRODUCTION TO PROCESSES 53
2.1.1 The Process Model 54
2.1.2 Process Creation 55
2.1.3 Process Termination 57
2.1.4 Process Hierarchies 58
2.1.5 Process States 58
2.1.6 Implementation of Processes 60
2.1.7 Threads 62
2.2 INTERPROCESS COMMUNICATION 67
2.2.1 Race Conditions 67
2.2.2 Critical Sections 68
2.2.3 Mutual Exclusion with Busy Waiting 69
2.2.4 Sleep and Wakeup 74
2.2.5 Semaphores 76
2.2.6 Mutexes 79
2.2.7 Monitors 79
2.2.8 Message Passing 83
2.3 CLASSICAL IPC PROBLEMS 86
2.3.1 The Dining Philosophers Problem 87
2.3.2 The Readers and Writers Problem 90
2.4 SCHEDULING 91
2.4.1 Introduction to Scheduling 92
2.4.2 Scheduling in Batch Systems 97
2.4.3 Scheduling in Interactive Systems 100
2.4.4 Scheduling in Real-Time Systems 107
2.4.5 Policy versus Mechanism 108
2.4.6 Thread Scheduling 108
2.5 OVERVIEW OF PROCESSES IN MINIX 3 110
2.5.1 The Internal Structure of MINIX 3 110
2.5.2 Process Management in MINIX 3 114
2.5.3 Interprocess Communication in MINIX 3 118
2.5.4 Process Scheduling in MINIX 3 120
2.6 IMPLEMENTATION OF PROCESSES IN MINIX 3 123
2.6.1 Organization of the MINIX 3 Source Code 123
2.6.2 Compiling and Runniing MINIX 3 126
2.6.3 The Common Header Files 128
2.6.4 The MINIX 3 Header Files 136
2.6.5 Process Data Structures and Header Files 144
2.6.6 Bootstrapping MINIX 3 154
2.6.7 System Initialization 158
2.6.8 Interrupt Handling in MINIX 3 165
2.6.9 Interprocess Communication in MINIX 3 176
2.6.10 Scheduling in MINIX 3 180
2.6.11 Hardware-Dependent Kernel Support 183
2.6.12 Utilities and the Kernel Library 188
2.7 THE SYSTEM TASK IN MINIX 3 190
2.7.1 Overview of the System Task 192
2.7.2 Implementation of the System Task 195
2.7.3 Implementation of the System Libarary 198
2.9 THE CLOCK TASK IN MINIX 3 202
2.8.1 Clock Hardware 202
2.8.2 Clock Software 204
2.8.3 Overview of the Clock Driver in MINIX 3 206
2.8.4 Implementation of the Clock Driver in MINIX 3 210
2.9 SUMMARY 212
3 INPUT/OUTPUT 219
3.1 PRINCIPLES OF I/O HARDWARE 220
3.1.1 I/O Devices 221
3.1.2 Device Controllers 221
3.1.3 Memory-Mapped I/O 223
3.1.4 Interrupts 224
3.1.5 Direct Memory Access 225
3.2 PRINCIPLES OF I/O SOFTWARE 227
3.2.1 Goals of the I/O Software 227
3.2.2 Interrupt Handlers 229
3.2.3 Device Drivers 229
3.2.4 Device-Independent I/O Software 231
3.2.5 User-Space I/O Software 234
3.3 DEADLOCKS 235
3.3.1 Resources 236
3.3.2 Principles of Deadlock 237
3.3.3 The Ostrich Algorithm 240
3.3.4 Detection and Recovery 242
3.3.5 Deadlock Prevention 243
3.3.6 Deadlock Avoidance 245
3.4 OVERVIEW OF I/O IN MINIX 3 250
3.4.1 Interrupt Handlers in MINIX 3 250
3.4.2 Device Drivers in MINIX 3 254
3.4.3 Device-Independent I/O Software in MINIX 3 257
3.4.4 User-level I/O Software in MINIX 3 258
3.4.5 Deadlock Handling in MINIX 3 258
3.5 BLOCK DEVICES IN MINIX 3 259
3.5.1 Overview of Block Device Drivers in MINIX 3 260
3.5.2 Common Block Device Driver Software 263
3.5.3 The Driver Library 267
3.6 RAM DISKS 269
3.6.1 RAM Disk Hardware and Software 269
3.6.2 Overview of the RAM Disk Driver in MINIX 3 271
3.6.3 Implementation of the RAM Disk Driver in MINIX 3 272
3.7 DISKS 276
3.7.1 Disk Hardware 276
3.7.2 RAID 278
3.7.3 Disk Software 279
3.7.4 Overview of the Hard Disk Driver in MINIX 3 285
3.7.5 Implementation of the Hard Disk Driver in MINIX 3 288
3.7.6 Floppy Disk Handling 298
3.8 TERMINALS 300
3.8.1 Terminal Hardware 301
3.8.2 Terminal Software 305
3.8.3 Overview of the Terminal Driver in MINIX 3 314
3.8.4 Implementation of the Device-Independent Terminal Driver 329
3.8.5 Implementation of the Keyboard Driver 348
3.8.6 Implementation of the Display Driver 355
3.9 SUMMARY 364
4 MEMORY MANAGEMENT 371
4.1 BASIC MEMORY MANAGEMENT 372
4.1.1 Monoprogramming without Swapping or Paging 372
4.1.2 Multiprogramming with Fixed Partitions 373
4.1.3 Relocation and Protection 375
4.2 SWAPPING 376
4.2.1 Memory Management with Bitmaps 378
4.2.2 Memory Management with Linked Lists 379
4.3 VIRTUAL MEMORY 381
4.3.1 Paging 382
4.3.2 Page Tables 386
4.3.3 TLBs—Translation Lookaside Buffers 390
4.3.4 Inverted Page Tables 393
4.4 PAGE REPLACEMENT ALGORITHMS 394
4.4.1 The Optimal Page Replacement Algorithm 395
4.4.2 The Not Recently Used Page Replacement Algorithm 396
4.4.3 The First-In,First-Out（FIFO）Page Replacement Algorithm 397
4.4.4 The Second Chance Page Replacement Algorithm 397
4.4.5 The Clock Page Replacement Algorithm 398
4.4.6 The Least Recently Used（LRU）Page Replacement Algorithm 399
4.4.7 Simulating LRU in Software 399
4.5 DESIGN ISSUES FOR PAGING SYSTEMS 402
4.5.1 The Working Set Model 402
4.5.2 Local versus Global Allocation Policies 404
4.5.3 Page Size 406
4.5.4 Virtual Memory Interface 408
4.6 SEGMENTATION 408
4.6.1 Implementation of Pure Segmentation 412
4.6.2 Segmentation with Paging：The Intel Pentium 413
4.7 OVERVIEW OF THE MINIX 3 PROCESS MANAGER 418
4.7.1 Memory Layout 420
4.7.2 Message Handling 423
4.7.3 Process Manager Data Structures and Algorithms 424
4.7.4 The FORK,EXIT,and WAIT System Calls 430
4.7.5 The EXEC System Call 431
4.7.6 The BRK System Call 435
4.7.7 Signal Handling 436
4.7.8 Other System Calls 444
4.8 IMPLEMENTATION OF THE MINIX 3 PROCESS MANAGER 445
4.8.1 The Header Files and Data Structures 445
4.8.2 The Main Program 448
4.8.3 Implementation of FORK,EXIT,and WAIT 453
4.8.4 Implementation of EXEC 456
4.8.5 Implementation of BRK 459
4.8.6 Implementation of Signal Handling 460
4.8.7 Implementation of Other System Calls 469
4.8.8 Memory Management Utilities 471
4.9 SUMMARY 473
5 FILE SYSTEMS 479
5.1 FILES 480
5.1.1 File Naming 480
5.1.2 File Structure 482
5.1.3 File Types 483
5.1.4 File Access 486
5.1.5 File Attributes 486
5.1.6 File Operations 488
5.2 DIRECTORIES 489
5.2.1 Simple Directories 489
5.2.2 Hierarchical Directory Systems 490
5.2.3 Path Names 491
5.2.4 Directory Operations 494
5.3 FILE SYSTEM IMPLEMENTATION 495
5.3.1 File System Layout 495
5.3.2 Implementing Files 497
5.3.3 Implementing Directories 500
5.3.4 Disk Space Management 507
5.3.5 File System Reliability 510
5.3.6 File System Performance 521
5.3.7 Log-Structured File Systems 522
5.4 SECURITY 524
5.4.1 The Security Environment 524
5.4.2 Generic Security Attacks 529
5.4.3 Design Principles for Security 530
5.4.4 User Authentication 531
5.5 PROTECTION MECHANISMS 535
5.5.1 Protection Domains 535
5.5.2 Access Control Lists 537
5.5 3 Capabilities 540
5.5.4 Covert Channels 543
5.6 OVERVIEW OF THE MINIX 3 FILE SYSTEM 546
5.6.1 Messages 547
5.6.2 File System Layout 547
5.6.3 Bitmaps 551
5.6.4 I-Nodes 553
5.6.5 The Block Cache 555
5.6.6 Directories and Paths 557
5.6.7 File Descriptors 559
5.6.8 File Locking 561
5.6.9 Pipes and Special Files 561
5.6.10 An Example：The READ System Call 563
5.7 IMPLEMENTATION OF THE MINIX 3 FILE SYSTEM 564
5.7.1 Header Files and Global Data Structures 564
5.7.2 Table Management 568
5.7.3 The Main Program 577
5.7.4 Operations on Individual Files 581
5.7.5 Directories and Paths 589
5.7.6 Other System Calls 594
5.7.7 The I/O Device Interface 595
5.7.8 Additional System Call Support 601
5.7.9 File System Utilities 603
5.7.10 Other MINIX 3 Components 604
SUMMARY 604
6 BIBLIOGRAPHY 609