8.1 Demand Paging & The Page Fault Handling Cycle

Back to Operating Systems Notes

📚Module 08: Virtual Memory & Page ReplacementTopic 8.1⏱️20 min read

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

💡 Core Intuition

🍳 The Everyday Analogy: The University Lending Library

Imagine a university student conducting comprehensive research for a master's thesis:

Architecture Flow

The Library Book Request Pipeline

Contrasting borrowing an entire warehouse with checking out chapters on demand

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

📚Naive Approach

Hauling the Entire Library

Pure Swapping

You attempt to haul all 500 reference books to your tiny desk before reading a single line.

→

Modern Optimization

📖On-Demand

Reading at the Desk

Demand Paging

You sit down with only the chapter open that you are actively reading right now.

→

Missing Reference

🛎️Book Retrieval

The Missing Book Request

Page Fault Interrupt

When a book is not on your desk, you place a reservation ticket with the librarian.

• Traditional Swapping: Requires loading an entire process into physical RAM before execution can begin.
• Demand Paging: Loads pages strictly on demand—only when the CPU attempts to execute code or access data residing on that specific page.
• The Page Fault: A hardware trap generated when the CPU attempts to access a page marked invalid (not currently resident in physical RAM).

---

💻 Bridging to Computer Science

In earlier memory systems, a program could not execute unless the entire executable image fitted completely inside physical DRAM. This imposed severe restrictions:

1. Program size was strictly bounded by the physical RAM installed on the motherboard.
2. Inactive code (such as error-handling routines, initialization scripts, and rarely used menu options) permanently squandered precious DRAM.

Virtual Memory shatters this constraint by separating the Logical Address Space perceived by user programs from the physical DRAM installed in the machine:

Virtual Memory Architectural Gains

Key operating system capabilities unlocked by decoupling virtual address space from physical DRAM

💾

Programs Exceed Physical RAM

Capacity Decoupling

• A 64 GB machine-learning model can execute on a system with only 16 GB of physical DRAM.
• Non-resident pages remain safely on backing swap storage until actively referenced.

⚡

Higher Degree of Multiprogramming (DoM)

Memory Efficiency

• Because each process consumes only a fraction of its total pages in physical RAM, the kernel can host dozens of concurrent processes simultaneously.
• Maximizes CPU utilization and prevents memory starvation.

🚀

Faster Launch Latency (Zero-I/O Cold Start)

Demand Paging

• The OS does not read gigabytes of binaries into RAM before calling main().
• Execution begins immediately via Demand Paging, faulting in pages only on demand.

🔄

Seamless Memory Sharing

Inter-Process Optimization

• Shared libraries (e.g., libc.so) and inter-process shared memory regions (POSIX shm) map to identical physical frames across disparate page tables.
• Dramatically reduces physical DRAM consumption across processes.

---

📚 Core Deep-Dive & Concepts

1. Pure Demand Paging & The Lazy Swapper (Pager)

Under Demand Paging, the operating system uses a Lazy Swapper (Pager):

• A traditional swapper manipulates entire process address spaces.
• A Pager manipulates individual pages. A page is never brought into physical memory unless the CPU actively references an instruction or operand on that page.
• In Pure Demand Paging, a process begins execution with zero pages in physical RAM.
  • The OS loads the PCB, sets the instruction pointer (PC) to the first instruction, and dispatches the process.
  • The very first memory fetch immediately triggers a Page Fault!
  • The OS pages in Page 0, restarts the instruction, and execution proceeds, faulting only as new un-cached pages are needed.
  • Thanks to the Principle of Locality of Reference, after an initial cluster of page faults, execution runs at full DRAM wire speed with minimal faults.

---

2. The Valid / Invalid Bit Mechanics

To support demand paging, every Page Table Entry (PTE) contains a hardware-monitored Valid-Invalid Bit ($V$):

Valid Bit ($V$)	Target Memory Residence	Hardware MMU & OS Action
1 (Valid)	Physical DRAM Frame ($f$)	Direct translation; memory access completes at full DRAM wire speed.
0 (Invalid)	Backing Store (Swap/Disk) or Unmapped	Hardware Page Fault Exception raised. OS checks VMA: loads page from disk if legal, or raises SIGSEGV if invalid.

When the CPU executes an instruction referencing page $p$:

1. The MMU consults the process's page table.
2. If Valid == 1: The translation succeeds instantly; frame $f$ is accessed in DRAM.
3. If Valid == 0: The MMU halts execution and triggers a hardware exception: Page Fault Trap.

---

3. The 7-Step Page Fault Handling Cycle

Handling a page fault requires a coordinated sequence between hardware MMU circuits and OS kernel interrupt routines:

---

4. Mathematical Modeling of Demand Paging: EMAT Performance

A standard DRAM access takes roughly $100\text{ ns}$ ($0.1\,\mu\text{s}$).
In contrast, servicing a page fault requires disk access, typically taking $5\text{ to }10\text{ milliseconds}$ ($5,000,000\text{ to }10,000,000\text{ ns}$)!

Because disk latency is $100,000\times$ slower than DRAM, even a tiny fraction of page faults degrades performance catastrophically.

The Effective Memory Access Time Formula

Let:

• $p$ = Page Fault Rate (Probability of a page fault per memory access, $0 \le p \le 1$).
• $\text{MA}$ = Main Memory (DRAM) access time (e.g. $100\text{ ns}$).
• $\text{PFST}$ = Page Fault Service Time (e.g. $8\text{ ms} = 8,000,000\text{ ns}$).

