COMP 3150Operating Systems

Module 3 · Unit 9 · Lesson 2 of 7

Page Tables

Lesson 9.1 presented paging with a simple assumption: the page table is a flat array with one entry per page of the address space. On a 64-bit system, this array would be terabytes in size — impossible to allocate. This lesson presents the multi-level page table, the hierarchical structure that modern systems use to keep the page table small while still supporting a large address space. It covers two-level, three-level, and four-level structures, the page-table walk that translates an address through them, the alternatives of inverted and hashed page tables, and the role of huge pages.

01 Introduction

Lesson 9.1 introduced paging as a scheme that divides the logical address space into fixed-size pages and physical memory into frames of the same size. It described the page table as an array indexed by page number, with each entry holding the frame number of the corresponding page. That description is accurate as far as it goes, and it is the model that every textbook uses to introduce the mechanism. But as soon as we ask how large the page table is, the model breaks down.

Consider a 64-bit system with a 4 KB page size. The logical address space is 264 bytes, which is 252 pages of 4 KB each. A flat page table with one entry per page would need 252 entries. Each entry is at least 8 bytes (typically 8 bytes on x86-64), so the table would be 255 bytes — thirty-two petabytes. Even the largest servers of today have only a few terabytes of memory; a page table of thirty-two petabytes is entirely infeasible.

The problem is not limited to 64-bit systems. A 32-bit system with a 4 KB page size has 232 bytes of address space, which is 220 pages. A flat page table with 220 entries of 4 bytes each would be 4 MB per process. On a system with hundreds of processes, that is hundreds of megabytes of page tables — a significant fraction of the physical memory, devoted to translation rather than to useful work. On a system with thousands of processes, the page tables could exceed the physical memory entirely.

The solution to this problem is the multi-level page table, a hierarchical structure in which the page table is divided into a hierarchy of smaller tables. The key insight is that a process typically uses only a small fraction of its address space — its code, its data, its heap, and its stack, which together occupy a handful of megabytes out of the enormous virtual address space. The multi-level structure exploits this sparsity: it allocates only the parts of the page table that correspond to the regions the process actually uses, and leaves the rest unallocated.

This lesson presents the page-table structures that modern systems use. It begins with the flat page table and the size problem, then presents the multi-level page table and the hierarchical walk. It presents the two-level, three-level, and four-level structures, with the x86-64 four-level structure as the detailed example. It examines the page-table entry fields, which are richer than just a frame number, and the alternatives — the inverted page table and the hashed page table — that are used in some systems. It closes with the role of huge pages, the large pages that reduce the depth of the walk and the size of the page table for memory-intensive applications.

Prerequisites

This lesson builds directly on Lesson 9.1. The concepts of a page, a frame, a page table, and paged address translation are assumed. The two-memory-access problem and the role of the TLB are referenced, but the TLB itself is the subject of Lesson 9.3. The structure of a page-table entry — including the valid, dirty, and protection bits — is introduced here in more detail than in Lesson 9.1. Familiarity with the segmentation and fragmentation material from Unit 8 is useful for understanding the trade-offs, but no additional prerequisite is required.

02 Learning objectives

By the end of this lesson you will be able to

  • Explain why a flat page table is infeasible on modern systems, and quantify the size problem.
  • Describe the multi-level page table and trace a hierarchical page-table walk from a logical address to a frame number.
  • Describe the x86-64 four-level page-table structure and the role of each level.
  • Identify the fields of a page-table entry and explain their purposes.
  • Describe inverted and hashed page tables, and explain the role of huge pages.

This lesson contributes to U9.2 and U9.3, and to course learning outcomes CLO1, CLO4, and CLO6.

03 Required reading

  • Operating System Concepts — Chapter 9, Section 9.4, Structure of the Page Table, and Chapter 10, Sections 10.1–10.3. The standard treatment of hierarchical page tables, hashed page tables, and inverted page tables.
  • OSTEP — Chapter 20, Paging: Smaller Tables. The clearest available treatment of the multi-level page table, with worked examples of the hierarchical walk and the space savings. OSTEP's treatment is the basis for the worked example in this lesson.
  • Tanenbaum & Bos — Modern Operating Systems, Chapter 3, Section 3.3, through the subsection on page-table structure. The two-level, three-level, and inverted page tables, presented with the historical context.
  • Silberschatz et al. — Chapter 9, Section 9.4. Read the discussion of the hashed page table and the inverted page table, which are the alternatives to the hierarchical structure used in some systems.
  • Intel Corporation. — Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3: System Programming Guide, Chapter 4, Paging. The definitive reference for the x86-64 four-level page table, including the format of each level's entries, the page-table walk, and the huge-page variants.
  • Bryant, R. E., & O'Hallaron, D. R. — Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 9, Virtual Memory, sections 9.6–9.7. The x86-64 page table presented from the programmer's perspective, with the details of the translation.
  • Linux kernel documentation — Documentation/arch/x86/x86_64/, and the Documentation/vm/ directory, which contain the Linux kernel's documentation of the x86-64 page table structure, the five-level paging extension, and the use of huge pages.
  • Linux man pages: man 3 getpagesize, man 2 mmap, man 2 madvise, man 5 proc, man 2 mmap2 and the MAP_HUGETLB flag.

Reading strategy

Read the OSTEP chapter first, and read it carefully. Its treatment of the multi-level page table is the clearest available, and its worked examples of the hierarchical walk are the basis for the worked example in this lesson. Then read the Silberschatz section on the structure of the page table for the alternatives — the hashed and inverted page tables. Finally, read the Intel manual's chapter on paging if you want the full detail of the x86-64 four-level structure; the manual is dense, but the sections on the page-table walk and the huge-page variants are the authoritative reference. Pay particular attention to the trade-off between the depth of the hierarchy and the size of the page-table entry: the deeper the hierarchy, the smaller the individual tables, but the longer the walk.

04 Core content

4.1 The flat page table and its size problem

A flat page table (also called a single-level page table) is an array with one entry per page of the process's logical address space. The entry for page number p is at index p, and it holds the frame number for that page.

The size of the table is straightforward to compute: it is the number of pages in the address space multiplied by the size of each entry. On a 32-bit system with a 4 KB page size, the number of pages is 232 / 212 = 220, and with 4-byte entries the table is 4 MB. On a 64-bit system with a 4 KB page size, the number of pages is 252, and with 8-byte entries the table is 255 bytes = 32 PB. Even the largest servers have only terabytes of memory; a page table of 32 petabytes is not merely impractical — it is impossible.

