Paging, Page Tables and TLB

Paging removes external fragmentation by giving up contiguity. The logical address space of a process is cut into fixed-size pages, physical memory into frames of the same size, and any page can sit in any free frame. A per-process page table records which frame holds each page, and the hardware consults it on every memory reference.

Paging costs two things: memory for the page tables, and time, because a reference now needs the page table as well as the data. The first cost leads to multilevel, hashed and inverted page tables; the second leads to the translation look-aside buffer (TLB).

Address translation, page-table entries, page-table size, multilevel and inverted tables, the TLB and effective access time, shared pages, and the internal fragmentation that paging keeps are the standard facts. Virtual Memory and Demand Paging builds on it by letting pages live on disk.

With page size $P = 2^d$ bytes and a logical address of $n$ bits, the low $d$ bits are the offset and the high $n - d$ bits the page number:

where $f$ is the frame number found in entry $p$ of the page table. Because $P$ is a power of 2, the split is just a choice of bits, and the offset is copied unchanged into the physical address. The number of pages is $2^{n-d}$; with $m$ physical address bits the number of frames is $2^{m-d}$ and a frame number needs $m - d$ bits.

The page table itself is in main memory. The page-table base register (PTBR) points to it, so a context switch changes only one register (plus the TLB state). A page-table length register (PTLR) may bound the number of valid pages.

The TLB is a small, fast, fully associative (or set-associative) cache of recent page-to-frame translations, typically tens to a few thousand entries. On a TLB hit the frame number comes from the TLB; on a miss the page table is read from memory and the translation is loaded into the TLB, replacing an entry. The associative lookup hardware is covered with cache organisation in Cache Mapping: Direct, Associative and Set-Associative.

A TLB entry belongs to one address space. On a context switch the OS either flushes the TLB or the entries carry an address-space identifier (ASID), so that entries of several processes can coexist. TLB reach is the memory a full TLB maps: entries times page size, for example $64 \times 4 \text{ KB} = 256 \text{ KB}$.

The protection check applies on hits as well: TLB entries carry the protection bits.

With 4 KB pages, the logical address 0x23A7C has offset 0xA7C (the last three hex digits) and page number 0x23 (35). If page 35 is in frame 0x1F4, the physical address is 0x1F4A7C. With hexadecimal addresses and pages of $2^{12}$ bytes, the offset is always the last three hex digits.

The page table has one entry per page:

with $e$ the entry size. For a 32-bit logical address, 4 KB pages ($d = 12$) and $e = 4$ bytes: $2^{20}$ entries, 4 MB per process, which must be contiguous in memory. With 1 GB of physical memory ($m = 30$), the frame number takes 18 bits; adding valid, dirty, referenced and three protection bits gives 24 bits, so 3 bytes would do, and the entry is usually rounded up to 4 bytes.

Page the page table itself. With entry size $e$, one page holds $P / e$ entries, so each level resolves $\lg (P / e)$ bits of the page number. The number of levels is

When the division is not exact, the outermost table is the partly filled one.

In the 40-bit case the outer table has $2^8 = 256$ entries, which occupy 1 KB, a quarter of a page. The 48-bit, 4 KB, 8-byte case is the four-level layout of x86-64.

Two-level walk. For a 32-bit address with the 10, 10, 12 split, the logical address 0x00403004 has outer index $p_1 = 1$, inner index $p_2 = 3$ and offset 0x004. If entry 1 of the outer table points to the inner table in frame 0x52, and entry 3 of that inner table holds frame 0x2A1, the physical address is 0x2A1004.

Why multilevel saves memory. Only the inner tables that map used pages need to exist. A process with 16 MB of code and data at the bottom of a 32-bit space and a 4 MB stack at the top needs four inner tables for the bottom (each maps 4 MB), one for the stack and one outer table: 6 pages, 24 KB, instead of the 4 MB single-level table. If every page were mapped, the two-level layout would use $1 + 1024$ pages, slightly more than one level.

Cost of a walk. A $k$-level table needs $k$ memory reads to find the frame on a TLB miss, then one more for the data: $k + 1$ accesses in all.

For large address spaces the page number is hashed into a table whose entries are chains of (page number, frame, next) elements. A lookup hashes $p$ and walks the chain. Hashed tables suit sparse 64-bit address spaces; a variant, the clustered page table, maps several consecutive pages per element.

An inverted page table has one entry per physical frame, holding the (process id, page number) that occupies it. There is one table for the whole system, and its size depends on physical memory, not on the address spaces.

Reentrant (read-only, non-self-modifying) code can be shared: the page tables of several processes point to the same frames. Forty users running an editor with 150 KB of code and 50 KB of private data each need $40 \times 200 = 8{,}000$ KB without sharing and $150 + 40 \times 50 = 2{,}150$ KB with it.

Let $m$ be the memory access time, $t$ the TLB lookup time, $h$ the TLB hit ratio and $k$ the number of page-table levels. With a sequential lookup (TLB first, page-table memory reads only after a TLB miss; the final data access follows on either path):

State which convention a question uses. Three conventions are in use:

Example. $t = 20$ ns, $m = 100$ ns, $h = 0.9$, single-level table ($k = 1$):

With a two-level table ($k = 2$) the miss path costs $20 + 200 + 100 = 320$ ns and the EAT becomes $0.9 \times 120 + 0.1 \times 320 = 140$ ns.

Required hit ratio. For the single-level case to reach 125 ns: $120h + 220(1 - h) = 125$, so $h = 0.95$.

A process of $S$ bytes needs $\lceil S / P \rceil$ frames, and the last one is partly empty. A 50,000-byte process with 4 KB pages needs 13 frames (12 full pages hold 49,152 bytes), and the last frame wastes $4096 - 848 = 3{,}248$ bytes. On average the waste is about half a page per process.

Related material. Tanenbaum (3.5.3) balances the two costs of page size. With average process size $s$ and entry size $e$, the overhead per process is $se/P$ for the page table plus $P/2$ for internal fragmentation, which is minimised at $P = \sqrt{2se}$. For $s = 1$ MB and $e = 8$ bytes that gives 4 KB.

Pages of 4 KB, page table: page 0 in frame 5, page 1 in frame 2, page 2 invalid, page 3 in frame 7, page 4 in frame 9.

46-bit logical addresses, 8 KB pages and 4-byte entries: the offset takes 13 bits, leaving 33 bits of page number. One page holds $8192 / 4 = 2048 = 2^{11}$ entries, so each level resolves 11 bits and $33 / 11 = 3$ levels are needed. A TLB miss then costs 3 page-table reads plus the data access.

32-bit logical addresses and 4-byte entries. What is the smallest page size for which a two-level table works with every table, outer and inner, fitting in one page? And for three levels?

With an offset of $d$ bits, a page holds $2^d / 4 = 2^{d-2}$ entries, so each level can resolve at most $d - 2$ bits. The page number has $32 - d$ bits, and $L$ levels need

These are the smallest integers $d$ that satisfy the inequalities, so no smaller page size works for either case.

Common misconceptions.