Along Came An Interactive Job
. . . . . . . . . . . . . . . . . . 74
8.4
A Mixed I/O-intensive and CPU-intensive Workload
. . . . . 75
8.5
Without (Left) and With (Right) Priority Boost
. . . . . . . . . 76
xxiii
xxiv
L
IST OF
F
IGURES
8.6
Without (Left) and With (Right) Gaming Tolerance
. . . . . . 77
8.7
Lower Priority, Longer Quanta
. . . . . . . . . . . . . . . . . . 78
9.1
Lottery Scheduling Decision Code
. . . . . . . . . . . . . . . . 86
9.2
Lottery Fairness Study
. . . . . . . . . . . . . . . . . . . . . . . 87
10.1 Single CPU With Cache
. . . . . . . . . . . . . . . . . . . . . . 94
10.2 Two CPUs With Caches Sharing Memory
. . . . . . . . . . . . 95
10.3 Simple List Delete Code
. . . . . . . . . . . . . . . . . . . . . . 97
13.1 Operating Systems: The Early Days
. . . . . . . . . . . . . . . 109
13.2 Three Processes: Sharing Memory
. . . . . . . . . . . . . . . . 110
13.3 An Example Address Space
. . . . . . . . . . . . . . . . . . . . 111
15.1 A Process And Its Address Space
. . . . . . . . . . . . . . . . . 132
15.2 Physical Memory with a Single Relocated Process
. . . . . . . 133
16.1 An Address Space (Again)
. . . . . . . . . . . . . . . . . . . . . 142
16.2 Placing Segments In Physical Memory
. . . . . . . . . . . . . 143
16.3 Non-compacted and Compacted Memory
. . . . . . . . . . . . 148
17.1 An Allocated Region Plus Header
. . . . . . . . . . . . . . . . 157
17.2 Specific Contents Of The Header
. . . . . . . . . . . . . . . . . 157
17.3 A Heap With One Free Chunk
. . . . . . . . . . . . . . . . . . 159
17.4 A Heap: After One Allocation
. . . . . . . . . . . . . . . . . . . 159
17.5 Free Space With Three Chunks Allocated
. . . . . . . . . . . . 160
17.6 Free Space With Two Chunks Allocated
. . . . . . . . . . . . . 161
17.7 A Non-Coalesced Free List
. . . . . . . . . . . . . . . . . . . . . 162
18.1 A Simple 64-byte Address Space
. . . . . . . . . . . . . . . . . 169
18.2 64-Byte Address Space Placed In Physical Memory
. . . . . . 170
18.3 The Address Translation Process
. . . . . . . . . . . . . . . . . 172
18.4 Example: Page Table in Kernel Physical Memory
. . . . . . . 173
18.5 An x86 Page Table Entry (PTE)
. . . . . . . . . . . . . . . . . . 174
18.6 Accessing Memory With Paging
. . . . . . . . . . . . . . . . . 175
18.7 A Virtual (And Physical) Memory Trace
. . . . . . . . . . . . . 178
19.1 TLB Control Flow Algorithm
. . . . . . . . . . . . . . . . . . . 184
19.2 Example: An Array In A Tiny Address Space
. . . . . . . . . . 185
19.3 TLB Control Flow Algorithm (OS Handled)
. . . . . . . . . . 188
19.4 A MIPS TLB Entry
. . . . . . . . . . . . . . . . . . . . . . . . . 193
19.5 Discovering TLB Sizes and Miss Costs
. . . . . . . . . . . . . 198
20.1 A 16-KB Address Space With 1-KB Pages
. . . . . . . . . . . . 203
20.2 Linear (Left) And Multi-Level (Right) Page Tables
. . . . . . . 206
20.3 A 16-KB Address Space With 64-byte Pages
. . . . . . . . . . . 207
20.4 Multi-level Page Table Control Flow
. . . . . . . . . . . . . . . 212
O
PERATING
S
YSTEMS
[V
ERSION
0.80]
WWW
.
OSTEP
.
ORG
L
IST OF
F
IGURES
xxv
21.1 Physical Memory and Swap Space
. . . . . . . . . . . . . . . . 219
21.2 Page-Fault Control Flow Algorithm (Hardware)
. . . . . . . . 222
21.3 Page-Fault Control Flow Algorithm (Software)
. . . . . . . . . 223
22.1 Random Performance over 10,000 Trials
. . . . . . . . . . . . . 232
22.2 The No-Locality Workload
. . . . . . . . . . . . . . . . . . . . . 235
22.3 The 80-20 Workload
. . . . . . . . . . . . . . . . . . . . . . . . . 236
22.4 The Looping Workload
. . . . . . . . . . . . . . . . . . . . . . . 237
22.5 The 80-20 Workload With Clock
. . . . . . . . . . . . . . . . . 239
23.1 The VAX/VMS Address Space
. . . . . . . . . . . . . . . . . . 247
26.1 A Single-Threaded Address Space
. . . . . . . . . . . . . . . . 264
26.2 Simple Thread Creation Code (t0.c)
. . . . . . . . . . . . . . . 265
26.3 Sharing Data: Oh Oh (t2)
. . . . . . . . . . . . . . . . . . . . . 267
27.1 Creating a Thread
. . . . . . . . . . . . . . . . . . . . . . . . . . 281
27.2 Waiting for Thread Completion
. . . . . . . . . . . . . . . . . . 282
27.3 Simpler Argument Passing to a Thread
. . . . . . . . . . . . . 283
27.4 An Example Wrapper
. . . . . . . . . . . . . . . . . . . . . . . . 285
28.1 First Attempt: A Simple Flag
. . . . . . . . . . . . . . . . . . . 296
28.2 A Simple Spin Lock Using Test-and-set
. . . . . . . . . . . . . 298
28.3 Compare-and-swap
. . . . . . . . . . . . . . . . . . . . . . . . . 299
28.4 Load-linked And Store-conditional
. . . . . . . . . . . . . . . 301
28.5 Using LL/SC To Build A Lock
. . . . . . . . . . . . . . . . . . . 301
28.6 Ticket Locks
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
28.7 Lock With Test-and-set And Yield
. . . . . . . . . . . . . . . . 304
28.8 Lock With Queues, Test-and-set, Yield, And Wakeup
. . . . . 306
28.9 Linux-based Futex Locks
. . . . . . . . . . . . . . . . . . . . . . 308
29.1 A Counter Without Locks
. . . . . . . . . . . . . . . . . . . . . 312
29.2 A Counter With Locks
. . . . . . . . . . . . . . . . . . . . . . . 312
29.3 Performance of Traditional vs. Sloppy Counters
. . . . . . . . 313
29.4 Sloppy Counter Implementation
. . . . . . . . . . . . . . . . . 315
29.5 Scaling Sloppy Counters
. . . . . . . . . . . . . . . . . . . . . . 316
29.6 Concurrent Linked List
. . . . . . . . . . . . . . . . . . . . . . 317
29.7 Concurrent Linked List: Rewritten
. . . . . . . . . . . . . . . . 318
29.8 Michael and Scott Concurrent Queue
. . . . . . . . . . . . . . 320
29.9 A Concurrent Hash Table
. . . . . . . . . . . . . . . . . . . . . 321
29.10 Scaling Hash Tables
. . . . . . . . . . . . . . . . . . . . . . . . 321
30.1 A Parent Waiting For Its Child
. . . . . . . . . . . . . . . . . . 325
30.2 Parent Waiting For Child: Spin-based Approach
. . . . . . . . 326
30.3 Parent Waiting For Child: Use A Condition Variable
. . . . . 327
30.4 The Put and Get Routines (Version 1)
. . . . . . . . . . . . . . 330
30.5 Producer/Consumer Threads (Version 1)
. . . . . . . . . . . . 330
c
2014, A
RPACI
-D
USSEAU
T
HREE
E
ASY
P
IECES
xxvi
L
IST OF
F
IGURES
30.6 Producer/Consumer: Single CV and If Statement
. . . . . . . 331
30.7 Producer/Consumer: Single CV and While
. . . . . . . . . . . 333
30.8 Producer/Consumer: Two CVs and While
. . . . . . . . . . . . 335
30.9 The Final Put and Get Routines
. . . . . . . . . . . . . . . . . . 336
30.10 The Final Working Solution
. . . . . . . . . . . . . . . . . . . . 336
30.11 Covering Conditions: An Example
. . . . . . . . . . . . . . . . 338
31.1 Initializing A Semaphore
. . . . . . . . . . . . . . . . . . . . . 342
31.2 Semaphore: Definitions of Wait and Post
. . . . . . . . . . . . 342
31.3 A Binary Semaphore, a.k.a. a Lock
. . . . . . . . . . . . . . . . 343
31.4 A Parent Waiting For Its Child
. . . . . . . . . . . . . . . . . . 345
31.5 The Put and Get Routines
. . . . . . . . . . . . . . . . . . . . . 347
31.6 Adding the Full and Empty Conditions
. . . . . . . . . . . . . 347
31.7 Adding Mutual Exclusion (Incorrectly)
. . . . . . . . . . . . . 349
31.8 Adding Mutual Exclusion (Correctly)
. . . . . . . . . . . . . . 350
31.9 A Simple Reader-Writer Lock
. . . . . . . . . . . . . . . . . . . 351
31.10 The Dining Philosophers
. . . . . . . . . . . . . . . . . . . . . 353
31.11 The getforks() and putforks() Routines
. . . . . . . . . 354
31.12 Implementing Zemaphores with Locks and CVs
. . . . . . . . 355
32.1 The Deadlock Dependency Graph
. . . . . . . . . . . . . . . . 364
33.1 Simple Code using select()
. . . . . . . . . . . . . . . . . . 376
36.1 Prototypical System Architecture
. . . . . . . . . . . . . . . . . 390
36.2 A Canonical Device
. . . . . . . . . . . . . . . . . . . . . . . . . 391
36.3 The File System Stack
. . . . . . . . . . . . . . . . . . . . . . . 396
36.4 The IDE Interface
. . . . . . . . . . . . . . . . . . . . . . . . . . 397
36.5 The xv6 IDE Disk Driver (Simplified)
. . . . . . . . . . . . . . 398
37.1 A Disk With Just A Single Track
. . . . . . . . . . . . . . . . . 404
37.2 A Single Track Plus A Head
. . . . . . . . . . . . . . . . . . . . 405
37.3 Three Tracks Plus A Head (Right: With Seek)
. . . . . . . . . 406
37.4 Three Tracks: Track Skew Of 2
. . . . . . . . . . . . . . . . . . 407
37.5 SSTF: Scheduling Requests 21 And 2
. . . . . . . . . . . . . . 412
37.6 SSTF: Sometimes Not Good Enough
. . . . . . . . . . . . . . . 414
39.1 An Example Directory Tree
. . . . . . . . . . . . . . . . . . . . 442
41.1 FFS Locality For SEER Traces
. . . . . . . . . . . . . . . . . . . 483
41.2 Amortization: How Big Do Chunks Have To Be?
. . . . . . . . 486
41.3 FFS: Standard Versus Parameterized Placement
. . . . . . . . 487
47.1 Example UDP/IP Client/Server Code
. . . . . . . . . . . . . . . 545
47.2 A Simple UDP Library
. . . . . . . . . . . . . . . . . . . . . . . 546
47.3 Message Plus Acknowledgment
. . . . . . . . . . . . . . . . . 547
47.4 Message Plus Acknowledgment: Dropped Request
. . . . . . 548
O
PERATING
S
YSTEMS
[V
ERSION
0.80]
WWW
.
OSTEP
.
ORG
L
IST OF
F
IGURES
xxvii
47.5 Message Plus Acknowledgment: Dropped Reply
. . . . . . . 549
48.1 A Generic Client/Server System
. . . . . . . . . . . . . . . . . 559
48.2 Distributed File System Architecture
. . . . . . . . . . . . . . 560
48.3 Client Code: Reading From A File
. . . . . . . . . . . . . . . . 562
48.4 The NFS Protocol: Examples
. . . . . . . . . . . . . . . . . . . 564
48.5 The Three Types of Loss
. . . . . . . . . . . . . . . . . . . . . . 568
48.6 The Cache Consistency Problem
. . . . . . . . . . . . . . . . . 570
49.1 AFSv1 Protocol Highlights
. . . . . . . . . . . . . . . . . . . . 576
c
2014, A
RPACI
-D
USSEAU
T
HREE
E
ASY
P
IECES
List of Tables
6.1
Do'stlaringiz bilan baham: |