操作系统入门经典：三易篇合集

需积分: 50 100 浏览量更新于2024-07-17 收藏 7.4MB PDF 举报

"《Operating Systems: Three Easy Pieces》是一本由Remzi H. Arpaci-Dusseau和Andrea C. Arpaci-Dusseau合著的深入浅出的计算机操作系统教程。这本书是对著名物理学家理查德·费曼关于物理学讲座笔记的致敬，虽然可能无法达到费曼那样的高度，但它旨在帮助读者理解操作系统以及更广泛系统的基本概念。两位作者通过自己的官方网站（http://pages.cs.wisc.edu/~remzi/OSTEP/）提供了一个完整的PDF版本，章节可在线阅读，但可能会有不便之处。由于作者偶尔会更新内容，我已将所有章节下载并合并成一本PDF，并创建了目录，便于读者查阅。这份整理的工作特别适合那些希望通过一个更方便的阅读体验来学习这本书的人，特别是当网络连接不可用时。尽管PDF包含了所有章节，但强烈建议访问原著者的网站，因为那里提供了配套的源代码、项目、作业，甚至可以购买纸质版书籍或进行捐赠以支持他们的工作。截至2018年10月3日，这个版本可以在GitHub（<https://github.com/DayuanTan/OSTEP>）上找到。参考文献应直接引用Remzi H. Arpaci-Dusseau和Andrea C. Arpaci-Dusseau的作品，以便追溯到原始资料。这份合集不仅是一份学习资源，也是一个向计算机科学领域经典之作致敬的实践成果。"

CONTENTS xvii

19.7 A Real TLB Entry . . . . . . . . . . . . . . . . . . . . . . . . 209

19.8 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

Homework (Measurement) . . . . . . . . . . . . . . . . . . . . . . 212

20 Paging: Smaller Tables 215

20.1 Simple Solution: Bigger Pages . . . . . . . . . . . . . . . . 215

20.2 Hybrid Approach: Paging and Segments . . . . . . . . . . 216

20.3 Multi-level Page Tables . . . . . . . . . . . . . . . . . . . . 219

20.4 Inver ted Page Tables . . . . . . . . . . . . . . . . . . . . . . 226

20.5 Swapping the Page Tables to Disk . . . . . . . . . . . . . . 227

20.6 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

Homework (Simulation) . . . . . . . . . . . . . . . . . . . . . . . 229

21 Beyond Physical Memory: Mechanisms 231

21.1 Swap Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

21.2 The Present Bit . . . . . . . . . . . . . . . . . . . . . . . . . 233

21.3 The Page Fault . . . . . . . . . . . . . . . . . . . . . . . . . 234

21.4 What If Memory Is Full? . . . . . . . . . . . . . . . . . . . . 235

21.5 Page Fault Control Flow . . . . . . . . . . . . . . . . . . . . 236

21.6 When Replacements Really Occur . . . . . . . . . . . . . . 237

21.7 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

Homework (Measurement) . . . . . . . . . . . . . . . . . . . . . . 240

22 Beyond Physical Memory: Policies 243

22.1 Cache Management . . . . . . . . . . . . . . . . . . . . . . 243

22.2 The Optimal Replacement Policy . . . . . . . . . . . . . . . 244

22.3 A Simple Policy: FIFO . . . . . . . . . . . . . . . . . . . . . 246

22.4 Another Simple Policy: Random . . . . . . . . . . . . . . . 248

22.5 Using History: LRU . . . . . . . . . . . . . . . . . . . . . . 249

22.6 Workload Examples . . . . . . . . . . . . . . . . . . . . . . 250

22.7 Implement ing Historical Algorithms . . . . . . . . . . . . . 253

22.8 Approximating LRU . . . . . . . . . . . . . . . . . . . . . . 254

22.9 Considering Dirty Pages . . . . . . . . . . . . . . . . . . . . 255

22.10 Other VM Policies . . . . . . . . . . . . . . . . . . . . . . . 256

22.11 Thrashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

22.12 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258

Homework (Simulation) . . . . . . . . . . . . . . . . . . . . . . . 259

23 Complete Virtual Memory Systems 261

23.1 VAX/VMS Virtual Memory . . . . . . . . . . . . . . . . . . 262

