第1页 / 共647页
第2页 / 共647页
第3页 / 共647页
第4页 / 共647页
第5页 / 共647页
第6页 / 共647页
第7页 / 共647页
第8页 / 共647页
Operating Systems: Three Easy Pieces 完整版.pdf
Contents
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
iii
.
.
v
. vi
. vii
ix
.
.
x
1
3
5
.
7
.
.
8
. 11
. 13
. 14
. 18
. 19
21
23
25
. 26
. 27
. 28
. 29
. 31
. 33
. 34
. 35
.
.
.
.
.
.
.
To Everyone .
.
To Educators .
To Students .
.
.
Acknowledgments .
.
Final Words
References .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1 A Dialogue on the Book
2
Introduction to Operating Systems
Virtualizing the CPU .
.
2.1
Virtualizing Memory .
2.2
.
.
.
Concurrency .
2.3
.
.
2.4
Persistence .
.
.
.
2.5 Design Goals .
.
.
Some History .
2.6
.
.
.
Summary .
2.7
References .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
I Virtualization
3 A Dialogue on Virtualization
4 The Abstraction: The Process
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.1
4.2
4.3
4.4
.
4.5 Data Structures .
.
4.6
.
References .
Homework .
.
.
The Abstraction: A Process .
Process API .
.
.
Process Creation: A Little More Detail .
Process States .
.
.
.
.
.
Summary .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
xi
xii
5
.
.
.
.
.
.
Interlude: Process API
5.1
5.2
5.3
5.4 Why? Motivating The API .
.
5.5 Other Parts Of The API
.
.
.
5.6
.
References .
.
.
.
.
Homework (Code) .
The fork() System Call
.
The wait() System Call
.
Finally, The exec() System Call .
.
.
.
.
.
Summary .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6 Mechanism: Limited Direct Execution
6.1
6.2
6.3
6.4 Worried About Concurrency? .
.
.
6.5
.
References .
.
Homework (Measurement) .
.
Basic Technique: Limited Direct Execution .
.
Problem #1: Restricted Operations .
.
Problem #2: Switching Between Processes .
.
.
.
.
.
.
.
.
.
Summary .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7 Scheduling: Introduction
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7.1 Workload Assumptions .
.
Scheduling Metrics .
7.2
.
.
First In, First Out (FIFO) .
7.3
Shortest Job First (SJF) .
7.4
.
.
Shortest Time-to-Completion First (STCF) .
7.5
7.6 A New Metric: Response Time .
.
.
.
7.7
.
.
7.8
.
.
7.9 No More Oracle .
.
.
.
7.10 Summary .
References .
.
.
.
.
.
.
.
.
Homework .
Round Robin .
.
Incorporating I/O .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8 Scheduling:
.
.
.
.
.
.
.
.
.
The Multi-Level Feedback Queue
8.1 MLFQ: Basic Rules .
.
.
8.2 Attempt #1: How To Change Priority .
.
8.3 Attempt #2: The Priority Boost
.
.
8.4 Attempt #3: Better Accounting .
.
8.5
.
8.6 MLFQ: Summary .
.
.
References .
Homework .
.
.
.
.
Tuning MLFQ And Other Issues .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9 Scheduling: Proportional Share
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9.1
9.2
Basic Concept: Tickets Represent Your Share .
Ticket Mechanisms .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
CONTENTS
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37
. 37
. 39
. 40
. 41
. 44
. 44
. 45
. 46
49
. 49
. 50
. 54
. 58
. 59
. 61
. 62
63
. 63
. 64
. 64
. 66
. 67
. 68
. 69
. 71
. 72
. 72
. 73
. 74
75
. 76
. 77
. 80
. 81
. 82
. 83
. 85
. 86
87
. 87
. 89
OPERATING
SYSTEMS
[VERSION 0.90]
WWW.OSTEP.ORG
CONTENTS
xiii
.
.
.
.
.
.
.
.
.
Implementation .
.
.
9.3
9.4 An Example .
.
9.5 How To Assign Tickets? .
9.6 Why Not Deterministic? .
.
9.7
.
References .
Homework .
.
Summary .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
10 Multiprocessor Scheduling (Advanced)
10.1 Background: Multiprocessor Architecture .
.
.
10.2 Don’t Forget Synchronization .
.
.
.
10.3 One Final Issue: Cache Affinity .
.
.
.
10.4 Single-Queue Scheduling .
.
10.5 Multi-Queue Scheduling .
.
.
.
.
10.6 Linux Multiprocessor Schedulers .
.
.
10.7 Summary .
References .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11 Summary Dialogue on CPU Virtualization
12 A Dialogue on Memory Virtualization
.
.
.
13 The Abstraction: Address Spaces
.
13.1 Early Systems .
.
13.2 Multiprogramming and Time Sharing .
13.3 The Address Space .
.
.
.
13.4 Goals .
.
.
.
13.5 Summary .
References .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
14 Interlude: Memory API
.
14.1 Types of Memory .
.
14.2 The malloc() Call
.
.
14.3 The free() Call
14.4 Common Errors
.
.
14.5 Underlying OS Support
14.6 Other Calls .
.
.
.
14.7 Summary .
.
References .
.
.
Homework (Code) .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15 Mechanism: Address Translation
.
.
.
15.1 Assumptions .
15.2 An Example .
.
.
15.3 Dynamic (Hardware-based) Relocation .
.
15.4 Hardware Support: A Summary .
15.5 Operating System Issues .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 90
. 91
. 92
. 92
. 93
. 95
. 96
97
. 98
. 100
. 101
. 101
. 103
. 106
. 106
. 107
109
111
113
. 113
. 114
. 115
. 117
. 119
. 120
123
. 123
. 124
. 126
. 126
. 129
. 130
. 130
. 131
. 132
135
. 136
. 136
. 139
. 142
. 143
c⃝ 2014, ARPACI-DUSSEAU
THREE
EASY
PIECES
xiv
15.6 Summary .
.
References .
Homework .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
16 Segmentation
.
16.1 Segmentation: Generalized Base/Bounds .
.
.
16.2 Which Segment Are We Referring To? .
.
16.3 What About The Stack? .
.
.
16.4 Support for Sharing .
.
.
.
.
16.5 Fine-grained vs. Coarse-grained Segmentation .
.
16.6 OS Support
.
16.7 Summary .
.
.
References .
Homework .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17 Free-Space Management
.
.
.
17.1 Assumptions .
.
17.2 Low-level Mechanisms
.
17.3 Basic Strategies .
.
17.4 Other Approaches .
.
.
.
17.5 Summary .
.
.
.
References .
Homework .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18 Paging: Introduction
18.1 A Simple Example And Overview .
18.2 Where Are Page Tables Stored? .
.
.
18.3 What’s Actually In The Page Table?
.
18.4 Paging: Also Too Slow .
.
.
18.5 A Memory Trace .
18.6 Summary .
.
.
.
.
.
.
.
References .
Homework .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
19 Paging: Faster Translations (TLBs)
.
.
.
.
.
19.1 TLB Basic Algorithm .
.
19.2 Example: Accessing An Array .
19.3 Who Handles The TLB Miss? .
.
19.4 TLB Contents: What’s In There?
.
19.5 TLB Issue: Context Switches
.
Issue: Replacement Policy .
19.6
.
.
.
19.7 A Real TLB Entry .
.
19.8 Summary .
.
.
.
.
.
References .
.
.
.
Homework (Measurement) .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20 Paging: Smaller Tables
OPERATING
SYSTEMS
[VERSION 0.90]
WWW.OSTEP.ORG
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
CONTENTS
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 146
. 147
. 148
149
. 149
. 152
. 153
. 154
. 155
. 155
. 157
. 158
. 160
161
. 162
. 163
. 171
. 173
. 175
. 176
. 177
179
. 179
. 183
. 184
. 185
. 186
. 189
. 190
. 191
193
. 193
. 195
. 197
. 199
. 200
. 202
. 203
. 204
. 205
. 207
211
CONTENTS
xv
.
.
.
.
.
.
20.1 Simple Solution: Bigger Pages
.
20.2 Hybrid Approach: Paging and Segments .
.
20.3 Multi-level Page Tables
.
.
20.4
.
Inverted Page Tables .
.
20.5 Swapping the Page Tables to Disk .
.
.
20.6 Summary .
.
.
.
References .
Homework .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
21 Beyond Physical Memory: Mechanisms
.
.
.
.
.
.
.
21.1 Swap Space .
.
.
.
21.2 The Present Bit
.
21.3 The Page Fault
.
.
21.4 What If Memory Is Full? .
21.5 Page Fault Control Flow .
.
21.6 When Replacements Really Occur
.
21.7 Summary .
References .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
22 Beyond Physical Memory: Policies
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
22.1 Cache Management
.
22.2 The Optimal Replacement Policy .
22.3 A Simple Policy: FIFO .
.
22.4 Another Simple Policy: Random .
.
22.5 Using History: LRU .
22.6 Workload Examples .
.
22.7
22.8 Approximating LRU .
.
22.9 Considering Dirty Pages .
22.10 Other VM Policies .
.
.
.
22.11 Thrashing .
.
.
22.12 Summary .
.
.
.
References .
Homework .
.
.
.
.
.
.
.
.
.
Implementing Historical Algorithms .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
23 The VAX/VMS Virtual Memory System
23.1 Background .
.
23.2 Memory Management Hardware .
.
23.3 A Real Address Space .
.
23.4 Page Replacement
.
23.5 Other Neat VM Tricks .
.
.
.
23.6 Summary .
References .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
24 Summary Dialogue on Memory Virtualization
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 211
. 212
. 215
. 222
. 223
. 223
. 224
. 225
227
. 228
. 229
. 230
. 231
. 232
. 233
. 234
. 235
237
. 237
. 238
. 240
. 242
. 243
. 244
. 247
. 248
. 249
. 250
. 250
. 251
. 252
. 254
255
. 255
. 256
. 257
. 259
. 260
. 262
. 263
265
c⃝ 2014, ARPACI-DUSSEAU
THREE
EASY
PIECES
xvi
CONTENTS
II Concurrency
25 A Dialogue on Concurrency
26 Concurrency: An Introduction
.
.
.
.
.
.
.
26.1 An Example: Thread Creation .
.
26.2 Why It Gets Worse: Shared Data .
.
26.3 The Heart Of The Problem: Uncontrolled Scheduling .
.
26.4 The Wish For Atomicity .
.
.
26.5 One More Problem: Waiting For Another .
.
.
26.6 Summary: Why in OS Class? .
.
.
.
References .
Homework .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
27 Interlude: Thread API
.
.
27.1 Thread Creation .
.
.
27.2 Thread Completion .
.
27.3 Locks
.
.
27.4 Condition Variables
.
27.5 Compiling and Running .
.
27.6 Summary .
References .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
28 Locks
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
28.1 Locks: The Basic Idea .
.
.
.
.
28.2 Pthread Locks .
.
.
.
.
.
.
.
28.3 Building A Lock .
.
.
.
.
28.4 Evaluating Locks .
.
.
.
.
28.5 Controlling Interrupts .
.
.
.
.
28.6 Test And Set (Atomic Exchange)
.
.
.
28.7 Building A Working Spin Lock .
.
.
.
.
28.8 Evaluating Spin Locks .
.
.
28.9 Compare-And-Swap .
.
.
.
.
.
28.10 Load-Linked and Store-Conditional
.
.
28.11 Fetch-And-Add .
.
.
28.12 Too Much Spinning: What Now? .
.
.
28.13 A Simple Approach: Just Yield, Baby .
28.14 Using Queues: Sleeping Instead Of Spinning .
.
28.15 Different OS, Different Support .
.
.
28.16 Two-Phase Locks .
.
.
.
28.17 Summary .
.
.
.
.
References .
Homework .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
29 Lock-based Concurrent Data Structures
.
.
29.1 Concurrent Counters .
.
29.2 Concurrent Linked Lists .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
OPERATING
SYSTEMS
[VERSION 0.90]
WWW.OSTEP.ORG
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
269
271
273
. 274
. 277
. 279
. 281
. 283
. 283
. 285
. 286
289
. 289
. 290
. 293
. 295
. 297
. 297
. 299
301
. 301
. 302
. 303
. 303
. 304
. 306
. 307
. 309
. 309
. 311
. 312
. 313
. 314
. 315
. 317
. 318
. 319
. 320
. 322
325
. 325
. 330
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
CONTENTS
xvii
29.3 Concurrent Queues .
.
29.4 Concurrent Hash Table
29.5 Summary .
.
.
.
References .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
30 Condition Variables
30.1 Definition and Routines .
.
30.2 The Producer/Consumer (Bounded Buffer) Problem .
.
30.3 Covering Conditions .
.
.
30.4 Summary .
References .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31 Semaphores
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31.1 Semaphores: A Definition .
.
31.2 Binary Semaphores (Locks)
.
31.3 Semaphores As Condition Variables .
.
31.4 The Producer/Consumer (Bounded Buffer) Problem .
.
.
31.5 Reader-Writer Locks .
.
.
31.6 The Dining Philosophers
.
.
31.7 How To Implement Semaphores .
.
.
31.8 Summary .
References .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
32 Common Concurrency Problems
32.1 What Types Of Bugs Exist? .
.
32.2 Non-Deadlock Bugs .
.
.
32.3 Deadlock Bugs .
.
.
.
32.4 Summary .
References .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
33 Event-based Concurrency (Advanced)
33.1 The Basic Idea: An Event Loop .
.
33.2 An Important API: select() (or poll()) .
.
33.3 Using select() .
.
.
.
33.4 Why Simpler? No Locks Needed .
.
.
33.5 A Problem: Blocking System Calls .
.
33.6 A Solution: Asynchronous I/O .
.
.
33.7 Another Problem: State Management
33.8 What Is Still Difficult With Events
.
.
.
.
.
33.9 Summary .
References .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
34 Summary Dialogue on Concurrency
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 333
. 334
. 336
. 337
339
. 340
. 343
. 351
. 352
. 353
355
. 355
. 357
. 358
. 360
. 364
. 366
. 369
. 370
. 371
373
. 373
. 374
. 377
. 385
. 386
389
. 389
. 390
. 391
. 392
. 393
. 393
. 396
. 397
. 397
. 398
399
c⃝ 2014, ARPACI-DUSSEAU
THREE
EASY
PIECES
xviii
CONTENTS
III Persistence
35 A Dialogue on Persistence
36 I/O Devices
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
36.1 System Architecture .
.
.
36.2 A Canonical Device .
.
.
36.3 The Canonical Protocol
36.4 Lowering CPU Overhead With Interrupts .
.
36.5 More Efficient Data Movement With DMA .
.
36.6 Methods Of Device Interaction .
.
.
36.7 Fitting Into The OS: The Device Driver .
.
36.8 Case Study: A Simple IDE Disk Driver .
36.9 Historical Notes
.
.
.
.
.
36.10 Summary .
References .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37 Hard Disk Drives
.
.
.
.
.
.
.
.
.
.
.
.
.
37.1 The Interface .
.
.
37.2 Basic Geometry .
.
37.3 A Simple Disk Drive .
37.4
37.5 Disk Scheduling .
.
37.6 Summary .
.
.
References .
Homework .
.
.
.
.
.
I/O Time: Doing The Math .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Interface And RAID Internals .
.
.
.
.
38 Redundant Arrays of Inexpensive Disks (RAIDs)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
38.1
.
38.2 Fault Model .
.
.
38.3 How To Evaluate A RAID .
.
.
38.4 RAID Level 0: Striping .
.
38.5 RAID Level 1: Mirroring .
.
.
38.6 RAID Level 4: Saving Space With Parity .
.
38.7 RAID Level 5: Rotating Parity .
.
.
38.8 RAID Comparison: A Summary .
38.9 Other Interesting RAID Issues
.
.
.
.
.
38.10 Summary .
.
.
.
.
References .
Homework .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
39 Interlude: File and Directories
.
.
39.1 Files and Directories .
.
.
39.2 The File System Interface .
.
39.3 Creating Files .
.
39.4 Reading and Writing Files .
.
39.5 Reading And Writing, But Not Sequentially .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
OPERATING
SYSTEMS
[VERSION 0.90]
WWW.OSTEP.ORG
401
403
405
. 405
. 406
. 407
. 408
. 409
. 410
. 411
. 412
. 415
. 415
. 416
419
. 419
. 420
. 421
. 424
. 428
. 432
. 433
. 434
437
. 438
. 439
. 439
. 440
. 443
. 446
. 450
. 451
. 452
. 452
. 453
. 455
457
. 457
. 459
. 459
. 460
. 462
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
