Unit 9: Virtual Memory

01 Unit learning outcomes

Upon completion of this unit you will be able to

U9.1 — Apply paging as an allocation scheme.
U9.2 — Analyse page-table structures.
U9.3 — Explain the role and operation of the TLB.
U9.4 — Explain demand paging and its performance implications.
U9.5 — Trace page-fault handling.
U9.6 — Compare page-replacement algorithms.
U9.7 — Diagnose and mitigate thrashing.

This unit addresses course learning outcomes CLO4 and CLO8. It closes Module 3.

02 Lessons in this unit

Lessons 9.1–9.3 build the translation machinery. Lessons 9.4–9.5 introduce demand paging and page faults. Lesson 9.6 surveys replacement algorithms and Lesson 9.7 examines the pathological case.

Lesson 9.1

Paging

Fixed-size pages and frames, the elimination of external fragmentation, and the cost of the last page.

Lesson 9.2

Page Tables

Single-level, multi-level, inverted, and hashed page tables — and the space-time trade-offs each makes.

Lesson 9.3

Translation Lookaside Buffer

The hardware cache of recent translations, its hit ratio, and its impact on effective access time.

Lesson 9.4

Demand Paging

Loading pages only when they are referenced, the lazy swapper, and the dramatic reduction in memory footprint.

Lesson 9.5

Page Faults

The full sequence of a page fault, from the trap through disk I/O to the resumed instruction.

Lesson 9.6

Page Replacement

FIFO, optimal, LRU, clock, and their approximations — and the anomalies each can produce.

Lesson 9.7

Thrashing

When the working set exceeds physical memory, why performance collapses, and how to prevent it.

03 What you will learn, lesson by lesson

9.1 Paging

Define pages and frames.
Translate virtual to physical.
Eliminate external fragmentation.
Analyse internal fragmentation.
Evaluate page-size trade-offs.

9.2 Page Tables

Describe single-level page tables.
Explain multi-level page tables.
Describe inverted page tables.
Analyse memory overhead.
Compare structures.

9.3 TLB

Explain TLB purpose.
Describe TLB operation.
Analyse hit ratio.
Compute effective access time.
Explain TLB flushing and ASIDs.

9.4 Demand Paging

Define demand paging.
Explain the lazy swapper.
Describe initial page-table state.
Analyse memory savings.
Evaluate startup costs.

9.5 Page Faults

Define a page fault.
Trace fault handling.
Explain restart of the instruction.
Analyse fault cost.
Distinguish valid from invalid faults.

9.6 Page Replacement

Apply FIFO.
Apply optimal replacement.
Apply LRU.
Describe clock approximation.
Analyse Belady's anomaly.

9.7 Thrashing

Define thrashing.
Explain the cause.
Apply working-set model.
Apply page-fault-frequency control.
Evaluate mitigation strategies.

04 Worked example

A page-replacement trace comparing FIFO, LRU, and optimal on the same reference string. This is the standard way to build intuition before Lesson 9.6 formalises the algorithms.

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3

Assume three page frames, initially empty.

FIFO — evict the oldest page:

7 → [7, -, -]  fault
0 → [7, 0, -]  fault
1 → [7, 0, 1]  fault
2 → [2, 0, 1]  fault (evict 7)
0 → hit
3 → [2, 3, 1]  fault (evict 0)
0 → [2, 3, 0]  fault (evict 1)
4 → [4, 3, 0]  fault (evict 2)
2 → [4, 2, 0]  fault (evict 3)
3 → [4, 2, 3]  fault (evict 0)
0 → [0, 2, 3]  fault (evict 4)
3 → hit
Total faults: 10

LRU — evict the least recently used page:

7 → [7, -, -]  fault
0 → [7, 0, -]  fault
1 → [7, 0, 1]  fault
2 → [2, 0, 1]  fault (evict 7; least recently used)
0 → hit
3 → [2, 0, 3]  fault (evict 1)
0 → hit
4 → [2, 0, 4]  fault (evict 3)
2 → hit
3 → [2, 3, 4]  fault (evict 0)
0 → [2, 3, 0]  fault (evict 4)
3 → hit
Total faults: 8

Optimal — evict the page not needed for the longest time:

7 → [7, -, -]  fault
0 → [7, 0, -]  fault
1 → [7, 0, 1]  fault
2 → [2, 0, 1]  fault (evict 7; next use far away)
0 → hit
3 → [2, 0, 3]  fault (evict 1; never used again)
0 → hit
4 → [2, 0, 4]  fault (evict 3; never used again)
2 → hit
3 → [2, 3, 4]  fault (evict 0? or 4? next uses are 0 at position 11, 4 never)
0 → [2, 3, 0]  fault (evict 4)
3 → hit
Total faults: 7

Optimal achieves the theoretical minimum of 7 faults, LRU comes close at 8, and FIFO is worst at 10. The pattern is typical: optimal is unachievable in practice (it requires future knowledge), LRU is a good approximation but expensive to implement exactly, and FIFO is cheap but can be pathological.

05 Required reading

Operating System Concepts — Chapter 10, Virtual Memory, in full. The primary reference for this unit.
OSTEP — Chapters 18–22 (paging, TLBs, and policy). OSTEP's treatment is more modern and includes material on the working-set model that complements the classical text.
Linux kernel documentation: Documentation/vm/, especially the discussion of page reclaim and the reverse mapping that makes page replacement tractable in practice.

Read OSTEP alongside Silberschatz

The classical text presents the algorithms; OSTEP explains why real systems cannot use the textbook versions and what they do instead. The two together give you both the theory and the engineering.

06 Unit discussion

Discussion prompt

Optimal page replacement is provably the best possible — it achieves the minimum number of faults for any given reference string. Yet no real system uses it, because it requires future knowledge.

But some workloads do have predictable access patterns. A streaming video decoder reads its file sequentially. A compiler's access pattern is a deterministic function of the input program. Pick one such workload and argue whether a domain-specific replacement policy could outperform the general-purpose LRU approximation. What would such a policy need to know, and could the OS realistically learn it?

Post your response to the Unit 9 discussion forum and reply to at least two classmates. Supports CLO4 and CLO7.

07 Laboratory connection

Lab 8 — Virtual Memory is completed at the end of this unit. It asks you to implement the page-replacement algorithms, measure their fault rates on the same reference string, and observe the effect of the working set on thrashing. This lab supplies the reference code for the Virtual Memory Simulator option in Assignment 2.

Lab 8 coverage
Lesson	Lab 8 exercise
9.1 Paging	Compute page offsets and frame numbers from example addresses
9.2 Page Tables	Walk a two-level page table by hand for a sample address
9.3 TLB	Compute effective access time for various hit ratios
9.4–9.5 Demand Paging	Trace a page fault from user access to resumption
9.6 Replacement	Implement FIFO, LRU, optimal; compare fault counts
9.7 Thrashing	Simulate the working-set model and observe the cliff

08 Knowledge check & quiz

Quick check before you begin

Question 1

Why does paging eliminate external fragmentation, and what price does it pay?

Show answer

Paging divides memory into fixed-size pages (in the address space) and frames (in physical memory). Any page can occupy any frame, so there is never a hole too small to use — every free frame is exactly the right size for the next page. External fragmentation disappears. The price is internal fragmentation: the last page of a process is typically only partially used, and the unused portion is wasted. On average, that waste is half a page per process, which is small when pages are small (4 KB typical) but large when pages are large (2 MB huge pages).

Question 2

What is the purpose of the TLB, and why is it necessary?

Show answer

The TLB (translation lookaside buffer) is a small, fast hardware cache of recent virtual-to-physical translations. Without it, every memory access would require one or more additional memory accesses to walk the page table — a significant slowdown. Because programs have strong locality of reference, a small TLB typically achieves a hit ratio of 99% or better, which brings the average translation cost down to a few percent of the access time.

Question 3

What is thrashing and what causes it?

Show answer

Thrashing is the pathological state in which the system spends more time paging than executing useful work. It occurs when the sum of the working sets of all active processes exceeds physical memory. Every time a process gets scheduled, it faults on a page it needs; to bring it in, the kernel evicts a page that another process needs; when that process runs, it faults immediately. The system oscillates between the disk and RAM with almost no useful work being done. The fix is to reduce the degree of multiprogramming — suspend some processes — so that the remaining working sets fit in physical memory.

After completing all seven lessons, take the Unit 9 quiz in the LMS. It covers paging, page tables, the TLB, demand paging, page faults, replacement algorithms, and thrashing.