23.2 The Linux Virtual Memory System . . . . . . . . . . . . . . 268

23.3 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278

 2008–18, ARPACI-DUSSEAU

THREE

EASY

PIECES

xviii CONTENTS

24 Summary Dialogue on Memory Virtualization 279

II Concurrency 283

25 A Dialogue on Concurrency 285

26 Concurrency: An Introduction 287

26.1 Why Use Threads? . . . . . . . . . . . . . . . . . . . . . . . 288

26.2 An Example: Thread Creation . . . . . . . . . . . . . . . . 289

26.3 Why It Gets Worse: Shared Data . . . . . . . . . . . . . . . 292

26.4 The Heart Of The Problem: Uncontrolled Scheduling . . . 294

26.5 The Wish For Atomicity . . . . . . . . . . . . . . . . . . . . 296

26.6 One More Problem: Waiting For Another . . . . . . . . . . 298

26.7 Summar y: Why in OS Class? . . . . . . . . . . . . . . . . . 298

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300

Homework (Simulation) . . . . . . . . . . . . . . . . . . . . . . . 301

27 Interlude: Thread API 303

27.1 Thread Creation . . . . . . . . . . . . . . . . . . . . . . . . 303

27.2 Thread Completion . . . . . . . . . . . . . . . . . . . . . . . 304

27.3 Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

27.4 Condition Variables . . . . . . . . . . . . . . . . . . . . . . 309

27.5 Compiling and Running . . . . . . . . . . . . . . . . . . . . 311

27.6 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

Homework (Code) . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

28 Locks 315

28.1 Locks: The Basic Idea . . . . . . . . . . . . . . . . . . . . . 315

28.2 Pthread Locks . . . . . . . . . . . . . . . . . . . . . . . . . . 316

28.3 Build ing A Lock . . . . . . . . . . . . . . . . . . . . . . . . 317

28.4 Evaluatin g Locks . . . . . . . . . . . . . . . . . . . . . . . . 317

28.5 Controlling Interrupts . . . . . . . . . . . . . . . . . . . . . 318

28.6 A Failed Attempt: Just Using Loads/Stores . . . . . . . . . 319

28.7 Build ing Working Spin Locks with Test-And-Set . . . . . . 320

28.8 Evaluatin g Spin Locks . . . . . . . . . . . . . . . . . . . . . 322

28.9 Compare-And-Swap . . . . . . . . . . . . . . . . . . . . . . 323

28.10 Load-Linked and Store-Conditional . . . . . . . . . . . . . 324

28.11 Fetch-And-Add . . . . . . . . . . . . . . . . . . . . . . . . . 326

28.12 Too Much Spinning: What Now? . . . . . . . . . . . . . . . 327

28.13 A Simple Approach: Just Yield, Baby . . . . . . . . . . . . . 328

28.14 Using Queues: Sleeping Instead Of Spinning . . . . . . . . 329

28.15 Different OS, Different Suppor t . . . . . . . . . . . . . . . . 332

28.16 Two-Phase Locks . . . . . . . . . . . . . . . . . . . . . . . . 332

28.17 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335

OPERATING

SYSTEMS

[VERSION 1.00] WWW.OSTEP.ORG

CONTENTS xix

Homework (Simulation) . . . . . . . . . . . . . . . . . . . . . . . 336

29 Lock-based Concurrent Data Structures 337

29.1 Concurrent Counters . . . . . . . . . . . . . . . . . . . . . . 337

29.2 Concurrent Linked Lists . . . . . . . . . . . . . . . . . . . . 342

29.3 Concurrent Queues . . . . . . . . . . . . . . . . . . . . . . . 345

29.4 Concurrent Hash Table . . . . . . . . . . . . . . . . . . . . 346

29.5 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

Homework (Code) . . . . . . . . . . . . . . . . . . . . . . . . . . . 350

30 Condition Variables 351

30.1 Deﬁnition and Routines . . . . . . . . . . . . . . . . . . . . 352

30.2 The Producer/Consumer (Bounded Buffer) Problem . . . . 355

30.3 Covering Conditions . . . . . . . . . . . . . . . . . . . . . . 363

30.4 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365

