Skip to main content

Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 21, Arpaci-Dusseau & Arpaci-Dusseau

Beyond Physical Memory: Mechanisms

So far every address space fit in RAM. Real systems support many large address spaces at once. That needs another level in the memory hierarchy: a big, slower device (disk or SSD) to hold pages that are not in demand.

Crux: how use a larger, slower device to transparently give the illusion of a huge virtual address space?

Convenience: allocate without worrying whether RAM is full. Multiprogramming also needs this — early machines could not hold every process’s pages at once.

Swap space​

Reserve disk for moving pages: swap space. The OS reads/writes it in page-sized units and remembers each page’s disk address. Capacity of swap bounds how much “memory” the system can pretend to have.

Fig 21.1 toy: 4 physical frames, 8 swap blocks. Several processes share RAM; some valid pages live only on disk; one process may be fully swapped out.

Code pages can also be re-fetched from the file system binary (not only swap) if the OS evicts them.

The present bit​

On a reference: TLB first. On miss, walk the PTE.

Add a present bit:

  • 1 — page in physical memory; PFN usable
  • 0 — not in memory (on disk); access is a page fault

“Fault” is a bit of a misnomer for a legal but not-present page — historically the same trap path as illegal accesses.

The page-fault handler​

Almost always software (even with a hardware-managed TLB). Reasons: disk I/O is slow (OS overhead is noise), and hardware would need to understand swap and I/O.

Rough flow when present=0:

  1. Read disk address from the PTE (bits that otherwise hold the PFN)
  2. Find a free frame (or evict — next chapter’s policy)
  3. DiskRead into that frame (process blocked; other jobs run)
  4. Set present=1, store PFN, retry the instruction (may TLB-miss then hit)
Quiz

Rank the sequence

1 / 1

Order the steps the page-fault handler takes when present=0 (top = first).

OrderDrag the handle to rearrange — top should be first.

  1. 1DiskRead the page into the frame while the process is blocked
  2. 2Find a free frame, evicting a page if necessary
  3. 3Set present=1, store the PFN, and retry the faulting instruction
  4. 4Read the disk address out of the PTE

Drag items into the correct order (or use ↑↓), then check.

Control flow (hardware sketch)​

On TLB miss, three important cases:

CaseMeaning
Valid + presentFill TLB, retry
Valid + not presentPAGE_FAULT → OS handler
InvalidSEGMENTATION_FAULT (bug) → usually kill

When memory is full​

Evicting to free a frame is the page-replacement policy (next lesson). Wrong victims → disk-speed execution.

Watermarks and the page daemon​

Do not wait until free=0. Keep a cushion with low watermark (LW) and high watermark (HW):

  • Free < LW → wake page daemon / swap daemon
  • Evict until free ≥ HW → sleep

Batching enables clustering writes to swap (better disk efficiency) [LL82].

Do work in the background

Background reclaim (and buffered writes) groups I/O, improves latency, and uses idle time [G+95].

Interactive​

Try: swap layout · page-fault path · LW/HW daemon.

Check your understanding​

Quiz

Beyond physical memory — mechanisms

1 / 6

Swap space is primarily…

Pick an answer to see if you are right.

Coding challenges​

Homework lab: vmstat / mem.c​

OSTEP’s measurement homework uses mem.c and vmstat on a real Linux machine (not the in-browser sandbox).

Lab

Homework: vmstat and mem.c

0/5 started

Loading lab…

Summary​

PieceRole
Swap spaceDisk backing for pages
Present bitIn RAM vs on disk
Page faultOS brings page in (maybe after eviction)
LW / HW + daemonProactive reclaim + clustered I/O

Transparency: the process still sees a private contiguous VA; behind the scenes pages move between RAM and disk.

Previous: Smaller Page Tables

Next: Beyond Physical Memory — Policies — which page to evict (OPT, FIFO, LRU, Clock).

Further Reading​