← tonia.ai
Computer Architecture

Memory that isn't there

How virtual memory gives every program a private, seemingly endless address space; how the system decides which pages to keep in physical memory; and what all of this costs in performance. Three tools let you walk a page table, compare page replacement algorithms, and see what page faults do to memory access time.

Part A

Principles of virtual memory

Why virtual memory

Every program runs as if it had a large, private memory starting at address zero. In reality, its code and data are scattered across physical memory in fixed-size pieces, some of them still on disk. The hardware translates each virtual address the program uses into a physical address in DRAM, using tables the operating system maintains.

The idea first appeared in the Manchester Atlas computer in 1962 as a "one-level store" that made a small core memory and a large drum look like a single memory. Today every general-purpose processor supports it.

AdvantageHow virtual memory provides it
Isolation and protectionEach process has its own page table, so it cannot even name another process's memory. Permission bits block writes to code and execution of data.
Larger than physical memoryPages not in use can live on disk or SSD and are brought in only when touched (demand paging).
Simpler allocationA program's memory looks contiguous even when its physical frames are scattered, so there is no need to find one large free block.
SharingSeveral processes can map the same physical page, so one copy of a shared library serves everyone.
Fast process creationCopy-on-write lets a new process share its parent's pages until one of them writes.
Memory-mapped filesA file can be mapped into the address space and accessed with ordinary loads and stores.

Pages and page tables

Virtual memory is divided into fixed-size pages, typically 4 KB, and physical memory into frames of the same size. A virtual address splits into a virtual page number (VPN) and a page offset; translation replaces the VPN with a physical frame number and keeps the offset unchanged.

The mapping lives in a page table, one per process. Each page table entry (PTE) holds:

FieldPurpose
Present (valid) bitIs the page in physical memory? If not, an access causes a page fault.
Frame numberWhere the page lives in physical memory.
Permission bitsRead, write and execute rights; user or kernel only.
Accessed (reference) bitSet by hardware on any access. Replacement algorithms use it to estimate recent use.
Dirty bitSet by hardware on a write. A dirty page must be written back to storage before its frame is reused.

Older systems also used segmentation, dividing memory into variable-size segments such as code, data and stack. Variable sizes cause external fragmentation, so modern systems rely on paging; segmentation survives on x86 mainly for compatibility.

Translating an address

Virtual address Virtual page no. Offset Physical address Frame no. Offset offsetunchanged TLB hit: frame number in about a cycle miss Page table walk present: frame number, TLB refilled not present Page fault: the OS loads the page and retries

Multilevel page tables

A flat table covering a 48-bit address space with 4 KB pages would need 236 entries, 512 GB of table per process. Instead, x86-64 and RISC-V Sv48 use a four-level tree. Each level is one 4 KB page holding 512 eight-byte entries, indexed by 9 bits of the address. Regions a program never uses need no table pages at all. A five-level mode extends addresses to 57 bits for very large memories.

The cost is the page walk: on a TLB miss, hardware reads one entry per level, four memory accesses before the real one. Huge pages (2 MB or 1 GB) stop the walk one or two levels early and cover far more memory per TLB entry.

Page-walk calculator

Enter an x86-64 virtual address to see which entry each level of the page table uses.

4 memory reads on a TLB miss

Page faults

When a program touches a page whose present bit is clear, the hardware raises a page fault and the operating system takes over:

  1. Check. Confirm the address is legal for this process. If not, the program receives a segmentation fault.
  2. Find a frame. Take a free frame, or run the replacement algorithm to choose a victim page. If the victim is dirty, write it to storage first.
  3. Load. Read the needed page from storage into the frame. The process sleeps and another runs meanwhile.
  4. Update. Point the page table entry at the frame, set the present bit, and invalidate any stale TLB entry.
  5. Retry. Restart the faulting instruction, which now succeeds. This is why precise exceptions matter.

A minor fault needs no storage access, for example when the page is already in memory for another process or is being zero-filled on first use. A major fault must read from storage and costs thousands to millions of times more than a memory access.

Part B

Page replacement

Choosing a victim

When memory is full, every page fault forces the system to evict a page. A good choice evicts a page that will not be needed for a long time; a bad choice evicts one that is needed again immediately, causing another fault. Evicting a clean page is cheaper than a dirty one, which must be written back first.

Belady showed in 1966 that the optimal choice is the page whose next use is furthest in the future. Real systems cannot see the future, so they approximate it from the past, mostly by assuming that pages used recently will be used again soon.

Replacement algorithms

