1 INTRODUCTION 1

I.I WHAT IS AN OPERATJNG SYSTEM? 4

1. 1. I The Operating System as all Exte17dcd Machine 4

1, 1 2 The Operating System as a Rcsollrce Manager 5

1.2 HISTORY OF OPERATING SYSTEMS 6

l .2.1 The First Generation (1945 55) Vacuum Tubes and Plugboards 7

l.2.2 The Second Generation (1955to5) Transistors and Batch Systems 7

123 The Third Generation (1965 1980) ICS and MuItIVrogramming 9

1.24 The Forth Generation (1980--Present) Personal Computers 13

I .2.5 History of MINce 3 14

I .3 OPERATING SYSTEM CONCENS 17

1 .3.1 Processes 18

1 .3.2 FileS 20

I.3.3 The Shell 23

] .4 SYSTEM CALLS 24

14.1 System Calls for PIDccss Management 25

I 42 System Ca]IS,or S]gnaIing 29

] .43 System Ca]]s [or File Management 31

1 .44 System Ca]]s tar Directory Management 36

l.4.5 System Calls for Protection 38

1,46 System Calls F()r Tirnc Management 40

'v CONTENTS

1 5 OPER-ATING SYSTEM STRUCTURE 40

1 .5. I Monolithic Syslems 40

1,5,2 Layered Systems 43

1,5,3 Virtual Machines 44

1 .5.4 Exokernels 47

I .5.5 C]ient Server MOdel 47

16 OUTLINE OF TIN REST OF THIS BOOK 49

I.7 SUMMARY 49

2 PROCESSES 53

2.1 INTRODUCTION TO PROCESSES 53

2. 1. I The Process Model 54

2.1.2 Pr'>ccss Creation 55

2,l.3 Process Termination 57

2.l.4 Process IJierarchies 58

2.l.5 Process States 58

2. 1 .6 lmplementahon or Pr(wesses 60

2.1 .7 Threads 62

22 INTERPROCESS COMMUNICATION

2.2] Race COndihons 67

2.22 CrItical Sechons 68

223 Mutual Exclusion with Busy Waitillg 69

2.2.4 Sleep and Wateup 74

2.2.5 Semaphores 76

2.2.6 Mutexes 79

2.2.7 MnIIItI)rs 79

2.2.8 Message Passing 83

2.3 CLASSICAL IPC PROBLEMS 86

2.3. 1 The Dining roiIOSOpIIers ProbICm 87

2.3.2 The Readers and Writers PI.oblelll 90

24 SCHEDULING 91

2.4.] IIIiroductIOn to SCneduIing 92

2.4.2 Schedu]]ng in batch Systems 97

243 Scheduling in inleractive Systems 100

244 Schedlllillg in Real Time Systems 107

245 POlICy virtue MechaIIism 108

246 Thread SChedII]Ing 108

CONTENTS V

2.5 OVERVIEW OF PROCESSES IN MINIX 3 110

2.5.1 The Internal Structure of MINIX 3 1 10

25.2 Process Management in MINIs 3 114

2.5.3 Interprocess C()mmunlcation in MINIX 3 1 18

2.5.4 DOCeds SCheduling in MIDIs 3 120

2.6 IMPLEMENTAnON OF PROCESSES IN MINIX 3 123

26. I orgamzation of [he MINIX 3 S',urcc COde 123

2.6.2 COmpiling and Annuling MINix 3 126

2.6.3 The Common Header Files 128

2.6.4 The MINIX 3 Header r.IIes 136

2.6.5 Process Data Srtuctures and Header FJles 144

26.6 BOOtstrapping MIN]X 3 154

26.7 System initiaIIZation 158

2.68 InterrIIpt HanoIing in MINce 3 ]65

2.6.9 Interprocess Colnmunlcatlon in aleX 3 176

2.6.10 SCheduling in MINIX 3 180

2.6.1 1 Hardware Dependent Kernel Sllpport 183

