A bigger room than the building has
In the last rung you learned how an OS lets many programs honestly share one bank of RAM: each process names memory with its own private addresses, and paging chops those addresses into fixed-size pages that map to equally-sized physical frames through a page table — a book's index from page number to frame. Crucially, paging already broke the rule that a process must sit in one continuous block: its pages can be scattered all over real memory, and nobody minds. That freedom is the door we now walk through. This rung asks a bolder question. What if a program's pages do not all have to be in RAM at the same time? What if some of them are not in RAM at all?
Here is the everyday observation that makes this possible. Open a 50-page document in an editor and you only look at one page at a time; load a giant game and at any instant you are standing in one room of its huge world. A program's full address space is often enormous, but the slice it is actually using right now is small. So why insist on hauling the whole thing into RAM before the first instruction runs? Virtual memory is the technique of running a process while keeping only the parts it currently needs in physical memory, parking the rest on disk. The promised payoff is the title's illusion: each program may believe in — and address — far more memory than the machine physically owns.
Two address spaces, only loosely connected
To make this work, we have to take the separation between logical and physical addresses — the load-bearing idea from the previous rung — and push it harder than ever. Until now you could half-imagine that every logical page quietly had some frame waiting for it. Drop that assumption. The logical address space is now a generous map of everything the program could ever name; the physical frames are a much smaller pool of real seats. A logical page might be sitting in a frame right now, or it might be out on disk, or it might never have been touched and so be backed by nothing at all yet. The map is large; the seats are few; and the connection between them is made and unmade on the fly.
Think of a vast theatre booking system. The seating chart printed in the brochure shows thousands of seat numbers — that is the logical address space, the same for every patron's brochure. But the actual theatre has only a few hundred real chairs (the frames). Most brochure seats correspond to no chair you are sitting in right now; they are just printed possibilities. The page table is the usher's clipboard that records, for each brochure seat you have actually claimed, which real chair you were put in — and, for the rest, a note saying 'not seated'. The brochure can promise a colossal hall; the building only ever holds what it holds.
The valid bit and bringing pages in on demand
How does the hardware know, on a given access, whether a logical page is currently seated in a frame or out on disk? Each page-table entry carries a small flag, the valid / invalid bit. When the bit reads valid, the entry holds a real frame number and the translation proceeds at full hardware speed. When it reads invalid, the entry is not (currently) backed by RAM: the page is on disk, or out of bounds, or simply never used yet. Crucially, this is the very same valid bit the previous rung used for protection — to mark addresses outside a process's allotment. Virtual memory reuses it for a second job: telling 'legal but not in RAM right now' apart from 'in RAM, go ahead'.
This unlocks the central technique: demand paging. Instead of loading every page up front, the OS starts the process with almost nothing in RAM and brings each page in lazily, only at the moment the program first reaches for it — exactly like a kitchen that fetches an ingredient from the cold store the instant a recipe step calls for it, never before. If a process never touches a page, that page is never loaded, and no time or RAM is spent on it. Carried to the extreme — starting a process with not a single page in memory and faulting every one in as it is first used — this is called pure demand paging.
Page table for one process (valid bit V):
logical page | V | where it is
-------------+---+--------------------------
0 | 1 | frame 17 (in RAM)
1 | 0 | on disk (not loaded yet)
2 | 1 | frame 04 (in RAM)
3 | 0 | never touched
... | |
CPU accesses logical page 1 -> valid bit = 0 -> trap! (a page fault)The page fault, and why the instruction must restart
What happens when the program reaches for a page whose valid bit is 0? The hardware cannot translate the address, so it does what hardware always does when it cannot proceed: it raises a trap into the kernel, much like the doorbell of an interrupt calling the building manager. This particular trap is a page fault. The name is misleading — it is not an error and nothing has gone wrong. It is simply the agreed signal that says 'this legal page is not in RAM; please go fetch it'. The full service sequence — find a free frame, read the page in from swap space on disk, fix up the page table, and resume — is the subject of the next two guides; here we just need the shape of it.
But there is a subtle, beautiful requirement hiding here, and it is worth pausing on because it shaped how processors are designed. When the fault happens, the offending instruction was caught mid-stride — it had already started, perhaps even half-modified a register, before discovering its page was missing. After the OS fetches the page, the program must continue as if nothing interrupted it. That demands the instruction restart property: the CPU must be able to re-execute the faulting instruction completely from scratch, with identical results, as though the first attempt never occurred. The OS rewinds the program counter to the faulting instruction and lets it run again — now that the page is present, it sails through.
Why even a rare fault hurts, and why it usually does not
Now the uncomfortable arithmetic. A memory access that hits a resident page takes maybe 100 nanoseconds. Servicing a page fault — trapping, finding a frame, reading from disk, restarting — can take several milliseconds, because it touches the disk. That is a factor of tens of thousands. So the average cost of an access, the effective access time, is dominated by the rare expensive case. If p is the page-fault rate (the fraction of accesses that fault) and a fault costs about 8 milliseconds while a hit costs 100 ns, the effective time is roughly (1 - p) times 100 ns plus p times 8 ms. The unsettling part is how tiny a p it takes to wreck things.
Put numbers in. Let p be just 1 in 1000, a fault on one access in a thousand. Then the effective time is about 0.999 times 100 ns plus 0.001 times 8,000,000 ns, which is roughly 100 ns + 8000 ns = about 8100 ns. We wanted 100 ns; we got 8100. One fault in a thousand made memory about eighty times slower. To keep the slowdown under, say, ten percent, the fault rate has to fall below roughly one in 400,000. The honest conclusion is stark: demand paging only works if page faults are extraordinarily rare. So why is it not a catastrophe in practice?
The rescue is a deep empirical fact about how real programs behave: locality of reference. Programs do not scatter their accesses uniformly across their whole address space; they cluster. A loop reruns the same handful of instructions thousands of times (temporal locality), and an array walk touches neighbours one after another (spatial locality). So at any moment a program is really only using a small, slowly-drifting set of pages — its working set. Keep that modest set in RAM and almost every access hits; faults become rare exactly because real code is repetitive and neighbourly. Locality is the empirical gift that turns the terrifying arithmetic above into a daily non-event — and the working set, plus copy-on-write and memory-mapped files, is where the rest of this rung goes next.
Two gifts the illusion makes cheap
Once you accept that a logical page need not have its own private frame, two lovely tricks fall out almost for free, and they round off this opening guide. The first is copy-on-write. Recall that fork makes a child process that is a near-perfect duplicate of its parent. Copying every page of the parent's memory would be wasteful, especially when the child often calls exec moments later and throws it all away. So instead the OS lets parent and child share the same physical frames, marked read-only, and only when one of them actually writes to a page does it quietly make a private copy of just that one page. Fork becomes cheap because almost nothing is copied until it must be.
The second is the memory-mapped file. Instead of reading a file with explicit calls like read(fd, buf, n), you can ask the OS to map the file directly into your address space, so the file's contents simply appear as a region of memory. Now reading the file is just reading those addresses, and the demand-paging machinery we just built handles everything: a page of the file is pulled in by an ordinary page fault the first time you touch it, and dirty pages are written back later. The same page-fault plumbing that powers the illusion of unlimited memory also turns a file on disk into something you can read and write as if it were plain memory. From one idea — addresses loosely connected to frames — flow isolation, oversized address spaces, cheap fork, and files-as-memory.