The Virtual Memory Illusion

Section 2 introduced paging: a process's pages can be scattered across any available physical frames. But paging still assumed that all of a process's pages must be in RAM simultaneously. Virtual memory removes even this constraint.

The key observation: At any point during execution, a process only actively uses a small fraction of its total address space. Functions that handle rare error conditions, initialization code that runs once and never again, large arrays where only a few elements are accessed at a time — all of this takes up space in the logical address space but sits idle most of the time.

Virtual memory's promise: Keep only the actively needed pages in RAM. Store the rest on disk. Move pages in and out of RAM on demand. The process never knows this is happening — it still sees a continuous, full logical address space.

---

Demand Paging: The Lazy Loading Strategy

Demand paging is the most widely used virtual memory scheme. Its principle is simple:

Never load a page into RAM until a process actually references it.

When a process starts, none of its pages need to be in RAM. The OS only loads a page when the process generates a memory access to that page. This is sometimes called lazy loading (as opposed to pre-paging, where the OS tries to predict and pre-load pages it thinks will be needed soon).

The Mechanism: The Valid/Invalid Bit (Revisited)

Recall from Section 2 that each page table entry has a valid/invalid bit:

• Valid (1): The page is in RAM. The frame number in the entry is correct and usable.
• Invalid (0): The page is either on disk (swapped out) or is not part of the process's legal address space.

With demand paging, when a process starts, all page table entries are initialized to invalid. Pages are loaded on demand, and their bits are flipped to valid one by one as they are needed.

Benefits of Demand Paging

1. Larger logical address spaces: A process can have a 4GB logical address space on a machine with only 512MB of RAM.
2. Higher degree of multiprogramming: Since each process only uses a fraction of RAM, more processes can be in memory simultaneously, improving CPU utilization.
3. Faster program startup: A program begins executing immediately (with no pages loaded) rather than waiting for its entire image to be copied to RAM.
4. Efficient RAM usage: RAM is only consumed by pages that are actually needed, not by code that is never reached.

The Page Fault: When a Required Page is Not in RAM

When the CPU generates a logical address and the MMU checks the page table entry for that page — and finds the valid/invalid bit = 0 (page not in RAM) — the hardware triggers a page fault trap. Control transfers immediately to the OS's page fault handler.

The Complete Page Fault Handling Sequence

The key insight — restarting the instruction: The faulting instruction is restarted from scratch (not resumed mid-execution). This is possible because the OS saved the process's exact state (PC, registers) before handling the fault. When the page is now in RAM, the instruction executes successfully without the process ever knowing a disk access occurred.

---

Performance of Demand Paging: The EAT Formula

Every page fault involves a disk I/O operation, which is millions of times slower than RAM access. Even rare page faults drastically degrade performance.

Effective Access Time with Page Faults:

$\text{EAT} = (1 - p) \times m + p \times \text{page fault service time}$

Where:

• $p$ = page fault rate (probability that a given memory access causes a fault; $0 \leq p \leq 1$)
• $m$ = memory access time (without a fault; e.g., 200 ns)
• Page fault service time = time to handle the fault, load the page from disk, and restart = typically 8–20 milliseconds (dominated by disk seek + rotational latency)

Worked Example:

Given: $m = 200$ ns, page fault service time = $8$ ms = $8,000,000$ ns, $p = \frac{1}{1000}$ (1 fault per 1000 accesses)

$\text{EAT} = \left(\frac{999}{1000}\right)(200) + \left(\frac{1}{1000}\right)(8{,}000{,}000)$ $= 199.8 + 8{,}000 = 8{,}199.8 \text{ ns}$

Without any page faults: EAT = 200 ns. With just 1 fault per 1000 accesses: EAT ≈ 8,200 ns — a 41× slowdown.

Conclusion: To keep demand paging practical, the page fault rate $p$ must be kept extremely small (typically $p < \frac{1}{400,000}$ to limit slowdown to under 10%). This is achieved by locality of reference — explained next.

Locality of Reference: Why Demand Paging Works in Practice

The EAT formula shows that even rare page faults are catastrophic. Yet demand paging works extremely well in practice, with CPUs spending very little time on page fault handling. Why?

The answer is Locality of Reference — a fundamental property of almost all programs.

---

Temporal Locality

A resource that was recently used is very likely to be used again in the near future.

• A loop iterates over the same instructions hundreds of times → same pages accessed repeatedly.
• A recently-called function's local variables are likely accessed again → same stack page accessed repeatedly.
• Implication: Once a page is loaded, it tends to be accessed many times before being needed from disk again.

Spatial Locality

If a resource at address X is accessed, resources at addresses near X are likely to be accessed soon.

• Sequential instruction execution: after instruction at address A, instruction at A+4 is next → same or adjacent page.
• Array traversal: after accessing arr[0], arr[1] is next → same page (for most array sizes).
• Implication: Loading a full page (4KB) at once captures dozens of nearby variables and instructions that will be needed shortly, amortizing the disk I/O cost.

Together, these two properties mean: The "active" set of pages a program needs at any point in time is small and changes slowly. This keeps the page fault rate $p$ extremely low.

---

The Working Set Model

The Working Set is the formal model that captures locality of reference. It is used by OS designers to decide how many frames each process needs.

Definition: The Working Set of process $P_i$ at time $t$ with window $\Delta$ is: $W(P_i, t, \Delta) = \text{set of distinct pages referenced by } P_i \text{ in the time interval } (t - \Delta,\; t)$

• $\Delta$ (the working set window) is typically measured in page references (e.g., $\Delta = 10,000$ references).
• $|W(P_i, t, \Delta)|$ = the working set size = number of distinct pages in the working set.

Intuition: The working set captures the pages a process is "actively using" right now. Pages that were used long ago (more than $\Delta$ references back) fall out of the working set.

---

Thrashing: When Working Sets Exceed Available RAM

Let $D$ = the total memory demand across all processes: $D = \sum_{i} |W(P_i, t, \Delta)|$

And let $m$ = total number of available physical frames.

If $D > m$: The OS cannot keep every process's working set in RAM simultaneously. Processes constantly page fault. Each fault causes a disk I/O. Processes are constantly suspended, waiting for pages to be loaded. The CPU becomes idle — not because processes are done, but because they're all waiting for disk I/O.

This vicious cycle is called thrashing. CPU utilization collapses despite the system being "busy."

The CPU Utilization vs. Degree of Multiprogramming Curve:

---

The Working Set Strategy: Preventing Thrashing

The OS uses the working set model to control the degree of multiprogramming:

1. Monitor the working set size $|W(P_i, t, \Delta)|$ of each process.
2. Calculate total demand $D = \sum |W_i|$.
3. If $D > m$: Suspend (swap out) one or more processes to free frames until $D \leq m$. The suspended process's pages are written to disk. When a frame becomes available, resume a suspended process.
4. If $D < m$ significantly: Admit a new process to improve CPU utilization.

This ensures every process in memory has its working set fully resident in RAM, keeping page fault rates low and CPU utilization high.

Exam note: The working set strategy is essentially a dynamic form of process scheduling at the memory level. The OS is deciding not just who gets the CPU, but who gets to stay in RAM.