O perating s ystems t hree e asy p ieces

Professor:

OK.

Student:

Go ahead.

Professor:

No, after you.

Student:

Please, professors first.

589

---

590

S

UMMARY

D

IALOGUE ON

D

ISTRIBUTION

Professor:

No, please, after you.

Student:

(exasperated) Fine!

Professor:

(waiting) ... so why haven’t you left?

Student:

I don’t know how. Turns out, the only thing I can do is participate in

these dialogues.

Professor:

Me too. And now you’ve learned our final lesson...

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

General Index

absolute pathname,

442

abstraction,

iv

,

112

,

395

abstractions,

13

access methods,

462

access path,

470

accessed bit,

174

accounting,

77

ack,

547

acknowledgment,

547

acquired,

291

additive parity,

432

address,

7

address space,

8

,

26

,

108

,

111

,

132

,

263

,

403

address space identifier,

191

address translation,

130

,

134

,

137

address translations,

170

address-based ordering,

164

address-space identifier,

190

address-translation cache,

183

admission control,

240

advice,

79

,

80

AIO control block,

378

AIX,

17

allocate,

472

allocation structures,

463

AMAT,

228

amortization,

66

,

485

amortize,

65

,

514

anonymous,

125

anticipatory disk scheduling,

415

ASID,

191

Aside,

16

asides,

iii

asynchronous,

375

asynchronous I/O,

377

asynchronous read,

378

asynchronously,

556

atomic,

274

,

403

,

448

atomic exchange,

296

atomically,

10

,

271

,

297

,

429

,

495

atomicity violation,

360

attribute cache,

571

automatic,

119

automatic memory management,

122

available,

291

average memory access time,

228

average turnaround time,

61

avoidance,

368

avoids,

474

B-tree,

470

baby proofing,

55

back pointer,

508

background,

224

backpointer-based consistency,

508

base,

133

,

135

,

204

base and bounds,

133

bash,

42

batch,

14

,

474

BBC,

508

Belady’s Anomaly,

231

Berkeley Systems Distribution,

17

best fit,

163

best-fit,

148

big endian,

554

big kernel lock,

322

Bill Joy,

17

binary buddy allocator,

166

binary semaphore,

344

bitmap,

463

BKL,

322

block corruption,

436

,

527

block groups,

481

Blocked,

29

blocked,

67

,

221

blocks,

462

boost,

76

bound,

204

bounded buffer,

329

,

346

bounded SATF,

419

bounded-buffer,

329

bounds,

133

,

135

591

---

592

DEPLOYMENT

break,

125

BSATF,

419

BSD,

17

btrfs,

523

buddy algorithm,

148

buffer,

447

buffer cache,

493

buffer overflow,

123

bugs,

561

bus snooping,

96

byte ordering,

554

C programming language,

iv

,

17

C-SCAN,

413

cache,

183

,

227

,

407

cache affinity,

97

cache coherence,

96

cache consistency problem,

569

cache hits,

227

cache misses,

227

cache replacement,

192

cached,

560

caches,

94

caching,

569

callback,

578

capability,

444

capacity,

423

capacity miss,

230

cast,

121

centralized administration,

559

checkpoint,

498

checkpoint region (CR),

517

checkpointing,

498

checksum,

530

,

546

child,

36

chunk size,

424

cigarette smoker’s problem,

355

circular log,

502

Circular SCAN,

413

CISC,

187

,

189

clean,

239

,

519

client stub,

551

client-side file system,

560

client/server,

543

clock algorithm,

238

clock hand,

238

close-to-open,

570

cluster,

223

clustering,

240

,

249

coalesce,

162

coalescing,

156

,

393

coarse-grained,

147

,

292

code,

111

code sharing,

146

cold-start miss,

229

,

230

collision,

532

command,

391

common case,

571

communication,

544

communication endpoint,

545

compact,

148

,

520

compaction,

154

compare-and-exchange,

299

compare-and-swap,

299

Complex Instruction Set Computing,

189

compulsory miss,

229

,

230

computed checksum,

533

concurrency,

iii

,

1

,

8

,

10

,

13

,

16

,

37

,

54

,

261

concurrently,

311

condition,

325

,

326

,

344

condition variable,

285

,

326

,

344

condition variables,

262

,

273

,

362

conflict miss,

230

consistent-update problem,

429

,

495

consumer,

331

context switch,

26

,

30

,

52

,

63

,

263

continuation,

380

convention,

443

convoy effect,

61

cooperative,

50

copy-on-write,

12

,

251

,

507

,

522

correctness,

299

corrupt,

528

covering condition,

338

COW,

251

,

507

CPU,

5

crash-consistency problem,

491

,

495

CRC,

532

critical section,

271

,

272

,

284

crux,

iii

crux of the problem,

iii

Culler’s Law,

194

cycle,

363

cyclic redundancy check,

532

cylinder groups,

481

dangling pointer,

124

dangling reference,

455

data,

391

data bitmap,

