Skip to content
Tutorials Center
My learning

Topics

Lesson 46 of 67 ยท Virtual Memory and Storage

Virtual Memory and Paging

Learn how virtual memory gives each process a private address space: pages, frames, page tables, page faults and multi-level translation, simulated in Python.

Every program you run believes it owns a huge, private block of memory that starts at address zero. It does not. Dozens of processes share a few gigabytes of physical RAM, and none of them is allowed to read another's data. The trick that makes this possible is virtual memory: the addresses your program uses are virtual, and the hardware, together with the operating system, translates them into physical addresses on every access.

Virtual memory solves three problems at once. It gives each process isolation (a bug cannot overwrite a neighbour), convenience (every program can be linked at the same addresses and see one flat space), and capacity (a process can use more memory than the machine has, by keeping rarely used parts on disk). This lesson explains paging, the mechanism behind all of it, and builds an address translator in Python. It assumes you know what a cache is; virtual memory is, in a sense, main memory acting as a cache for the disk.

Pages and frames

Memory is divided into fixed-size chunks. In the virtual address space they are called pages; in physical memory they are called frames (or page frames). A page and a frame have the same size, most often 4 KB (4,096 bytes = 2^12).

Because the size is a power of two, an address splits cleanly into two fields:

  • the page number (the high bits), which says which page, and
  • the offset (the low 12 bits for a 4 KB page), which says where inside the page.

Translation changes the page number and leaves the offset alone. The virtual page number (VPN) is looked up in a page table, which stores the physical frame number (PFN); the physical address is the frame number followed by the same offset.

flowchart LR
  VA["Virtual address<br/>VPN | offset"] --> PT["Page table<br/>VPN -> frame"]
  PT --> PA["Physical address<br/>frame | offset"]
  VA -. "offset copied unchanged" .-> PA

Only the page number is translated. The offset within the page is the same in both address spaces.

For example, with 4 KB pages the virtual address 0x1234 has VPN 1 (0x1234 >> 12) and offset 0x234. If page 1 lives in frame 5, the physical address is (5 << 12) | 0x234 = 0x5234.

The page table and page faults

The page table is a data structure maintained by the operating system, one per process. Each entry (a PTE) holds the frame number and a few control bits:

  • Present (valid): is the page currently in RAM?
  • Read/write and user/supervisor: what access is permitted? A write to a read-only page, or a user access to kernel memory, raises an exception.
  • Accessed and dirty: set by the hardware when the page is read or written. The OS uses them to choose pages to evict, just as a cache uses a dirty bit (see Replacement and Write Policies).

If the present bit is 0 when the CPU touches a page, the hardware raises a page fault. This is not necessarily an error. The operating system's handler decides what happened:

  1. The page was never used yet (for example fresh heap memory): allocate a frame, fill it with zeros, map it.
  2. The page lives on disk (swapped out, or part of an executable not yet loaded): read it into a free frame, update the PTE, and restart the instruction.
  3. The address is not part of the process at all: send the process a segmentation fault.

A page fault that has to read from disk costs millions of cycles, which is why programs that constantly fault ("thrash") crawl. Operating systems keep many pages ready in RAM to avoid it.

Simulating translation and faults

The AddressSpace class below keeps a dictionary as its page table and a list of free frames. Each translation splits the address, looks up the VPN and, on a fault, maps the next free frame (a real OS would also load data and pick a victim page when no frame is free).

Python Translate virtual addresses and count page faults

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at what the output shows:

  • 0x0000 and 0x0FFF are different addresses but share page 0, so only the first one faults. Locality works for pages just like it does for cache blocks.
  • 0x7ABC sits in virtual page 7 but gets frame 2: virtual page numbers need not be contiguous or ordered, and physical frames are handed out in whatever order is convenient. The offset 0xABC is kept, giving 0x2ABC.
  • 0x1004 and 0x0010 are hits because pages 1 and 0 are already mapped.
  • The seven accesses cause 4 faults (pages 0, 1, 7 and 9), and the four frames are now all in use. A fifth distinct page would force the OS to evict something; the next lesson, TLBs and Page Replacement Algorithms, covers how it chooses.

Why a single flat table does not scale

A flat page table has one entry per virtual page. With 32-bit addresses and 4 KB pages that is 2^20 (about one million) entries per process; at 4 bytes each, 4 MB per process. That is tolerable on a 32-bit machine, but with 48-bit addresses it explodes. The calculation below shows the sizes (8-byte entries, as on modern 64-bit CPUs).

Python How big would a flat page table be?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A flat table for a 48-bit space would need 512 GB for every process, which is absurd, because most processes use a few megabytes spread across a handful of regions (code, heap, stack, libraries). Two ideas fix this: bigger pages (the 2 MB row, which is why operating systems offer "huge pages" for large allocations) and, more importantly, multi-level page tables.

Multi-level page tables

A multi-level table splits the VPN into several indexes and builds a tree. The top-level table points to second-level tables, and only the second-level tables that cover addresses actually in use need to exist. A missing entry at the top means a whole region of the address space is unmapped, and no memory is spent on it.

The classic 32-bit layout uses 10 + 10 + 12 bits: 10 bits index the top table (1,024 entries), 10 bits index a second-level table (1,024 entries), and 12 bits are the page offset. Each table has 1,024 entries of 4 bytes, so it fits exactly in one 4 KB page. The 64-bit x86 design extends the same pattern to four levels of 9 bits (512 entries of 8 bytes, again exactly 4 KB) plus a 12-bit offset, as the last lines of the previous program printed.

