Core · Operating systemsLesson 3 of 6Free to read

Virtual memory and paging · Operating Systems

How can every program think it owns all the memory?

Why you need it

Two programs can both use address 0x1000 without clashing, a crashed program can't corrupt another, and you can run more programs than fit in RAM. All three come from virtual memory. It's the answer to many interview questions and explains errors like "segmentation fault" and slowdowns from swapping.

The intuition

Memory is cut into fixed-size pages (often 4 KB). Each process has a page table: virtual page number → physical frame number.

To translate a virtual address:

page number = address // page size
offset = address % page size
look the page up in the table → frame
physical address = frame × page size + offset

A page that isn't in the table (or is marked "on disk") causes a page fault: the OS loads it, or kills the process if the address is invalid (segmentation fault).

Definition

Page table

A per-process map from virtual page numbers to physical frames, with flags such as present, writable and user-accessible.

Page fault

An access to a page that isn't currently mapped in RAM. The OS either loads it from disk or, for an invalid address, ends the process.

Examples

Translate an address

Try it yourself

Pages of 100 bytes keep the arithmetic readable. Real systems use 4096.

PAGE = 100
page_table = {0: 7, 1: 3, 2: None}

def translate(vaddr):
    page, offset = vaddr // PAGE, vaddr % PAGE
    frame = page_table.get(page)
    if frame is None:
        return f"page fault (page {page})"
    return frame * PAGE + offset

print(translate(42))
print(translate(150))
print(translate(230))

Step by step

L542 is page 0, offset 42.
L9Page 0 is in frame 7: 742.742
L12Page 1, offset 50, frame 3.350
L13Page 2 isn't in memory.page fault (page 2)

Common mistakes

Virtual = physical

The address a program prints is virtual. Two processes printing the same address are looking at different physical memory.

Swap as free memory

When RAM fills up, pages move to disk, which is thousands of times slower. A machine that swaps constantly (thrashing) slows to a crawl.

Quick quiz

1. What does this print?

1
2
3

PAGE = 4096
addr = 9000
print(addr // PAGE, addr % PAGE)

A
```
2 808
```
B
```
9 0
```
C
```
2 9000
```

Show the answer

Answer: A

2 × 4096 = 8192, and 9000 − 8192 = 808.

2. A program reads an address that no page of its own covers. What happens?

AThe OS stops it with a segmentation fault
BIt reads another program's memory
CIt reads zeros

Show the answer

Answer: A

The page fault can't be resolved, so the OS ends the process. That isolation is the point.

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictTranslate by hand
Type exactly what this program prints.
ModifyRespect read-only pages
Each page table entry is now (frame, writable). access(table, vaddr, write) should return the physical address, "fault" for an unmapped page, or "protection" when writing to a page that isn't writable. Add the protection check.
WriteTwo processes, one address
Write physical(tables, pid, vaddr, page_size) where tables maps each process id to its own page table ({page: frame}). Return the physical address, or None if that process has no such page.

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

Term	Chinese	Definition
Virtual memory	虚拟内存	Each process sees its own address space, mapped to RAM by the OS.
Page	页	A fixed-size block of memory, often 4 KB.
Page fault	缺页	Access to a page not currently in RAM.
Segmentation fault	段错误	The OS stopping a process that accessed memory it doesn't own.