3.1 Virtual Memory Foundations & Hardware Paging Mechanics

Back to DBMS Notes

📚03Topic 3.1⏱️14 min

🎯High-Yield For:Virtual memory and hardware paging form the bedrock of modern operating systems, ensuring process memory isolation, eliminating external fragmentation, and orchestrating hardware MMU translation on every memory reference.

💡 Core Intuition:

🍳 The Everyday Analogy:

Imagine an international cargo distribution company operating across a vast metropolitan network. When a customer places an order, the central computer generates a Universal Tracking Catalog Number (e.g., Item #94,821, Offset: Box 4).

The customer does not know—and does not care—which physical warehouse, aisle, or shelf actually stores that physical crate. The customer's tracking number represents a Virtual Catalog Address.

At the logistics hub, an automated routing controller (The Memory Management Unit) consults a centralized Manifest Ledger (the Page Table). The ledger translates Item #94,821 into a physical warehouse coordinates: Building B, Rack 12. The requested goods are retrieved directly from that physical slot.

If the customer requests an item that has not yet arrived at the warehouse from the deep shipping dock, the manifest marks it as Not Present. The automated crane immediately pauses fulfillment and issues an urgent requisition to ship the crate from the deep shipping container yard (Page Fault from Disk/SSD). Once loaded onto a free warehouse rack, the manifest ledger is updated, and the order proceeds seamlessly.

💻 Bridging to Computer Science:

In computer architecture, early computing systems required programs to be loaded into contiguous physical RAM. This caused two fatal bottlenecks:

1. External Fragmentation: Free memory was broken into tiny, unusable holes between allocated tasks.
2. Physical Memory Ceiling: A program could never be larger than the physical RAM installed on the motherboard.

Virtual Memory with Hardware Paging completely decouples the programmer's view of memory from physical silicon. The CPU executes instructions within a uniform, private Virtual Address Space (VAS). Physical RAM is partitioned into fixed-size slots called Frames, and the program's virtual address space is partitioned into identical-sized chunks called Pages.

Hardware within the Memory Management Unit (MMU) automatically translates every logical address into a physical address on the fly using a per-process lookup structure called the Page Table.

---

📑Table of Contents

• 🛡️ The Dual Mandate of Virtual Memory
  • Key Terminologies:
• 📐 Mathematical Anatomy of Logical & Physical Addresses
  • 1. Logical Address Breakdown (n bits)
  • 2. Physical Address Breakdown (m bits)
• 🗄️ Page Table Architecture & Hardware Translation Flow
  • Hardware Support: The Page Table Base Register (PTBR)
  • The Paging Penalty: Two Memory Accesses per Instruction
• 🔍 Deep-Dive: Anatomy of a Page Table Entry (PTE)
  • How to Calculate Minimum PTE Size:
• 📊 Page Table Size (PTS) Derivations & Memory Overhead
  • The Linear Scaling Crisis: Why Flat Page Tables Break
• ⚖️ Paging vs Segmentation Architectural Comparison
  • Internal Fragmentation in Paging:
• 🏭 Real-World Production Context:
  • 1. Linux Kernel Paging & Page Tables
  • 2. Linux HugePages (2 MB & 1 GB) in High-Performance Databases
  • 3. Dirty-Bit Hardware Synchronization in SSD Wear Leveling
• 📐 Numerical Applications & Worked Examples
  • Example 1: End-to-End Address Sizing & Page Table Overhead
  • Example 2: Determining Minimum & Byte-Aligned PTE Size
  • Example 3: Step-by-Step Physical Address Translation with Page Fault Detection
• 🎯 Exam & Interview Pitfall Check

---

🛡️ The Dual Mandate of Virtual Memory

Virtual memory is not merely a mechanism to extend RAM onto disk; it is an architectural contract between the processor and operating system that fulfills two critical mandates:

The Dual Mandate of Modern Virtual Memory

Hardware abstraction providing memory capacity expansion and strict process isolation

Mandate 1

Capacity Expansion (Illusion of Infinite Memory)

🌌

Programs execute within an address space significantly larger than physical DRAM (VAS >> PAS).

Demand Paging: Only active working sets occupy physical RAM framesSecondary storage (NVMe/SSD) acts as backing store for inactive pagesEliminates static overlay trees and contiguous memory allocation limits

↓Hardware MMU Translation

Mandate 2

Memory Protection & Isolation (Security Firewalls)

🔒

Every process receives a sandboxed, private 0 to 2^n - 1 address space isolated from all others.

Total Isolation: Process A cannot read or corrupt Process B's memoryKernel Space Protection: User-mode code cannot overwrite OS kernel page tablesGranular Permissions: Page-level Read (R), Write (W), and Execute (X) enforcement

Key Terminologies:

1. Logical Address Space (LAS) / Virtual Address Space (VAS): The total collection of addresses generated by the CPU for a given process. If the processor generates an $n$-bit logical address, the virtual address space is: $\text{VAS} = 2^n\text{ bytes}$
2. Physical Address Space (PAS): The actual addressable range supported by physical DRAM installed on the system. If physical memory bus width is $m$ bits, the physical address space is: $\text{PAS} = 2^m\text{ bytes}$
3. Pages: The logical address space of a process is partitioned into fixed-size contiguous contiguous blocks called Pages.
4. Frames (Page Frames): Physical memory (RAM) is partitioned into fixed-size contiguous blocks called Frames.
5. Golden Rule of Paging: $\mathbf{\text{Page Size (PS)} = \text{Frame Size (FS)} = S = 2^d\text{ bytes}}$

---

📐 Mathematical Anatomy of Logical & Physical Addresses

When the CPU executes an instruction referencing memory (e.g., MOV EAX, [0x0040A1F0]), the address emitted is a Logical (Virtual) Address. The hardware decomposes this address into two distinct bit-fields:

1. Logical Address Breakdown ($n$ bits)

• Page Number ($p$ bits): Identifies which virtual page of the process is being referenced.
• Page Offset ($d$ bits): Specifies the exact byte within that page.

$\text{Offset Bits } d = \log_2(\text{Page Size in Bytes}) = \log_2(S)$ $\text{Page Number Bits } p = n - d$ $\text{Total Number of Pages in Process} = \frac{\text{VAS}}{\text{Page Size}} = \frac{2^n}{2^d} = 2^{n - d} = 2^p$

CPU GenerationTotal Frame: n Bits Wide

Logical (Virtual) Address Format

Emitted by CPU Execution Units: n-bit Virtual Address

Page Number (p)

p = n - d Bits MSB

Page Offset (d)

d = log2(Page Size) Bits LSB

p = n - d Bits MSBPage Number (p)

Used by hardware MMU as an index into the process page table to retrieve the target physical frame.

2. Physical Address Breakdown ($m$ bits)

When the MMU translates the page number into a physical frame, the resulting physical address is routed across the memory bus:

• Frame Number ($f$ bits): Identifies which physical DRAM frame contains the target page.
• Frame Offset ($d$ bits): Specifies the exact byte within that frame.

$\text{Frame Offset Bits } d = \log_2(\text{Frame Size in Bytes}) = \log_2(S)$ $\text{Frame Number Bits } f = m - d$ $\text{Total Number of Frames in RAM} = \frac{\text{PAS}}{\text{Frame Size}} = \frac{2^m}{2^d} = 2^{m - d} = 2^f$

RAM Bus AddressingTotal Frame: m Bits Wide

Physical (DRAM) Address Format

Emitted by MMU to Memory Controller Bus: m-bit Physical Address

Frame Number (f)

f = m - d Bits MSB

Frame Offset (d)

d Bits (Identical to Logical) LSB

f = m - d Bits MSBFrame Number (f)

Extracted directly from the Page Table Entry (PTE). Identifies the physical slot in RAM.

[!IMPORTANT] The Offset Invariant: The offset $d$ is never translated. Because $\text{Page Size} = \text{Frame Size}$, the displacement of a byte relative to the start of its page is identical to its displacement relative to the start of the physical frame! Hardware only translates the Page Number ($p$) $\to$ Frame Number ($f$).

---

🗄️ Page Table Architecture & Hardware Translation Flow

To translate virtual page numbers to physical frame numbers, the operating system maintains a dedicated data structure for each active process called the Page Table. The page table is stored in physical main memory (RAM).

Hardware Support: The Page Table Base Register (PTBR)

Because each process has its own unique page table, switching processes during an operating system context switch requires only updating a single CPU hardware control register:

• PTBR (Page Table Base Register): Holds the physical starting address of the active process's page table in DRAM.
• PTLR (Page Table Length Register): Holds the total number of entries in the page table to detect out-of-bounds segmentation violations.

$\text{Physical Address of PTE for Page } p = \text{PTBR} + (p \times \text{PTE Size})$

Architecture Flow

Hardware Address Translation Pipeline (MMU Execution Cycle)

Cycle-by-cycle hardware progression from CPU logical address to physical DRAM access

✂️Step 1

Address Splitting

CPU emits n-bit address; hardware extracts Page Number p (MSBs) and Offset d (LSBs).

→

📍Step 2

PTBR Indexing

MMU computes PTE address = PTBR + (p * PTE_size) and fetches entry from DRAM.

→

🔍Step 3

Validity Check

MMU inspects Valid bit (V). If V = 0, trap to OS (Page Fault). If V = 1, extract Frame Number f.

→

🔗Step 4

Address Concatenation

MMU concatenates Frame Number f with original Offset d to form m-bit Physical Address (f, d).

→

⚡Step 5

DRAM Access

Physical address is placed on memory address bus; desired data word is returned to CPU.

The Paging Penalty: Two Memory Accesses per Instruction

A major architectural cost of basic paging is memory latency:

1. Memory Access 1: Access main memory to read the Page Table Entry (PTE) at $\text{PTBR} + p \times e$.
2. Memory Access 2: Access main memory at the physical address $(f, d)$ to fetch the actual instruction or operand.

$\text{Effective Access Time (EAT)} = 2 \times T_{\text{RAM}}$

This $100\%$ slowdown provides the direct engineering motivation for the Translation Lookaside Buffer (TLB), which caches frequent translations in fast hardware associative memory.

---

🔍 Deep-Dive: Anatomy of a Page Table Entry (PTE)

A Page Table is an array of Page Table Entries (PTEs). A PTE does not merely store the destination frame number; it contains vital hardware status flags used by the MMU and OS kernel:

MMU Control WordTotal Frame: e Bytes Wide (Typically 4 or 8 Bytes)

Standard Page Table Entry (PTE) Hardware Bit-Field Format

Comprehensive control word stored per virtual page in main memory

Frame Number (f)

f Bits [Base Address] MSB Field

Valid / Present (V)

1 Bit Status Flag

Dirty / Modified (D)

1 Bit Status Flag

Reference / Access (R)

1 Bit Status Flag

Protection / Mode

2 to 3 Bits Security

Cache Disable (CD)

1 Bit Control

f Bits [Base Address] MSB FieldFrame Number (f)

Specifies the physical memory frame index where this page is currently pinned in DRAM.

How to Calculate Minimum PTE Size:

In numerical problems, the minimum size of a PTE is determined by the number of bits needed to address all physical frames plus any mandatory status flags: $\text{Frame Bits } f = \log_2(\text{Total Number of Frames in RAM}) = \log_2\left(\frac{\text{PAS}}{\text{Frame Size}}\right)$ $\text{Minimum Bits in PTE} = f + \text{Status Bits}$

Since computer memory is byte-addressable, memory controllers cannot easily read fractional bytes. Therefore, the actual PTE size ($e$) is rounded up to the nearest whole integer byte: $e = \left\lceil \frac{f + \text{Status Bits}}{8} \right\rceil \text{ bytes}$

In modern architectures (e.g., x86, ARM), $e$ is rounded to the nearest power of 2 ($2\text{ bytes}$, $4\text{ bytes}$, or $8\text{ bytes}$) for natural memory bus alignment.

---

📊 Page Table Size (PTS) Derivations & Memory Overhead

One of the most heavily tested mathematical derivations in computer architecture is the total memory footprint consumed by the Page Table itself:

📐Universal Page Table Size (PTS) Formulatheorem

$\text{Total Entries in Page Table} = \text{Total Pages in Process} = \frac{\text{Virtual Address Space (VAS)}}{\text{Page Size (PS)}} = 2^{n - d} = 2^p$

$\mathbf{\text{Page Table Size (PTS)}} = (\text{Number of Entries}) \times (\text{PTE Size}) = 2^p \times e = \frac{\text{VAS}}{\text{Page Size}} \times e$

The Linear Scaling Crisis: Why Flat Page Tables Break

Consider how a flat, single-level page table scales across different computer architectures:

Case A: 32-Bit System with $4\text{ KB}$ Pages

• $\text{VAS} = 2^{32}\text{ bytes} = 4\text{ GB}$.
• $\text{Page Size} = 4\text{ KB} = 2^{12}\text{ bytes} \implies d = 12\text{ bits}$.
• $\text{Number of Pages} = 2^{32 - 12} = 2^{20} = 1,048,576\text{ pages}$.
• Let $\text{PTE Size } e = 4\text{ bytes}$ ($32\text{ bits}$).
• $\text{Page Table Size} = 2^{20} \times 4\text{ bytes} = \mathbf{4\text{ MB per process!}}$

If 100 processes are running concurrently: $\text{Memory Wasted on Page Tables} = 100 \times 4\text{ MB} = \mathbf{400\text{ MB}}$ Nearly $10\%$ of total $4\text{ GB}$ system RAM is lost strictly to store address mapping tables!

Case B: 64-Bit System with $4\text{ KB}$ Pages

• $\text{VAS} = 2^{64}\text{ bytes} \implies n = 64\text{ bits}$.
• $\text{Page Size} = 4\text{ KB} = 2^{12}\text{ bytes} \implies d = 12\text{ bits}$.
• $\text{Number of Pages} = 2^{64 - 12} = 2^{52}\text{ pages}$.
• Let $\text{PTE Size } e = 8\text{ bytes}$.
• $\text{Page Table Size} = 2^{52} \times 8\text{ bytes} = 2^{55}\text{ bytes} = \mathbf{32\text{ Petabytes per process!}}$

It is physically impossible to store a $32\text{ Petabyte}$ table in physical RAM. This catastrophic scaling directly mandates Multi-Level Paging, Inverted Page Tables, and Virtual Page Table Paging (covered in Topics 3.2 and 3.3).

---

⚖️ Paging vs Segmentation Architectural Comparison

Before examining multi-level structures, it is essential to compare paging with its historical alternative: Segmentation.

Internal Fragmentation in Paging:

Because process memory allocation is quantized to whole page boundaries, the final page of a process is rarely completely full:

• If process size is $17\text{ KB}$ and $\text{Page Size} = 4\text{ KB}$: $\text{Pages Allocated} = \left\lceil \frac{17\text{ KB}}{4\text{ KB}} \right\rceil = 5\text{ pages} = 20\text{ KB}$ $\text{Internal Fragmentation} = 20\text{ KB} - 17\text{ KB} = \mathbf{3\text{ KB wasted}}$
• Across thousands of running threads and processes, the mathematical average internal fragmentation is: $\text{Average Internal Fragmentation per Process} \approx \frac{\text{Page Size}}{2}$

---

🏭 Real-World Production Context:

1. Linux Kernel Paging & Page Tables

In the Linux kernel, every user process has an mm_struct data structure containing pgd_t *pgd, which points to the base of the process's page table. During a context switch via switch_mm(), the kernel writes the physical address of this PGD into the x86-64 CR3 control register (the x86 equivalent of the PTBR).

/* Conceptual Linux Process Memory Descriptor */
struct mm_struct {
    pgd_t *pgd;                 /* Points to Page Global Directory (CR3 value) */
    unsigned long total_vm;     /* Total allocated virtual pages */
    unsigned long locked_vm;    /* Pinned pages that cannot be swapped */
    struct vm_area_struct *mmap;/* List of Virtual Memory Areas (text, data, heap) */
};

2. Linux HugePages (2 MB & 1 GB) in High-Performance Databases

Standard $4\text{ KB}$ pages work well for general desktop software, but for massive in-memory databases like PostgreSQL, Redis, and MySQL InnoDB, millions of $4\text{ KB}$ pages flood the CPU's Translation Lookaside Buffer (TLB), causing chronic TLB thrashing:

• A $64\text{ GB}$ database buffer pool requires: $\frac{64\text{ GB}}{4\text{ KB}} = 16,777,216\text{ pages}$ This demands $16.7\text{ million PTEs} \times 8\text{ bytes} = \mathbf{128\text{ MB of page table metadata}}$!
• By enabling Linux Transparent HugePages (THP) or explicit HugeTLB ($2\text{ MB}$ pages): $\frac{64\text{ GB}}{2\text{ MB}} = 32,768\text{ pages}$ The page table overhead plummets from $128\text{ MB}$ down to just $256\text{ KB}$, and the working set fits comfortably inside the CPU TLB cache, boosting query throughput by $15\%\text{--}30\%$.

3. Dirty-Bit Hardware Synchronization in SSD Wear Leveling

The hardware Dirty Bit ($D$) in the PTE is critical to modern flash durability. When an operating system memory manager needs to reclaim physical frames (page replacement):

• Clean Page ($D = 0$): The page was read but never modified. The kernel instantly evicts the frame and reclaims it without writing to disk, since an exact copy already exists in the file backing store.
• Dirty Page ($D = 1$): The page was modified in DRAM. The kernel must schedule an asynchronous writeback to storage before freeing the frame. Tracking the dirty bit eliminates millions of redundant write cycles, prolonging NVMe/SSD drive lifespan by orders of magnitude.

---

📐 Numerical Applications & Worked Examples

Example 1: End-to-End Address Sizing & Page Table Overhead

Problem Statement:
A computer system has a 36-bit Virtual Address Space and a 32-bit Physical Address Space. The system utilizes hardware paging with a Page Size of $8\text{ KB}$. Memory is byte-addressable.

1. Determine the bit allocation for the Logical Address (Page Number $p$ and Offset $d$).
2. Determine the bit allocation for the Physical Address (Frame Number $f$ and Offset $d$).
3. Calculate the total number of pages in a process and total frames in physical RAM.
4. If each Page Table Entry (PTE) requires $4\text{ bytes}$, compute the total size of the Page Table for a process.

Step-by-Step Solution:

1. Logical Address Bit Allocation:

   • $\text{VAS} = 2^{36}\text{ bytes} \implies n = 36\text{ bits}$.
   • $\text{Page Size (PS)} = 8\text{ KB} = 8 \times 2^{10}\text{ bytes} = 2^3 \times 2^{10} = 2^{13}\text{ bytes}$.
   • $\text{Offset Bits } d = \log_2(2^{13}) = \mathbf{13\text{ bits}}$.
   • $\text{Page Number Bits } p = n - d = 36 - 13 = \mathbf{23\text{ bits}}$.
   • Logical Address Layout: $[p: 23\text{ bits} \mid d: 13\text{ bits}] = 36\text{ bits total}$.

2. Physical Address Bit Allocation:

   • $\text{PAS} = 2^{32}\text{ bytes} \implies m = 32\text{ bits}$.
   • Since $\text{Frame Size} = \text{Page Size} = 2^{13}\text{ bytes}$, $\text{Frame Offset } d = \mathbf{13\text{ bits}}$.
   • $\text{Frame Number Bits } f = m - d = 32 - 13 = \mathbf{19\text{ bits}}$.
   • Physical Address Layout: $[f: 19\text{ bits} \mid d: 13\text{ bits}] = 32\text{ bits total}$.

3. Total Pages and Total Frames:

   • $\text{Total Pages in Process} = 2^p = 2^{23} = \mathbf{8,388,608\text{ pages (8M pages)}}$.
   • $\text{Total Frames in RAM} = 2^f = 2^{19} = \mathbf{524,288\text{ frames (512K frames)}}$.

4. Page Table Size (PTS): $\text{PTS} = (\text{Number of Pages}) \times (\text{PTE Size})$ $\text{PTS} = 2^{23} \times 4\text{ bytes} = 2^{23} \times 2^2\text{ bytes} = 2^{25}\text{ bytes}$ $\text{PTS} = \frac{2^{25}}{2^{20}}\text{ MB} = \mathbf{32\text{ MB per process}}$

---

Example 2: Determining Minimum & Byte-Aligned PTE Size

Problem Statement:
A system supports an address space where the Virtual Address is 32 bits, the Physical Address is 28 bits, and the Page Size is $4\text{ KB}$. Each Page Table Entry must store:

• The physical Frame Number.
• $1$ Valid/Invalid bit.
• $1$ Dirty bit.
• $2$ Protection bits.
• $1$ Reference bit.

Calculate:

1. The minimum number of bits strictly required for one PTE.
2. The practical PTE size rounded to the nearest byte.
3. The total Page Table Size using the byte-rounded PTE size.
4. The unused padding bits per PTE.

Step-by-Step Solution:

1. Calculate Frame Bits ($f$):

   • $\text{Page Size} = 4\text{ KB} = 2^{12}\text{ bytes} \implies d = 12\text{ bits}$.
   • $\text{Physical Address } m = 28\text{ bits}$.
   • $\text{Frame Number Bits } f = m - d = 28 - 12 = \mathbf{16\text{ bits}}$.

2. Minimum PTE Bits: $\text{PTE Bits} = \text{Frame Bits } (f) + \text{Valid} + \text{Dirty} + \text{Protection} + \text{Reference}$ $\text{PTE Bits} = 16 + 1 + 1 + 2 + 1 = \mathbf{21\text{ bits}}$

3. Byte-Rounded PTE Size: Memory controllers address whole bytes. Rounding $21\text{ bits}$ up: $e = \left\lceil \frac{21}{8} \right\rceil = \lceil 2.625 \rceil = \mathbf{3\text{ bytes (24 bits)}}$ (Note: If the system strictly requires power-of-two memory alignment, hardware would round this to $4\text{ bytes} = 32\text{ bits}$. For standard byte-addressing calculations, $3\text{ bytes}$ is the minimum storage).

4. Page Table Size with $3\text{ Bytes}$ per Entry:

   • $\text{Page Number Bits } p = 32 - 12 = 20\text{ bits} \implies \text{Number of Pages} = 2^{20}$. $\text{PTS} = 2^{20} \times 3\text{ bytes} = 3 \times 1\text{ MB} = \mathbf{3\text{ MB}}$

5. Unused Padding Bits: $\text{Padding} = 24\text{ bits} - 21\text{ bits} = \mathbf{3\text{ bits per PTE}}$

---

Example 3: Step-by-Step Physical Address Translation with Page Fault Detection

Problem Statement:
Consider a system with a 16-bit Virtual Address Space and an 8-bit Physical Address Space. The Page Size is $256\text{ bytes}$. Below is a snapshot of the current process's Page Table:

Page Number ($p$)	Frame Number ($f$)	Valid Bit ($V$)	Protection
0x0	0x3	1	Read/Write
0x1	0x7	1	Read-Only
0x2	0x0	0	Invalid (On Disk)
0x3	0x1	1	Read/Write
0x4	0x0	0	Invalid (On Disk)
0x5	0x2	1	Read-Only

Translate the following logical addresses into their corresponding physical addresses (or identify if a fault occurs):

1. Logical Address: 0x015A (Read operation)
2. Logical Address: 0x0240 (Read operation)
3. Logical Address: 0x037F (Write operation)
4. Logical Address: 0x0120 (Write operation)

Step-by-Step Solution:

1. Determine Bit Boundaries:

   • $\text{Page Size} = 256\text{ bytes} = 2^8\text{ bytes} \implies d = 8\text{ bits}$ (the lowest 2 hex digits represent the offset).
   • Logical Address has 16 bits $\implies p = 16 - 8 = 8\text{ bits}$ (the upper 2 hex digits represent the page number).
   • Physical Address has 8 bits. With $d = 8\text{ bits}$, the physical frame number $f$ occupies the upper bits. Here $m = 8$ and $d = 8 \implies f = 0\text{ bits}$, which means RAM consists of exactly $2^8 = 256\text{ bytes}$ (1 frame).
     (Let us adjust the physical address specification to 12 bits so frames exist: $m = 12\text{ bits} \implies f = 12 - 8 = 4\text{ bits}$, matching the 1-hex-digit frame numbers 0x3, 0x7, 0x1, 0x2).

2. Translate Request 1: 0x015A (Read):

   • Split address: $\text{Page } p = \text{0x01}$, $\text{Offset } d = \text{0x5A}$.
   • Consult Page Table at index 0x01:
     • $\text{Frame } f = \text{0x7}$, $\text{Valid } V = 1$, $\text{Protection} = \text{Read-Only}$.
   • Operation is a Read on a Read-Only page $\implies$ Permission check PASSES.
   • Form Physical Address: Concatenate $f$ with $d$: $\text{Physical Address} = (0\text{x}7 \ll 8) \mid 0\text{x}5\text{A} = \mathbf{0\text{x}75\text{A}}$

3. Translate Request 2: 0x0240 (Read):

   • Split address: $\text{Page } p = \text{0x02}$, $\text{Offset } d = \text{0x40}$.
   • Consult Page Table at index 0x02:
     • $\text{Valid bit } V = 0$.
   • Result: PAGE FAULT EXCEPTION!
     The requested page is not currently resident in physical memory. The MMU raises an interrupt trap to the operating system kernel to fetch Page 2 from the backing store.

4. Translate Request 3: 0x037F (Write):

   • Split address: $\text{Page } p = \text{0x03}$, $\text{Offset } d = \text{0x7F}$.
   • Consult Page Table at index 0x03:
     • $\text{Frame } f = \text{0x1}$, $\text{Valid } V = 1$, $\text{Protection} = \text{Read/Write}$.
   • Operation is Write on Read/Write page $\implies$ Permission check PASSES.
   • Set Dirty bit $D = 1$ in PTE.
   • Form Physical Address: $\text{Physical Address} = (0\text{x}1 \ll 8) \mid 0\text{x}7\text{F} = \mathbf{0\text{x}17\text{F}}$

5. Translate Request 4: 0x0120 (Write):

   • Split address: $\text{Page } p = \text{0x01}$, $\text{Offset } d = \text{0x20}$.
   • Consult Page Table at index 0x01:
     • $\text{Frame } f = \text{0x7}$, $\text{Valid } V = 1$, but $\text{Protection} = \mathbf{\text{Read-Only}}$.
   • Operation is a Write to a Read-Only segment!
   • Result: GENERAL PROTECTION FAULT (ACCESS VIOLATION)!
     The MMU triggers a segmentation/protection violation trap. The OS terminates the process with a SIGSEGV (Segmentation Fault).

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

• Question 1: Why does the Page Offset ($d$) remain completely unchanged during address translation?
  Answer: Because the Page Size is defined to be strictly identical to the Physical Frame Size ($\text{Page Size} = \text{Frame Size} = 2^d$). An offset represents the byte distance from the base of the block. If Page 4 is placed inside Frame 9, the 100th byte of Page 4 is located at exactly the 100th byte of Frame 9. The relative intra-block position is invariant under relocation.

• Question 2: Does Page Table Entry (PTE) size depend on the size of the Virtual Address Space or the Physical Address Space?
  Answer: The PTE size depends fundamentally on the Physical Address Space (PAS), not the Virtual Address Space! The PTE must store the Frame Number ($f$), where $f = \log_2(\text{PAS} / \text{Frame Size})$. Increasing the VAS increases the number of entries in the page table, but does not increase the width of the frame field within each entry.

• Question 3: Why does hardware paging eliminate external fragmentation but still suffer from internal fragmentation?
  Answer: External fragmentation occurs when free memory cannot be allocated because it is non-contiguous. Paging eliminates this completely because physical memory is allocated in uniform, fixed-size frames; any free frame anywhere in RAM can satisfy any page request. However, because process memory requests are rarely exact multiples of the page size, the final page allocated to a process is only partially filled, leaving an average of $\text{Page Size} / 2$ wasted space at the end (internal fragmentation).

Common Interview Traps

• Trap 1: Calculating Frame Bits ($f$) using Virtual Address Space instead of Physical Address Space.
  Never calculate $f = \log_2(\text{VAS} / \text{Page Size})$. That calculates the Page Number bits ($p$)! Frames exist strictly in physical DRAM. Always compute: $f = \log_2\left(\frac{\text{PAS}}{\text{Frame Size}}\right) = m - d$

• Trap 2: Forgetting to Round PTE Size Up to Integer Bytes.
  If a problem states that $f = 17\text{ bits}$ and there are $3$ control bits, the minimum PTE width is $17 + 3 = 20\text{ bits}$. If asked for the size of the Page Table in megabytes, you must not multiply $2^{20}\text{ entries} \times 20\text{ bits} = 2.5\text{ MB}$. Memory controllers address whole bytes! You must round up: $e = \left\lceil \frac{20}{8} \right\rceil = 3\text{ bytes} \implies \text{PTS} = 2^{20} \times 3\text{ bytes} = 3\text{ MB}$

• Trap 3: Confusing Page Table Size (PTS) with Page Size (PS).
  $\text{Page Size (PS)}$ is the size of an individual data block (e.g., $4\text{ KB}$). $\text{Page Table Size (PTS)}$ is the total memory footprint occupied by the entire translation array ($2^p \times e$). Never substitute one for the other in formulas!

---

🗺️View Complete COA Roadmap & Syllabus

← Previous Topic2.4 Cache Write Policies, Replacement Algorithms & Multi-Level AMATNext Topic →3.2 Translation Lookaside Buffer (TLB) & Multi-Level Page Tables