Every program thinks it is alone
A program uses memory addresses constantly: "store this at address 5,000", "read what is at 12,000". On your machine dozens of programs do this at the same time. If they all used the real memory directly, they would have to agree on who gets which addresses, and one mistake would overwrite another program's data.
They do not have to agree, because none of them sees the real memory. Each program is given its own private, imaginary address space, starting from zero. This is virtual memory.
The operating system and the processor quietly translate every address the program uses into a real location. The program never knows.
Pages and frames
Translating addresses one at a time would need an impossibly large table. So memory is cut into fixed-size blocks, usually 4 kilobytes each.
- A block of a program's virtual memory is a page.
- A block of real memory is a frame.
For each program, the operating system keeps a page table: for every page, which frame holds it.
The program uses an address
Say, something in page 3.
The processor looks up page 3 in the page table
It finds: page 3 is in frame 1.
The address is translated and the access happens
This is done by hardware on every single memory access, and is extremely fast.
Two programs can both use "page 3". Their page tables point at different frames, so they never collide. That is the isolation between processes.
More memory than you have
Here is the second trick. A page does not have to be in real memory at all. The page table can say: this page is on disk.
Pages the program touches
Page table: where is each page?
Real memory: 4 frames
Start. The program believes it has 8 pages of memory, numbered 0 to 7. The machine only has room for 4 of them at a time. The rest stay on disk until needed.
- Straight through
- 0
- Page faults
- 0
When a program touches a page that is not in memory:
The processor raises a page fault
It is not an error. It means "I need the operating system's help".
The program is paused
It does not know it has been.
The operating system finds a frame
If none is free, it picks a page that has not been used lately and writes it out to disk.
The wanted page is read in from disk
And the page table is updated.
The program resumes at the same instruction
Which now succeeds.
So the total memory used by all programs can exceed the real memory in the machine. The overflow lives on disk, in what is called swap space or the page file.
The catch: disk is slow
A memory access takes nanoseconds. A page fault that reads from disk takes thousands of times longer.
That is fine if it is rare. Most programs use a small part of their memory at any moment, and those pages stay loaded.
Example
Thrashing
Open too many heavy programs and they need more pages, actively, than there are frames. Loading one page pushes out a page another program needs a moment later. That one faults, and pushes out something else.
The machine spends nearly all its time moving pages to and from disk and almost none doing work. Everything freezes and the disk light stays on. That is thrashing, and the only cures are closing programs or adding memory.
Choosing which page to push out is the same problem as cache eviction: keep what will be needed again, guess what will not.
Other things the page table makes possible
Once every access goes through a table, the operating system gains several abilities for free.
- Protection. Each entry says whether the page may be read, written or executed. Writing to a read-only page, or to an address with no entry at all, is stopped. That is where "segmentation fault" and "access violation" come from.
- Lazy allocation. A program asks for a gigabyte. Nothing is handed over until it actually touches each page.
- Sharing. The code of a library used by fifty programs is loaded once, and all fifty page tables point at the same frames.
- Copy on write. Two processes share the same pages until one of them writes, and only then is that one page copied.
- Memory-mapped files. A file is made to look like a region of memory, and its parts are loaded as they are touched.
Key takeaways
- Each program gets its own virtual address space, translated to real memory behind its back.
- Memory is divided into pages, and a page table records which real frame holds each one.
- A page that is not in memory causes a page fault, and the operating system loads it from disk.
- This lets programs use more memory than exists, at the cost of slow disk access.
- The same mechanism isolates programs and protects memory from illegal access.