Homework (Code) . . . . . . . . . . . . . . . . . . . . . . . . . . . 366

31 Semaphores 367

31.1 Semaphores: A Deﬁnition . . . . . . . . . . . . . . . . . . . 367

31.2 Binary Semaphores (Locks) . . . . . . . . . . . . . . . . . . 369

31.3 Semaphores For Ordering . . . . . . . . . . . . . . . . . . . 370

31.4 The Producer/Consumer (Bounded Buffer) Problem . . . . 372

31.5 Reader-Writer Locks . . . . . . . . . . . . . . . . . . . . . . 376

31.6 The Dining Philosophers . . . . . . . . . . . . . . . . . . . 378

31.7 How To Implement Semaphores . . . . . . . . . . . . . . . 381

31.8 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383

Homework (Code) . . . . . . . . . . . . . . . . . . . . . . . . . . . 384

32 Common Concurrency Problems 385

32.1 What Types Of Bugs Exist? . . . . . . . . . . . . . . . . . . 385

32.2 Non-Deadlock Bugs . . . . . . . . . . . . . . . . . . . . . . 386

32.3 Deadlock Bugs . . . . . . . . . . . . . . . . . . . . . . . . . 389

32.4 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399

Homework (Code) . . . . . . . . . . . . . . . . . . . . . . . . . . . 400

33 Event-based Concurrency (Advanced) 401

33.1 The Basic Idea: An Event Loop . . . . . . . . . . . . . . . . 401

33.2 An Important API: select() (or poll()).........402

33.3 Using select() ........................403

33.4 Why Simpler? No Locks Needed . . . . . . . . . . . . . . . 404

33.5 A Problem: Blocking System Calls . . . . . . . . . . . . . . 405

33.6 A Solution: Asynchronous I/O . . . . . . . . . . . . . . . . 405

33.7 Another Problem: State Management . . . . . . . . . . . . 408

 2008–18, ARPACI-DUSSEAU

THREE

EASY

PIECES

xx CONTENTS

33.8 What Is Still Difﬁcult With Events . . . . . . . . . . . . . . 409

33.9 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410

Homework (Code) . . . . . . . . . . . . . . . . . . . . . . . . . . . 411

34 Summary Dialogue on Concurrency 413

III Persistence 415

35 A Dialogue on Persistence 417

36 I/O Devices 419

36.1 System Architecture . . . . . . . . . . . . . . . . . . . . . . 419

36.2 A Canonical Device . . . . . . . . . . . . . . . . . . . . . . 421

36.3 The Canonical Protocol . . . . . . . . . . . . . . . . . . . . 422

36.4 Lowering CPU Overhead With Interrupts . . . . . . . . . . 423

36.5 More Efﬁcient Data Movement With DMA . . . . . . . . . 424

36.6 Methods Of Device Interaction . . . . . . . . . . . . . . . . 425

36.7 Fitting Into The OS: The Device Driver . . . . . . . . . . . . 426

36.8 Case Study: A Simple IDE Disk Driver . . . . . . . . . . . . 427

36.9 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . 430

36.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431

37 Hard Disk Drives 433

37.1 The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 433

37.2 Basic Geometry . . . . . . . . . . . . . . . . . . . . . . . . . 434

37.3 A Simple Disk Drive . . . . . . . . . . . . . . . . . . . . . . 435

37.4 I/O Time: Doing The Math . . . . . . . . . . . . . . . . . . 438

37.5 Disk Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 442

37.6 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447

Homework (Simulation) . . . . . . . . . . . . . . . . . . . . . . . 448

38 Redundant Arrays of Inexpensive Disks (RAIDs) 449

38.1 Inter face And RAID Internals . . . . . . . . . . . . . . . . . 450

38.2 Fault Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 451

38.3 How To Evaluate A RAID . . . . . . . . . . . . . . . . . . . 451

38.4 RAID Level 0: Striping . . . . . . . . . . . . . . . . . . . . . 452

38.5 RAID Level 1: Mirroring . . . . . . . . . . . . . . . . . . . . 455

38.6 RAID Level 4: Saving Space With Parity . . . . . . . . . . . 458

38.7 RAID Level 5: Rotating Parit y . . . . . . . . . . . . . . . . 462

