Paging: Introduction

Why Paging Beats Segmentation

Variable-sized segments quickly shatter free space into unusable holes, forcing the allocator to hunt for fitting gaps. Paging turns memory into identical building blocks; any free frame can accept any page, so a simple free list suffices and no assumptions about heap or stack growth are required.

How an Address Is Split and Reassembled

The high bits of a virtual address form the virtual page number while the low bits form the offset. The page number indexes the page table to fetch a physical frame number; concatenating that frame number with the untouched offset yields the physical address. The offset is never translated because it merely selects a byte inside the page.

Where Page Tables Live and How Large They Grow

Page tables are private kernel structures belonging to each process. A 32-bit space with 4 KiB pages produces roughly a million entries; even four bytes per entry makes a single table 4 MiB. Hundreds of processes would therefore consume hundreds of megabytes just for translations, motivating more compact representations.

Pitfalls

• Looking up the offset inside the page table
• Believing a single page table is shared by every process
• Underestimating that page tables can dwarf the user data they describe

Minimum C11 · complete program · Download .c

#include <stdio.h>
#include <stdint.h>

int main(void) {
    const uint8_t page_table[4] = {3, 7, 5, 2};
    const uint8_t virtual_addrs[4] = {21, 0, 32, 48};
    for (int i = 0; i < 4; ++i) {
        uint8_t va = virtual_addrs[i];
        uint8_t vpn = va >> 4;
        uint8_t offset = va & 0x0F;
        uint8_t pfn = page_table[vpn];
        uint8_t pa = (uint8_t)((pfn << 4) | offset);
        printf("VA %u (VPN %u, offset %u) -> PA %u (PFN %u)\n",
               va, vpn, offset, pa, pfn);
    }
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-18-paging.c -o example && ./example

Expected result

VA 21 (VPN 1, offset 5) -> PA 117 (PFN 7)
VA 0 (VPN 0, offset 0) -> PA 48 (PFN 3)
VA 32 (VPN 2, offset 0) -> PA 80 (PFN 5)
VA 48 (VPN 3, offset 0) -> PA 32 (PFN 2)

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

64-byte virtual space, 16-byte pages. Virtual address 21 is binary 010101; its VPN=1 maps to physical frame 7. What physical address results?

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.