flowchart LR
  V["Virtual address<br/>10 bits | 10 bits | 12 bits"] --> T1["Top-level table<br/>indexed by bits 31-22"]
  T1 --> T2["Second-level table<br/>indexed by bits 21-12"]
  T2 --> F["Frame number"]
  F --> P["Physical address<br/>frame | offset"]

Two memory reads walk the tree before the data access itself; an unused region costs no second-level table.

The simulator below builds a two-level table with three mapped pages (two adjacent code pages and one stack page near the top) and walks it for four addresses.

Python A two-level page table walk

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two code pages share one second-level table (top index 1), the stack needs a second (top index 511), and the unmapped address 0x10000000 fails at the first level (top index 64) without any second-level table existing. The whole mapping costs 12 KB instead of 4,096 KB.

The price is time. A walk of an N-level table needs N extra memory reads before the real access, so a four-level walk quadruples the cost of a load that misses all caches. Hardware solves this with a small, fast cache of recent translations, the TLB, which is the subject of the next lesson. In practice, nearly all accesses hit in the TLB and never walk the table.

Each process has its own page table, and the CPU switches between them on a context switch by loading a single register (CR3 on x86, TTBR on ARM). That is how two programs can both use virtual address 0x400000 for different data without ever seeing each other's memory.

Segmentation and segmented paging

Paging cuts the address space into equal, fixed-size pages that mean nothing to the program. Segmentation cuts it along the lines a programmer sees: one segment for the code, one for the stack, one for each array or module. Segments have different lengths, and each is a logical unit that can be protected or shared on its own (for example, a read-only code segment shared by many processes).

A logical address has two parts: (segment number, offset). The hardware looks up the segment number in a segment table. Each entry holds the segment's base (where it starts in physical memory) and its limit (its length), plus protection bits.

Text
physical address = base[segment] + offset        if offset < limit[segment]
otherwise: trap (segmentation fault)

The limit check is what gives segmentation its protection: a stray offset cannot reach beyond the segment. Unlike paging, the offset is checked against a variable limit, not masked to a fixed width.

Python Segment table translation with base and limit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The problem: external fragmentation

Because segments have different sizes, placing and removing them leaves holes in physical memory. After many allocations there can be plenty of free memory in total, but no single hole large enough for a new segment. This is external fragmentation. Paging does not have it (every page fits every frame), but it has a little internal fragmentation: the unused tail of each process's last page. The operating system can compact memory by moving segments together, which is expensive.

Segmented paging: the best of both

Segmented paging keeps logical segments but pages each segment. The segment table entry no longer holds a base address; it holds the address of a page table for that segment. A logical address becomes (segment, page, offset):

  1. Use the segment number to find the segment's page table and check the segment limit.
  2. Use the page number to look up the frame in that page table.
  3. Combine the frame number with the offset.
flowchart LR
  LA["Logical address<br/>segment | page | offset"] --> ST["Segment table<br/>(page-table address, limit)"]
  ST --> PT["Page table<br/>of that segment"]
  LA --> PT
  PT --> F["Frame number"]
  F --> PA["Physical address<br/>frame | offset"]
  LA --> PA

Segment gives the page table; page gives the frame; offset passes through.

Segments are no longer placed contiguously: any frame can hold any page of any segment, so external fragmentation disappears, while sharing and protection still work per segment. The cost is an extra table lookup, so a TLB is essential. The original Intel 80386 used this scheme (segmentation in front of paging); modern 64-bit operating systems use almost pure paging and treat segmentation as a leftover, keeping only the FS and GS registers for thread-local storage.

Paging Segmentation Segmented paging
Unit size Fixed Variable Fixed pages inside variable segments
Visible to programmer No Yes Partly
External fragmentation None Yes None
Internal fragmentation Yes (last page) None Yes (last page of each segment)
Protection and sharing Per page Per segment Per segment and page
Lookup cost One table One table Two tables
Python Translate through a segment table and per-segment page tables

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. With 4 KB pages, what are the page number and offset of the virtual address 0x3A7C?

    4 KB pages use the low 12 bits (three hex digits) as the offset, so the offset is 0xA7C and the page number is the remaining high bits, 0x3.
  2. 2. What does the operating system do when a page fault occurs on a valid but swapped-out page?

    A fault on a legitimate page is a normal event. The handler brings the data in, sets the present bit and lets the faulting instruction run again.
  3. 3. Why do operating systems use multi-level page tables?

    A flat table needs an entry for every virtual page. A tree only needs second-level tables for regions that are actually mapped.
  4. 4. A 32-bit system uses 4 KB pages and 4-byte page-table entries. How large is a flat page table?

    2^32 / 2^12 = 2^20 pages, and 2^20 entries x 4 bytes = 4 MB per process.
  5. 5. In translation, which part of the virtual address is copied unchanged into the physical address?

    Only the page number is mapped to a frame number. The page and the frame have the same size, so the byte position inside it stays the same.

Summary

  • Virtual memory gives every process a private, uniform address space, providing isolation, convenience and the ability to use more memory than the RAM installed.
  • Memory is split into pages (virtual) and frames (physical) of the same size, typically 4 KB; an address is a page number plus an offset.
  • A page table maps page numbers to frame numbers, with present, permission, accessed and dirty bits in each entry.
  • A page fault is the exception raised when a page is not present; the OS loads or allocates the page and restarts the instruction.
  • A flat table is too big for large address spaces; multi-level tables allocate only the parts that are in use, at the cost of extra memory reads per walk.

Continue with TLBs and Page Replacement Algorithms.