Virtual Memory

Why programs can't share real memory#

Think of RAM as a very long row of numbered lockers. Each locker holds one byte. The locker's number is its address. When a program stores a value, it goes into a locker. To read it back, the program asks for that locker number.

Now run many programs on one row of lockers. Two things go wrong. A bug in Chrome writes to the wrong locker, and Spotify's data is gone. And programs are built with fixed addresses in them, so two programs that both use locker 1,000 can't run together. There's only one locker 1,000.

First try: give each program its own block#

The obvious fix: give each program a fixed range. Chrome gets lockers 0 to 999, Spotify 1,000 to 1,999, and the CPU blocks access outside a program's range. Early machines did this. It breaks four ways.

• Programs can't grow. Chrome needs more, but Spotify's block sits right after Chrome's.
• Free space breaks into holes: 500 MB free in total, but no 400 MB in one run.
• Reserved means wasted. A program that reserves 8 GB and uses 2 GB still locks up all 8.
• No sharing. A hundred programs using one library need a hundred copies.

Small pieces, and a table#

Cut memory into small, equal pieces instead: 4 KB each, which is 4,096 bytes. (KB, GB and TB here count in steps of 1,024, the way memory is measured.) A program that needs memory gets any free pieces, wherever they are.

That fixes growth and holes. But the pieces are scattered: say one at real address 40,000, the next at 900,000, the last at 12,000. Now it stores a 10,000-byte array. Code assumes memory is continuous: element 5,000 is at start + 5,000. That runs off the first piece into someone else's memory.

So the program must never see real addresses. It sees one continuous range of pretend addresses: 0, 1, 2 and up. A table maps each pretend piece to its real piece. Pretend pieces are called pages. Real pieces are called frames. The table is the page table, and every program gets its own. It has one line per page: line 12 holds the frame for page 12.

Pretend addresses are called virtual addresses: the virtual in virtual memory.

How one address is translated#

A program asks for address 50,000. Pages are 4,096 bytes, laid back to back: page 0 is addresses 0 to 4,095, page 1 is 4,096 to 8,191, and so on. 50,000 ÷ 4,096 = 12, remainder 848. So it's page 12, 848 bytes in. (For now, picture one flat table. The next section shows why the real one is a tree.)

There's no searching. 4,096 is a power of two, so the CPU just splits the address's bits, and line 12 is found directly, like table[12].

Why the table is a tree#

A phone book for a huge country doesn't list every possible number. A first book lists regions. Most say "nobody here"; the rest point to a smaller book.

The page table works the same way. The top table has one line per big region. An unused region is one line marked empty. A used region points to a smaller table, and so on down, four levels deep. A program pays only for what it uses. The tables themselves are ordinary data, sitting in RAM like everything else.

How does the CPU find its way down? The address spells out the path, like a phone number: country, then city, then line. The CPU cuts the address into chunks, each picking the line at the next level. The last chunk is the position inside the page.

Where does it start? The CPU has a few tiny built-in storage slots, called registers. One of them holds where the current program's top table is. Switching programs means pointing it at another table.

Nothing is loaded until it's touched#

Follow java Hello from the start. Here java is itself a program, a file on disk. The addresses are round, made-up numbers.

1. The layout is decided before it runs. When the java program was built, its build tools wrote into it: code goes at pretend addresses from 40,960, and running starts at 50,000. Just numbers in a file.
2. Starting the program loads nothing. The operating system writes a plan of allowed ranges, like "code from 40,960 comes from the java file", and an empty page table.
3. Empty means one flag. Every line has a present flag, and line 12 says present: no.
4. The first instruction trips it. The CPU tries 50,000: page 12, not present. It stops the program and calls the operating system. That's a page fault.
5. The operating system fills it in. The plan says page 12 is code from the file. It takes a free frame, say 7,731, copies one page of the file into it, marks line 12 present at frame 7,731, and lets the program carry on.

Every page gets its frame this way, on first touch, and one page always fits one frame. Memory that doesn't come from a file, like space a program asks for while running, gets a frame filled with zeros. Touch an address outside the plan, and the program is killed with "Segmentation fault".

So 50,000 points nowhere when the program starts. The frame it gets can differ on every run, and even mid-run, if the page is moved to disk and brought back.

What it costs#

With four levels, every memory access means four extra trips to RAM, one per table, before the real one. That would make every program several times slower. It doesn't, because the CPU keeps a small cache of recent translations. That cache is called the TLB, and it's the next article in this series.

If this comes up in an interview#

In interview words: program = process, pretend = virtual, real = physical.