Virtual Memory Concepts

In 1968, programmers at MIT developed the first commercial time-sharing system on a machine with 256 KB of memory—yet each user's program could address far more memory than physically existed. This seeming paradox wasn't magic; it was the birth of virtual memory's most transformative capability: allowing programs to use more memory than the machine physically contains.

Today, this capability is so fundamental that we take it for granted. Your laptop with 16 GB of RAM routinely runs applications whose combined memory demands exceed 100 GB. Video editing software opens 8K footage files larger than physical memory. Databases hold indexes that dwarf available RAM. Scientific simulations work with datasets measured in terabytes.

How is this possible? How can software use memory that doesn't exist? This page answers that question, exploring the mechanisms that break the physical memory barrier and the profound implications for system design.

At first glance, using more memory than exists seems impossible. Where can data go if there's no physical storage for it? The apparent contradiction dissolves when we realize that not all data needs to be in physical memory simultaneously.

The key insight: Locality of Reference

Programs don't access all their data uniformly. At any given moment, they're focused on a small subset of their total address space—the working set. This behavior, called locality of reference, has two forms:

• Temporal locality — Recently accessed locations are likely to be accessed again soon
• Spatial locality — Locations near recently accessed ones are likely to be accessed soon

Because of locality, we only need the currently active portions of a program in physical memory. Everything else can wait on disk until it's needed.

The enabling abstraction:

Virtual memory exploits locality by creating a two-level memory hierarchy:

1. Primary level (Physical RAM) — Fast but limited; holds the working set
2. Secondary level (Disk/SSD) — Slow but vast; holds everything else

The operating system automatically migrates data between these levels, keeping hot data in RAM and cold data on disk. From the program's perspective, it appears to have unlimited fast memory—the abstraction hides the underlying reality.

The mechanism that enables virtual address spaces larger than physical memory involves several cooperating components working together.

The core concept: Partial Residency

At any moment, only a fraction of a process's virtual pages are 'resident' in physical memory. The rest exist only in the backing store (swap space on disk). When a process accesses a non-resident page, a page fault occurs, triggering the OS to load the page from disk.

Step-by-step mechanism:

Let's examine the quantitative aspects of having virtual address spaces exceed physical memory. Understanding these numbers helps in system sizing and performance tuning.

Virtual address space vs. allocated memory vs. resident memory:

Three different measurements describe a process's memory usage:

Over-commitment ratios:

Systems routinely over-commit memory—promising more virtual memory than physical memory exists:

Over-commitment Ratio = Total Virtual Memory Promised / Physical RAM Available

Example:
  - 50 processes, each with 8 GB virtual space = 400 GB
  - Physical RAM = 32 GB
  - Over-commitment ratio = 400 / 32 = 12.5x

This works because:

1. Processes don't use their entire virtual space
2. Shared libraries are counted once physically but appear in each process's virtual space
3. Locality means most pages aren't needed simultaneously
4. Memory-mapped files can be re-read from their original file (not swap)

The OOM (Out of Memory) risk:

Over-commitment has a failure mode: if processes collectively try to use more memory than RAM + swap, the system runs out. This triggers the OOM Killer on Linux, which terminates processes to free memory—a traumatic but necessary response to over-commitment failure.

The backing store is the secondary storage that holds pages not currently in physical memory. Without it, virtual memory larger than physical memory would be impossible.

Types of backing store:

Swap space design:

Swap space is dedicated storage for pages that have no other backing file (anonymous pages). Design considerations include:

1. Swap partition vs. swap file:

• Partition: Slightly faster, dedicated space, harder to resize
• File: Flexible size, can be added/removed dynamically, slight overhead

2. Sizing guidance:

• Historical rule: swap = 2× RAM (from memory-scarce era)
• Modern practice: swap = RAM or less for desktops; depends on workload for servers
• Hibernation: swap ≥ RAM (to store entire memory image)

3. SSD considerations:

• SSDs make swap much faster (~100× vs HDD)
• Write wear is a concern for heavy swapping
• Many modern systems rely more on memory compression than swap

Demand paging is the mechanism that enables virtual spaces larger than physical memory. Instead of loading an entire program into memory at startup, the OS loads pages only when they're accessed—'on demand.'

Why demand paging is essential:

Without demand paging, a program would need all its pages loaded before execution. Consider:

• A modern browser binary: 200+ MB
• Linked libraries: 500+ MB
• Data files: potentially GB
• Total: Would require gigabytes of free RAM before starting

With demand paging:

• Process starts with almost no pages loaded (or just a few critical ones)
• Execution begins immediately
• Pages are faulted in as accessed
• Many pages may never be loaded (unused features, error handlers)

The page fault as the loading trigger:

When a program references a page not yet loaded:

1. The page table entry has Present=0 (not in RAM)
2. CPU raises a page fault exception
3. OS page fault handler determines the page should be loaded (vs. a genuine error)
4. OS reads the page from its backing store into a physical frame
5. Page table is updated with the frame number and Present=1
6. Faulting instruction is restarted

This is invisible to the program. The load instruction sees a brief delay, then gets its data. The program doesn't explicitly request page loading—it just uses addresses, and the system provides the data.

Having virtual address spaces exceed physical memory isn't just a trick—it fundamentally changes what's possible in computing. Let's enumerate the benefits:

The economic argument:

Virtual memory larger than physical has significant economic implications:

Virtual memory finds the sweet spot: it enables capabilities that would otherwise require expensive hardware, accepting occasional slowdowns when working sets exceed RAM.

The software architecture impact:

Programmers can design software as if memory were unlimited:

• Databases can index huge datasets in 'memory' (actually virtual memory)
• Applications can memory-map large files for convenient access
• Scientific software can work with datasets larger than any machine's RAM
• Caches can be sized generously without counting every byte

The ability to exceed physical memory isn't free—it comes with significant tradeoffs that system designers and performance engineers must understand.

The fundamental tradeoff: Space vs. Time

When virtual > physical fails:

Thrashing — When the working set exceeds physical memory, the system spends most of its time swapping pages in and out rather than doing useful work. CPU utilization drops even as the system is 100% busy doing I/O.

OOM conditions — If swap space is exhausted and memory is still needed, the OS must kill processes. This is non-deterministic and can kill the wrong process.

Latency-sensitive workloads — Real-time systems, low-latency trading, interactive applications—page faults introduce unacceptable jitter.

Why locality can fail:

• Random access patterns (graph traversal, hash table with random keys)
• Working set grows suddenly (batch job processing large dataset)
• Many concurrent processes with overlapping working sets
• Memory pressure from other processes

The idea that virtual memory could exceed physical memory was not obvious—it was a breakthrough that took decades to develop and refine.

Timeline of virtual memory development:

The Atlas computer's insight:

The Atlas computer at the University of Manchester first demonstrated that programmers could use more addresses than fit in physical memory. The key insight of Tom Kilburn and colleagues was that the working set principle made this practical—most programs exhibited locality, making demand paging viable.

Resistance to virtual memory:

Not everyone was convinced. Some concerns were valid, others less so:

• 'Too slow' — Early systems with drum storage were indeed slow; SSDs changed this
• 'Too complex' — Hardware support and OS complexity; now routine
• 'Wastes memory' — Page tables consume memory; hierarchical tables addressed this
• 'Unpredictable performance' — Real concern for real-time systems; mitigated with page locking

Despite early skepticism, virtual memory won because the programmer productivity gains outweighed the complexity and occasional performance variability.

The ability for virtual address spaces to exceed physical memory is one of computing's most significant abstractions. We've explored how this works and why it matters:

What's next:

We've seen that virtual memory can exceed physical memory through demand paging. The next page examines the demand paging mechanism in detail—how pages are brought in lazily, what happens during page faults, and the distinction between demand paging and demand segmentation.