26.] 2 Utilities and lhc Kernel Libl+ary 188

27 THE SYSTEM TASK IN MINIX 3 190

2.7.1 Overview of' the System Task 192

2.7.2 Implementation ot' the Syslern Task 195

2.7.3 hoplemelltaiion of the System Libarary 198

2.9 THE CLOCK TASK IN MINIX 3 202

2.8.1 Clock Hardware 202

28.2 ClOCk SOftware ZOo

2.8.3 Overview of the Clock Driver in MINix 3 206

2.8.4 Implementat)on of the ClOck Diver in MINIX 3 210

2.9 SUMMARY 212

3 INPUTIOUTPUT 219

3.1 PRINC]PLES OF CO HARDWARE 220

3 1. 1 I/o Devices 221

31 .2 Device COntrollers 221

31 3 MeInory-Mapped I/o 223

3.] .4 Interrupts 224

3.1.5 Direct Memory Access 225

3.2 PRINCIPLES OF I/O SOFTWARE 227

3.2. ] Coals of the UO Software 227

3.22 Interrupt IJandlers 229

3.2.3 Device Dnvers 220

3.2.4 Device-independent l/O Sot'lware 231

3.2.> User Space ilO Software 234

3.3 DEADLOCKS 235

3.3.1 Resources 236

3.3.2 Principles of DCadIOCk 237

3.3.3 The Ostrich Algorlthln 240

3.3.4 Detection and Rccovery 242

3.3.5 DCadIOCk WevenIIOn 243

3.36 DeadlOCk AVOIdance 245

34 OVERVIEW OF I/O IN MINIX 3 250

3.4. 1 Interrupt HandIers in MINIX 3 250

3.4.2 DCVice 13rivers in M]N]X 3 254

3.4.3 Device-Independent CO SOftware in MINIX 3 257

3.4.4 USCr ]eveI W SOftware in MINX 3 258

345 DeauIOCk HandlIng in MINIX 3 258

3.5 BLOCK DEVICES IN MINIX 3 259

35.1 OVerview of BlOCk Device Dnt/crs in MINix 3 260

35.2 Common Block Device Driver Soltwure 263

3.5.3 The Dnaal Librmp 267

36 ~ DISKS 269

3.6.] RAM Disk Hardwtire and Sol'twarc 269

3.62 OVCrview of me AM Disk Driver in MINIX 3 271

3.6.3 I]nplemental]on of the RAM D]sk Dnver in MIN]X 3 272

3.7 DISKS 276

3.7.1 D]sk HaTdware 276

3.7.2 RAID 278

3.7.3 DISk SO,tware 279

3.7.4 Overylew of the Ha]+d Disk Dnver in MINce 3 285

3.75 Inlplemcntation ot' the Had Disk DTiver in MINIX 3 288

3.76 FIOnpy DISk Handling 298

38 TErmINALS 30U

38.1 Terminal HaTdwarc 301

3.8.2 Temlina] Software 305

3.8.3 Overview of the Terminal Dnver 111 MINIX 3 314

3.8.4 Implementation of the Device-independent Terminal aliver 329

CON~TS Vii

3.8.5 Iruplemeotation of the Keyboard Driver 348

3.8.6 imPlementation of the D]splny Dnver 355

3.9 SUMMARY 364

4 MEMORY MANAGEMENT 371

4.] BASIC MEMORY MANAGEMENT 372

4.l.l Monoprogramming without Swapping or Paging 372

4.l.2 Multiprograrnming with Fixed Parutions 373

4.l.3 Relocation and Pr(,tectlon 375

4.2 SWAPPING 376

4.2.1 Memory Management with Blimaps 378

4.2.2 Memory Management with Linked Lists 379

4.3 VIRTUAL MEMORY 381

4.3.1 PagIng 382

4.3.2 Page TabbIed 386

43.3 TLBS--Translation LOOkaside Bull.ers 390

4.3.4 Inverted Page Tables 393

4.4 PAGE REPLACEMENT ALGORITHMS 394

44. I The Optinml Page Replacement Algorithms 395

4.4.2 The Nc)t Recently Used Page Replacement Algorithm 396