38.8 RAID Comparison: A Summary . . . . . . . . . . . . . . . 463

38.9 Other Interesting RAID Issues . . . . . . . . . . . . . . . . 464

38.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465

OPERATING

SYSTEMS

[VERSION 1.00] WWW.OSTEP.ORG

CONTENTS xxi

Homework (Simulation) . . . . . . . . . . . . . . . . . . . . . . . 466

39 Interlude: Files and Directories 467

39.1 Files And Directories . . . . . . . . . . . . . . . . . . . . . . 467

39.2 The File System Interface . . . . . . . . . . . . . . . . . . . 469

39.3 Creating Files . . . . . . . . . . . . . . . . . . . . . . . . . . 469

39.4 Reading And Writing Files . . . . . . . . . . . . . . . . . . 470

39.5 Reading And Writing, But Not Sequentially . . . . . . . . . 472

39.6 Shared File Table Entries: fork() And dup() .......475

39.7 Writing Immediately With fsync() .............477

39.8 Renaming Files . . . . . . . . . . . . . . . . . . . . . . . . . 478

39.9 Getting Information About Files . . . . . . . . . . . . . . . 479

39.10 Removing Files . . . . . . . . . . . . . . . . . . . . . . . . . 480

39.11 Making Directories . . . . . . . . . . . . . . . . . . . . . . . 480

39.12 Reading Directories . . . . . . . . . . . . . . . . . . . . . . 481

39.13 Deleting Directories . . . . . . . . . . . . . . . . . . . . . . 482

39.14 Hard Links . . . . . . . . . . . . . . . . . . . . . . . . . . . 482

39.15 Symbolic Links . . . . . . . . . . . . . . . . . . . . . . . . . 484

39.16 Permission Bits And Access Control Lists . . . . . . . . . . 485

39.17 Making And Mounting A File System . . . . . . . . . . . . 488

39.18 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491

Homework (Code) . . . . . . . . . . . . . . . . . . . . . . . . . . . 492

40 File System Implementation 493

40.1 The Way To Think . . . . . . . . . . . . . . . . . . . . . . . 493

40.2 Overall Organization . . . . . . . . . . . . . . . . . . . . . . 494

40.3 File Organization: The Inode . . . . . . . . . . . . . . . . . 496

40.4 Directory Organization . . . . . . . . . . . . . . . . . . . . 501

40.5 Free Space Management . . . . . . . . . . . . . . . . . . . . 501

40.6 Access Paths: Reading and Writing . . . . . . . . . . . . . . 502

40.7 Caching and Buffering . . . . . . . . . . . . . . . . . . . . . 506

40.8 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509

Homework (Simulation) . . . . . . . . . . . . . . . . . . . . . . . 510

41 Locality and The Fast File System 511

41.1 The Problem: Poor Performance . . . . . . . . . . . . . . . 511

41.2 FFS: Disk Awareness Is The Solution . . . . . . . . . . . . . 513

41.3 Organizing Structure: T he Cylinder Group . . . . . . . . . 513

41.4 Policies: How To Allocate Files and Directories . . . . . . . 515

41.5 Measuring File Locality . . . . . . . . . . . . . . . . . . . . 517

41.6 The Large-File Exception . . . . . . . . . . . . . . . . . . . 518

41.7 A Few Other Things About FFS . . . . . . . . . . . . . . . . 520

41.8 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523

Homework (Simulation) . . . . . . . . . . . . . . . . . . . . . . . 524

 2008–18, ARPACI-DUSSEAU

THREE

EASY

PIECES

剩余708页未读，继续阅读

qq_39939580

粉丝: 0
资源: 2

操作系统入门经典：三易篇合集

Operating Systems_Three Easy Pieces

Operating Systems:Three Easy Pieces(OSTEP).pdf

Operating Systems: Three Easy Pieces

Operating Systems - Three Easy Pieces.pdf.zip

Operating Systems Three Easy Pieces.rar

operating systems three easy pieces E.pdf

Operating Systems Three Easy Pieces v1_0.pdf

operating systems three easy pieces

Operating Systems Three Easy Pieces 0.92

operating systems three easy pieces中文

最新资源