463

,

481

,

492

data integrity,

527

data journaling,

498

,

503

data protection,

527

data region,

462

data structures,

32

,

461

database management system,

194

datagrams,

545

DBMS,

194

deadlock,

354

,

359

,

363

DEC,

245

decay-usage,

79

decodes,

3

demand paging,

240

demand zeroing,

250

deployability,

422

deployment,

422

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

EXPLICIT

593

descheduled,

30

deserialization,

552

deterministic,

37

,

268

,

270

,

272

device driver,

12

,

395

dialogue,

iii

Digital Equipment Corporation,

245

dimensional analysis,

408

dining philosopher’s problem,

352

direct I/O,

474

Direct Memory Access (DMA),

394

direct pointers,

466

directory,

442

directory hierarchy,

442

directory tree,

442

dirty,

239

,

447

dirty bit,

174

,

190

,

239

disable interrupts,

55

disassemble,

176

disassembler.,

269

disciplines,

59

disk,

28

disk address,

218

disk arm,

404

disk head,

404

Disk Operating System,

16

disk scheduler,

412

disk scrubbing,

535

disks,

389

distributed shared memory,

550

distributed state,

562

DOS,

16

double free,

124

double indirect pointer,

467

drop,

545

DSM,

550

dtruss,

444

dynamic relocation,

133

,

134

eagerly,

28

ease of use,

108

easy to use,

3

,

111

ECC,

528

Edsger Dijkstra,

341

efficiency,

110

,

113

efficient,

113

elevator,

413

empty,

335

encapsulation,

364

end-to-end argument,

545

,

555

energy-efficiency,

14

error correcting codes,

528

event handler,

374

event loop,

374

event-based concurrency,

373

evict,

227

exactly once,

548

executable format,

28

executes,

3

explicit,

144

exponential back-off,

550

extents,

467

eXternal Data Representation,

555

external fragmentation,

148

,

153

,

154

F-SCAN,

413

fail-partial,

528

fail-stop,

423

,

527

failure,

543

fair,

66

fair-share,

83

fairness,

60

,

293

,

299

Fast File System (FFS),

481

FAT,

468

FCFS,

61

fetch-and-add,

302

fetches,

3

FID,

578

FIFO,

60

,

230

file,

441

file allocation table,

468

file descriptor,

444

file descriptors,

29

file handle,

563

,

578

file identifier,

578

file offset,

446

file server,

560

file system,

11

,

12

,

15

file system checker,

492

file-level locking,

580

file-system inconsistency,

494

files,

11

fill,

335

final,

31

fine-grained,

147

,

292

firmware,

390

First Come, First Served,

60

first fit,

164

First In, First Out,

60

first-fit,

148

fix-sized cache,

474

flash-based SSDs,

28

Fletcher checksum,

532

flush,

191

flush-on-close,

570

fork(),

36

fragmentation,

554

fragmented,

480

frame pointer,

27

free,

291

free list,

136

,

154

,

170

,

463

free lists,

470

free space management,

469

free-space management,

153

frequency,

233

fsck,

492

,

495

full-stripe write,

432

c

 2014, A

RPACI

-D

USSEAU

T

HREE

E

ASY

P

IECES

---

594

LINK COUNT

fully associative,

189

fully-associative,

189

,

230

function pointer,

280

futex,

307

,

308

game the scheduler,

76

garbage,

494

,

518

garbage collection,

519

garbage collector,

122

graphics,

18

greedy,

419

group,

223

grouping,

240

hand-over-hand locking,

318

hard disk drive,

217

,

403

,

441

hard drive,

11

hardware caches,

94

hardware privilege level,

15

hardware-based address translation,

130

hardware-managed TLB,

183

hardware-managed TLBs,

187

head crash,

528

header,

157

heap,

29

,

111

,

119

,

288

heartbeat,

582

held,

291

high watermark,

223

Hill’s Law,

352

hints,

80

hit rate,

186

,

192

,

228

Hoare semantics,

333

holds,

296

holes,

520

homeworks,

iv

hot spare,

436

HPUX,

17

HUP,

379

hybrid,

202

,

205

,

308

,

393

I/O,

11

I/O bus,

389

I/O instructions,

394

I/O merging,

415

Idempotency,

567

idempotent,

567

idle time,

224

illusion,

130

immediate reporting,

407

,

499

implicit,

145

inconsistent,

429

,

491

indeterminate,

270

,

272

index node,

464

,

465

indirect pointer,

466

initial,

31

inode,

450

,

463

–

465

,

512

inode bitmap,

463

,

481

,

492

inode map (imap),

515

inode number,

442

inode table,

463

input/output,

11

input/output (I/O) device,

389

instruction pointer,

26

INT,

379

interactivity,

110

interface,

390

internal,

202

internal fragmentation,

138

,

154

,

167

,

202

,

480

,

486

internal structure,

390

interposing,

129

interrupt,

378

,

392

interrupt handler,

51

,

392