4.4.3 The First-in. FITSt-Ollt (FIFO) Page Rcplaccmcnt Algorithm 397

4.4.4 The Second Chance Pace Replacement Algorithm 397

4.4.5 The Clock Page Rcplaccmcnt A]gorithm 398

446 The Least Recently Used (LRU) Page Replacement Algorithm 399

447 Simulating LRU in Software 399

4.5 DESIGN ISSUES FOR PAGINC SYSTEMS 402

45 1 The WOrking Set MOdel 402

4.5.2 Local vereus Global Allocation POlicies 404

4.53 Pangs Size 406

4.5.4 Virtual Memory IntcrfMc 408

4.6 SEGMENTAnON 405

4.6.] Implementation of pore Segmentation 412

4.6.2 Segmentation with Paging f The intel Pentium 413

47 OVERVIEW OIl rHE MINIX 3 PROCESS MANAGER 418

47.1 Memory Layout 420

4.7.2 Message Handling 423

4.7.3 Process Manager Data Smictules and AlgoTithms 424

4.7.4 The roax. ~. and WAIT SystenI CallS 430

4.7.5 The EXEC System Call 431

4.7.6 The BRK SysteIn Call 435

4,77 Signal Handling 436

4.7.8 Other System Calls 444

4.8 IMPLEMEN'fATION OF THE MINIX 3 PROCESS MANAGER 445

4.81 The Header F]]es and Data Smictures 445

4.8.2 The Main program 448

48.3 Implementation of FORK, EXIT. and WArs 453

48.4 implementation of EXEC 456

48.5 lmplemenL3tion of BRK 459

4.8.6 Implementation of Signal Handling 460

48,7 Implementutjon of Other System Calls 469

4.8.8 Memory Management Utilities 471

4.9 SU~ARY 473

5 FILE SYSTEMS 479

5.] m.ES 480

5.]. I File Naming 480

51.2 File Structure 482

51 .3 File Types 483

5.1 .4 File ACCess 486

5. I.5 FIIC AttrIbutes 486

5. I,6 File OpeTaiions 488

5.2 DIreCTORIES 489

5.2.] Simple Directones 489

5,22 Hierarchical Direct(lry Systems 490

5.2.3 Path Names 491

5.2.4 Directory Operahons 494

5.3 FILE SYSTEM IMPLEMENTATION 495

5.31 File System La)zoui 495

5.32 Implementing Files 497

5.3.3 Implementing Directories 500

534 Disk Space MtInageInent 507

CO~NTS iX

535 File System ReIiabiIitv 510

536 File System Perf(lrmance 52]

537 Log Structured File Systems 522

5.4 SECURITY 524

5.4.1 The Secuniy Envirollment 524

5.4.2 Genenc Security Attacks 529

5.4.3 Design Pnnciplcs for Sccunty 530

5.4.4 User Authentication 531

5.5 PROTECTION MECHANISMS 535

5.5.1 Protechon Domains 535

5.52 Access Colltr<,I l.ists 537

5.5.3 CanabiIities 540

5.5,4 Covert Channels 543

5.6 OVERVIEW OF TIlE 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 1 NOdes 553

5.6.5 The BlOCk Cache 555

5.6.6 Directories and Pains 557

56.7 File Dcscnptors 559

5.6.8 File LOCking 561

569 Pipes and Special Files 561

5.6.10 An Example f The axAN 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 DITcctoncs and Paths 589

5.7,6 Other System Calls 594

5.7.7 The I/o Device interface 595

>.7.8 Additional System Call SuPPort 6(}l

5.7.9 File System Utilities 603

>.7. 10 Ottier MINJX 3 COmponents 60'

SUMMARY 604

6 BIBLIOGRAPHY 609