CS330 · Chapter 9 · Annotated SlidesVirtual Memory
Original
Overview

Virtual Memory

Virtual memory larger than physical memory, demand paging and the valid–invalid bit, page faults and their handling, demand-paging performance, page replacement (FIFO and Belady’s anomaly, optimal, LRU) and thrashing.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 30 slides
  1. 1 Slide 1
  2. 2 Outline of this lecture
  3. 3 Recall from previous chapter
  4. 4 Background
  5. 5 Virtual Memory That is Larger Than Physical Memory
  6. 6 Demand paging
  7. 7 Demand Paging
  8. 8 Transfer of a Paged Memory to Contiguous Disk Space
  9. 9 Valid-Invalid Bit
  10. 10 Page Table When Some Pages Are Not in MM
  11. 11 Page Fault
  12. 12 Steps in Handling a Page Fault
  13. 13 What happens if there is no free frame?
  14. 14 Performance of Demand Paging
  15. 15 Demand Paging Example
  16. 16 Basic Page Replacement
  17. 17 Need For Page Replacement
  18. 18 Basic Page Replacement (cont.)
  19. 19 Page Replacement
  20. 20 Page-Replacement Algorithms
  21. 21 Graph of Page Faults Versus The Number of Frames
  22. 22 First-In-First-Out (FIFO) Algorithm
  23. 23 FIFO Page Replacement
  24. 24 FIFO Illustrating Belady s Anomaly ’
  25. 25 Optimal Algorithm
  26. 26 Optimal Page Replacement
  27. 27 Least Recently Used (LRU) Algorithm
  28. 28 LRU Page Replacement
  29. 29 Thrashing
  30. 30 Thrashing
Slide 1 / 30

Slide 1

Slide 1: Slide 1
Slide 2 / 30

Outline of this lecture

Slide 2: Outline of this lecture
Slide 3 / 30

Recall from previous chapter

Slide 3: Recall from previous chapter
Slide 4 / 30

Background

Slide 4: Background
Slide 5 / 30

Virtual Memory That is Larger Than Physical Memory

Slide 5: Virtual Memory That is Larger Than Physical Memory
Slide 6 / 30

Demand paging

Slide 6: Demand paging
Slide 7 / 30

Demand Paging

Slide 7: Demand Paging
Slide 8 / 30

Transfer of a Paged Memory to Contiguous Disk Space

Slide 8: Transfer of a Paged Memory to Contiguous Disk Space
Slide 9 / 30

Valid-Invalid Bit

Slide 9: Valid-Invalid Bit
Slide 10 / 30

Page Table When Some Pages Are Not in MM

Slide 10: Page Table When Some Pages Are Not in MM
Slide 11 / 30

Page Fault

Slide 11: Page Fault
Slide 12 / 30

Steps in Handling a Page Fault

Slide 12: Steps in Handling a Page Fault

Notes

  1. Handling: trap → check the reference → find a free frame → read the page from disk → update the table, set v → restart the instruction.

Exam angle

PredictionQ1

After the page is loaded, the OS:

Slide 13 / 30

What happens if there is no free frame?

Slide 13: What happens if there is no free frame?
Slide 14 / 30

Performance of Demand Paging

Slide 14: Performance of Demand Paging

Notes

  1. EAT = (1 − p)·memory access + p·page-fault time. Even a tiny p hurts because a fault costs milliseconds.

Exam angle

PredictionQ1

Memory 200 ns, fault service 8 ms, p = 0.001. EAT ≈

Slide 15 / 30

Demand Paging Example

Slide 15: Demand Paging Example
Slide 16 / 30

Basic Page Replacement

Slide 16: Basic Page Replacement

Notes

  1. Page replacement: if no free frame, pick a victim; use a dirty (modify) bit so only modified pages are written back.

Slide 17 / 30

Need For Page Replacement

Slide 17: Need For Page Replacement
Slide 18 / 30

Basic Page Replacement (cont.)

Slide 18: Basic Page Replacement (cont.)
Slide 19 / 30

Page Replacement

Slide 19: Page Replacement
Slide 20 / 30

Page-Replacement Algorithms

Slide 20: Page-Replacement Algorithms

Notes

  1. Tip Practice string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with 3 frames → FIFO 15 faults, OPT 9, LRU 12.

Slide 21 / 30

Graph of Page Faults Versus The Number of Frames

Slide 21: Graph of Page Faults Versus The Number of Frames
Slide 22 / 30

First-In-First-Out (FIFO) Algorithm

Slide 22: First-In-First-Out (FIFO) Algorithm
Slide 23 / 30

FIFO Page Replacement

Slide 23: FIFO Page Replacement
Slide 24 / 30

FIFO Illustrating Belady s Anomaly ’

Slide 24: FIFO Illustrating Belady s Anomaly ’

Notes

  1. Belady’s anomaly: with FIFO, MORE frames can cause MORE page faults.

Exam angle

PredictionQ1

Belady’s anomaly occurs with:

Slide 25 / 30

Optimal Algorithm

Slide 25: Optimal Algorithm

Notes

  1. Optimal (OPT/MIN): replace the page not used for the longest time in the future. Lowest fault rate but needs the future: used as a benchmark.

Exam angle

PredictionQ1

The optimal page-replacement algorithm can be implemented in a real OS.

Slide 26 / 30

Optimal Page Replacement

Slide 26: Optimal Page Replacement
Slide 27 / 30

Least Recently Used (LRU) Algorithm

Slide 27: Least Recently Used (LRU) Algorithm

Notes

  1. LRU: replace the page not used for the longest time in the past. Implemented with counters or a stack; no Belady’s anomaly.

Exam angle

PredictionQ1

Reference string 1 2 3 4 1 2 5 1 2 3 4 5 with 3 frames. Count FIFO page faults.

Compare with the model answer

9 faults (and 10 with 4 frames: Belady’s anomaly).

Slide 28 / 30

LRU Page Replacement

Slide 28: LRU Page Replacement
Slide 29 / 30

Thrashing

Slide 29: Thrashing

Notes

  1. Thrashing: the process spends more time paging than executing because it has too few frames; CPU utilization drops.

Exam angle

PredictionQ1

Thrashing is when a process:

Slide 30 / 30

Thrashing

Slide 30: Thrashing