AlgorithmEvictsPerformanceCost to implement
OPT (Belady's MIN)The page used furthest in the futureFewest possible faultsImpossible in practice; used as a benchmark
FIFOThe page loaded longest agoPoor: may evict heavily used pages; suffers Belady's anomalyVery low: a queue
LRUThe page unused for the longest timeClose to OPT for most programs; bad for loops larger than memoryHigh: exact LRU must update an ordering on every memory access
Clock (second chance)The first page the clock hand finds with its reference bit clear, clearing bits as it passesClose to LRULow: one hardware reference bit per page
Enhanced clock / NRUPrefers pages that are both unreferenced and cleanAvoids costly write-backsLow: reference and dirty bits
WSClockClock restricted to pages outside the working set (Carr and Hennessy)Good under multiprogrammingLow
LFUThe least frequently used pageKeeps old pages that were once popularCounters per page
Adaptive (ARC, LRU-K, multi-generation LRU)Balance recency and frequency, adapting to the workloadResist scans and loops that defeat LRUModerate: extra lists or history

Exact LRU is too expensive for page replacement because it would need work on every memory access. Operating systems instead use the hardware's accessed bit. Linux, for example, keeps active and inactive lists and, since version 6.1, offers a multi-generation LRU that sorts pages into age groups.

Page replacement simulator

Enter a sequence of page numbers and the number of physical frames. Each row shows one algorithm: filled cells are hits, outlined cells are page faults. The chart shows how each algorithm's fault count changes with the number of frames.

OPTLRUFIFOClock

Things to try. The textbook string with 3 frames gives the classic result: OPT 9 faults, LRU 12, FIFO 15. "Loop larger than memory" makes LRU, FIFO and Clock fault on every reference with 3 frames, because each evicts exactly the page needed next, while OPT faults half as often. "Belady's anomaly" shows FIFO getting worse when a frame is added.

Belady's anomaly

Adding memory should never increase page faults, yet with FIFO it can. On the reference string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO causes 9 faults with 3 frames but 10 with 4. Belady, Nelson and Shedler reported the effect in 1969.

LRU and OPT cannot show the anomaly. They are stack algorithms (Mattson and colleagues): the set of pages kept with n frames is always a subset of the set kept with n + 1 frames, so more memory can only help. A useful side effect is that one pass over a reference trace gives the fault count for every memory size at once.

Working sets and thrashing

Denning defined a process's working set as the pages it referenced in its most recent window of execution, a measure of how much memory it needs right now. If the combined working sets of all running processes exceed physical memory, every process keeps faulting on pages another just evicted. The system spends its time moving pages instead of computing: this is thrashing.

Thrashing feeds on itself. As CPU utilization drops, a naive scheduler admits more processes to use the idle processor, which shrinks everyone's memory further. The remedies control the load rather than the replacement policy: keep each process's working set resident, monitor the page-fault frequency and give memory to processes faulting too often, and suspend or swap out whole processes when memory is overcommitted.

Part C

Virtual memory and system performance

Effective access time

EAT = (1 − p) × Memory access time + p × Page-fault service time

Here p is the probability that an access causes a page fault. With 100 ns memory and an 8 ms fault service time (a hard disk), one fault per 1,000 accesses gives EAT = 0.999 × 100 + 0.001 × 8,000,000 ≈ 8,100 ns: the machine runs about 80 times slower. Keeping the slowdown under 10% would require fewer than one fault per 800,000 accesses.

Faster storage changes the numbers but not the lesson. An SSD fault may take around 100 µs instead of 8 ms, yet it is still about a thousand times slower than a DRAM access. Virtual memory performs well only when the working set fits in physical memory and faults are rare.

Access time calculator

Combine TLB misses, page walks and page faults into one average access time.

Effective access time106ns
Slowdown vs. one memory access1.06× 

TLB lookup is assumed to take 1 ns, and each page-walk level costs one memory access with no page-walk caches. Real processors cache upper page-table levels and often find walk entries in the data caches, so walks are usually cheaper.

TLBs and huge pages

The translation lookaside buffer caches recent translations so most accesses skip the walk. Modern cores have small L1 TLBs and a shared L2 TLB of a few thousand entries, plus caches for upper page-table levels. TLB reach, entries × page size, is how much memory a program can touch without a TLB miss: 2,048 entries cover 8 MB with 4 KB pages but 4 GB with 2 MB pages.

Large-memory workloads such as databases, scientific codes and AI training often spend a significant share of their time on page walks. Remedies include huge pages, managed transparently by the operating system or requested explicitly; page-walk caches (Barr, Cox and Rixner); TLBs that coalesce neighboring translations (Pham and colleagues); and direct segments for very large regions (Basu and colleagues).

To overlap translation with the cache lookup, L1 caches are usually virtually indexed, physically tagged: the set index comes from the page offset, which translation leaves unchanged. This limits L1 size to page size × ways, which is why a 4 KB page and 12 ways give a 48 KB L1.

Hidden costs

CostWhere it comes fromMitigation
Context switchesA new process needs different translations, so TLB entries must be flushed or taggedAddress-space identifiers (ASIDs on Arm and RISC-V, PCIDs on x86) keep entries from several processes
Page-table memoryEvery process needs its own tables; huge address spaces need many table pagesMultilevel tables; huge pages
VirtualizationA guest's addresses are translated twice. A two-dimensional walk can need up to 24 memory references instead of 4Nested-paging caches (Bhargava and colleagues); huge pages in both guest and host
Security isolationAfter Meltdown, kernels separated kernel and user page tables, adding switches and TLB flushes on system callsHardware fixes in newer processors; PCIDs reduce flush cost
NUMAA page may sit in memory attached to another socket, making every access slowerAllocate on the node that uses the page; migrate pages that move
TLB shootdownsChanging a shared mapping requires interrupting every core that may cache itBatching changes; avoiding unnecessary unmaps

In practice

Measure before tuning: hardware counters report TLB misses and page faults directly, for example on Linux:

perf stat -e dTLB-load-misses,page-faults ./myprogram

Then:

  • Keep the working set in memory. Swapping to storage is a safety net, not extra capacity.
  • Use huge pages for large, long-lived data, through transparent huge pages or explicit allocation.
  • Touch memory in order and reuse it while it is hot. Locality helps the TLB just as it helps caches.
  • Pin latency-critical memory (mlock) so it can never be paged out.
  • On multi-socket machines, keep threads and their memory on the same node.
Go further

Resources

Interactive tools and references

Peer-reviewed reading

  • Kilburn, T., Edwards, D. B. G., Lanigan, M. J., & Sumner, F. H. (1962). One-level storage system. IRE Transactions on Electronic Computers, EC-11(2), 223–235.The Atlas computer, where virtual memory began.doi.org/10.1109/TEC.1962.5219356
  • Denning, P. J. (1970). Virtual memory. ACM Computing Surveys, 2(3), 153–189.The foundational survey of paging, segmentation and replacement.doi.org/10.1145/356571.356573
  • Belady, L. A. (1966). A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2), 78–101.The optimal policy and early comparisons.doi.org/10.1147/sj.52.0078
  • Belady, L. A., Nelson, R. A., & Shedler, G. S. (1969). An anomaly in space-time characteristics of certain programs running in a paging machine. Communications of the ACM, 12(6), 349–353.Belady's anomaly.doi.org/10.1145/363011.363155
  • Mattson, R. L., Gecsei, J., Slutz, D. R., & Traiger, I. L. (1970). Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2), 78–117.Stack algorithms, and why LRU and OPT cannot show the anomaly.doi.org/10.1147/sj.92.0078
  • Denning, P. J. (1968). The working set model for program behavior. Communications of the ACM, 11(5), 323–333.How much memory a program needs right now.doi.org/10.1145/363095.363141
  • Denning, P. J. (1968). Thrashing: Its causes and prevention. Proc. AFIPS Fall Joint Computer Conference, 915–922.Why overcommitted systems collapse, and how to prevent it.doi.org/10.1145/1476589.1476705
  • Carr, R. W., & Hennessy, J. L. (1981). WSCLOCK: A simple and effective algorithm for virtual memory management. Proc. ACM SOSP, 87–95.Combining the clock algorithm with working sets.doi.org/10.1145/800216.806596
  • O'Neil, E. J., O'Neil, P. E., & Weikum, G. (1993). The LRU-K page replacement algorithm for database disk buffering. Proc. ACM SIGMOD, 297–306.Using reference history beyond the most recent access.doi.org/10.1145/170035.170081
  • Megiddo, N., & Modha, D. S. (2004). Outperforming LRU with an adaptive replacement cache algorithm. IEEE Computer, 37(4), 58–65.ARC: balancing recency and frequency automatically.doi.org/10.1109/MC.2004.1297303
  • Jacob, B., & Mudge, T. (1998). Virtual memory in contemporary microprocessors. IEEE Micro, 18(4), 60–75.How different architectures implement translation in hardware.doi.org/10.1109/40.710872
  • Navarro, J., Iyer, S., Druschel, P., & Cox, A. (2002). Practical, transparent operating system support for superpages. ACM SIGOPS Operating Systems Review, 36(SI), 89–104 (Proc. OSDI).How an OS can use huge pages automatically.doi.org/10.1145/844128.844138
  • Bhargava, R., et al. (2008). Accelerating two-dimensional page walks for virtualized systems. Proc. ASPLOS XIII, 26–35.The cost of nested translation and how to cut it.doi.org/10.1145/1353534.1346286
  • Barr, T. W., Cox, A. L., & Rixner, S. (2010). Translation caching: Skip, don't walk (the page table). Proc. ISCA, 48–59.Page-walk caches that shorten TLB misses.doi.org/10.1145/1815961.1815970
  • Pham, B., et al. (2012). CoLT: Coalesced large-reach TLBs. Proc. MICRO-45, 258–269.Extending TLB reach without huge pages.doi.org/10.1109/MICRO.2012.32
  • Basu, A., et al. (2013). Efficient virtual memory for big memory servers. Proc. ISCA, 237–248.Direct segments for workloads that outgrow the TLB.doi.org/10.1145/2485922.2485943
  • Lipp, M., et al. (2020). Meltdown: Reading kernel memory from user space. Communications of the ACM, 63(6), 46–56.The attack that changed how kernels use page tables.doi.org/10.1145/3357033