O perating s ystems t hree e asy p ieces

partitioned,

561

pass,

88

Patterson’s Law,

577

PC,

16

,

26

PCB,

32

PCI,

389

PDE,

206

perfect scaling,

313

performance,

13

,

60

,

293

,

299

,

423

,

544

peripheral bus,

389

persist,

387

,

491

persistence,

iii

,

1

,

11

,

12

,

29

,

387

persistent storage,

441

persistently,

11

,

13

personal computer,

16

physical,

4

,

23

,

130

physical address,

134

physical ID,

534

physical identifier,

534

physical logging,

498

physical memory,

7

physically-indexed cache,

194

PID,

36

,

191

pipe,

41

,

329

pipes,

17

platter,

404

policies,

26

,

59

,

114

policy,

6

poll,

378

polling,

391

,

578

power loss,

491

power outage,

561

pre-allocation,

470

preempt,

63

preemptive,

63

preemptive scheduler,

298

Preemptive Shortest Job First,

64

prefetching,

240

premature optimization,

322

present,

222

present bit,

174

,

219

,

224

principle of locality,

233

,

234

principle of SJF (shortest job first),

412

priority level,

72

privileged,

49

,

137

,

193

,

395

procedure call,

15

,

283

process,

25

,

26

Process Control Block,

32

process control block,

137

process control block (PCB),

263

process identifier,

36

,

191

process list,

30

,

32

process structure,

137

producer,

331

producer/consumer,

329

,

346

program counter,

26

programmed I/O (PIO),

391

projects,

iv

prompt,

40

proportional-share,

83

protect,

113

protection,

13

,

108

,

111

,

113

,

190

protection bits,

146

,

173

protocol,

575

protocol compiler,

551

pseudocode,

iv

PSJF,

64

purify,

125

queues,

72

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

ROTATIONS PER MINUTE

597

race condition,

270

,

272

RAID,

421

RAID 0+1,

428

RAID 1+0,

428

RAID-01,

428

RAID-10,

428

RAID-DP,

530

RAM,

194

RAM isn’t always RAM,

194

random,

192

,

409

,

426

,

446

random-access memory,

194

randomness,

84

raw disk,

475

read-after-write,

535

reader-writer lock,

350

Ready,

29

ready,

304

real code,

iv

reassembly,

554

reboot the machine,

51

recency,

233

reconstruct,

431

,

530

recover,

501

recovery,

429

recovery protocol,

562

recursive update problem,

518

redirected,

40

redo logging,

501

Reduced Instruction Set Computing,

189

redundancy,

421

Redundant Array of Inexpensive Disks,

421

reference bit,

174

,

238

,

249

reference count,

453

regain control,

50

register context,

30

reliability,

13

,

423

relocate,

132

remote method invocation,

551

remote procedure call,

551

replace,

192

,

221

replacement policy,

227

replayed,

501

resident set size,

249

resource,

4

resource manager,

4

,

6

resources,

13

response time,

64

retry,

548

return-from-trap,

15

,

47

revoke,

506

RISC,

188

,

189

RMI,

551

roll forward,

522

root directory,

442

,

471

rotates,

434

rotation delay,

405

rotational delay,

405

rotations per minute,

408

rotations per minute (RPM),

404

round robin,

99

Round-Robin (RR),

65

RPC,

551

RPM,

408

RSS,

249

run-time library,

551

run-time stack,

29

Running,

29

running,

304

running program,

25

SATA,

389

SATF,

414

scalability,

98

scale,

575

scaling,

167

SCAN,

413

scan resistance,

241

schedule,

474

scheduled,

30

scheduler,

37

,

52

scheduler state,

344

scheduling metric,

60

scheduling policies,

59

scheduling policy,

26

scheduling quantum,

65

SCSI,

389

second-chance lists,

249

security,

14

,

18

,

544

,

559

seek,

406

,

447

segment,

141

,

512

,

513

segment summary block,

520

segment table,

147

segmentation,

138

,

141

,

153

,

155

segmentation fault,

122

,

144

segmentation violation,

144

segmented FIFO,

249

segregated lists,

165

SEGV,

379

semaphore,

341

separator,

442

sequence counter,

549

sequential,

409

,

426

,

446

serialization,

552

server-side file system,

560

set,

298

set-associativity,

230

sets,

296

settling time,

406

shadow paging,

522

share,

11

,

146

shared state,

562

sharing,

559

shell,

17

shortest access time first,

414

Shortest Job First (SJF),

62

c

 2014, A

RPACI

-D

USSEAU

T

HREE

E

ASY

P

IECES

---

598

TIME SLICE

