7.7 Multi-Level Paging, Inverted Page Tables & Segmentation

Back to Operating Systems Notes

📚Module 07: Main Memory ManagementTopic 7.7⏱️24 min read

🎯High-Yield For:Computer Science Foundations • Systems Engineering • Advanced Architecture

💡 Core Intuition

🍳 The Everyday Analogy: The Multi-Volume Encyclopedia & Specialized Dossiers

Imagine organizing the collective archives of human knowledge:

Architecture Flow

The Knowledge Indexing Pipeline

Contrasting single-level directories, hierarchical tables of contents, and modular folders

💡 Hover or click any card for deep-dive operational details

📜The Problem

One Giant 10,000-Page Index

Single-Level Page Table

A single index book that lists every topic word across 10,000 pages.

→

Divide the Directory

📚Hierarchical

Table of Contents of Volumes

Multi-Level Paging

Master Index -> Volume Index -> Chapter Index -> Topic.

→

User-Centric Reorganization

📁Logical Segments

Modular Departmental Folders

Segmentation

Instead of arbitrary fixed page counts, documents are sorted into logical folders.

• Multi-Level Paging: Solves the gigantic page table problem by paging the page table itself into hierarchical tiers.
• Inverted Page Table: Flips the mapping by maintaining one entry per physical RAM frame rather than per virtual page.
• Segmentation: Bridges user-program semantics (code, stack, heap, data) to physical memory using variable-sized logical segments.

---

💻 Bridging to Computer Science

On a standard 32-bit architecture with $4\text{ KB}$ pages ($2^{12}\text{ B}$), a process's virtual address space has:

$\text{Total Pages} = \frac{2^{32}\text{ B}}{2^{12}\text{ B}} = 2^{20} = 1,048,576\text{ Pages}$

With a $4\text{-byte}$ Page Table Entry (PTE), each process requires:

$\text{Page Table Size} = 2^{20} \times 4\text{ Bytes} = \mathbf{4\text{ MB}}$

If 100 processes run simultaneously, the kernel wastes $400\text{ MB}$ of physical RAM solely on page table metadata! Worse, on 64-bit systems ($2^{64}$ address space), a linear page table would require petabytes of storage.

Computer systems resolve this crisis through three architectural pillars:

1. Multi-Level Hierarchical Paging: Breaking page tables into smaller chunks that can be paged out or allocated non-contiguously.
2. Inverted Page Tables: Inverting the lookup by indexing physical DRAM frames instead of virtual pages.
3. Segmentation: Structuring memory according to the programmer's logical view of code, data, and stack modules.

---

📚 Core Deep-Dive & Concepts

1. Multi-Level Hierarchical Paging

The core insight of multi-level paging is simple: Page the page table itself!

Two-Level Hierarchical Paging Address Translation

Translating 32-bit virtual addresses through Page Directory and Page Table tiers

CPU Core

Outer Page Table (Directory)

Inner Page Table (Level 2)

Physical DRAM Bus

1

CPU Core→Outer Page Table (Directory)

Index Outer Directory via PTBR + (p1 × Entry Size)

2

Outer Page Table (Directory)→Inner Page Table (Level 2)

Resolve Base Pointer to Inner Page Table

3

Inner Page Table (Level 2)→Physical DRAM Bus

Index Inner Table with p2 & Extract Frame f

4

CPU Core→Physical DRAM Bus

Synthesize Physical Address [f | d] & Read/Write Word

Why Multi-Level Paging Saves Massive Memory

• In a single-level page table, all $1\text{ Million}$ entries must be allocated contiguously in physical RAM from the start, even if the program only uses a few kilobytes of code and stack.
• In a multi-level scheme, only the top-level Outer Page Table ($4\text{ KB}$) is permanently resident.
• Inner page tables are allocated dynamically on demand. If vast regions of the virtual address space between the heap and the stack are unmapped, their corresponding inner page tables are never created!

Level Calculation Formula

The number of pages required at any level $k$ is governed by:

$\text{Pages at Level } k = \frac{\text{Number of entries from level } (k-1) \times \text{PTE Size}}{\text{Page Size}}$

---

2. Derivation of the Optimal Page Size (Silberschatz Model)

What is the mathematically ideal page size that minimizes total system memory waste? Total overhead consists of two conflicting terms:

1. Page Table Overhead: As page size $y$ decreases, the number of pages increases, causing page table size to explode.
2. Internal Fragmentation Overhead: On average, the final page of a process wastes half of a page ($\frac{y}{2}$). As page size $y$ increases, internal fragmentation explodes.

Formal Mathematical Derivation

Let:

• $x$ = Average Process Size (in bytes).
• $y$ = Page Size (in bytes).
• $z$ = Size of each Page Table Entry (in bytes).

$\text{Number of Pages per Process} = \frac{x}{y}$

$\text{Page Table Size (Overhead 1)} = \frac{x}{y} \cdot z$

$\text{Average Internal Fragmentation (Overhead 2)} = \frac{y}{2}$

$\text{Total Memory Waste } S(y) = \frac{x \cdot z}{y} + \frac{y}{2}$

To find the minimum overhead, differentiate $S(y)$ with respect to $y$ and set to zero:

$\frac{dS}{dy} = -\frac{x \cdot z}{y^2} + \frac{1}{2} = 0$

$\frac{x \cdot z}{y^2} = \frac{1}{2}$

$y^2 = 2 \cdot x \cdot z$

$\mathbf{y = \sqrt{2 \cdot x \cdot z}}$

Fundamental Theorem of Optimal Page Size:
The optimal page size $y$ that minimizes aggregate memory waste is the geometric mean product $\sqrt{2xz}$.

Numerical Application

• If an average process size $x = 1\text{ MB} = 2^{20}\text{ B}$ and $\text{PTE Size } z = 8\text{ Bytes}$: $y = \sqrt{2 \times 10^6 \times 8} = \sqrt{16 \times 10^6} = 4000\text{ Bytes} \approx \mathbf{4\text{ KB}}$
• This elegant mathematical derivation proves why modern operating systems universally converge on $4\text{ KB}$ page sizes!

---

3. Inverted Page Tables

In 64-bit systems, multi-level paging requires $4$ to $5$ levels of table indirection. To eliminate multi-level tables entirely, architectures such as IBM PowerPC and UltraSPARC implement the Inverted Page Table:

---

4. Segmentation: The Programmer's View of Memory

Paging divides memory into arbitrary fixed power-of-two boundaries without regard for program structure. In contrast, Segmentation organizes memory into logical, variable-sized units reflecting programmer intent:

Segmentation Hardware Address Translation Blueprint

Translating two-dimensional logical addresses (s, d) through limit verification and base addition

CPU Core

Segment Table (STBR)

Protection Comparator

Physical RAM

1

CPU Core→Segment Table (STBR)

Index Segment Table using Segment Number (s)

2

Segment Table (STBR)→Protection Comparator

Verify Offset Bounds: d < Limit

3

Protection Comparator→Physical RAM

Compute Physical Address: Base + d

Anatomy of Logical Segments

A program is composed of distinct functional segments:

1. Code Segment (Text): Read-Only, Executable.
2. Data Segment: Global/Static variables, Read-Write, Non-Executable.
3. Stack Segment: Function stack frames, grows downwards.
4. Heap Segment: Dynamic memory allocations (malloc), grows upwards.

The Segment Table

Each segment entry stores:

• Base: The starting physical address where the segment resides in RAM.
• Limit: The length (size) of the segment.

$\text{Validation Condition: } \quad 0 \le d < \text{Limit}$

$\text{Physical Address } = \text{Base} + d$

If an instruction attempts to access offset $d \ge \text{Limit}$, the MMU triggers a Segmentation Fault trap to the OS kernel.

---

5. Architectural Synthesis: Segmented Paging

Pure segmentation suffers from external fragmentation because segments are variable in length. Pure paging suffers from lack of logical protection boundaries.

Modern architectures (such as Intel x86 Protected Mode) combine both into Segmented Paging:

---

6. Architectural Impact of Page Size Variations

Metric / Parameter	Impact of INCREASING Page Size ($4\text{ KB} \to 2\text{ MB}$)	Impact of DECREASING Page Size ($4\text{ KB} \to 512\text{ B}$)
Page Table Size	Decreases (Fewer pages needed to cover memory)	Increases (Millions of additional PTE entries)
TLB Hit Ratio	Increases (Each TLB entry covers vastly more RAM)	Decreases (TLB reach shrinks; thrashing occurs)
Internal Fragmentation	Increases (Average waste $\approx \text{Page Size} / 2$)	Decreases (Minimal wasted slack on final page)
Disk I/O Transfer Speed	Increases (Larger sequential block transfers from SSD)	Decreases (Seek time dominates tiny random page I/Os)
Locality of Reference	Lower spatial precision; loads irrelevant data	Higher spatial precision; loads only needed bytes

---

🏭 In The Real World: Production Case Study

WebAssembly (Wasm) Linear Memory & Modern Memory Safety

WebAssembly runs high-performance native code inside web browsers and cloud edge workers (Cloudflare Workers, Fastly). Instead of raw pointers, Wasm uses a software-enforced form of Segmentation with Bounds Checking:

WebAssembly Sandboxed Linear Memory Architecture

Hardware-backed segmented isolation running untrusted bytecode at native speeds

Layer 1: Execution

Wasm Instance & Linear Memory Array

📦

Contiguous byte array (WebAssembly.Memory) with hardware base pointer and page limit.

64 KB Wasm Page GranularityBase: 0x7fff0000Limit: 64 MB

↓Memory access request: wasm_load(offset)

Layer 2: Protection

4 GB Hardware Guard Page Region

🛡️

Zero-cost hardware bounds checking. JIT compiler reserves unmapped virtual space beyond the limit.

Zero software if-checksImmediate MMU protection trap on out-of-bounds

1. Hardware-Accelerated Bounds Checking:
   • Modern 64-bit JIT compilers (V8, SpiderMonkey) reserve an unmapped $4\text{ GB}$ guard page region directly following the Wasm linear memory.
   • Any out-of-bounds access immediately triggers a hardware MMU page protection trap without requiring explicit software comparison instructions on every memory load!

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: In a 2-level paging scheme on a 32-bit machine, the page size is $4\text{ KB}$. The first level page table has $1024$ entries.

1. How many bits are allocated for the page offset?
2. How many bits are allocated for the first-level page number ($p_1$)?
3. How many bits are allocated for the second-level page number ($p_2$)?
4. How many entries are present in each second-level page table?

Answer:

1. Offset Bits ($d$):
   • $\text{Page Size} = 4\text{ KB} = 2^{12}\text{ bytes} \implies \mathbf{d = 12\text{ bits}}$.
2. First-Level Bits ($p_1$):
   • Number of entries in first-level table $= 1024 = 2^{10} \implies \mathbf{p_1 = 10\text{ bits}}$.
3. Second-Level Bits ($p_2$):
   • Total logical address bits $= 32$.
   • $\text{LA} = p_1 + p_2 + d \implies 32 = 10 + p_2 + 12 \implies \mathbf{p_2 = 10\text{ bits}}$.
4. Entries in Second-Level Table:
   • Number of entries $= 2^{p_2} = 2^{10} = \mathbf{1024\text{ entries}}$.

---

Question 2: Derive the optimal page size for a system where the average process size is $256\text{ KB}$ and each page table entry occupies $8$ bytes. Answer:

1. Formula: $y = \sqrt{2 \cdot x \cdot z}$
2. Substitute Parameters:
   • $x = 256\text{ KB} = 256 \times 1024\text{ bytes} = 262,144\text{ bytes} = 2^{18}\text{ bytes}$.
   • $z = 8\text{ bytes} = 2^3\text{ bytes}$.
3. Calculate: $y = \sqrt{2 \times 2^{18} \times 2^3} = \sqrt{2^{22}} = 2^{11}\text{ bytes} = \mathbf{2048\text{ bytes}} = \mathbf{2\text{ KB}}$
4. Result: The mathematically optimal page size is $2\text{ KB}$.

Common Interview Traps

• The Inverted Page Table Sharing Dilemma: Traditional page tables easily support shared memory (e.g. shared libc.so) by pointing entries in two different processes to the same frame. In an Inverted Page Table, each frame has strictly one entry containing a single [PID, Page]. Supporting shared memory in an IPT requires complex aliasing mechanisms or hashing chains!
• Segmentation vs Paging Fragmentation Trap: Never say segmentation eliminates internal and external fragmentation. Segmentation suffers from external fragmentation because segments have variable lengths! Only paging eliminates external fragmentation.
• The "Multi-Level Paging Accelerates Access" Myth: Multi-level paging slows down memory translation (each additional level requires an additional DRAM access on a TLB miss). Its sole purpose is to save memory space, never to increase speed.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic7.6 TLB & Effective Access TimeNext Topic →8.1 Demand Paging & Page Faults