The problem is not only the absolute size but the size per process. Every process needs its own page table, because every process has its own address space. On a system with a hundred processes, a 4 MB table per process would consume 400 MB of physical memory for page tables alone. On a system with thousands of processes, the tables could exceed the physical memory entirely.

The size problem has two aspects. The first is the absolute size: the table is bigger than any conceivable physical memory. The second is the waste: the table has entries for every page in the address space, but a process typically uses only a small fraction of that space. The code, data, heap, and stack together occupy a handful of megabytes, but the page table must have entries for all 252 pages in the 64-bit address space, most of which are unused. The entries for the unused pages are mostly zero — or, more precisely, marked as invalid — but they still occupy space in the table.

The flat page table size problem A diagram showing a process's address space and its flat page table. The address space is a single long bar representing 2 to the 64 bytes. Most of it is unused, with a small region at the bottom for the code, data, heap, and stack. The flat page table is a correspondingly long array with one entry per page of the address space. Almost all entries are unused (marked with a dash), and the few entries that correspond to the used regions hold frame numbers. The table's total size is 32 petabytes, which is far larger than any physical memory. The diagram illustrates that the flat page table is infeasible because it must have an entry for every page, even those that are never used. THE FLAT PAGE TABLE SIZE PROBLEM Process address space (64-bit) 2^64 bytes = 2^52 pages of 4 KB each used code + data + heap + stack (a few MB) unused (the vast majority of the address space) Flat page table (one entry per page) entries 2^52 entries, mostly invalid — a dash in every position Table size = 2^52 entries × 8 bytes = 2^55 bytes = 32 PB Comparison Flat page table per process: 32 PB Physical memory in a large server: a few TB The flat page table is infeasible. The table is larger than the machine it is meant to describe, and it is needed once per process. The multi-level page table solves this problem.
Figure 9.2 — The flat page table size problem. A 64-bit address space has 252 pages of 4 KB each, so a flat page table would need 252 entries. With 8-byte entries, this is 32 petabytes — far larger than any physical memory, and needed once per process. The multi-level page table solves the problem by allocating entries only for the regions of the address space the process actually uses.

4.2 The multi-level page table

The multi-level page table (also called a hierarchical page table) is the structure that solves the size problem. The idea is to divide the page table into a hierarchy of smaller tables, so that the tables corresponding to unused regions of the address space need not be allocated at all.

In a two-level page table, the page number portion of the logical address is split into two parts: an outer page number and an inner page number. There are two levels of tables:

  • A first-level table (also called the page directory, top-level table, or PMLE — for Page Middle-Level Entry), which is indexed by the outer page number. Each entry in the first-level table points to a second-level table.
  • A second-level table, which is indexed by the inner page number. Each entry in the second-level table holds the frame number for the corresponding page.

The translation of a logical address through a two-level table is a two-step walk. First, the outer page number indexes into the first-level table, yielding the address of the second-level table that holds the entry for this address. Second, the inner page number indexes into that second-level table, yielding the frame number for the page. The frame number is then concatenated with the page offset to produce the physical address.

The savings come from the fact that second-level tables are allocated only for the regions of the address space the process actually uses. A process that uses only a few megabytes of its 64-bit address space has only a few second-level tables; the first-level table has entries for every possible inner table, but most of those entries are marked invalid and require no second-level table at all.

Two-level page table structure A diagram showing a two-level page table. On the left is the logical address, split into three fields: outer page number, inner page number, and page offset. The outer page number indexes into the first-level table (page directory), which has entries pointing to second-level tables. The inner page number indexes into the second-level table, which has entries pointing to frames in physical memory. The page offset is concatenated with the frame number to form the physical address. The diagram shows that the first-level table has many entries, most of which are invalid (marked as dashes) because the process does not use the corresponding regions of the address space. Only a few entries are valid and point to second-level tables. TWO-LEVEL PAGE TABLE STRUCTURE Logical address outer pn inner pn page offset First-level table (page directory) index 0 → second-level table 1 → — 2 → second-level table 3 → — 4 → — 5 → second-level table … most entries are invalid Second-level tables (allocated only for used regions) table for outer index 0 inner 0 → frame 5 inner 1 → frame 9 inner 2 → frame 3 inner 3 → frame 7 table for outer index 2 inner 0 → frame 12 inner 1 → frame 6 inner 2 → frame 8 Physical memory frames frame 3 frame 5 frame 6 frame 7 frame 8 frame 9 frame 12 and other frames Physical address frame number page offset (unchanged) The savings The first-level table has an entry for every outer page number, but most entries are invalid and require no second-level table. Second-level tables are allocated only for the outer page numbers that the process actually uses, so the total table size is proportional to the used address space, not to its size.
Figure 9.2b — Two-level page table structure. The logical address is split into an outer page number, an inner page number, and the page offset. The outer page number indexes into the first-level table (the page directory), which points to second-level tables. The inner page number indexes into the selected second-level table, which holds the frame number. The frame number is concatenated with the page offset to form the physical address. Only second-level tables for the used regions of the address space are allocated, so the total table size is proportional to the used space, not the full address space.

4.3 The multi-level page-table walk

The translation of a logical address through a multi-level page table is called a page-table walk. The number of memory accesses the walk requires is proportional to the number of levels.

For a two-level page table, the walk is:

  1. The MMU reads the first-level table entry at the index given by the outer page number. This is a memory access (assuming the entry is not already cached).
  2. The entry gives the physical address of a second-level table. The MMU reads the second-level table entry at the index given by the inner page number. This is a second memory access.
  3. The entry gives the frame number for the page. The MMU concatenates the frame number with the page offset to produce the physical address, and performs the actual data access. This is a third memory access.

The two-level page table therefore requires three memory accesses per logical access, instead of the two of the flat page table. For a four-level page table (as used on x86-64), the walk requires five memory accesses: four for the four levels of the table, plus one for the data. In the worst case, a single load or store instruction would take five times as long as a direct memory access.

This is the price of the multi-level structure, and it is why the TLB (Lesson 9.3) is essential. The TLB caches the final translation — the frame number for a page — not the intermediate entries. On a TLB hit, the entire walk is bypassed: the TLB provides the frame number directly, and only the data access is performed. Because the TLB's hit rate is very high, the average cost of translation is much closer to a single memory access than to the worst-case walk.

The multi-level walk also interacts with the page-table entry's valid bit at each level. The first-level table entry must be valid (indicating that the corresponding second-level table exists) before the second-level table can be read. If it is not valid, the walk terminates immediately: the page is not mapped, and the MMU raises a page fault. This is the mechanism by which the multi-level structure saves memory: a large region of unused address space is represented by a single invalid entry in the first-level table, with no second-level table allocated at all.