shortest positioning time first,

414

Shortest Time-to-Completion First,

64

shortest-seek-first,

412

shortest-seek-time-first,

412

SIG,

379

signal handler,

379

signaling,

326

signals,

42

,

378

,

379

SIGSEGV,

379

silent faults,

528

simulations,

iv

single-queue multiprocessor scheduling,

97

single-threaded,

263

slab allocator,

165

slabs,

165

sleeping barber problem,

355

sloppy counter,

314

small-write problem,

433

,

511

snapshots,

523

sockets,

545

soft link,

454

software RAID,

436

software-managed TLB,

188

solid-state drives,

11

solid-state storage device,

441

space leak,

494

space sharing,

26

sparse address spaces,

143

spatial locality,

95

,

186

,

187

,

234

spin lock,

298

spin-wait,

296

spin-waiting,

297

spindle,

404

split,

159

splitting,

155

SPTF,

414

spurious wakeups,

337

SQMS,

97

SSDs,

11

SSF,

412

SSTF,

412

stack,

29

,

111

,

119

stack pointer,

27

stack property,

231

stale cache,

570

standard library,

4

,

12

standard output,

40

starvation,

76

,

413

starve,

76

state,

565

stateful,

562

stateless,

562

states,

29

static relocation,

134

status,

391

STCF,

64

store-conditional,

300

stored checksum,

533

strace,

444

stride,

88

stride scheduling,

88

stripe,

424

striping,

424

stub generator,

551

sub-blocks,

486

sub-directories,

442

subtractive parity,

432

SunOS,

17

super block,

481

superblock,

464

superpages,

214

supervisor,

4

surface,

404

swap,

213

swap daemon,

223

swap space,

125

,

218

swapping,

28

switches contexts,

53

symbolic link,

454

,

488

synchronization primitives,

271

synchronous,

375

,

552

synchronously,

555

system call,

15

,

47

system calls,

4

,

12

,

50

,

560

system crash,

491

systems programming,

iv

TCP,

549

TCP/IP,

549

tcsh,

42

temporal locality,

95

,

186

,

187

,

234

test,

298

test-and-set,

297

test-and-set instruction,

296

tests,

296

the mapping problem,

425

the web,

42

thrashing,

240

thread,

262

,

263

thread control blocks (TCBs),

263

thread pool,

553

thread safe,

311

thread-local,

264

threads,

9

,

93

,

112

Three C’s,

230

ticket,

85

ticket currency,

85

ticket inflation,

85

ticket lock,

302

ticket transfer,

85

tickets,

83

TID,

498

Time sharing,

26

time sharing,

25

,

45

,

46

,

110

time slice,

65

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

VALID BIT

599

time-sharing,

26

time-slicing,

65

time-space trade-off,

207

time-space trade-offs,

207

timeout,

548

timeout/retry,

548

timer interrupt,

51

,

52

tips,

iii

TLB,

183

TLB coverage,

194

TLB hit,

184

,

219

TLB miss,

184

,

219

torn write,

403

total ordering,

365

track,

404

track buffer,

407

,

487

track skew,

406

trade-off,

66

transaction,

274

transaction checksum,

508

transaction identifier,

498

transfer,

406

translate,

174

translated,

133

translation lookaside buffer,

195

translation-lookaside buffer,

183

transparency,

113

,

131

transparent,

132

,

560

transparently,

224

,

422

trap,

15

,

47

,

51

trap handler,

15

,

188

trap handlers,

48

trap table,

47

,

48

traverse,

471

triple indirect pointer,

467

truss,

444

Turing Award,

71

turnaround time,

60

two-phase lock,

307

two-phased,

393

type,

443

UDP/IP,

545

unfairness metric,

87

unified page cache,

474

uninitialized read,

123

unlocked,

291

unmapped,

188

unmarshaling,

552

update,

7

,

96

update visibility,

570

USB,

389

use bit,

238

user mode,

15

,

47

utilization,

110

valgrind,

125

valid,

190

,

222

valid bit,

173

,

206

Venus,

576

version number,

521

versioning file system,

519

Very Simple File System,

461

Vice,

576

virtual,

4

,

23

,

130

virtual address,

112

,

114

,

134

virtual address space,

8

virtual CPUs,

263

virtual machine,

4

virtual memory,

263

virtual page number (VPN),

171

virtual-to-physical address translations,

176

virtualization,

iii

,

1

,

4

,

8

,

23

virtualized,

90

,

269

virtualizes,

13

virtualizing,

25

virtualizing memory,

8

,

112

virtualizing the CPU,

6

virtually-indexed cache,

194

void pointer,

154

,

280

