Multilevel, inverted and hashed page tables

Why it exists

A flat page table has one entry for every page of the whole logical address space, whether the process uses it or not. For 32-bit addresses with 4 KB pages that is $2^{20}$ entries, about 4 MB per process; for 64-bit addresses the table would be larger than any memory. Most processes use only a small, scattered part of their address space (a little code and data at the bottom, a stack at the top), so most of the table would be empty. Three structures avoid storing it all: hierarchical (multilevel) tables, hashed tables and inverted tables. GATE asks for the number of levels, the bit split of the address, the size of the tables for a given process, and the number of memory accesses per translation.

Prerequisites

You need the page, frame, offset and page-table calculations of paging.

Precise definitions

Hierarchical (multilevel) paging. The page table itself is paged. The page number is split into several parts: an index into the outer (top-level) table, which points to an inner table, which holds (or points to the next level of tables that finally hold) the frame number. Inner tables are created only for the parts of the address space the process uses, so unused regions need no table.

For a two-level scheme the logical address is

$\underbrace{p_1}_{\text{outer index}} \quad \underbrace{p_2}_{\text{inner index}} \quad \underbrace{d}_{\text{offset}}$

Translation: use $p_1$ to find the inner table in the outer table, use $p_2$ to find the frame in the inner table, then form $f \cdot 2^n + d$. Because the address is translated from the outside in, the scheme is also called a forward-mapped page table.

Choosing the bit split. Make every table fit exactly in one page (so tables can be allocated and swapped like any other page). With page size $2^n$ bytes and page-table entries of $e$ bytes, a table holds $2^n/e$ entries, so each level uses

$b = \log_2 (2^n / e) \text{ bits of the address.}$

With $m$-bit logical addresses the page number has $m - n$ bits, so the number of levels is

$\text{levels} = \left\lceil \frac{m - n}{b} \right\rceil.$

If the bits do not divide exactly, the top level uses the remainder (it is smaller than a page). Examples: $m = 32$, 4 KB pages, 4-byte entries: $b = 10$, levels $= \lceil 20/10 \rceil = 2$, split 10 + 10 + 12. $m = 64$, 4 KB pages, 8-byte entries: $b = 9$, levels $= \lceil 52/9 \rceil = 6$; with 48-bit addresses $\lceil 36/9 \rceil = 4$ (the usual four-level scheme). $m = 38$: $\lceil 26/9 \rceil = 3$ levels, the top one with $26 - 18 = 8$ bits.

Memory references. With a $k$-level table and no TLB each reference costs $k + 1$ memory accesses ($k$ table lookups and the data). The TLB caches the final translation to avoid most of them.

Size of the tables. A flat table has $2^{m-n}$ entries. A multilevel table needs the outer table plus one inner table for each region of the address space (one inner table covers $2^{b}$ pages) that contains at least one used page. A process using a contiguous part of $U$ pages needs $\lceil U/2^b \rceil$ inner tables.

Hashed page tables (for address spaces larger than 32 bits). The virtual page number is hashed into a table; each entry is a chain of elements (virtual page number, frame number, pointer to the next). Translation hashes the page number, walks the chain comparing page numbers, and takes the frame of the matching element. Sparse address spaces cost only as many elements as there are mapped pages. Clustered page tables put several consecutive pages in one element.

Inverted page table. One table for the whole system, with one entry per physical frame: the entry for frame $i$ holds the process id and the page number currently stored in it. Translating $(\text{pid}, p, d)$ means searching the table for the entry $(\text{pid}, p)$; the position $i$ of the matching entry is the frame number, and the physical address is $i \cdot 2^n + d$. A hash on $(\text{pid}, p)$ speeds the search. Its size follows the physical memory (frames $\times$ entry size), not the logical address spaces or the number of processes. The disadvantages: the lookup is a search; shared pages are awkward (a frame has one $(\text{pid}, \text{page})$); and it cannot say where a page is on disk (a separate per-process table is needed for pages that are not in memory).

Comparison.

How it works

The first animation is a two-level translation in a toy 12-bit address space: page size 64 bytes (6-bit offset), a 6-bit page number split into 3 + 3 bits. The outer table has 8 entries; only three inner tables exist (for $p_1 = 0, 2, 5$); the other five outer entries are empty. A flat table would need 64 entries; this structure stores $8 + 3 \times 8 = 32$. Two addresses fault: one finds an empty outer entry (no inner table at all), the other an invalid inner entry.

The second animation is an inverted page table for a memory of 8 frames. The table is searched for the entry $(\text{pid}, \text{page})$; its position is the frame number.

Worked examples

#include <stdio.h>
#include <string.h>
 
/* a flat page table and a two-level one for a toy 12-bit address space: page size 64 (6-bit offset), 3 + 3 bits of page number */
static int flat[64];
static int outer[8];                       /* index of the inner table, or -1 */
static int inner[8][8];                    /* frame or -1 */
 
static int levels(int va_bits, int page, int entry) {
    int offset = 0, per_table = page / entry, level_bits = 0;
    while ((1 << offset) < page) offset++;
    while ((1 << level_bits) < per_table) level_bits++;
    return (va_bits - offset + level_bits - 1) / level_bits;
}
 
