Operating System Concepts Chapter 10 — Virtual Memory Explained

// the one-minute version

Virtual memory lets a process run with only part of it in RAM. Pages load on demand — only when touched — and a miss triggers a page fault that fetches the page from disk. When RAM is full, a replacement algorithm (ideally LRU) picks a victim to evict. Push it too far and the system thrashes: it spends all its time swapping pages instead of working. The working-set model is the defense.

Your machine runs programs that together need more memory than it physically has, and it works. The trick is a beautiful lie: give each process a huge address space, but keep only the pages it's actually using in RAM, parking the rest on disk. The program never knows.

01 Demand paging

Instead of loading a whole program at launch, demand paging loads each page only when first touched. Most programs use only a fraction of their code and data at any moment, so this saves enormous memory and makes startup fast. Pages not yet needed stay on disk; some may never be loaded at all.

02 The page fault

Each page-table entry has a valid bit saying whether the page is in RAM. Touch a page that isn't, and the MMU raises a page fault — a trap to the OS. The OS finds a free frame (or evicts one), reads the page from disk into it, updates the page table, and restarts the faulting instruction. To the program, nothing happened except a pause.

Fig 1 — Servicing a page fault. A disk read is ~100,000× slower than RAM, so faults must be rare for the illusion to feel fast.

watch outA page fault is cheap to handle but brutally slow — a disk fetch is tens of thousands of times slower than a RAM access. The whole scheme only works because faults are rare. A workload that faults constantly performs terribly even though nothing is broken. This is why the effective access time is dominated by the fault rate: even a 1-in-1000 fault rate can multiply average access time many-fold.

03 Copy-on-write: making fork cheap

Virtual memory enables a neat trick. When a process forks (Chapter 3), copying its entire address space would be wasteful — the child often immediately execs a new program anyway. Copy-on-write instead lets parent and child share the same physical frames, marked read-only. Only when one of them writes a shared page does the OS copy that single page. Fork becomes nearly free.

04 Page replacement

When a fault hits and RAM is full, the OS must evict an existing page. Which one? Evict a page about to be used again and you just create another fault.

FIFO

Evict the oldest-loaded page. Simple, but dumb — it can toss a heavily-used page just because it arrived early. Can even suffer Belady's anomaly.

Optimal (OPT)

Evict the page not used for the longest time in future. Provably best — but it requires knowing the future, so it's only a benchmark.

LRU — least recently used

Evict the page unused longest, betting the recent past predicts the near future. Close to optimal in practice; approximated cheaply with reference bits.

Second-chance / clock

A practical LRU approximation: scan pages in a circle, giving a referenced page a "second chance" before evicting. What real kernels actually use.

the catchFIFO has a bizarre flaw called Belady's anomaly: giving it more frames can sometimes cause more page faults — the opposite of what you'd expect. Stack-based algorithms like LRU and OPT never suffer it. It's a favorite exam "gotcha" precisely because it's so counterintuitive.

noteLRU is the practical sweet spot. True LRU is costly to track exactly (you'd timestamp every access), so hardware/OS use approximations — a reference bit set on each access and periodically cleared — that capture most of the benefit cheaply. The clock algorithm is the classic implementation.

05 How many frames per process?

The OS must split frames among processes. Too few frames for a process and it faults constantly; too many and other processes suffer. Allocation can be equal, proportional to process size, or priority-weighted. This decision feeds directly into the worst failure mode in the chapter.

06 Thrashing

If a process lacks enough frames to hold the pages it actively needs, it faults on almost every access, evicting pages it's about to need again. This is thrashing: the CPU sits nearly idle while the disk runs flat-out swapping. Throughput collapses. Counterintuitively, the fix is often to run fewer processes so each gets enough frames.

think of it likeThrashing is a tiny desk with a huge filing cabinet. If the desk holds two folders but your task needs five, you spend all day swapping folders and get no work done. Give the desk more room (frames) or work on fewer tasks at once.

07 The working-set model

The defense is the working set: the pages a process has used recently — roughly, what it actually needs now. If the OS keeps each active process's working set in RAM, faults stay rare. If combined working sets exceed RAM, the OS should reduce the degree of multiprogramming (suspend a process) rather than let everyone thrash. Page-fault frequency is a practical signal: too high → give the process more frames; too low → it can spare some.

common catches & gotchas

Page fault ≠ error — A page fault is normal, expected, and silently handled — not a crash. The name misleads beginners.
Belady's anomaly — More frames can mean more faults under FIFO. LRU/OPT are immune. Classic trick question.
OPT is unimplementable — It needs the future. It exists only to measure how close real algorithms get — never as something you can run.
Thrashing fix is counterintuitive — When the system thrashes, running fewer processes (so each has enough frames) speeds everything up. Adding more makes it worse.
Effective access time is fault-dominated — Because a disk fetch is ~100,000× a RAM access, even a tiny fault rate dominates average memory latency. Faults must be rare.

08 Questions students actually ask

What is demand paging?

Loading each page into RAM only when the program first accesses it, rather than loading the whole program up front. Since programs use only part of their memory at a time, this saves RAM and speeds startup.

What happens on a page fault?

The MMU traps to the OS because the page isn't in RAM. The OS reads it from disk into a frame (evicting one if needed), updates the page table, and restarts the faulting instruction. The program just experiences a pause.

Why can't we use the optimal replacement algorithm?

It requires knowing which page will be used furthest in the future — knowledge we don't have. It's used only as a benchmark; LRU approximates it using recent history.

What is Belady's anomaly?

A counterintuitive effect where giving FIFO more frames can increase page faults. Stack algorithms like LRU and OPT never exhibit it.

What causes thrashing and how do you stop it?

Too little RAM per process, so it constantly faults on pages it just evicted. Fix it by giving processes more frames or, often, running fewer processes so each one's working set fits in memory.

09 Key takeaways

Virtual memory runs programs with only part of them in RAM; the rest waits on disk.
Demand paging loads pages only when first touched; copy-on-write makes fork cheap.
A page fault fetches a missing page from disk — correct but very slow, so faults must be rare.
Replacement: FIFO (can hit Belady's anomaly), OPT (ideal but impossible), LRU/clock (practical).
Thrashing = constant faulting; the CPU idles while the disk thrashes — fix by running fewer processes.
The working-set model and page-fault frequency keep active pages resident.

10 Wrapping up

Virtual memory is the OS's most impressive illusion — more memory than exists, conjured with paging and a disk. Which raises the question of what that disk actually is and how the OS drives it. The storage half of the book begins now. Next up: Mass-Storage Structure.

Operating System Concepts Chapter 10 — Virtual Memory.