4.4 Three-level and four-level page tables

The two-level structure is sufficient for 32-bit systems with a 4 KB page size. The address has 32 bits, of which 12 are the offset and 20 are the page number. Splitting the 20-bit page number into two 10-bit parts gives two-level tables of 210 = 1024 entries each, which is a convenient size: 4 KB per table with 4-byte entries, or 8 KB with 8-byte entries. This is exactly the structure used by the 32-bit x86 architecture (the "PAE" — Physical Address Extension — variant, introduced with the Pentium Pro).

For 64-bit systems, the two-level structure is insufficient. The x86-64 architecture uses a four-level page table, with the page number portion of the address split into four parts of 9 bits each, plus a 12-bit offset. The four levels are:

  • PML4 (Page Map Level 4) — the top level, with 512 entries, each pointing to a PDPT.
  • PDPT (Page Directory Pointer Table) — the second level, with 512 entries, each pointing to a PD.
  • PD (Page Directory) — the third level, with 512 entries, each pointing to a PT. In this level, an entry can also point directly to a 2 MB page (a huge page), which saves a level of the walk.
  • PT (Page Table) — the bottom level, with 512 entries, each pointing to a 4 KB page. This level is not consulted if the corresponding PD entry points to a 2 MB page.

Each level's table has 512 entries, each 8 bytes, so each table is 4 KB — exactly one page. This is deliberate: the tables fit neatly in pages, and the operating system can allocate them from the same frame pool as everything else. The four levels give 4 × 9 = 36 bits of page number, plus 12 bits of offset, for a total of 48 bits of virtual address. The x86-64 architecture allows 48-bit virtual addresses, which is 256 TB of address space per process — enough for any current application, and enough headroom for the future. (A five-level extension, adding a PML5, extends this to 57 bits — 128 PB — on some recent processors.)

The four-level walk requires four memory accesses for the page-table entries plus one for the data, for a total of five memory accesses per logical access in the worst case. This is why the TLB is so important on modern systems: without it, every memory reference would cost five times the raw memory latency.

4.5 Page-table entry fields

A page-table entry is not simply a frame number. Modern page-table entries contain a set of fields that the MMU and the operating system use to implement protection, replacement, and other policies. The fields of the x86-64 page-table entry are representative.

Fields of an x86-64 page-table entry
Field Purpose
Present (P) Indicates whether the entry is valid. If clear, the page is not mapped, and an access raises a page fault.
Read/Write (R/W) Indicates whether the page is writable. If clear, the page is read-only.
User/Supervisor (U/S) Indicates whether the page is accessible from user mode. If clear, the page is accessible only from kernel mode.
Page-Level Write-Through (PWT) Controls the cache write policy for the page.
Page-Level Cache Disable (PCD) Indicates whether the page may be cached.
Accessed (A) Set by the MMU when the page is accessed. Used by the operating system's page-replacement algorithm.
Dirty (D) Set by the MMU when the page is written. Used by the operating system to decide whether the page must be written back to disk when it is evicted.
Page Size (PS) In the PD level, indicates that the entry points to a 2 MB page rather than a PT.
Global (G) Indicates that the page is global and should not be flushed from the TLB on a context switch (used for kernel pages).
NX (No-Execute) Indicates whether the page is executable. Used to implement the W^X policy and to prevent code-injection attacks.
Physical address of the next table or the frame The bulk of the entry: the bits that identify the physical address of the next level's table, or, at the lowest level, the frame that holds the page.

The Accessed and Dirty bits are particularly important for the operating system's page-replacement policy (Lesson 9.6). The operating system periodically scans the page-table entries and clears the accessed bits; pages whose accessed bits are subsequently set are pages that have been referenced recently, and pages whose bits remain clear are candidates for eviction. The dirty bit tells the operating system whether a page must be written to disk before its frame is reused; a clean page (one whose dirty bit is clear) can simply be discarded, because the disk already holds an up-to-date copy.

The NX bit deserves a special mention, because it is a security feature of modern processors. Without the NX bit, a page would be either readable and writable or readable and executable, and a page that held both data and code would be vulnerable to code-injection attacks: a buffer overflow could overwrite a data page with executable code, and the CPU would execute it. The NX bit allows the operating system to mark data pages as non-executable, so an attempt to execute them raises a fault. Together with the read-only marking of code pages, this implements the W^X policy that prevents code from being both writable and executable.

4.6 Inverted page tables

An inverted page table is an alternative to the multi-level structure, used in some systems. Instead of one entry per page of the process's address space, the inverted page table has one entry per frame of physical memory. Each entry records which process and which page occupy the frame.

The inverted page table has a single global structure, not one per process, and its size is proportional to the physical memory, not to the address space. A system with 1 GB of physical memory and 4 KB pages has 218 frames, so the inverted page table has 218 entries — a few megabytes, regardless of how many processes are running or how large their address spaces are. This is a substantial saving over the multi-level structure on systems where the address spaces are large.

The disadvantage is that the table cannot be indexed by page number. To translate an address, the MMU must search the table for the entry whose process identifier and page number match the address. A linear search would be prohibitively slow, so the inverted page table is usually combined with a hash table: the page number is hashed to give a starting position, and the table is searched from there. This is why the inverted page table is sometimes called the hashed page table, though the two are distinct in principle: an inverted page table has one entry per frame, whereas a hashed page table has one entry per page but is indexed by a hash of the page number.