$\mathbf{\text{EMAT}_{\text{DP}} = (1 - p) \cdot \text{MA} + p \cdot \text{PFST}}$

Numerical Derivation: Tolerable Page Fault Rate

Suppose an operating system targets a maximum performance degradation of less than $10\%$:

$\text{EMAT}_{\text{DP}} \le 1.10 \times \text{MA}$

$(1 - p) \cdot \text{MA} + p \cdot \text{PFST} \le 1.10 \cdot \text{MA}$

$\text{MA} - p \cdot \text{MA} + p \cdot \text{PFST} \le 1.10 \cdot \text{MA}$

$p \cdot (\text{PFST} - \text{MA}) \le 0.10 \cdot \text{MA}$

$p \le \frac{0.10 \cdot \text{MA}}{\text{PFST} - \text{MA}} \approx \frac{0.10 \cdot 100\text{ ns}}{8,000,000\text{ ns}} = \frac{10}{8,000,000} = \mathbf{1.25 \times 10^{-6}}$

Critical Performance Axiom:
To keep system slowdown under $10\%$, fewer than $1$ out of every $800,000$ memory references may trigger a page fault! ($p < 0.000125\%$).

---

5. The Modify (Dirty) Bit Optimization

When memory is completely full and a page fault occurs, the kernel must evict an existing victim page from physical DRAM to make room for the incoming page:

---

🏭 In The Real World: Production Case Study

Linux kswapd, Anonymous Pages & Memory Compaction

In production Linux kernels, waiting for a memory allocation to fail before evicting pages (Direct Reclaim) introduces massive tail-latency spikes. The kernel prevents this using asynchronous memory daemons:

Linux Memory Pressure Watermarks

Hierarchical memory thresholds governing background eviction and synchronous reclaim

High Watermark

Normal Wire-Speed Allocation (> 15% Free RAM)

🟢

Sufficient free memory available. Memory allocations complete directly from free page lists with zero swap stalls.

Fast-path allocationZero swap I/O latency

↓Free RAM decreases below low threshold

Low Watermark

Asynchronous Background Reclaim (< 10% Free RAM)

🟡

Kernel activates kswapd daemon in background. Asynchronously scans LRU lists and flushes dirty pages to disk.

kswapd background sweepFlushes dirty pages to swap

↓Free RAM drops below critical floor

Min Watermark

Direct Reclaim & OOM Killer (< 3% Free RAM)

🔴

Allocating threads stall synchronously in Direct Reclaim. If allocations still fail, kernel OOM Killer terminates processes.

Synchronous allocation stallsOOM Killer triggers SIGKILL

1. Background Eviction via kswapd:
   • When free memory crosses below the low watermark, kswapd wakes up in the background and writes dirty pages out to storage before RAM is completely exhausted.
2. File-Backed vs Anonymous Memory:
   • File-backed pages (such as code binaries and mapped database files) are clean and can be dropped instantly without writing to swap space.
   • Anonymous pages (stack, heap, and malloc buffers) have no file on disk and must be explicitly written to swap partitions or compressed in RAM using zRAM.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: In a computer system, memory access time is $200\text{ ns}$. It takes $10\text{ ms}$ ($10,000,000\text{ ns}$) to service a page fault if the victim page is clean, and $20\text{ ms}$ if the victim page is dirty. If $70\%$ of victim pages are dirty, and the page fault rate is $p = 10^{-4}$ ($0.01\%$), calculate the Effective Memory Access Time (EMAT). Answer:

1. Average Page Fault Service Time ($\text{PFST}$): $\text{PFST} = (0.30 \times 10\text{ ms}) + (0.70 \times 20\text{ ms}) = 3\text{ ms} + 14\text{ ms} = 17\text{ ms} = 17,000,000\text{ ns}$
2. Calculate EMAT: $\text{EMAT} = (1 - p) \cdot \text{MA} + p \cdot \text{PFST}$ $\text{EMAT} = (1 - 0.0001) \times 200 + (0.0001) \times 17,000,000$ $\text{EMAT} = 199.98 + 1700 = \mathbf{1899.98\text{ ns}} \approx \mathbf{1.9\,\mu\text{s}}$
3. Observation: A tiny page fault rate of only $0.01\%$ slows down average memory access from $200\text{ ns}$ to nearly $1900\text{ ns}$ (an almost $10\times$ performance collapse)!

---

Question 2: Why must the CPU restart the exact instruction that triggered a page fault, rather than proceeding to the next instruction? Answer:

1. A page fault is an interrupt / trap that occurs mid-instruction execution (during the instruction fetch phase or operand read/write phase).
2. The instruction never finished executing; its destination register or memory location was never updated.
3. If the CPU simply executed the next instruction, the program state would become corrupted (e.g. an un-fetched operand would be treated as garbage data).
4. Therefore, the CPU must roll back any micro-architectural side-effects (such as autoincremented index registers) and restart the identical instruction from scratch once the missing page is resident in RAM.

Common Interview Traps

• The Unit Conversion Trap: Always convert units to nanoseconds or milliseconds before evaluating EMAT. Mixing $100\text{ ns}$ with $8\text{ ms}$ without converting ($1\text{ ms} = 10^6\text{ ns}$) is the single most common mathematical mistake on university and technical exams.
• Confusing Page Fault with Hardware Crash: A page fault is NOT an error; it is a routine, planned hardware-software coordination mechanism that allows programs to execute seamlessly without requiring all pages to be pre-loaded into physical DRAM.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic7.7 Multi-Level Paging & SegmentationNext Topic →8.2 FIFO & Belady's Anomaly