操作系统三易篇：官方教材合并与更新

操作系统

OSTEP

需积分: 9 106 浏览量更新于2024-07-18 1 收藏 7.32MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

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

xxii CONTENTS

42 Crash Consistency: FSCK and Journaling 525

42.1 A Detailed Example . . . . . . . . . . . . . . . . . . . . . . 526

42.2 Solution #1: The File System Checker . . . . . . . . . . . . 529

42.3 Solution #2: Journaling (or Write-Ahead Logging) . . . . . 531

42.4 Solution #3: Other Approaches . . . . . . . . . . . . . . . . 541

42.5 Summar y . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543

Homework (Simulation) . . . . . . . . . . . . . . . . . . . . . . . 545

43 Log-structured File Systems 547

43.1 Writing To Disk Sequentially . . . . . . . . . . . . . . . . . 548

43.2 Writing Sequentially And Effectively . . . . . . . . . . . . . 549

43.3 How Much To Buffer? . . . . . . . . . . . . . . . . . . . . . 550

43.4 Problem: Finding Inodes . . . . . . . . . . . . . . . . . . . 551

43.5 Solution Through Indirection: The Inode Map . . . . . . . 551

43.6 Completing The Solution: The Checkpoint Region . . . . . 553

43.7 Reading A File From Disk: A Recap . . . . . . . . . . . . . 553

43.8 What About Directories? . . . . . . . . . . . . . . . . . . . 554

43.9 A New Problem: Garbage Collection . . . . . . . . . . . . . 555

43.10 Determining Block Liveness . . . . . . . . . . . . . . . . . . 556

43.11 A Policy Question: Which Blocks To Clean, And When? . . 557

43.12 Crash Recovery And The Log . . . . . . . . . . . . . . . . . 558

43.13 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560

Homework (Simulation) . . . . . . . . . . . . . . . . . . . . . . . 561

44 Flash-based SSDs 563

44.1 Storing a Single Bit . . . . . . . . . . . . . . . . . . . . . . . 563

44.2 From Bits to Banks/Planes . . . . . . . . . . . . . . . . . . 564

44.3 Basic Flash Operations . . . . . . . . . . . . . . . . . . . . . 565

44.4 Flash Performance And Reliability . . . . . . . . . . . . . . 567

44.5 From Raw F lash to Flash-Based SSDs . . . . . . . . . . . . 568

44.6 FTL Organization: A Bad Approach . . . . . . . . . . . . . 569

44.7 A Log-Structured FTL . . . . . . . . . . . . . . . . . . . . . 570

44.8 Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . 572

44.9 Mapping Table Size . . . . . . . . . . . . . . . . . . . . . . 574

44.10 Wear Leveling . . . . . . . . . . . . . . . . . . . . . . . . . 579

44.11 SSD Performance And Cost . . . . . . . . . . . . . . . . . . 579

44.12 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583

Homework (Simulation) . . . . . . . . . . . . . . . . . . . . . . . 585

45 Data Integrity and Protection 587

45.1 Disk Failure Modes . . . . . . . . . . . . . . . . . . . . . . . 587

45.2 Handling Latent Sector Errors . . . . . . . . . . . . . . . . 589

45.3 Detecting Corruption: The Checksum . . . . . . . . . . . . 590

45.4 Using Checksums . . . . . . . . . . . . . . . . . . . . . . . 593

OPERATING

SYSTEMS

[VERSION 1.00] WWW.OSTEP.ORG

剩余707页未读，继续阅读

lzxr8903

粉丝: 0
资源: 2

操作系统三易篇：官方教材合并与更新

Operating Systems:Three Easy Pieces(OSTEP).pdf

Operating Systems: Three Easy Pieces 国外著名大学研究生操作系统课本(0.90版本)

Operating Systems Three Easy Pieces V0.90

operating systems: three easy pieces 英文版

operating systems: three easy pieces

operating systems three easy pieces中文

operating systems:principles and practice pdf

tanenbaum operating systems: design and implementation

operating systems: principles and practice pdf

operating system three easy pieces pdf

3. Describe each of the three categories of operating systems.

operating system three pieces pdf

operating System: 下拉项选择 Linux - Generic和Ubuntu-linux区别

4. What is an operating system? List at least three functions of an operating system.

计算机操作系统经典的入门书籍

ipv6 link local address

4. What is an operating system? List at least three functions of an operating system

怎样显示python代码的运行环境

operating systems principles and practice

4.What is an operating system? List at least three functions of an operating system. (20 points)

最新资源