Pointer Walk

Virtual Memory and Paging

Every program believes it has memory to itself. A page table maps that illusion onto real memory, and a page fault fills in what is missing.

Operating SystemsIntermediate10 min read

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.

  1. The program uses an address

    Say, something in page 3.

  2. The processor looks up page 3 in the page table

    It finds: page 3 is in frame 1.

  3. 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.

Eight pages of program, four frames of memoryInteractive

Pages the program touches

012034105201

Page table: where is each page?

page 0on disk
page 1on disk
page 2on disk
page 3on disk
page 4on disk
page 5on disk
page 6on disk
page 7on disk

Real memory: 4 frames

frame 0empty
frame 1empty
frame 2empty
frame 3empty

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:

  1. The processor raises a page fault

    It is not an error. It means "I need the operating system's help".

  2. The program is paused

    It does not know it has been.

  3. 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.

  4. The wanted page is read in from disk

    And the page table is updated.

  5. 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    8 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress