3.3 Inverted Page Tables, Segmentation & EMAT Performance Analysis

Back to DBMS Notes

📚03Topic 3.3⏱️15 min

🎯High-Yield For:Inverted Page Tables and Segmentation solve the ultimate physical scaling limits of 64-bit address spaces, decoupling page table size from virtual memory and enforcing modular memory protection in modern operating systems.

💡 Core Intuition:

🍳 The Everyday Analogy:

Imagine a world-famous grand luxury hotel with exactly $500$ guest rooms.

• The Traditional (Forward) Approach: The hotel reception keeps an alphabetical ledger containing an entry for every single registered citizen in the nation (tens of millions of pre-printed pages), stating which room they are staying in today. Over $99.99\%$ of the ledger pages are blank, yet the hotel must build a separate warehouse just to store the book!
• The Inverted Approach: The receptionist discards the national citizen catalog and looks directly at the Keycard Wall Behind the Desk. The board has exactly $500$ slots—one for each physical room in the building. Each slot holds a single card: Room 104 -> Occupied by Guest ID #98,412 (Page 4).

The size of the keycard board depends strictly on the number of physical rooms in the hotel ($500$ frames), completely independent of how many millions of citizens exist in the country (Virtual Address Space)!

For near-instant guest lookup, the clerk computes a quick hash of the guest's name to jump directly to the likely room slot, avoiding linear room-by-room searches.

💻 Bridging to Computer Science:

In traditional paging, page tables scale with the size of the Virtual Address Space (VAS). For 64-bit architectures, this leads to an untenable memory footprint.

An Inverted Page Table (IPT) inverts the relationship: there is one global table for the entire system, indexed by the Physical Frame Number ($f$). The table size scales strictly with the amount of Physical DRAM installed, regardless of whether the virtual address space is 32 bits, 64 bits, or 128 bits.

Meanwhile, Hardware Segmentation addresses memory from the programmer's perspective—organizing memory into variable-sized logical units (Code, Stack, Heap) with strict hardware Base and Limit protection registers. Combining both yields Segmented Paging, the hybrid architectural foundation of modern secure computing.

---

📑Table of Contents

• 🔄 The Inverted Page Table (IPT) Paradigm Shift
  • The Inverted Solution: One Global Table
  • Anatomy of an Inverted Page Table Entry (IPTE)
  • Mathematical Derivation of IPT Size:
• ⚡ The Translation Bottleneck & Hashed Inverted Page Tables
  • The Hardware Hashing Solution (Hashed IPT)
  • Average Memory Accesses in a Hashed IPT:
• 🧩 Hardware Segmentation Mechanics & Protection Registers
  • Logical Address Format in Segmentation
  • Hardware Translation via the Segment Table
  • The Fatal Flaw of Pure Segmentation: External Fragmentation
• 🛡️ Segmented Paging: Combining Modular Protection with Fixed Allocation
  • Address Decomposition in Segmented Paging:
• 📊 Unified EMAT Mathematical Masterclass (Comprehensive Comparison)
  • Comparative Architecture Matrix:
• 🏭 Real-World Production Context:
  • 1. Inverted Page Tables in Enterprise Systems: IBM Power & UltraSPARC
  • 2. The Death of Segmentation in 64-Bit x86 (Flat Memory Model)
  • 3. Shared Memory Pages via Memory Mapping (mmap)
• 📐 Numerical Applications & Worked Examples
  • Example 1: Inverted Page Table Sizing vs Flat Forward Page Table
  • Example 2: Comprehensive EMAT with Hashed Inverted Page Table
  • Example 3: Segment Table Validation and Protection Fault Traps
• 🎯 Exam & Interview Pitfall Check

---

🔄 The Inverted Page Table (IPT) Paradigm Shift

In standard forward paging, each process maintains its own independent page table. Because the table is indexed by Virtual Page Number ($p$), the number of entries is bounded by the virtual address range: $\text{Forward Table Entries per Process} = \frac{\text{VAS}}{\text{Page Size}} = 2^p$

As 64-bit processors proliferated, virtual address spaces grew from $4\text{ GB}$ ($2^{32}$) to $16\text{ Exabytes}$ ($2^{64}$). Even with multi-level tree pruning, storing page tables for thousands of active processes creates unsustainable memory overhead.

The Inverted Solution: One Global Table

An Inverted Page Table (IPT) fundamentally changes the indexing direction:

1. Single Global Table: There is only one page table shared across the entire operating system and all running processes.
2. Indexed by Physical Frame Number: Entry $i$ in the table corresponds directly to physical memory Frame $i$.
3. Fixed Size: The total number of entries in the IPT is strictly equal to the number of physical frames in RAM: $\mathbf{\text{Total Entries in IPT} = \text{Total Frames in RAM} = \frac{\text{PAS}}{\text{Frame Size}} = 2^f}$

Forward Page Table vs Inverted Page Table Architecture

Fundamental shift from per-process virtual indexing to single global physical frame indexing

Traditional Paging

Per-Process Forward Page Tables

📚

Indexed by Page Number p. One dedicated table per process.

Table size scales with Virtual Address Space (VAS)Empty virtual address ranges require multi-level tree pruningContext switch requires changing PTBR/CR3 register

↓Architectural Paradigm Shift

Inverted Paging

Global Inverted Page Table (IPT)

🗄️

Indexed by Physical Frame Number f. One single table for the entire operating system.

Table size scales strictly with Physical Address Space (PAS / DRAM capacity)Completely independent of Virtual Address Space bit-width (32-bit vs 64-bit)Every entry stores: Process ID (PID) + Virtual Page Number (VPN) + Flags

Anatomy of an Inverted Page Table Entry (IPTE)

Because a single global table maps frames for all processes simultaneously, each entry must record which process currently owns that physical frame:

Global Hardware DescriptorTotal Frame: e Bytes Wide (Typically 8 to 16 Bytes)

Inverted Page Table Entry (IPTE) Format

Hardware descriptor stored per physical DRAM frame

Process ID (PID)

16 to 32 Bits Bytes

Virtual Page Number (p)

p Bits Bytes

Chain / Next Pointer

f Bits Bytes

Status Flags (V, D, R, Prot)

4 to 8 Bits Bytes

16 to 32 Bits BytesProcess ID (PID)

Identifies the specific process that currently owns this physical frame. Prevents cross-process address aliasing.

Mathematical Derivation of IPT Size:

$\mathbf{\text{IPT Size (Bytes)} = (\text{Total Frames in RAM}) \times (\text{IPTE Size}) = \frac{\text{PAS}}{\text{Frame Size}} \times e}$

[!IMPORTANT] The Inversion Invariant: In an Inverted Page Table, Virtual Address Space ($n$) has zero effect on the size of the page table! Adding more RAM increases the IPT size, while expanding the virtual address space from 32-bit to 64-bit only widens the $p$-bit tag field inside each entry by a few bits.

---

⚡ The Translation Bottleneck & Hashed Inverted Page Tables

The fundamental engineering trade-off of an Inverted Page Table is lookup latency:

• In a forward page table, the CPU provides Page Number $p$, which serves as a direct direct memory index ($\text{Address} = \text{PTBR} + p \times e$). The entry is located in $O(1)$ constant time.
• In an inverted table, the table is indexed by Frame Number $f$. But the CPU emits Page Number $p$! To find which frame holds page $p$, the hardware would have to search all $2^f$ entries sequentially: $\text{Linear Search Complexity} = O(N_{\text{frames}})$ If physical RAM has $1\text{ million frames}$, searching $1\text{ million entries}$ on every memory reference is completely unthinkable.

The Hardware Hashing Solution (Hashed IPT)

To restore near-$O(1)$ translation speeds, computer architects implement a Hardware Hash Table (Hash Anchor Table, or HAT):

Architecture Flow

Hashed Inverted Page Table Translation Architecture

Hardware resolution pipeline combining TLB caching, hardware hashing, and collision traversal

📍Step 1

CPU Address & TLB

CPU emits (PID, p, d). MMU checks TLB. If TLB Hit -> extract Frame f instantly in < 1 ns.

→

⚙️Step 2

Hardware Hash Function

On TLB Miss, hardware hashes (PID, p) to compute Hash Anchor Table (HAT) index: h = Hash(PID, p).

→

🔗Step 3

Anchor Table Lookup

MMU reads HAT[h] in DRAM to retrieve the head pointer of the inverted page table collision chain.

→

🔍Step 4

Chain Traversal

MMU walks chain comparing (PID, p) against IPTE fields. If match found -> Frame Number = Entry Index f!

→

⚡Step 5

Physical Access

Concatenate Frame Number f with Offset d -> Access target DRAM byte. Update TLB with new mapping.

Average Memory Accesses in a Hashed IPT:

If the hash function has an average chain search length of $\bar{L}$ probes:

• On a TLB Hit: $1\text{ DRAM access}$ (for data).
• On a TLB Miss: $1\text{ access}$ (for Hash Anchor) + $\bar{L}\text{ accesses}$ (for IPT chain) + $1\text{ access}$ (for data) = $2 + \bar{L}\text{ DRAM accesses}$.

With a well-distributed hash function where $\bar{L} \approx 1.1\text{ to }1.2$, lookup latency remains competitive with multi-level paging while saving gigabytes of memory.

---

🧩 Hardware Segmentation Mechanics & Protection Registers

While paging partitions memory into uniform physical blocks ($4\text{ KB}$), human software engineers write programs structured into logical semantic components:

• A function/subroutine (Code Segment).
• Global variables (Data Segment).
• Dynamically allocated heap memory (Heap Segment).
• Local function call frames (Stack Segment).

Segmentation is a memory management scheme that supports this programmer view directly.

Logical Segmentation Memory Architecture

Variable-size semantic modularity with hardware boundary enforcement

Segment 0

Code / Text Segment

💻

Contains executable machine instructions. Strictly Read-Only and Shared across processes.

Permissions: Read + Execute (R-X)Base: 0x1000Limit: 32 KB

↓

Segment 1

Data / Global Segment

📊

Contains initialized global variables and static program constants.

Permissions: Read + Write (RW-)Base: 0x9000Limit: 16 KB

↓

Segment 2

Call Stack Segment

🥞

Grows downwards. Stores local variables, activation records, and return instruction pointers.

Permissions: Read + Write (RW-)Base: 0xF000Limit: 64 KB

Logical Address Format in Segmentation

A logical address in pure segmentation is a two-dimensional tuple: $\mathbf{\text{Logical Address} = [\text{Segment Number } s \mid \text{Segment Offset } d]}$

Hardware Translation via the Segment Table

The hardware maintains a Segment Table for each process. The CPU provides two hardware control registers:

• STBR (Segment Table Base Register): Physical address of the process's segment table in DRAM.
• STLR (Segment Table Length Register): Total number of valid segments defined by the program.

Each Segment Table Entry (STE) contains two primary fields:

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

📐Segmentation Hardware Translation & Protection Logicequation

When the CPU emits address $(s, d)$:

1. Segment Bound Check: Verify segment exists: $\text{If } s \ge \text{STLR} \implies \mathbf{\text{Trap: Invalid Segment Fault}}$
2. Offset Limit Check (Hardware Security): $\text{If } d \ge \text{Limit} \implies \mathbf{\text{Trap: Segmentation Fault (SIGSEGV)}}$
3. Physical Address Calculation: $\mathbf{\text{Physical Address} = \text{Base} + d}$

Architecture Flow

Hardware Segmentation Address Translation & Limit Verification

Hardware bounds verification preventing buffer overflow before physical DRAM calculation

📍Step 1

Logical Tuple

CPU emits [Segment Number s, Offset d]. STBR points to process Segment Table.

→

🔍Step 2

Table Dereference

Hardware reads Segment Table Entry at STBR + (s * STE_size) to fetch Base and Limit.

→

🛡️Step 3

Hardware Bound Check

Hardware comparator evaluates: Is d < Limit? If No -> Trigger Segmentation Fault (SIGSEGV).

→

⚡Step 4

Physical Base Offset

If Yes -> Hardware adder computes Physical Address = Base + d to access physical DRAM.

The Fatal Flaw of Pure Segmentation: External Fragmentation

Because segments match variable program modules (e.g., Segment 0 is $37\text{ KB}$, Segment 1 is $12\text{ KB}$, Segment 2 is $105\text{ KB}$), loading and unloading processes leaves irregular holes in physical memory. Over time, physical RAM suffers from catastrophic External Fragmentation, requiring costly memory compaction routines that freeze system execution.

---

🛡️ Segmented Paging: Combining Modular Protection with Fixed Allocation

To harvest the benefits of both worlds while eliminating their flaws, modern architectures combine them into Paged Segmentation (Segmented Paging):

• The Programmer's View: The application sees logical variable-sized segments (Code, Data, Stack) with independent protection and sharing rights.
• The Hardware's View: Instead of allocating each segment contiguously in RAM, each segment is internally divided into fixed-size $4\text{ KB}$ pages!

Address Decomposition in Segmented Paging:

$\mathbf{\text{Logical Address} = [\text{Segment Number } s \mid \text{Page Number } p \mid \text{Page Offset } d]}$

1. Segment Number $s$ indexes the Segment Table to retrieve the base address of the Page Table for Segment $s$.
2. Page Number $p$ indexes that segment's Page Table to retrieve the Physical Frame Number $f$.
3. Frame Number $f$ is concatenated with Offset $d$ to form the final Physical Address $(f, d)$.

---

📊 Unified EMAT Mathematical Masterclass (Comprehensive Comparison)

Effective Memory Access Time (EMAT) is the ultimate metric unifying memory hierarchy performance across all translation architectures:

📐Master EMAT Formulas Across All Architecturessummary

Let $m$ = Main Memory (DRAM) access time, $t$ = TLB lookup time, $c$ = TLB hit ratio:

1. Basic Single-Level Paging (No TLB): $\text{EMAT} = 2m$

2. Single-Level Paging (With TLB): $\text{EMAT} = c(t + m) + (1 - c)(t + 2m) = t + (2 - c)m$

3. $k$-Level Hierarchical Paging (With TLB): $\mathbf{\text{EMAT} = c(t + m) + (1 - c)(t + (k + 1)m)}$

4. Hashed Inverted Page Table (With TLB): $\mathbf{\text{EMAT} = c(t + m) + (1 - c)(t + (2 + \bar{L})m)}$ (where $\bar{L}$ is the average number of collision chain link traversals)

5. Segmented Paging (With TLB): $\text{EMAT} = c(t + m) + (1 - c)(t + 3m)$ (TLB miss requires Segment Table access + Page Table access + Data access = 3 RAM accesses)

Comparative Architecture Matrix:

Parameter	Flat Forward Paging	Multi-Level Paging ($k$-Level)	Inverted Page Table (IPT)	Pure Segmentation	Segmented Paging
Table Sizing Bound	Virtual Address Space ($\text{VAS}$)	Active $\text{VAS}$ regions	Physical DRAM ($\text{PAS}$)	Number of Segments	Segments $\times$ Pages
Number of Tables	One per Process	Tree per Process	One for entire OS	One per Process	Segment Table + PTs
External Fragmentation	Zero	Zero	Zero	Severe	Zero
Internal Fragmentation	$\approx \frac{\text{Page Size}}{2}$	$\approx \frac{\text{Page Size}}{2}$	$\approx \frac{\text{Page Size}}{2}$	Zero	$\le \frac{\text{Page Size}}{2}$ per segment
RAM Accesses on TLB Miss	$2$	$k + 1$	$2 + \bar{L}$	$2$ (Segment Table + Data)	$3$ (Seg + PT + Data)
Sharing & Protection	Page-level flags	Page-level flags	Difficult (Global)	Natural (Module-level)	Optimal (Module-level)

---

🏭 Real-World Production Context:

1. Inverted Page Tables in Enterprise Systems: IBM Power & UltraSPARC

Inverted Page Tables were historically deployed in commercial 64-bit enterprise servers:

• IBM Power Architecture (POWER8/POWER9): Uses an Inverted Page Table called the HPT (Hashed Page Table). The PowerPC MMU hashes the virtual address to index into a Page Table Entry Group (PTEG) containing 8 associative slots, solving 64-bit memory explosion before multi-level caches matured.
• Intel Itanium (IA-64): Implemented a Virtual Hash Page Table (VHPT) operating as an extension of the hardware TLB.

2. The Death of Segmentation in 64-Bit x86 (Flat Memory Model)

Students frequently ask: "If segmentation provides such elegant logical protection, why do modern 64-bit systems ignore it?"

• In x86-64 long mode, AMD and Intel architects disabled hardware segmentation:
  • Segment registers CS, DS, ES, and SS have their Base addresses forced hardwired to 0, and Limits forced to $2^{64} - 1$.
  • The operating system runs in a Flat Memory Model where the logical address is strictly identical to the linear virtual address.
• Why was segmentation deprecated?
  1. Compilers and software debuggers struggled with two-dimensional pointer arithmetic.
  2. Paging already provides granular memory protection flags ($R, W, X$) on a per-page basis.
  3. Disabling segmentation limit-checks eliminated hardware comparator propagation delays, increasing CPU clock frequencies. (Only FS and GS segment registers survive in x86-64, repurposed to point to Thread Local Storage (TLS) and kernel thread control blocks).

3. Shared Memory Pages via Memory Mapping (mmap)

Segmented Paging concepts live on in the POSIX mmap() system call. When two processes map the same shared library (libc.so) using MAP_SHARED:

• Process A's page table and Process B's page table point their respective virtual pages to the exact same physical frame numbers in DRAM.
• The physical frames are marked Read-Only. If either process attempts a write, the MMU triggers a Copy-on-Write (CoW) page fault, allocating a private frame on demand.

---

📐 Numerical Applications & Worked Examples

Example 1: Inverted Page Table Sizing vs Flat Forward Page Table

Problem Statement:
A 64-bit processor uses an Inverted Page Table. The system is equipped with $32\text{ GB}$ of physical RAM and a Page Size of $8\text{ KB}$. Each Inverted Page Table Entry (IPTE) contains:

• Process ID (PID): $16\text{ bits}$.
• Virtual Page Number: $51\text{ bits}$.
• Control/Status bits: $5\text{ bits}$.
• Next Chain Pointer: $f\text{ bits}$ (matching frame address bits).

Calculate:

1. The total number of entries in the Inverted Page Table.
2. The exact size of one IPTE (rounded up to whole bytes).
3. The total physical memory consumed by the Inverted Page Table.
4. Compare this size against the theoretical single-level forward page table for a single process.

Step-by-Step Solution:

1. Calculate Number of Frames in RAM:

   • $\text{PAS} = 32\text{ GB} = 32 \times 2^{30}\text{ bytes} = 2^5 \times 2^{30} = 2^{35}\text{ bytes} \implies m = 35\text{ bits}$.
   • $\text{Page Size} = 8\text{ KB} = 2^{13}\text{ bytes} \implies d = 13\text{ bits}$.
   • $\text{Frame Bits } f = m - d = 35 - 13 = \mathbf{22\text{ bits}}$. $\text{Total Entries in IPT} = 2^f = 2^{22} = \mathbf{4,194,304\text{ entries (4M entries)}}$

2. Calculate IPTE Size: $\text{Total Bits in IPTE} = \text{PID} + p + \text{Control} + \text{Chain Pointer}$ $\text{Total Bits in IPTE} = 16 + 51 + 5 + 22 = \mathbf{94\text{ bits}}$ Rounding up to whole bytes: $e = \left\lceil \frac{94}{8} \right\rceil = \lceil 11.75 \rceil = \mathbf{12\text{ bytes per entry}}$ (If rounded to power-of-two alignment for 64-bit bus: $16\text{ bytes}$. We will use $12\text{ bytes}$ for exact byte calculation).

3. Total Inverted Page Table Size: $\text{IPT Size} = (\text{Entries}) \times e = 2^{22} \times 12\text{ bytes} = 4\text{ M} \times 12\text{ bytes} = \mathbf{48\text{ MB}}$ Notice: This $48\text{ MB}$ table serves the entire operating system across all processes!

4. Comparison Against Forward Page Table: A single-level forward page table for a 64-bit space requires: $\text{Pages} = 2^{64 - 13} = 2^{51}\text{ pages}$ $\text{Forward PTS} = 2^{51} \times 8\text{ bytes} = 2^{54}\text{ bytes} = \mathbf{16\text{ Petabytes per process!}}$ The Inverted Page Table reduces memory requirements from an impossible $16\text{ Petabytes}$ down to $48\text{ Megabytes}$.

---

Example 2: Comprehensive EMAT with Hashed Inverted Page Table

Problem Statement:
A 64-bit workstation operates with a Hashed Inverted Page Table. The hardware parameters are:

• TLB Access Latency: $4\text{ ns}$.
• Main Memory (DRAM) Access Latency: $50\text{ ns}$.
• TLB Hit Ratio: $94\%$ ($0.94$).
• When a TLB miss occurs, hardware hashes the address and accesses the Hash Anchor Table (HAT) in DRAM.
• The average length of the collision chain search in the IPT is $\bar{L} = 1.5$ entries.
• Assume sequential hardware access.

Calculate:

1. The memory latency on a TLB Hit.
2. The total memory latency on a TLB Miss.
3. The Effective Memory Access Time (EMAT) of the workstation.

Step-by-Step Solution:

1. TLB Hit Latency ($T_{\text{hit}}$): On a hit, the translation is retrieved from the TLB, followed by accessing data in DRAM: $T_{\text{hit}} = \text{TLB Access} + \text{DRAM Access} = 4\text{ ns} + 50\text{ ns} = \mathbf{54\text{ ns}}$

2. TLB Miss Latency ($T_{\text{miss}}$): On a TLB miss:

   • First, search the TLB: $4\text{ ns}$.
   • Second, access the Hash Anchor Table in DRAM: $1 \times 50\text{ ns} = 50\text{ ns}$.
   • Third, traverse the collision chain in the Inverted Page Table (averaging $\bar{L} = 1.5$ table reads in DRAM): $1.5 \times 50\text{ ns} = 75\text{ ns}$.
   • Fourth, access the actual data operand in DRAM: $1 \times 50\text{ ns} = 50\text{ ns}$. $T_{\text{miss}} = 4 + 50 + 75 + 50 = \mathbf{179\text{ ns}}$

3. Effective Memory Access Time (EMAT): $\text{EMAT} = c \times T_{\text{hit}} + (1 - c) \times T_{\text{miss}}$ $\text{EMAT} = (0.94 \times 54) + (0.06 \times 179)$ $\text{EMAT} = 50.76 + 10.74 = \mathbf{61.5\text{ ns}}$

---

Example 3: Segment Table Validation and Protection Fault Traps

Problem Statement:
A processor uses hardware segmentation. Below is the current process's Segment Table:

Segment Number ($s$)	Base Address	Limit (Length)	Protection
0 (Code)	0x2000	0x0800 ($2048\text{ B}$)	Read / Execute
1 (Data)	0x5000	0x0400 ($1024\text{ B}$)	Read / Write
2 (Shared)	0x8000	0x0200 ($512\text{ B}$)	Read-Only
3 (Stack)	0xB000	0x1000 ($4096\text{ B}$)	Read / Write

Translate each of the following logical addresses $[s, d]$ into physical memory addresses, or identify the exact hardware exception raised:

1. Logical Address: $[s = 0, d = \text{0x0450}]$ (Instruction Fetch)
2. Logical Address: $[s = 1, d = \text{0x0400}]$ (Write Operation)
3. Logical Address: $[s = 2, d = \text{0x0150}]$ (Write Operation)
4. Logical Address: $[s = 3, d = \text{0x0FFF}]$ (Write Operation)
5. Logical Address: $[s = 5, d = \text{0x0100}]$ (Read Operation)

Step-by-Step Solution:

1. Address 1: $[s = 0, d = \text{0x0450}]$ (Instruction Fetch):

   • Limit check: Is $d < \text{Limit}$?
     $0\text{x}0450 < 0\text{x}0800$ ($1104 < 2048$). PASSES.
   • Protection check: Instruction fetch on Read/Execute segment $\implies$ PASSES.
   • Compute Physical Address: $\text{PA} = \text{Base} + d = 0\text{x}2000 + 0\text{x}0450 = \mathbf{0\text{x}2450}$

2. Address 2: $[s = 1, d = \text{0x0400}]$ (Write):

   • Limit check: Is $d < \text{Limit}$?
     Offset is $0\text{x}0400$ ($1024$), but Limit is $0\text{x}0400$ ($1024$). Since offsets are 0-indexed ($0 \le d < \text{Limit}$), an offset equal to the limit is strictly out of bounds!
   • Result: SEGMENTATION FAULT (OUT OF BOUNDS TRAP)!
     The MMU triggers a hardware boundary violation trap (SIGSEGV).

3. Address 3: $[s = 2, d = \text{0x0150}]$ (Write):

   • Limit check: $0\text{x}0150 < 0\text{x}0200$ ($336 < 512$). PASSES.
   • Protection check: Attempting a Write operation on a Read-Only segment!
   • Result: GENERAL PROTECTION FAULT (ACCESS VIOLATION)!
     The hardware denies write access and terminates the offending instruction.

4. Address 4: $[s = 3, d = \text{0x0FFF}]$ (Write):

   • Limit check: $0\text{x}0\text{FFF} < 0\text{x}1000$ ($4095 < 4096$). PASSES.
   • Protection check: Write on Read/Write stack $\implies$ PASSES.
   • Compute Physical Address: $\text{PA} = \text{Base} + d = 0\text{x}\text{B}000 + 0\text{x}0\text{FFF} = \mathbf{0\text{xBFFF}}$

5. Address 5: $[s = 5, d = \text{0x0100}]$ (Read):

   • The process segment table only defines segments $0, 1, 2, 3$ ($\text{STLR} = 4$).
   • Here $s = 5 \ge \text{STLR}$.
   • Result: INVALID SEGMENT EXCEPTION!
     The requested segment does not exist.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

• Question 1: Why is Virtual Address Space (VAS) completely irrelevant when computing the size of an Inverted Page Table?
  Answer: Because the Inverted Page Table is indexed by the Physical Frame Number ($f$), not the virtual page number. There is exactly one entry per physical frame installed in DRAM ($\text{PAS} / \text{Frame Size}$). Expanding the virtual address space from 32-bit to 64-bit merely widens the $p$-bit tag field inside each entry by 32 bits, but does not add a single new entry to the table!

• Question 2: Why do modern 64-bit architectures like x86-64 enforce a flat memory model and disable hardware segmentation?
  Answer: Multi-level paging already provides all necessary memory isolation, sharing, and read/write/execute protection flags at the $4\text{ KB}$ granularity without suffering from external fragmentation. Hardware segmentation introduced complex two-dimensional pointer arithmetic, slowed down CPU pipeline clocks with boundary-limit comparator checks, and caused severe compiler portability issues.

• Question 3: How does Segmented Paging solve both external and internal fragmentation?
  Answer: By layering the two concepts: Paging operates at the bottom physical layer, allocating memory in fixed-size $4\text{ KB}$ frames, which completely eliminates external fragmentation. Segmentation operates at the top logical layer, dividing programs into semantic modules. Because each segment's page table only allocates enough pages to cover the segment's actual size, internal fragmentation is confined strictly to the final partial page of each segment ($\le \text{Page Size} / 2$).

Common Interview Traps

• Trap 1: Confusing Segment Limit with Segment Maximum Offset.
  If a segment has a Limit of $1000\text{ bytes}$, the valid byte offsets range from $0$ to $999$. An offset of $1000$ triggers a Segmentation Fault! The hardware test is strictly $d < \text{Limit}$, never $d \le \text{Limit}$.

• Trap 2: Sizing an Inverted Page Table Using VAS.
  Never calculate $\text{IPT Size} = (\text{VAS} / \text{Page Size}) \times e$. That is the formula for a Forward Page Table! For an Inverted Page Table, always use: $\text{IPT Size} = \frac{\mathbf{\text{PAS}}}{\text{Frame Size}} \times e$

• Trap 3: Forgetting the Hash Table Anchor Access in Hashed IPT EMAT.
  On a TLB miss in a Hashed IPT, students often remember to add the collision chain accesses and data access, but forget the initial access to the Hash Anchor Table (HAT) in DRAM. Traversing the hash anchor requires $1$ physical memory access before the first IPTE link can even be examined!

---

🗺️View Complete COA Roadmap & Syllabus

← Previous Topic3.2 Translation Lookaside Buffer (TLB) & Multi-Level Page TablesNext Topic →4.1 I/O System Architectures: Memory-Mapped vs Isolated I/O