电子书
ContentsTo Everyone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTo Educators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTo Students . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . viiFinal Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixReferences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x1 A Dialogue on the Book 12 Introduction to Operating Systems 32.1 Virtualizing the CPU . . . . . . . . . . . . . . . . . . . . . . 52.2 Virtualizing Memory . . . . . . . . . . . . . . . . . . . . . . 72.3 Concurrency . . . . . . . . . . . . . . . . . . . . . . . . . . 82.4 Persistence . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.5 Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . . 132.6 Some History . . . . . . . . . . . . . . . . . . . . . . . . . . 142.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19I Virtualization 213 A Dialogue on Virtualization 234 The Abstraction: The Process 254.1 The Abstraction: A Process . . . . . . . . . . . . . . . . . . 264.2 Process API . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.3 Process Creation: A Little More Detail . . . . . . . . . . . . 284.4 Process States . . . . . . . . . . . . . . . . . . . . . . . . . . 294.5 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . 314.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35xixii CONTENTS5 Interlude: Process API 375.1 The fork() System Call . . . . . . . . . . . . . . . . . . . 375.2 The wait() System Call . . . . . . . . . . . . . . . . . . . 395.3 Finally, The exec() System Call . . . . . . . . . . . . . . . 405.4 Why? Motivating The API . . . . . . . . . . . . . . . . . . . 415.5 Other Parts Of The API . . . . . . . . . . . . . . . . . . . . 445.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Homework (Code) . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 Mechanism: Limited Direct Execution 496.1 Basic Technique: Limited Direct Execution . . . . . . . . . 496.2 Problem #1: Restricted Operations . . . . . . . . . . . . . . 506.3 Problem #2: Switching Between Processes . . . . . . . . . . 546.4 Worried About Concurrency? . . . . . . . . . . . . . . . . . 586.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61Homework (Measurement) . . . . . . . . . . . . . . . . . . . . . . 627 Scheduling: Introduction 637.1 Workload Assumptions . . . . . . . . . . . . . . . . . . . . 637.2 Scheduling Metrics . . . . . . . . . . . . . . . . . . . . . . . 647.3 First In, First Out (FIFO) . . . . . . . . . . . . . . . . . . . . 647.4 Shortest Job First (SJF) . . . . . . . . . . . . . . . . . . . . . 667.5 Shortest Time-to-Completion First (STCF) . . . . . . . . . . 677.6 A New Metric: Response Time . . . . . . . . . . . . . . . . 687.7 Round Robin . . . . . . . . . . . . . . . . . . . . . . . . . . 697.8 Incorporating I/O . . . . . . . . . . . . . . . . . . . . . . . 717.9 No More Oracle . . . . . . . . . . . . . . . . . . . . . . . . . 727.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748 Scheduling:The Multi-Level Feedback Queue 758.1 MLFQ: Basic Rules . . . . . . . . . . . . . . . . . . . . . . . 768.2 Attempt #1: How To Change Priority . . . . . . . . . . . . 778.3 Attempt #2: The Priority Boost . . . . . . . . . . . . . . . . 808.4 Attempt #3: Better Accounting . . . . . . . . . . . . . . . . 818.5 Tuning MLFQ And Other Issues . . . . . . . . . . . . . . . 828.6 MLFQ: Summary . . . . . . . . . . . . . . . . . . . . . . . . 83References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 869 Scheduling: Proportional Share 879.1 Basic Concept: Tickets Represent Your Share . . . . . . . . 879.2 Ticket Mechanisms . . . . . . . . . . . . . . . . . . . . . . . 89OPERATINGSYSTEMS[VERSION 0.90] WWW.OSTEP.ORGCONTENTS xiii9.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 909.4 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 919.5 How To Assign Tickets? . . . . . . . . . . . . . . . . . . . . 929.6 Why Not Deterministic? . . . . . . . . . . . . . . . . . . . . 929.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9610 Multiprocessor Scheduling (Advanced) 9710.1 Background: Multiprocessor Architecture . . . . . . . . . . 9810.2 Don’t Forget Synchronization . . . . . . . . . . . . . . . . . 10010.3 One Final Issue: Cache Affinity . . . . . . . . . . . . . . . . 10110.4 Single-Queue Scheduling . . . . . . . . . . . . . . . . . . . 10110.5 Multi-Queue Scheduling . . . . . . . . . . . . . . . . . . . . 10310.6 Linux Multiprocessor Schedulers . . . . . . . . . . . . . . . 10610.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10711 Summary Dialogue on CPU Virtualization 10912 A Dialogue on Memory Virtualization 11113 The Abstraction: Address Spaces 11313.1 Early Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 11313.2 Multiprogramming and Time Sharing . . . . . . . . . . . . 11413.3 The Address Space . . . . . . . . . . . . . . . . . . . . . . . 11513.4 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11713.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12014 Interlude: Memory API 12314.1 Types of Memory . . . . . . . . . . . . . . . . . . . . . . . . 12314.2 The malloc() Call . . . . . . . . . . . . . . . . . . . . . . 12414.3 The free() Call . . . . . . . . . . . . . . . . . . . . . . . . 12614.4 Common Errors . . . . . . . . . . . . . . . . . . . . . . . . 12614.5 Underlying OS Support . . . . . . . . . . . . . . . . . . . . 12914.6 Other Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . 13014.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131Homework (Code) . . . . . . . . . . . . . . . . . . . . . . . . . . . 13215 Mechanism: Address Translation 13515.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . 13615.2 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 13615.3 Dynamic (Hardware-based) Relocation . . . . . . . . . . . 13915.4 Hardware Support: A Summary . . . . . . . . . . . . . . . 14215.5 Operating System Issues . . . . . . . . . . . . . . . . . . . . 143⃝c 2014, ARPACI-DUSSEAUTHREEEASYPIECESxiv CONTENTS15.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14816 Segmentation 14916.1 Segmentation: Generalized Base/Bounds . . . . . . . . . . 14916.2 Which Segment Are We Referring To? . . . . . . . . . . . . 15216.3 What About The Stack? . . . . . . . . . . . . . . . . . . . . 15316.4 Support for Sharing . . . . . . . . . . . . . . . . . . . . . . 15416.5 Fine-grained vs. Coarse-grained Segmentation . . . . . . . 15516.6 OS Support . . . . . . . . . . . . . . . . . . . . . . . . . . . 15516.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16017 Free-Space Management 16117.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . 16217.2 Low-level Mechanisms . . . . . . . . . . . . . . . . . . . . 16317.3 Basic Strategies . . . . . . . . . . . . . . . . . . . . . . . . . 17117.4 Other Approaches . . . . . . . . . . . . . . . . . . . . . . . 17317.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17718 Paging: Introduction 17918.1 A Simple Example And Overview . . . . . . . . . . . . . . 17918.2 Where Are Page Tables Stored? . . . . . . . . . . . . . . . . 18318.3 What’s Actually In The Page Table? . . . . . . . . . . . . . 18418.4 Paging: Also Too Slow . . . . . . . . . . . . . . . . . . . . . 18518.5 A Memory Trace . . . . . . . . . . . . . . . . . . . . . . . . 18618.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19119 Paging: Faster Translations (TLBs) 19319.1 TLB Basic Algorithm . . . . . . . . . . . . . . . . . . . . . . 19319.2 Example: Accessing An Array . . . . . . . . . . . . . . . . 19519.3 Who Handles The TLB Miss? . . . . . . . . . . . . . . . . . 19719.4 TLB Contents: What’s In There? . . . . . . . . . . . . . . . 19919.5 TLB Issue: Context Switches . . . . . . . . . . . . . . . . . 20019.6 Issue: Replacement Policy . . . . . . . . . . . . . . . . . . . 20219.7 A Real TLB Entry . . . . . . . . . . . . . . . . . . . . . . . . 20319.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205Homework (Measurement) . . . . . . . . . . . . . . . . . . . . . . 20720 Paging: Smaller Tables 211OPERATINGSYSTEMS[VERSION 0.90] WWW.OSTEP.ORGCONTENTS xv20.1 Simple Solution: Bigger Pages . . . . . . . . . . . . . . . . 21120.2 Hybrid Approach: Paging and Segments . . . . . . . . . . 21220.3 Multi-level Page Tables . . . . . . . . . . . . . . . . . . . . 21520.4 Inverted Page Tables . . . . . . . . . . . . . . . . . . . . . . 22220.5 Swapping the Page Tables to Disk . . . . . . . . . . . . . . 22320.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22521 Beyond Physical Memory: Mechanisms 22721.1 Swap Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 22821.2 The Present Bit . . . . . . . . . . . . . . . . . . . . . . . . . 22921.3 The Page Fault . . . . . . . . . . . . . . . . . . . . . . . . . 23021.4 What If Memory Is Full? . . . . . . . . . . . . . . . . . . . . 23121.5 Page Fault Control Flow . . . . . . . . . . . . . . . . . . . . 23221.6 When Replacements Really Occur . . . . . . . . . . . . . . 23321.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23522 Beyond Physical Memory: Policies 23722.1 Cache Management . . . . . . . . . . . . . . . . . . . . . . 23722.2 The Optimal Replacement Policy . . . . . . . . . . . . . . . 23822.3 A Simple Policy: FIFO . . . . . . . . . . . . . . . . . . . . . 24022.4 Another Simple Policy: Random . . . . . . . . . . . . . . . 24222.5 Using History: LRU . . . . . . . . . . . . . . . . . . . . . . 24322.6 Workload Examples . . . . . . . . . . . . . . . . . . . . . . 24422.7 Implementing Historical Algorithms . . . . . . . . . . . . . 24722.8 Approximating LRU . . . . . . . . . . . . . . . . . . . . . . 24822.9 Considering Dirty Pages . . . . . . . . . . . . . . . . . . . . 24922.10 Other VM Policies . . . . . . . . . . . . . . . . . . . . . . . 25022.11 Thrashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25022.12 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25423 The VAX/VMS Virtual Memory System 25523.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . 25523.2 Memory Management Hardware . . . . . . . . . . . . . . . 25623.3 A Real Address Space . . . . . . . . . . . . . . . . . . . . . 25723.4 Page Replacement . . . . . . . . . . . . . . . . . . . . . . . 25923.5 Other Neat VM Tricks . . . . . . . . . . . . . . . . . . . . . 26023.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26324 Summary Dialogue on Memory Virtualization 265⃝c 2014, ARPACI-DUSSEAUTHREEEASYPIECESxvi CONTENTSII Concurrency 26925 A Dialogue on Concurrency 27126 Concurrency: An Introduction 27326.1 An Example: Thread Creation . . . . . . . . . . . . . . . . 27426.2 Why It Gets Worse: Shared Data . . . . . . . . . . . . . . . 27726.3 The Heart Of The Problem: Uncontrolled Scheduling . . . 27926.4 The Wish For Atomicity . . . . . . . . . . . . . . . . . . . . 28126.5 One More Problem: Waiting For Another . . . . . . . . . . 28326.6 Summary: Why in OS Class? . . . . . . . . . . . . . . . . . 283References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28627 Interlude: Thread API 28927.1 Thread Creation . . . . . . . . . . . . . . . . . . . . . . . . 28927.2 Thread Completion . . . . . . . . . . . . . . . . . . . . . . . 29027.3 Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29327.4 Condition Variables . . . . . . . . . . . . . . . . . . . . . . 29527.5 Compiling and Running . . . . . . . . . . . . . . . . . . . . 29727.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29928 Locks 30128.1 Locks: The Basic Idea . . . . . . . . . . . . . . . . . . . . . 30128.2 Pthread Locks . . . . . . . . . . . . . . . . . . . . . . . . . . 30228.3 Building A Lock . . . . . . . . . . . . . . . . . . . . . . . . 30328.4 Evaluating Locks . . . . . . . . . . . . . . . . . . . . . . . . 30328.5 Controlling Interrupts . . . . . . . . . . . . . . . . . . . . . 30428.6 Test And Set (Atomic Exchange) . . . . . . . . . . . . . . . 30628.7 Building A Working Spin Lock . . . . . . . . . . . . . . . . 30728.8 Evaluating Spin Locks . . . . . . . . . . . . . . . . . . . . . 30928.9 Compare-And-Swap . . . . . . . . . . . . . . . . . . . . . . 30928.10 Load-Linked and Store-Conditional . . . . . . . . . . . . . 31128.11 Fetch-And-Add . . . . . . . . . . . . . . . . . . . . . . . . . 31228.12 Too Much Spinning: What Now? . . . . . . . . . . . . . . . 31328.13 A Simple Approach: Just Yield, Baby . . . . . . . . . . . . . 31428.14 Using Queues: Sleeping Instead Of Spinning . . . . . . . . 31528.15 Different OS, Different Support . . . . . . . . . . . . . . . . 31728.16 Two-Phase Locks . . . . . . . . . . . . . . . . . . . . . . . . 31828.17 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32229 Lock-based Concurrent Data Structures 32529.1 Concurrent Counters . . . . . . . . . . . . . . . . . . . . . . 32529.2 Concurrent Linked Lists . . . . . . . . . . . . . . . . . . . . 330OPERATINGSYSTEMS[VERSION 0.90] WWW.OSTEP.ORGCONTENTS xvii29.3 Concurrent Queues . . . . . . . . . . . . . . . . . . . . . . . 33329.4 Concurrent Hash Table . . . . . . . . . . . . . . . . . . . . 33429.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33730 Condition Variables 33930.1 Definition and Routines . . . . . . . . . . . . . . . . . . . . 34030.2 The Producer/Consumer (Bounded Buffer) Problem . . . . 34330.3 Covering Conditions . . . . . . . . . . . . . . . . . . . . . . 35130.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35331 Semaphores 35531.1 Semaphores: A Definition . . . . . . . . . . . . . . . . . . . 35531.2 Binary Semaphores (Locks) . . . . . . . . . . . . . . . . . . 35731.3 Semaphores As Condition Variables . . . . . . . . . . . . . 35831.4 The Producer/Consumer (Bounded Buffer) Problem . . . . 36031.5 Reader-Writer Locks . . . . . . . . . . . . . . . . . . . . . . 36431.6 The Dining Philosophers . . . . . . . . . . . . . . . . . . . 36631.7 How To Implement Semaphores . . . . . . . . . . . . . . . 36931.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37132 Common Concurrency Problems 37332.1 What Types Of Bugs Exist? . . . . . . . . . . . . . . . . . . 37332.2 Non-Deadlock Bugs . . . . . . . . . . . . . . . . . . . . . . 37432.3 Deadlock Bugs . . . . . . . . . . . . . . . . . . . . . . . . . 37732.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38633 Event-based Concurrency (Advanced) 38933.1 The Basic Idea: An Event Loop . . . . . . . . . . . . . . . . 38933.2 An Important API: select() (or poll()) . . . . . . . . . 39033.3 Using select() . . . . . . . . . . . . . . . . . . . . . . . . 39133.4 Why Simpler? No Locks Needed . . . . . . . . . . . . . . . 39233.5 A Problem: Blocking System Calls . . . . . . . . . . . . . . 39333.6 A Solution: Asynchronous I/O . . . . . . . . . . . . . . . . 39333.7 Another Problem: State Management . . . . . . . . . . . . 39633.8 What Is Still Difficult With Events . . . . . . . . . . . . . . 39733.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39834 Summary Dialogue on Concurrency 399⃝c 2014, ARPACI-DUSSEAUTHREEEASYPIECESxviii CONTENTSIII Persistence 40135 A Dialogue on Persistence 40336 I/O Devices 40536.1 System Architecture . . . . . . . . . . . . . . . . . . . . . . 40536.2 A Canonical Device . . . . . . . . . . . . . . . . . . . . . . 40636.3 The Canonical Protocol . . . . . . . . . . . . . . . . . . . . 40736.4 Lowering CPU Overhead With Interrupts . . . . . . . . . . 40836.5 More Efficient Data Movement With DMA . . . . . . . . . 40936.6 Methods Of Device Interaction . . . . . . . . . . . . . . . . 41036.7 Fitting Into The OS: The Device Driver . . . . . . . . . . . . 41136.8 Case Study: A Simple IDE Disk Driver . . . . . . . . . . . . 41236.9 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . 41536.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41637 Hard Disk Drives 41937.1 The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 41937.2 Basic Geometry . . . . . . . . . . . . . . . . . . . . . . . . . 42037.3 A Simple Disk Drive . . . . . . . . . . . . . . . . . . . . . . 42137.4 I/O Time: Doing The Math . . . . . . . . . . . . . . . . . . 42437.5 Disk Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 42837.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43438 Redundant Arrays of Inexpensive Disks (RAIDs) 43738.1 Interface And RAID Internals . . . . . . . . . . . . . . . . . 43838.2 Fault Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 43938.3 How To Evaluate A RAID . . . . . . . . . . . . . . . . . . . 43938.4 RAID Level 0: Striping . . . . . . . . . . . . . . . . . . . . . 44038.5 RAID Level 1: Mirroring . . . . . . . . . . . . . . . . . . . . 44338.6 RAID Level 4: Saving Space With Parity . . . . . . . . . . . 44638.7 RAID Level 5: Rotating Parity . . . . . . . . . . . . . . . . 45038.8 RAID Comparison: A Summary . . . . . . . . . . . . . . . 45138.9 Other Interesting RAID Issues . . . . . . . . . . . . . . . . 45238.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45539 Interlude: File and Directories 45739.1 Files and Directories . . . . . . . . . . . . . . . . . . . . . . 45739.2 The File System Interface . . . . . . . . . . . . . . . . . . . 45939.3 Creating Files . . . . . . . . . . . . . . . . . . . . . . . . . . 45939.4 Reading and Writing Files . . . . . . . . . . . . . . . . . . . 46039.5 Reading And Writing, But Not Sequentially . . . . . . . . . 462OPERATINGSYSTEMS[VERSION 0.90] WWW.OSTEP.ORGCONTENTS xix39.6 Writing Immediately with fsync() . . . . . . . . . . . . . 46339.7 Renaming Files . . . . . . . . . . . . . . . . . . . . . . . . . 46439.8 Getting Information About Files . . . . . . . . . . . . . . . 46539.9 Removing Files . . . . . . . . . . . . . . . . . . . . . . . . . 46639.10 Making Directories . . . . . . . . . . . . . . . . . . . . . . . 46639.11 Reading Directories . . . . . . . . . . . . . . . . . . . . . . 46739.12 Deleting Directories . . . . . . . . . . . . . . . . . . . . . . 46839.13 Hard Links . . . . . . . . . . . . . . . . . . . . . . . . . . . 46839.14 Symbolic Links . . . . . . . . . . . . . . . . . . . . . . . . . 47039.15 Making and Mounting a File System . . . . . . . . . . . . . 47239.16 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47540 File System Implementation 47740.1 The Way To Think . . . . . . . . . . . . . . . . . . . . . . . 47740.2 Overall Organization . . . . . . . . . . . . . . . . . . . . . . 47840.3 File Organization: The Inode . . . . . . . . . . . . . . . . . 48040.4 Directory Organization . . . . . . . . . . . . . . . . . . . . 48540.5 Free Space Management . . . . . . . . . . . . . . . . . . . . 48540.6 Access Paths: Reading and Writing . . . . . . . . . . . . . . 48640.7 Caching and Buffering . . . . . . . . . . . . . . . . . . . . . 49040.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49441 Locality and The Fast File System 49541.1 The Problem: Poor Performance . . . . . . . . . . . . . . . 49541.2 FFS: Disk Awareness Is The Solution . . . . . . . . . . . . . 49741.3 Organizing Structure: The Cylinder Group . . . . . . . . . 49741.4 Policies: How To Allocate Files and Directories . . . . . . . 49841.5 Measuring File Locality . . . . . . . . . . . . . . . . . . . . 49941.6 The Large-File Exception . . . . . . . . . . . . . . . . . . . 50041.7 A Few Other Things About FFS . . . . . . . . . . . . . . . . 50241.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50542 Crash Consistency: FSCK and Journaling 50742.1 A Detailed Example . . . . . . . . . . . . . . . . . . . . . . 50842.2 Solution #1: The File System Checker . . . . . . . . . . . . 51142.3 Solution #2: Journaling (or Write-Ahead Logging) . . . . . 51342.4 Solution #3: Other Approaches . . . . . . . . . . . . . . . . 52342.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52543 Log-structured File Systems 52743.1 Writing To Disk Sequentially . . . . . . . . . . . . . . . . . 528⃝c 2014, ARPACI-DUSSEAUTHREEEASYPIECESxx CONTENTS43.2 Writing Sequentially And Effectively . . . . . . . . . . . . . 52943.3 How Much To Buffer? . . . . . . . . . . . . . . . . . . . . . 53043.4 Problem: Finding Inodes . . . . . . . . . . . . . . . . . . . 53143.5 Solution Through Indirection: The Inode Map . . . . . . . 53143.6 The Checkpoint Region . . . . . . . . . . . . . . . . . . . . 53243.7 Reading A File From Disk: A Recap . . . . . . . . . . . . . 53343.8 What About Directories? . . . . . . . . . . . . . . . . . . . 53343.9 A New Problem: Garbage Collection . . . . . . . . . . . . . 53443.10 Determining Block Liveness . . . . . . . . . . . . . . . . . . 53643.11 A Policy Question: Which Blocks To Clean, And When? . . 53743.12 Crash Recovery And The Log . . . . . . . . . . . . . . . . . 53743.13 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54044 Data Integrity and Protection 54344.1 Disk Failure Modes . . . . . . . . . . . . . . . . . . . . . . . 54344.2 Handling Latent Sector Errors . . . . . . . . . . . . . . . . 54544.3 Detecting Corruption: The Checksum . . . . . . . . . . . . 54644.4 Using Checksums . . . . . . . . . . . . . . . . . . . . . . . 54944.5 A New Problem: Misdirected Writes . . . . . . . . . . . . . 55044.6 One Last Problem: Lost Writes . . . . . . . . . . . . . . . . 55144.7 Scrubbing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55144.8 Overheads Of Checksumming . . . . . . . . . . . . . . . . 55244.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55345 Summary Dialogue on Persistence 55546 A Dialogue on Distribution 55747 Distributed Systems 55947.1 Communication Basics . . . . . . . . . . . . . . . . . . . . . 56047.2 Unreliable Communication Layers . . . . . . . . . . . . . . 56147.3 Reliable Communication Layers . . . . . . . . . . . . . . . 56347.4 Communication Abstractions . . . . . . . . . . . . . . . . . 56547.5 Remote Procedure Call (RPC) . . . . . . . . . . . . . . . . . 56747.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57348 Sun’s Network File System (NFS) 57548.1 A Basic Distributed File System . . . . . . . . . . . . . . . . 57648.2 On To NFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57748.3 Focus: Simple and Fast Server Crash Recovery . . . . . . . 57748.4 Key To Fast Crash Recovery: Statelessness . . . . . . . . . 57848.5 The NFSv2 Protocol . . . . . . . . . . . . . . . . . . . . . . 57948.6 From Protocol to Distributed File System . . . . . . . . . . 58148.7 Handling Server Failure with Idempotent Operations . . . 583OPERATINGSYSTEMS[VERSION 0.90] WWW.OSTEP.ORGCONTENTS xxi48.8 Improving Performance: Client-side Caching . . . . . . . . 58548.9 The Cache Consistency Problem . . . . . . . . . . . . . . . 58548.10 Assessing NFS Cache Consistency . . . . . . . . . . . . . . 58748.11 Implications on Server-Side Write Buffering . . . . . . . . . 58748.12 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59049 The Andrew File System (AFS) 59149.1 AFS Version 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 59149.2 Problems with Version 1 . . . . . . . . . . . . . . . . . . . . 59249.3 Improving the Protocol . . . . . . . . . . . . . . . . . . . . 59449.4 AFS Version 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 59449.5 Cache Consistency . . . . . . . . . . . . . . . . . . . . . . . 59649.6 Crash Recovery . . . . . . . . . . . . . . . . . . . . . . . . . 59849.7 Scale And Performance Of AFSv2 . . . . . . . . . . . . . . 59849.8 AFS: Other Improvements . . . . . . . . . . . . . . . . . . . 60049.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603Homework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60450 Summary Dialogue on Distribution 605General Index 607Asides 617Tips 619Cruces 621
评论