interrupt service routine (ISR),

392

interrupts,

578

inumber,

465

invalid,

173

,

203

invalid frees,

124

invalidate,

96

invalidates,

570

invariant,

431

inverted page table,

170

inverted page tables,

212

IP,

26

IRIX,

17

isolation,

13

,

108

,

113

Jain’s Fairness Index,

60

jobs,

60

journal superblock,

503

journaling,

12

,

492

,

497

kernel mode,

15

,

47

kernel stack,

48

kernel virtual memory,

213

kill,

379

Knuth,

322

last closer wins,

581

last writer wins,

581

latent sector errors,

436

latent-sector errors,

527

Lauer’s Law,

302

lazily,

28

lazy,

250

LDE,

129

Least-Frequently-Used,

233

Least-Recently-Used,

233

least-recently-used,

192

level of indirection,

207

,

515

,

516

LFS,

512

LFU,

233

limit,

133

,

135

,

204

limited direct execution,

45

,

55

,

105

,

129

linear page table,

173

,

183

link count,

454

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

MERGE

595

linked list,

468

Linus Torvalds,

18

Linux,

18

Linux ext2,

497

Linux ext3,

497

Linux ext4,

500

little endian,

554

live,

519

livelock,

366

,

393

lmbench,

55

load,

28

load imbalance,

100

load-linked,

300

loader,

134

loads,

39

locality,

95

,

187

lock,

291

lock coupling,

318

lock variable,

291

lock-free,

96

locked,

291

locking,

55

,

97

,

98

locks,

262

,

283

log,

522

Log-structured File System,

512

logical logging,

498

long file names,

487

lookaside buffer,

195

lost write,

535

lottery scheduling,

83

low watermark,

223

low-level name,

441

,

465

LRU,

192

,

233

,

474

LSEs,

527

Mac OS,

16

machine state,

26

malicious scheduler,

297

man pages,

42

manage,

4

manage memory,

130

manual pages,

42

manual stack management,

380

marshaling,

552

master control program,

4

measurement,

577

mechanisms,

6

,

25

,

59

,

105

,

114

memory bus,

389

memory hierarchy,

217

memory hogs,

249

memory leak,

124

memory management unit (MMU),

135

memory overlays,

217

memory pressure,

227

memory protection,

16

memory-management unit,

183

memory-mapped I/O,

395

MenuMeters,

42

merge,

162

,

415

Mesa semantics,

333

,

337

metadata,

449

,

463

,

466

,

512

metadata journaling,

503

MFU,

234

mice,

389

microkernels,

33

,

113

Microsoft,

16

migrating,

99

migration,

101

minicomputer,

15

minimize the overheads,

13

mirrored,

422

misdirected write,

534

miss rate,

192

,

228

MMU,

183

mobility,

14

modified,

239

modified bit,

239

modularity,

27

monitors,

312

Most-Frequently-Used,

234

Most-Recently-Used,

234

mount point,

456

mount protocol,

564

MQMS,

99

MRU,

234

multi-level feedback queue,

68

Multi-level Feedback Queue (MLFQ),

71

multi-level index,

467

multi-level page table,

187

,

205

multi-queue multiprocessor scheduling,

99

multi-threaded,

9

,

262

,

263

multi-threaded programs,

37

multi-zoned,

407

multicore,

93

Multics,

17

multiprocessor,

93

multiprocessor scheduling,

93

,

94

multiprogramming,

15

,

110

mutex,

292

mutual exclusion,

271

,

272

,

292

,

293

name,

443

naming,

553

NBF,

412

nearest-block-first,

412

networking,

18

new,

122

next fit,

164

NeXTStep,

18

node.js,

373

non-blocking data structures,

322

non-determinism,

37

non-preemptive,

63

non-work-conserving,

415

null-pointer,

248

c

 2014, A

RPACI

-D

USSEAU

T

HREE

E

ASY

P

IECES

---

596

QUEUES

object caches,

165

offset,

171

open protocol,

561

open-source software,

17

operating system,

4

Operating Systems in Three Easy Pieces,

1

optimal,

62

,

228

optimistic crash consistency,

508

order violation,

360

,

361

ordered journaling,

503

OS,

4

Ousterhout’s Law,

79

out-of-memory killer,

240

overlap,

67

,

68

,

221

,

377

,

392

owner,

292

page,

169

page cache,

493

page daemon,

223

page directory,

205

,

209

page directory entries,

206

page fault,

219

,

220

,

224

page frame,

170

page frame number,

206

page in,

221

page miss,

220

page out,

221

page replacement,

174

page selection,

240

page table,

170

,

176

page table base register,

219

page table entry (PTE),

172

,

219

page-directory index,

208

page-fault handler,

220

,

224

page-replacement policy,

221

page-table base register,

175

,

187

page-table index,

209

paging,

28

,

153

,

169

,

179

,

381

paging out,

227

parallel,

93

parameterization,

487

parameterize,

78

parent,

31

,

36

parity,

430