The inverted page table is used in some systems (IBM's PowerPC-based systems, for example, and some RISC architectures), but not in x86-64 or ARM64, which use multi-level page tables. The reason is that the multi-level structure has become the dominant design, partly because the TLB hides the walk's cost in the common case, and partly because the multi-level structure's sparsity advantage is sufficient on most workloads.

4.7 Huge pages

The page sizes discussed so far — 4 KB on x86-64 — are the base page sizes. Modern systems also support huge pages, which are pages much larger than the base size. On x86-64, the supported huge-page sizes are 2 MB (the "large page" or "2 MB page") and 1 GB (the "huge page" or "1 GB page").

Huge pages reduce the size of the page table and improve TLB performance, at the cost of internal fragmentation. Their principal advantages are:

  • Fewer page-table entries. A 2 MB huge page covers 512 base pages, so one huge-page entry replaces 512 base-page entries. The page table for a memory-intensive application can be dramatically smaller — often a factor of 512 — which saves memory and reduces the number of memory accesses in the walk.
  • Better TLB coverage. A TLB with, say, 64 entries can cover 64 × 4 KB = 256 KB with base pages, but 64 × 2 MB = 128 MB with 2 MB huge pages. For applications that touch large amounts of memory randomly — databases, virtual machines, machine-learning training — this is the difference between constant TLB misses and near-constant TLB hits.
  • Shorter page-table walk. Because the PD entry can point directly to a 2 MB page rather than to a PT, the walk for a huge page requires one fewer level of indirection.

The principal disadvantage of huge pages is internal fragmentation. A 2 MB page holds 2 MB of data, and if the application uses only a small fraction of that, the rest is wasted. On a system with many small processes, using 2 MB pages for everything would waste enormous amounts of memory. Huge pages are therefore used selectively, for the specific regions of the address space where the application touches a large amount of memory and the fragmentation cost is acceptable.

On Linux, huge pages can be allocated explicitly through the mmap system call with the MAP_HUGETLB flag, or through the hugetlbfs file system. Some systems also use transparent huge pages (THP), in which the kernel automatically promotes base pages to huge pages when it detects an opportunity, without any application involvement. THP was introduced in the Linux kernel in 2011 and has become the default on many distributions, though its benefits are workload-dependent and it can increase memory consumption significantly on workloads that do not need the large pages.

4.8 The relationship to the TLB

The multi-level page table and the TLB are closely linked. The TLB's purpose is to hide the cost of the page-table walk, and the walk's depth — four levels on x86-64 — is what makes the TLB essential rather than merely helpful.

Two aspects of the multi-level structure affect the TLB's performance.

  • TLB reach. The TLB's reach is the amount of memory its entries can cover: the number of entries multiplied by the page size. With 4 KB pages and, say, 64 entries, the reach is 256 KB, which is smaller than the working set of many modern applications. With 2 MB huge pages, the same TLB covers 128 MB, which is enough for most applications. This is one of the main reasons huge pages are attractive.
  • TLB misses and the walk's cost. On a TLB miss, the MMU must perform the full page-table walk. Because the walk is four levels deep on x86-64, a miss costs four memory accesses. The TLB's hit rate must therefore be very high for the memory system to perform well; a hit rate of 99 percent means an average of 0.04 extra memory accesses per translation, whereas a hit rate of 95 percent means 0.20 extra accesses per translation — a difference of a factor of five in translation overhead.

Lesson 9.3 presents the TLB in detail: its structure, its replacement policy, its interaction with the caches, and the practical consequences of its design for performance. The multi-level page table is the structure that the TLB caches entries from, and understanding the page table is prerequisite to understanding the TLB.

4.9 Common misconceptions

"The multi-level page table is slower than a flat one."

In the worst case, yes: a two-level walk costs three memory accesses instead of two, and a four-level walk costs five instead of two. But the TLB hides the cost in the common case, and the multi-level structure is what makes a 64-bit address space feasible at all.

"Every process has its own first-level table."

Yes, the first-level table is per-process, because each process has its own address space. The second-level tables are also per-process, but they are allocated only for the regions the process uses.

"A page-table entry is just a frame number."

A page-table entry contains the frame number plus a set of control bits: present, read-write, user-supervisor, accessed, dirty, global, and no-execute. These bits implement protection, the replacement policy, and other kernel policies.

"The page-table walk is done by the operating system."

The walk is done by the MMU in hardware. The operating system sets up the page tables and handles faults, but the translation itself is pure hardware.

"The four-level page table means four memory accesses."

A four-level walk requires four page-table reads plus one data access — five memory accesses total in the worst case. On a TLB hit, none of the four reads is performed.

"Huge pages are always better."

Huge pages reduce the page table size and improve TLB coverage, but they increase internal fragmentation. A process that uses a small fraction of a 2 MB huge page wastes the rest.

"The inverted page table is faster than a multi-level table."

The inverted page table avoids the walk but requires a hash lookup, which is not necessarily faster. Its advantage is its fixed size — proportional to physical memory, not to the address space — not its speed.

"The page table fits in one page."

A single level of the multi-level table fits in one page (512 entries × 8 bytes = 4 KB on x86-64). The full page table — all levels combined — is larger, but only the used parts are allocated.

05 Worked example

The following example traces a two-level page-table walk for several logical addresses, showing the intermediate values at each level and the resulting physical addresses. It also computes the memory savings of the two-level structure compared to a flat page table.

A two-level page table for a 32-bit address space

A 32-bit system with a 4 KB page size uses a two-level page table with the following address split:

  • Bits 31–22 (10 bits) — outer page number, indexing the first-level table (the page directory).
  • Bits 21–12 (10 bits) — inner page number, indexing the second-level table.
  • Bits 11–0 (12 bits) — page offset.

The first-level table has 210 = 1024 entries, and so does each second-level table. Each entry is 4 bytes, so each table is 4 KB — one page.

For a particular process, the first-level table has the following entries (simplified for illustration):

Outer index Points to Present?
0second-level table at physical address 0x1000yes
1—no
2second-level table at physical address 0x2000yes
3–255—no
256second-level table at physical address 0x3000yes
257–1023—no

The process uses three second-level tables, at outer indices 0, 2, and 256. The other 1021 entries in the first-level table are invalid, and no second-level table is allocated for them.

We translate three logical addresses.

Address 1: 0x0000_1234

The logical address is 0x00001234. In binary, the three fields are: 

0x00001234 = 0000 0000 0000 0000 0001 0010 0011 0100
             └─outer─┘ └─inner─┘ └───offset───┘
             = 0000000000  0000010010  0011 0100
             = 0x000 (0)   0x012 (18)  0x234
  • Outer index: 0. The first-level table entry at index 0 is valid and points to the second-level table at physical address 0x1000.
  • Inner index: 18 (0x012). The second-level table at 0x1000 has 1024 entries of 4 bytes each. The entry at index 18 is at physical address 0x1000 + 18 × 4 = 0x1048. Suppose this entry holds the frame number 5 (present, read-write).
  • Physical address: frame × 4096 + offset = 5 × 4096 + 0x234 = 0x5000 + 0x234 = 0x5234.

The physical address is 0x5234. The page offset (0x234) is unchanged; only the page number (0x00012) was replaced by the frame number (5).

Address 2: 0x0080_ABCD

The logical address is 0x0080ABCD. In binary: 

0x0080ABCD = 0000 0000 1000 0000 1010 1011 1100 1101
             └─outer─┘ └─inner─┘ └───offset───┘
             = 0000000010  0000001010  1011 1100 1101
             = 0x002 (2)   0x00A (10)  0xBCD
  • Outer index: 2. The first-level table entry at index 2 is valid and points to the second-level table at physical address 0x2000.
  • Inner index: 10 (0x00A). The entry at 0x2000 + 10 × 4 = 0x2028 holds frame number 9.
  • Physical address: 9 × 4096 + 0xBCD = 0x9000 + 0xBCD = 0x9BCD.

The physical address is 0x9BCD.

Address 3: 0x4000_5678

The logical address is 0x40005678. In binary: 

0x40005678 = 0100 0000 0000 0000 0101 0110 0111 1000
             └─outer─┘ └─inner─┘ └───offset───┘
             = 0100000000  0000000001  0101 0110 0111 1000
             = 0x100 (256) 0x001 (1)   0x678
  • Outer index: 256 (0x100). The first-level table entry at index 256 is valid and points to the second-level table at physical address 0x3000.
  • Inner index: 1 (0x001). The entry at 0x3000 + 1 × 4 = 0x3004 holds frame number 3.
  • Physical address: 3 × 4096 + 0x678 = 0x3000 + 0x678 = 0x3678.

The physical address is 0x3678.

Address 4: 0x0000_0000 — a fault

The logical address is 0x00000000. This is a valid address, in the sense that its page number is in range, but suppose the process has not mapped page 0 (for example, page 0 is reserved as a null page, so that a null-pointer dereference faults). The second-level table at outer index 0 has the entry at inner index 0 marked as not present. The walk terminates at the second level, and the MMU raises a page fault. The operating system's fault handler would see that the page is not mapped and would terminate the process with SIGSEGV.

Memory savings

The two-level structure saves memory compared to a flat page table. The flat table for a 32-bit address space would have 220 = 1,048,576 entries of 4 bytes each, or 4 MB. The two-level structure has:

  • First-level table: 1024 entries × 4 bytes = 4 KB.
  • Second-level tables: 3 tables × 1024 entries × 4 bytes = 12 KB.
  • Total: 16 KB.

The two-level structure uses 16 KB instead of 4 MB — a savings of 256×. The savings come from the fact that most of the address space is unused, and the corresponding second-level tables need not be allocated. On a 64-bit system, the savings are far larger: the flat table would be 32 PB, while the multi-level structure might be tens of kilobytes.

Cost of the walk

The price of the savings is the extra memory accesses in the walk. Translating a single address now requires:

  1. Read the first-level table entry (1 memory access).
  2. Read the second-level table entry (1 memory access).
  3. Read or write the data (1 memory access).

Three accesses instead of the two of a flat table, or the one of a direct access with no translation. On a system without a TLB, this would triple the cost of every memory reference. The TLB (Lesson 9.3) caches the final translation — the frame number for a page — so that on a TLB hit, the two page-table reads are skipped and only the data access is performed. On a TLB hit, the multi-level structure costs no more than a flat table.

Extending to four levels

The x86-64 four-level page table works the same way, but with four levels instead of two. The logical address is split into: 

63       48 47    39 38    30 29    21 20       12 11        0
+-----------+--------+--------+--------+-----------+-----------+
| sign ext  | PML4   | PDPT   |  PD    |    PT     |  offset   |
| (16 bits) | (9)    | (9)    | (9)    |   (9)     |  (12)     |
+-----------+--------+--------+--------+-----------+-----------+

Each of the four fields (PML4, PDPT, PD, PT) is 9 bits, so each level's table has 29 = 512 entries. Each entry is 8 bytes, so each table is 4 KB — one page. The walk is four memory accesses, plus the data access, for a total of five. This is the structure that every x86-64 processor uses for its general-purpose memory, and it is the structure that the TLB caches entries from.

The process's page table on x86-64 might have several PML4 entries (one for each 512 GB region of the address space the process uses), a few PDPT entries per PML4 entry, several PD entries per PDPT entry, and a few PT entries per PD entry. The total size depends on the pattern of the process's memory usage, but for a typical process it is on the order of tens of kilobytes.

06 Interactive activity

Activity · implement and explore multi-level page tables

The goal of this activity is to implement a two-level page table, trace the walk, and observe the structure in a real system. Work through the steps in your course VM.

  1. Implement a two-level page table. Write a program that defines a two-level page table for a 32-bit address space with a 4 KB page size. The program should:
    • Have a first-level table with 1024 entries.
    • Have second-level tables allocated as needed.
    • Support allocating a page at a given virtual address.
    • Support translating a virtual address to a physical address.
    #include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define PAGE_SIZE   4096
#define ENTRIES     1024
#define OUTER_SHIFT 22
#define INNER_SHIFT 12

struct second_level {
    uint32_t entries[ENTRIES];
    int      present;
};

struct first_level {
    struct second_level *tables[ENTRIES];
};

struct first_level dir;

uint32_t *alloc_page_table_entry(uint32_t vaddr) {
    uint32_t outer = (vaddr >> OUTER_SHIFT) & 0x3FF;
    uint32_t inner = (vaddr >> INNER_SHIFT) & 0x3FF;

    if (!dir.tables[outer]) {
        dir.tables[outer] = calloc(1, sizeof(struct second_level));
        if (!dir.tables[outer]) return NULL;
        dir.tables[outer]->present = 1;
    }
    return &dir.tables[outer]->entries[inner];
}
  2. Test with the worked example. Populate the page table with the entries from the worked example (second-level tables at outer indices 0, 2, and 256, with the entries listed). Then translate the four addresses and verify that the physical addresses match the worked example. 
    /* helper: set a mapping */
void map(uint32_t vaddr, uint32_t frame, int prot) {
    uint32_t *entry = alloc_page_table_entry(vaddr);
    *entry = (frame << 12) | (prot & 0xFFF);
}

/* helper: translate */
uint32_t translate(uint32_t vaddr, int *fault) {
    uint32_t outer = (vaddr >> OUTER_SHIFT) & 0x3FF;
    uint32_t inner = (vaddr >> INNER_SHIFT) & 0x3FF;
    uint32_t off   = vaddr & (PAGE_SIZE - 1);

    if (!dir.tables[outer] || !dir.tables[outer]->present) {
        *fault = 1; return 0;
    }
    uint32_t e = dir.tables[outer]->entries[inner];
    if (!(e & 1)) { *fault = 1; return 0; }

    uint32_t frame = e >> 12;
    *fault = 0;
    return (frame << 12) | off;
}
  3. Try fault cases. Add test cases that fault:
    • An address whose outer index has no second-level table (e.g., outer index 1).
    • An address whose inner entry is marked not present.
    Verify that the translate function correctly reports a fault for both.
  4. Measure the memory savings. Modify the program to report the total memory allocated for the page table, and compare it to the 4 MB that a flat table would require. Compute the savings ratio. 
    size_t page_table_size(void) {
    size_t total = sizeof(dir);
    for (int i = 0; i < ENTRIES; i++)
        if (dir.tables[i])
            total += sizeof(struct second_level);
    return total;
}
  5. Extend to three levels. Modify the program to use a three-level page table, with the 32-bit page number split into three parts: 10 bits for the top level, 6 bits for the middle, and 4 bits for the bottom — or any other split you choose. Trace a walk through the three levels and compare the total memory use to the two-level version. 
    /* For a three-level structure, the page number is split as:
   - top:     bits 31-22 (10 bits)
   - middle:  bits 21-16 (6 bits)
   - bottom:  bits 15-12 (4 bits)
   - offset:  bits 11-0  (12 bits)
   Each level has 2^n entries, where n is the number of bits. */
  6. Inspect the x86-64 page table in gdb. On a Linux x86-64 system, use gdb to inspect the page table of a running process. 
    gdb /bin/ls
(gdb) start
(gdb) info registers cr3
(gdb) quit
    The CR3 register holds the physical address of the PML4 (the top-level page table). Its value should be a multiple of 4 KB, because the PML4 itself is one page.
  7. Read the kernel's pagemap interface. The /proc/<pid>/pagemap file gives per-page information about a process's address space, including the frame number. Reading it requires root privileges, but if you have access, you can extract the frame number for a virtual address and confirm that it matches the page-table walk. 
    sudo cat /proc/self/pagemap | head -c 64 | xxd
    The format is documented in man 5 proc. Each 8-byte entry corresponds to one page of the process's virtual address space, and the low bits include the present bit, the swapped bit, and the frame number.
  8. Observe transparent huge pages. On a Linux system with transparent huge pages (THP) enabled, examine the THP statistics. 
    cat /sys/kernel/mm/transparent_hugepage/enabled
cat /proc/meminfo | grep -i huge
grep -i anonhugepage /proc/vmstat
    The first shows whether THP is enabled (always, madvise, or never). The second shows the huge-page sizes and totals. The third shows statistics on anonymous huge pages. What is the current policy, and how many huge pages has the system allocated?
  9. Read the OSTEP chapter. Read OSTEP Chapter 20, Paging: Smaller Tables. Compare its presentation of the multi-level page table to this lesson. What additional considerations does OSTEP raise — for example, the exact space savings for a specific example, the cost of the walk, and the alternatives to multi-level tables? Write a short paragraph summarising the differences.

Reflect: the multi-level page table is a beautiful example of the way that hardware and software cooperate to solve a problem neither can solve alone. The hardware cannot decide which regions of the address space a process will use — that is a policy decision — but it can walk a hierarchical structure quickly. The software cannot perform the walk on every memory access — that would be too slow — but it can set up the structure to have a shape that the hardware can traverse. What other structures in a computer system are hierarchical in the same way? Consider the file system, the DNS, the class hierarchy of an object-oriented program, and the directory structure of a large codebase. What do they have in common with the multi-level page table?

07 Knowledge check

Check your understanding

Question 1

Explain the size problem with a flat page table. Why is a flat page table infeasible on a 64-bit system, and what is the fundamental observation that the multi-level page table exploits?

Show answer
A flat page table is an array with one entry per page of the process's logical address space. On a 64-bit system with a 4 KB page size, the address space is 264 bytes = 252 pages, so the flat table would need 252 entries. With 8-byte entries, the table would be 255 bytes = 32 PB. Even the largest servers have only terabytes of memory, and the table would be needed once per process, so a flat page table is not merely impractical — it is physically impossible. On a 32-bit system, the problem is less severe but still significant: a flat table would be 220 entries × 4 bytes = 4 MB per process, which on a system with hundreds or thousands of processes is a significant fraction of the physical memory. The fundamental observation that the multi-level page table exploits is that a process uses only a small fraction of its address space. A typical program has a few megabytes of code, data, heap, and stack, out of an address space of 264 bytes. The vast majority of the address space is unused. A flat page table has entries for every page — including the unused ones — but a multi-level structure can represent a large unused region with a single invalid entry at the top level, with no lower-level tables allocated for it. The savings are proportional to the ratio of the unused space to the used space, which on modern systems is enormous.

Question 2

Describe the structure of a two-level page table. What are the two levels called, how is the logical address split, and how does the page-table walk proceed? Why does the structure save memory?

Show answer
A two-level page table divides the page number portion of the logical address into two parts: an outer page number and an inner page number. There are two levels of tables. The first-level table (also called the page directory or top-level table) is indexed by the outer page number; each entry in it points to a second-level table, or is marked invalid. The second-level table is indexed by the inner page number; each entry in it holds the frame number for the corresponding page. The page-table walk proceeds as follows. First, the outer page number indexes into the first-level table, yielding the address of the appropriate second-level table. Second, the inner page number indexes into that second-level table, yielding the frame number for the page. Third, the frame number is concatenated with the page offset (which is unchanged by the walk) to produce the physical address. The walk requires two memory accesses for the table entries (the first-level entry and the second-level entry), plus the data access. The structure saves memory because second-level tables are allocated only for the outer page numbers that the process actually uses. If a process uses only a few regions of its address space, the first-level table has invalid entries for most of the other outer page numbers, and no second-level tables are allocated for them. In the worked example, a process with 3 used outer page numbers out of 1024 possible uses only 3 second-level tables, so the total page-table memory is 4 KB + 3 × 4 KB = 16 KB, compared to the 4 MB a flat table would require. The savings factor is the ratio of the number of possible outer page numbers to the number actually used.

Question 3

Describe the x86-64 four-level page table. How is the logical address split, what are the four levels called, and how many entries does each level have? What is the role of the page offset, and why is the four-level structure used rather than a two-level one?

Show answer
The x86-64 four-level page table splits the 48-bit canonical virtual address into five parts: four 9-bit page number fields and a 12-bit page offset. The four levels are:
  • PML4 (Page Map Level 4) — the top level, indexed by bits 47–39.
  • PDPT (Page Directory Pointer Table) — the second level, indexed by bits 38–30.
  • PD (Page Directory) — the third level, indexed by bits 29–21.
  • PT (Page Table) — the bottom level, indexed by bits 20–12.
Each field is 9 bits, so each level's table has 29 = 512 entries. Each entry is 8 bytes, so each table is 4 KB — exactly one page. The page offset is the low 12 bits of the address (bits 11–0), and it is not used by the walk. It is concatenated with the frame number from the PT entry to form the physical address. The offset is unchanged by the walk because pages and frames are the same size. The four-level structure is used instead of a two-level one because the 48-bit address space cannot be handled by a two-level structure with reasonable table sizes. A two-level structure for 48 bits would have to allocate 236 pages per level, which is far too many entries per table. The four-level structure keeps each table at 512 entries — a single page — which is a convenient size for allocation and for the TLB's reach. The walk requires four memory accesses for the table entries plus one for the data, for a total of five in the worst case. The TLB hides the cost of the walk in the common case, because on a TLB hit the entire walk is bypassed and only the data access remains.

Question 4

Describe the fields of a page-table entry. What is the purpose of the valid (present) bit, the dirty bit, the accessed bit, and the no-execute bit? How do these fields support protection, the replacement policy, and security?

Show answer
A page-table entry contains the frame number (or, in the intermediate levels, the address of the next table) plus a set of control bits. The important fields are: the present bit, which indicates whether the entry is valid; the read/write bit, which indicates whether the page is writable; the user/supervisor bit, which indicates whether the page is accessible from user mode; the accessed bit, which the MMU sets when the page is accessed; the dirty bit, which the MMU sets when the page is written; the no-execute bit, which indicates whether the page is executable; and the page size bit, which indicates whether the entry points to a huge page. The present bit is the foundation of the multi-level structure's memory savings: if the entry at any level is not present, the walk terminates and no lower-level tables need be consulted. It is also the mechanism by which demand paging works (Lesson 9.4): a page that is not currently in memory has its present bit clear, and an access to it raises a page fault. The dirty bit supports the replacement policy (Lesson 9.6). When the operating system evicts a page, it must write the page back to disk if the page has been modified. The dirty bit tells the operating system whether the page has been modified since it was loaded; a page whose dirty bit is clear can simply be discarded, because the disk already holds an up-to-date copy. The accessed bit is used by the replacement algorithm to identify pages that have been recently used. The operating system periodically clears the accessed bits, and pages whose bits remain clear after a period are candidates for eviction. The no-execute bit is a security feature. Without it, a page would be either readable and writable, or readable and executable, and a page that held both data and code would be vulnerable to code-injection attacks. The NX bit allows the operating system to mark data pages as non-executable, so an attempt to execute them raises a fault. Together with the read-only marking of code pages, this implements the W^X policy.

Question 5

What are huge pages, and what advantages do they offer? What is their principal disadvantage, and under what circumstances would you choose to use them?

Show answer
Huge pages are pages that are much larger than the base page size. On x86-64, the base page size is 4 KB, and the huge-page sizes are 2 MB and 1 GB. Huge pages offer three principal advantages. First, they reduce the size of the page table: a 2 MB page covers 512 base pages, so one huge-page entry replaces 512 base-page entries. The page table for a memory-intensive application can be dramatically smaller, which saves memory and reduces the number of memory accesses in the walk. Second, they improve TLB coverage: a TLB with 64 entries can cover 64 × 4 KB = 256 KB with base pages, but 64 × 2 MB = 128 MB with huge pages. This is the difference between constant TLB misses and near-constant TLB hits for applications that touch large amounts of memory. Third, they shorten the page-table walk: because the PD entry can point directly to a huge page rather than to a PT, the walk for a huge page requires one fewer level of indirection. The principal disadvantage of huge pages is internal fragmentation. A 2 MB page holds 2 MB of data, and if the application uses only a small fraction of that, the rest is wasted. On a system with many small processes, using 2 MB pages for everything would waste enormous amounts of memory. You would choose huge pages when the application's working set is large and it touches memory with poor locality — databases, virtual machines, machine-learning training, scientific simulations — where the page-table savings and TLB coverage outweigh the internal fragmentation. You would avoid them for processes with small, scattered memory usage. Linux supports both explicit huge-page allocation (via mmap with MAP_HUGETLB or hugetlbfs) and transparent huge pages (THP), in which the kernel promotes base pages to huge pages automatically when it detects an opportunity.

08 Unit discussion

Discussion prompt

The multi-level page table is an elegant solution to a problem that seems, at first glance, to have no solution. The problem is that a flat page table is too large to be allocated, and the solution is to make the table hierarchical, allocating only the parts that correspond to the address space the process actually uses. The saving comes from the sparsity of a process's address space: the fact that a 64-bit process uses only a small fraction of its 264 possible addresses.

This pattern — solving a big problem by exploiting sparsity — recurs throughout computer science. A hash table stores only the keys that have been inserted, not all possible keys. A sparse matrix stores only the non-zero elements, not the full grid. A trie stores only the prefixes that have been used. A B-tree stores only the keys that have been inserted, with internal nodes that branch only where necessary. A hierarchical directory stores only the paths that have been created. In each case, the structure is sparse because the actual data is sparse, and the representation exploits that sparsity to save memory.

The multi-level page table is a particularly clear example of this pattern, because the hierarchy is fixed — four levels on x86-64, five on some newer processors — and the sparsity is exploited at every level. But is the hierarchical structure the right one for all workloads? Some workloads have dense, uniform access patterns — a machine-learning training loop that touches every element of a large tensor, for example — and for those workloads, the hierarchy is more overhead than it is worth. Huge pages, discussed in this lesson, are one response: they use a shallower hierarchy for the memory regions where sparsity does not apply.

What would a memory-management system designed for dense workloads look like? Would it use a different page-table structure? Would it use a different page size? Would it use a completely different approach to address translation? Consider the workloads you know — a web browser, a database, a machine-learning training run, a compiler, a graphics renderer — and think about what their memory access patterns look like and what structure would serve them best. Post your response to the Unit 9 discussion forum and reply to at least two classmates. Supports CLO1, CLO4, and CLO6.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Lesson 9.3. Aim to spend 60–90 minutes on it.

  1. Compute flat page table sizes. For the following configurations, compute the size of a flat page table (in bytes, KB, MB, and GB as appropriate):
    • 32-bit address space, 4 KB pages, 4-byte entries.
    • 32-bit address space, 4 KB pages, 8-byte entries.
    • 64-bit address space, 4 KB pages, 8-byte entries.
    • 64-bit address space, 2 MB pages, 8-byte entries.
    • 48-bit address space, 4 KB pages, 8-byte entries (x86-64 with 48-bit virtual addresses).
    For each, state whether the size is feasible on a system with 16 GB of physical memory.
  2. Trace a two-level walk. For the two-level page table in the worked example, translate the following addresses, showing the outer index, inner index, offset, the first-level table entry, the second-level table entry, the frame number, and the physical address:
    • 0x0000_0000
    • 0x0000_1000
    • 0x0000_FFFF
    • 0x0020_0000
    • 0x0080_0000
    • 0x4000_0000
    • 0x8000_0000
    • 0xC000_0000
    For each, state whether the address is mapped, and if not, explain why.
  3. Design a three-level page table. A 32-bit address space is to be divided into a three-level page table. Choose how to split the 20 bits of page number (excluding the 12-bit offset) among the three levels, and justify your choice. What is the number of entries in each level's table? What is the size of each table? How many memory accesses does the walk require?
  4. Explain the four-level walk. Write a step-by-step description of the x86-64 four-level page-table walk, for a logical address. Your description should include: the name of each level, the bits of the address that index into it, the number of entries in each level's table, and what the entry points to. Then draw a diagram showing the four levels and the final concatenation with the page offset.
  5. Compute the memory savings of a two-level table. Consider a process that uses only three regions of its 32-bit address space: 4 MB at the bottom (for code and data), 8 MB in the middle (for a heap), and 2 MB near the top (for the stack). Assume a 4 KB page size, a two-level page table with 10-bit outer and inner indices, and 4-byte entries. How many second-level tables are needed? What is the total size of the process's page table? Compare to the size of a flat page table for the same process.
  6. Investigate huge pages. Write a program that uses mmap with and without the MAP_HUGETLB flag to allocate a large region of memory (say, 100 MB). Then use /proc/self/smaps or /proc/meminfo to observe the difference. How much page-table memory does each version use? What is the TLB coverage of each? Note that MAP_HUGETLB may require root privileges or a pre-allocated pool of huge pages. 
    void *p = mmap(NULL, 100 * 1024 * 1024,
               PROT_READ | PROT_WRITE,
               MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB,
               -1, 0);
if (p == MAP_FAILED) {
    perror("mmap");
    /* try without MAP_HUGETLB */
}
  7. Compare page-table structures. Write a short paragraph (200–250 words) comparing the multi-level page table, the inverted page table, and the hashed page table. For each, describe the structure, the size, the lookup mechanism, and the advantages and disadvantages. Then state which structure you would choose for a hypothetical new architecture, and why.
  8. Reflect. In your own words, explain why the multi-level page table is possible — that is, what property of a process's address space makes the hierarchical structure work. Then describe one situation in your own experience — a program you have written or a system you have used — where the sparsity of memory usage was important. What was the pattern, and how did it affect the memory-system behaviour?

10 Summary

  • A flat page table has one entry per page of the process's logical address space. On a 64-bit system with a 4 KB page size, it would be 32 PB — far larger than any physical memory, and needed once per process. On a 32-bit system, it would be 4 MB per process, which is a significant fraction of physical memory on a system with many processes.
  • A multi-level page table divides the page number into several parts, each indexing a different level of the table hierarchy. The structure is sparse: only the parts of the table that correspond to the regions the process actually uses are allocated, so the total table size is proportional to the used address space, not to its total size.
  • In a two-level page table, the logical address is split into an outer page number, an inner page number, and the page offset. The outer page number indexes the first-level table (page directory), whose entry points to a second-level table; the inner page number indexes that table, whose entry holds the frame number. The page-table walk requires two memory accesses for the table entries plus one for the data.
  • On x86-64, the four-level page table splits the 48-bit virtual address into a 12-bit page offset and four 9-bit fields: PML4, PDPT, PD, and PT. Each table has 512 entries of 8 bytes, so each table is exactly one 4 KB page. The walk requires four memory accesses for the tables plus one for the data.
  • The page-table entry contains the frame number (or the address of the next table) plus a set of control bits: present, read/write, user/supervisor, accessed, dirty, global, page size, and no-execute. These bits implement protection, the page-replacement policy, and security features such as W^X.
  • The present bit is the key to the multi-level structure's memory savings: if an entry at any level is not present, the walk terminates, and no lower-level tables need be allocated. It is also the mechanism by which demand paging works.
  • An inverted page table has one entry per frame of physical memory, not per page of the address space. Its size is proportional to physical memory, regardless of the number or size of the processes. To translate an address, the MMU must search the table, typically using a hash function.
  • A hashed page table has one entry per page, but is indexed by a hash of the page number rather than by the page number directly. Both the inverted and hashed structures are alternatives to the multi-level page table, and are used in some architectures.
  • Huge pages are pages much larger than the base size (2 MB and 1 GB on x86-64). They reduce the page-table size, increase TLB coverage, and shorten the page-table walk, at the cost of increased internal fragmentation. They are used selectively for memory-intensive applications, and Linux supports both explicit allocation and transparent huge pages.
  • The multi-level page table and the TLB are closely linked: the TLB caches final translations so that on a TLB hit, the entire walk is bypassed. The walk's depth — four levels on x86-64 — is what makes the TLB essential, and the TLB's effectiveness depends on the locality of the program's accesses. The TLB is the subject of Lesson 9.3.

Looking ahead

This lesson presented the structure of the page table, and in particular the multi-level page table that modern systems use. It showed that the multi-level structure solves the size problem by exploiting the sparsity of a process's address space, at the cost of a deeper page-table walk. Lesson 9.3 presents the translation lookaside buffer (TLB), the small hardware cache of page-table entries that hides the cost of the walk in the common case. The lesson covers the TLB's structure, its hit rate and miss cost, its replacement policy, its interaction with the caches, the effect of context switches on the TLB, the use of address-space identifiers (ASIDs) to avoid flushing the TLB, and the practical considerations that determine the TLB's effectiveness. The TLB is the mechanism that makes paging practical, and understanding it is essential to understanding the performance of modern memory systems.

11 References

  • Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 20, Paging: Smaller Tables. Available online at ostep.org.
  • Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 9, Section 9.4, and Chapter 10, Sections 10.1–10.3.
  • Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3, Section 3.3.
  • Bryant, R. E., & O'Hallaron, D. R. Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 9, Virtual Memory, sections 9.6–9.7.
  • Intel Corporation. Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3: System Programming Guide, Chapter 4, Paging.
  • Jacob, B., & Mudge, T. Virtual Memory: Issues of Implementation and Performance. IEEE Computer, 1998. A survey of virtual memory implementations across architectures, including the alternatives to multi-level page tables.
  • Talluri, M., & Hill, M. D. Surpassing the TLB Performance of Segmentation for Pure Demand Paging. Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, 1994. A paper on the trade-offs of different page-table structures.
  • Love, R. Linux Kernel Development, 3rd ed., Chapter 12, Memory Management. The Linux kernel's implementation of the multi-level page table, including its handling of huge pages.
  • Linux kernel documentation: Documentation/arch/x86/x86_64/ and Documentation/vm/.
  • Linux man-pages: man 5 proc (the pagemap interface), man 2 mmap (the MAP_HUGETLB flag), man 2 madvise (the MADV_HUGEPAGE flag).
👤