volatile,

11

Voltaire’s Law,

569

volumes,

577

Von Neumann,

3

voo-doo constants,

77

vsfs,

461

WAFL,

523

,

530

wait-free,

367

wait-free synchronization,

300

waiting,

326

wakeup/waiting race,

306

whole-file caching,

575

wired,

188

work stealing,

101

work-conserving,

415

working sets,

240

workload,

59

,

492

,

585

workloads,

234

worst fit,

163

worst-fit,

148

write back,

407

write barriers,

499

write buffering,

474

,

513

,

569

write through,

407

write verify,

535

write-ahead log,

429

write-ahead logging,

492

,

497

x86,

177

XDR,

555

XOR,

430

yield,

51

Zemaphores,

355

c

 2014, A

RPACI

-D

USSEAU

T

HREE

E

ASY

P

IECES

---

600

ZOMBIE

Zettabyte File System,

535

ZFS,

523

,

535

zombie,

31

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

Asides

U

NIX

Signals,

379

Advanced Chapters,

93

And Then Came Linux,

18

Belady’s Anomaly,

231

Blocking vs. Non-blocking Interfaces,

375

Cache Consistency Is Not A Panacea,

580

Calling lseek() Does Not Perform A Disk Seek,

447

Computing The “Average” Seek,

411

Data Structure – The Free List,

136

Data Structure – The Inode,

465

Data Structure – The Page Table,

176

Data Structure – The Process List,

32

Dekker’s and Peterson’s Algorithms,

295

Dimensional Analysis,

408

Emulating Reference Bits,

250

Every Address You See Is Virtual,

114

FFS File Creation,

482

Forcing Writes To Disk,

499

Free Space Management,

470

Great Engineers Are Really Great,

166

How Long Context Switches Take,

55

Interludes,

35

Key Concurrency Terms,

272

601

---

602

W

HY

S

YSTEM

C

ALLS

L

OOK

L

IKE

P

ROCEDURE

C

ALLS

Linked-based Approaches,

468

Measurement Homeworks,

58

Mental Models Of File Systems,

462

Multiple Page Sizes,

202

Optimizing Log Writes,

500

Preemptive Schedulers,

63

Reads Don’t Access Allocation Structures,

472

RISC vs. CISC,

189

RTFM – Read The Man Pages,

42

Simulation Homeworks,

70

Software-based Relocation,

134

Storage Technologies,

218

Swapping Terminology And Other Things,

220

The creat() System Call,

444

The End-to-End Argument,

555

The Importance of U

NIX

,

17

The Importance Of Workload,

585

The RAID Consistent-Update Problem,

429

The RAID Mapping Problem,

425

The Segmentation Fault,

144

Thread API Guidelines,

288

TLB Valid Bit 6= Page Table Valid Bit,

190

Types of Cache Misses,

230

Types of Locality,

234

Why Hardware Doesn’t Handle Page Faults,

221

Why Null Pointer Accesses Cause Seg Faults,

248

Why Servers Crash,

561

Why System Calls Look Like Procedure Calls,

48

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

Tips

Always Hold The Lock While Signaling,

329

Amortization Can Reduce Costs,

66

Avoid Premature Optimization (Knuth’s Law),

322

Avoid Voo-doo Constants (Ousterhout’s Law),

79

Be Careful Setting The Timeout Value,

550

Be Careful With Generalization,

356

Be Lazy,

251

Be Wary of Complexity,

208

Be Wary Of Locks and Control Flow,

319

Be Wary Of Powerful Commands,

451

Communication Is Inherently Unreliable,

544

Comparing Against Optimal is Useful,

229

Consider Extent-based Approaches,

467

Dealing With Application Misbehavior,

51

Details Matter,

513

Do Work In The Background,

224

Don’t Always Do It Perfectly (Tom West’s Law),

370

Don’t Block In Event-based Servers,

377

Getting It Right (Lampson’s Law),

40

Hardware-based Dynamic Relocation,

135

Idempotency Is Powerful,

567

If 1000 Solutions Exist, No Great One Does,

149

Interposition Is Powerful,

131

Interrupts Not Always Better Than PIO,

393

It Always Depends (Livny’s Law),

415

It Compiled or It Ran 6= It Is Correct,

123

Know And Use Your Tools,

269

603

---

604

W

HEN

I

N

D

OUBT

, T

RY

I

T

O

UT

Learn From History,

72

Less Code Is Better Code (Lauer’s Law),

302

Make The System Usable,

488

Measure Then Build (Patterson’s Law),

577

More Concurrency Isn’t Necessarily Faster,

319

Overlap Enables Higher Utilization,

68

