O perating s ystems t hree e asy p ieces

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