int main(void) {
    memset(flat, -1, sizeof flat);
    memset(outer, -1, sizeof outer);
    memset(inner, -1, sizeof inner);
    int mapped[8][2] = {{1, 10}, {2, 11}, {6, 40}, {19, 21}, {20, 22}, {23, 5}, {40, 33}, {47, 8}};   /* page -> frame */
    int next_inner = 0;
    for (int i = 0; i < 8; i++) {
        int p = mapped[i][0], f = mapped[i][1];
        flat[p] = f;
        if (outer[p >> 3] < 0) outer[p >> 3] = next_inner++;
        inner[outer[p >> 3]][p & 7] = f;
    }
    int agree = 0;
    for (int L = 0; L < 4096; L++) {
        int p = L >> 6, d = L & 63;
        int a = flat[p] < 0 ? -1 : flat[p] * 64 + d;
        int t = outer[p >> 3];
        int f = t < 0 ? -1 : inner[t][p & 7];
        int b = f < 0 ? -1 : f * 64 + d;
        agree += a == b;
    }
    printf("flat table and two-level table agree on %d of 4096 addresses\n", agree);
    printf("entries stored: flat 64, two-level 8 + %d x 8 = %d\n", next_inner, 8 + next_inner * 8);
    printf("32-bit, 4 KB pages, 4-byte entries: %d levels, flat table %d KB\n", levels(32, 4096, 4), (1 << 20) * 4 / 1024);
    int used_pages = 12 * 1024 * 1024 / 4096, per = 1024;
    int inner_tables = (used_pages + per - 1) / per;
    printf("a 12 MB process: %d pages, %d inner tables, %d KB of tables in all\n", used_pages, inner_tables, (1 + inner_tables) * 4);
    printf("64-bit, 4 KB pages, 8-byte entries: %d levels; with 48-bit addresses: %d levels\n", levels(64, 4096, 8), levels(48, 4096, 8));
    return 0;
}

flat table and two-level table agree on 4096 of 4096 addresses
entries stored: flat 64, two-level 8 + 3 x 8 = 32
32-bit, 4 KB pages, 4-byte entries: 2 levels, flat table 4096 KB
a 12 MB process: 3072 pages, 3 inner tables, 16 KB of tables in all
64-bit, 4 KB pages, 8-byte entries: 6 levels; with 48-bit addresses: 4 levels

Cheat box

Traps and GATE patterns

Connections

All of these refine the single table of paging. The extra accesses they cost are why a TLB is essential, and the valid bit in each entry is what virtual memory uses to mean "not in memory". A segment can have its own page table, giving segmentation with paging. A hashed lookup resembles a cache index: a short key chooses where to look.

PYQs

A computer system supports a logical address space
of 232bytes. It uses two-level hierarchical paging
with a page size of 4096 bytes. A logical address is
divided into a b-bit index to the outer page table, an
offset within the page of the inner page table, and an
offset within the desired page. Each entry of the inner
page table uses eight bytes. All the pages in the
system have the same size.The value of b is ______.

Consider a 32-bit system with 4 KB page size and
page table entries of size 4 bytes each. Assume 1 KB
= 210 bytes. The OS uses a 2-level page table for
memory management, with the page table containing
an outer page directory and an inner page table. The
OS allocates a page for the outer page directory upon
process creation. The OS uses demand paging when
allocating memory for the inner page table, i.e., a
page of the inner page table is allocated only if it
contains at least one valid page table entry.

An active process in this system accesses 2000 unique
pages during its execution, and none of the pages are
swapped out to disk. After it completes the page
accesses, let X denote the minimum and Y denote the
maximum number of pages across the two levels of
the page table of the process.

The value of X + Y is _____

Consider a computer system with 57-bit virtual
addressing using multi-level tree-structured page
tables with L levels for virtual to physical address
translation. The page size is 4 KB (1 KB = 1024 B)
and a page table entry at any of the levels occupies
8 bytes.The value of L is.........

Which one of the following statements is FALSE?

Consider a three-level page table to translate a 39-bit
virtual address to a physical address as shown below.

The page size is 4KB (1KB = 210 bytes) and page table
entry size at every level is 8 bytes. A process P is
currently using 2GB (1GB = 230 bytes) virtual
memory which is mapped to 2GB of physical
memory. The minimum amount of memory required
for the page table of P across all levels is
_______  KB

OPERATING SYSTEMS

Consider a computer system with 40-bit virtual
addressing and page size of sixteen kilobytes. If the
computer system has a one-level page table per
process and each page table entry requires 48 bits,
then the size of the per-process page table is
__________ megabytes.

A computer system implements 8 kilobyte pages and
a 32-bit physical address space. Each page table entry
contains a valid bit, a dirty bit, three permission bits,
and the translation. If the maximum size of the page
table of a process is 24 megabytes, the length of the
virtual address supported by the system is ________
bits.

A computer uses 46-bit virtual address, 32-bit
physical address, and a three-level paged page table
organization. The page table base register stores the
base address of the first-level table (T1), which
occupies exactly one page. Each entry of T1 stores the
base address of a page of the second-level table (T2).
Each entry of T2 stores the base address of a page of
the third-level table (T3). Each entry of T3 stores a
page table entry (PTE). The PTE is 32 bits in size.
The processor used in the computer has a 1 MB 16-
way set associative virtually indexed physically
tagged cache. The cache block size is 64 bytes.

What is the minimum number of page colors needed
to guarantee that no two synonyms map to different
sets in the processor cache of this computer?

A multilevel page table is preferred in comparison to
a single level page table for translating virtual address
to physical address because

A processor uses:
Physical address = 36 bits
Virtual address = 32 bits
Page size = 4 KB
PTE size = 4 bytes

Three-level page table with:
● bits 30–31 → 1st level index
● bits 21–29 → 2nd level index
● bits 12–20 → 3rd level index
● bits 0–11 → offset

Find number of bits required in PTE to address the
next level page table (or page frame) at first, second,
and third levels respectively.

Self-check

Revision card

References