Paging

Paging cuts a process's logical memory into fixed-size pages, and physical memory into frames of the same size. Any page can go in any free frame. A process no longer needs one big hole, so there is no external fragmentation; the only waste is the unused end of its last page (a little internal fragmentation).

The OS keeps a page table for each process: entry p says which frame holds page p.

Translating an address

The page size is always a power of 2, such as 4 KB (4096 = 2¹² bytes). Then a logical address splits into two parts:

• page number p = address / page size,
• offset d = address % page size (the position inside the page).

The MMU looks up the frame f = page_table[p], and the physical address is f × page size + d. Because the size is a power of 2, the split is just bits: with 4 KB pages, the low 12 bits are the offset and the rest is the page number, so no division is needed.

#include <stdio.h>

#define PAGE_SIZE 1024
#define PAGES 4

int page_table[PAGES] = {5, 2, -1, 7};   /* frame of each page; -1: not in memory */

void translate(int address) {
    int page = address / PAGE_SIZE;
    int offset = address % PAGE_SIZE;
    if (page >= PAGES) {
        printf("%4d: page %d does not exist\n", address, page);
    } else if (page_table[page] < 0) {
        printf("%4d: page %d, offset %d -> page fault\n", address, page, offset);
    } else {
        int physical = page_table[page] * PAGE_SIZE + offset;
        printf("%4d: page %d, offset %d -> frame %d -> %d\n", address, page, offset, page_table[page], physical);
    }
}

int main(void) {
    int addresses[5] = {0, 1500, 2100, 3100, 4100};
    for (int i = 0; i < 5; i++) translate(addresses[i]);

    /* The same split with bits: 1024 = 2 to the 10th */
    for (int i = 0; i < 5; i++)
        printf("%d: page %d, offset %d\n", addresses[i], addresses[i] >> 10, addresses[i] & 1023);
    return 0;
}

This program uses 1 KB pages (1024 = 2¹⁰). Address 2100 is in page 2 at offset 52. Page 2 is not in memory (its entry is −1): the MMU would raise a page fault, the subject of the next lesson. The second loop does the same split with >> 10 and & 1023, the way hardware does it.

Each page-table entry also has bits for valid (is the page in memory?), protection (read, write, execute), dirty (changed since it was loaded?) and referenced (used lately?).

The TLB

A page table lives in memory, so every access would need two memory reads: one for the page-table entry and one for the data. The translation lookaside buffer (TLB) is a small, very fast cache of recent translations inside the CPU. Programs touch the same pages again and again, so the TLB usually has the answer.

The effective access time with TLB hit ratio h, memory time m and TLB time t:

EAT = h × (t + m) + (1 − h) × (t + 2m)

With h = 0.8, t = 20 ns and m = 100 ns: 0.8 × 120 + 0.2 × 220 = 140 ns. With h = 0.98 it is 122 ns. Many textbook exercises leave out t: then EAT = h × m + (1 − h) × 2m.

Big page tables

A 32-bit address space with 4 KB pages has 2²⁰, about a million, pages: at 4 bytes an entry, a 4 MB table for every process, mostly empty. Two fixes:

• Multi-level page tables: page the page table. The page number is split again; the outer table points to inner tables, and an inner table exists only where the process uses memory. 64-bit x86 uses 4 levels (5 on the newest machines).
• Inverted page tables: one table for the whole machine, with one entry per frame, saying which process and page it holds. Small, but slower to search.

Mark lesson complete