Perfect Is The Enemy Of The Good (Voltaire’s Law),

569

RAM Isn’t Always RAM (Culler’s Law),

194

Reboot Is Useful,

56

Separate Policy And Mechanism,

27

Simple And Dumb Can Be Better (Hill’s Law),

352

The Principle of Isolation,

113

The Principle of SJF,

62

There’s No Free Lunch,

531

Think About Concurrency As Malicious Scheduler,

297

Think Carefully About Naming,

443

Transparency Enables Deployment,

422

Turn Flaws Into Virtues,

523

Understand Time-Space Trade-offs,

207

Use strace (And Similar Tools),

445

Use A Level Of Indirection,

516

Use Advice Where Possible,

80

Use Atomic Operations,

274

Use Caching When Possible,

187

Use Checksums For Integrity,

547

Use Disks Sequentially,

410

Use Hybrids,

205

Use Protected Control Transfer,

47

Use Randomness,

84

Use The Timer Interrupt To Regain Control,

52

Use Tickets To Represent Shares,

85

Use Time Sharing (and Space Sharing),

26

Use While (Not If) For Conditions,

337

When In Doubt, Try It Out,

121

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

Cruces

How To Account For Disk Rotation Costs,

413

How To Add Locks To Data Structures,

311

How To Allocate And Manage Memory,

119

How To Avoid Spinning,

304

How To Avoid The Costs Of Polling,

392

How To Avoid The Curse Of Generality,

245

How To Build A Device-neutral OS,

395

How To Build A Distributed File System,

560

How To Build A Lock,

293

How To Build Concurrent Servers Without Threads,

373

How To Build Correct Concurrent Programs,

10

How To Build Systems That Work When Components Fail,

543

How To Communicate With Devices,

394

How To Create And Control Processes,

35

How To Create And Control Threads,

279

How To Deal With Deadlock,

363

How To Deal With Load Imbalance,

101

How To Decide Which Page To Evict,

227

How To Define A Stateless File Protocol,

563

How To Design A Scalable File Protocol,

578

How To Design TLB Replacement Policy,

192

How To Develop Scheduling Policy,

59

How To Efficiently And Flexibly Virtualize Memory,

129

How To Efficiently Virtualize The CPU With Control,

45

How To Ensure Data Integrity,

527

How To Gain Control Without Cooperation,

51

How To Go Beyond Physical Memory,

217

How To Handle Common Concurrency Bugs,

359

How To Handle Disk Starvation,

413

How To Handle Latent Sector Errors,

529

How To Handle Lost Writes,

535

How To Handle Misdirected Writes,

534

How To Implement A Simple File System,

461

605

---

606

H

OW

T

O

W

AIT

F

OR

A C

ONDITION

How To Implement An LRU Replacement Policy,

238

How To Integrate I/O Into Systems,

389

How To Lower PIO Overheads,

394

How To Make A Large, Fast, Reliable Disk,

421

How To Make All Writes Sequential Writes,

512

How To Make Page Tables Smaller,

201

How To Manage A Persistent Device,

441

How To Manage Free Space,

154

How To Manage TLB Contents On A Context Switch,

191

How To Organize On-disk Data To Improve Performance,

480

How To Perform Restricted Operations,

46

How To Preserve Data Integrity Despite Corruption,

530

How To Provide Support For Synchronization,

272

How To Provide The Illusion Of Many CPUs,

25

How To Reduce File System I/O Costs,

473

How To Regain Control Of The CPU,

50

How To Schedule Jobs On Multiple CPUs,

94

How To Schedule Without Perfect Knowledge,

71

How To Share The CPU Proportionally,

83

How To Speed Up Address Translation,

183

How To Store And Access Data On Disk,

403

How To Store Data Persistently,

12

How To Support A Large Address Space,

141

How To Update The Disk Despite Crashes,

491

How To Use Semaphores,

341

How To Virtualize Memory,

112

How To Virtualize Memory Without Segments,

169

How To Virtualize Resources,

4

How To Wait For A Condition,

326

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

This book was typeset using the amazing L

A

TEX typesetting system and

the wonderful memoir book-making package. A heartfelt thank you to

the legions of programmers who have contributed to this powerful tool

over the many years of its development.

All of the graphs and figures in the book were generated using a Python-

based version of zplot, a simple and useful tool developed by R. Arpaci-

Dusseau to generate graphs in PostScript. The zplot tool arose after

many years of frustration with existing graphing tools such as gnuplot

(which was limited) and ploticus (which was overly complex though

admittedly quite awesome). As a result, R. A-D finally put his years of

study of PostScript to good use and developed zplot.

---