Virtual Memory: Page Faults, Thrashing, and Replacement Algorithms

This comprehensive chapter explores advanced memory management mechanisms in operating systems, focusing on how virtual memory abstracts physical constraints, how demand paging handles missing pages, how replacement algorithms optimize resource allocation, and how system degradation like thrashing occurs when overhead overtakes execution.

1. Why Do We Need Virtual Memory? (The Problem Statement)

In traditional memory management systems, an entire process must be loaded into physical memory (RAM) contiguously or non-contiguously before execution can begin. This imposes strict hardware bottlenecks:

• Limited RAM Capacity: Large programs (e.g., modern IDEs, games, heavy computations) exceed physical RAM size.
• Low Multipriming Degree: Fitting entire processes limits how many concurrent programs can reside in memory simultaneously.
• Internal and External Fragmentation: Wasted memory blocks degrade overall system throughput.

Virtual Memory solves this by separating the logical memory perceived by the user/programmer from the physical memory available in hardware. It creates an illusion of a massive, contiguous address space backed by secondary storage (SSD/HDD).

2. Core Mental Model: The Illusion of Infinite Space

Virtual memory acts like a librarian managing a massive library with a tiny reading desk (RAM). Instead of keeping all books (processes) on the desk at once, the librarian keeps only the currently needed chapters open on the desk and stores the rest on the bookshelves (secondary storage/swap space). When a reader requests a chapter not currently on the desk, the librarian swaps out an inactive chapter to fetch the requested one.

3. Segmentation vs. Paging: A Comparative Breakdown

Before diving into virtual memory mechanics, it is vital to contrast the two primary memory management strategies that precede it: Paging and Segmentation.

Note: As discussed in interviews, while paging handles allocation cleanly via fixed frames, segmentation preserves the logical structure of programs (functions, data structures, stacks).

4. Demand Paging and Page Fault Handling

What is Demand Paging?

Demand paging is a lazy-loading strategy where pages are loaded into physical memory only when they are explicitly demanded during execution.

Page Fault Life Cycle

When a CPU tries to access a virtual address whose page is currently resident only in secondary storage (not in RAM), a hardware trap occurs—known as a Page Fault.

Step-by-Step Page Fault Workflow:

5. Page Replacement Algorithms

When a page fault occurs and physical RAM is completely full, the operating system must evict an existing page to make room for the incoming page. Several classic algorithms govern this selection process.

A. FIFO (First-In, First-Out)

• Mechanism: Replaces the oldest page in memory—the one that has resided in RAM the longest, regardless of how frequently or recently it has been accessed.
• Drawback: Can suffer from Belady's Anomaly, where increasing the number of allocated physical frames paradoxically increases the number of page faults.

B. Optimal Page Replacement

• Mechanism: Replaces the page that will not be used for the longest period of time in the future.
• Drawback: Theoretical / unplementable in general-purpose operating systems because it requires clairvoyance (knowing future CPU reference strings). It serves as a benchmark for evaluating other algorithms.

C. LRU (Least Recently Used)

• Mechanism: Approximates the optimal algorithm by looking backward rather than forward. It evicts the page that has not been referenced for the longest duration.
• Implementation: Requires hardware timestamping or doubly linked lists of reference bits, making it accurate but resource-intensive.

D. Clock Algorithm (Second Chance)

• Mechanism: A practical approximation of LRU. Pages are arranged in a circular buffer (like a clock face) with a reference bit.
  • If the reference bit is 1, it is given a "second chance" (reset to 0), and the clock hand moves to the next page.
  • If the reference bit is 0, that page is immediately evicted and replaced.

6. Thrashing: When Overhead Outpaces Execution

Definition of Thrashing

Real-Life Analogy: Thrashing is akin to spending more time driving to the grocery store, looking for parking, and walking back than actually buying groceries. In computing, Process Execution Time < Paging Overhead Time.

Thrashing occurs when a system spends more time servicing page faults than executing actual application instructions.

Why Thrashing Happens

1. Over-allocation: The operating system admits too many concurrent processes into memory.
2. Insufficient Frames: Each process receives fewer frames than its working set requires.
3. Continuous Swapping: Process $A$ faults, evicting a page belonging to Process $B$. Process $B$ immediately faults to retrieve its page, evicting Process $A$'s page.
4. CPU Starvation: CPU utilization plummets because the CPU sits idle waiting for slow disk I/O operations to complete.

7. File Systems and Storage Organization

Transitioning from core memory management, operating systems also organize persistent data via file systems.

File Attributes & Operations

• Attributes: File Name, Type, Location, Size, Creation Timestamp, Ownership, and Access Permissions.
• Core Operations: Create, Read, Write, Reposition (Seek), Delete, Open, and Close.

File Access Methods

1. Sequential Access: Data is processed in order, one record after another (e.g., magnetic tapes).
2. Direct / Random Access: Records can be accessed in any arbitrary order directly via block numbers (e.g., SSDs, hard disks).
3. Indexed Access: Built on top of direct access using index structures (analogous to database indexes in SQL or MongoDB) to speed up record retrieval.

Directory Structures

Directories organize files hierarchically:

• Single-Level Directories: All files reside in one shared directory (prone to naming collisions).
• Two-Level Directories: Separate directories maintained for each individual user.
• Tree-Structured Directories (Hierarchical): Modern standard where directories can contain subdirectories (folders) and files arbitrarily deep (e.g., /home/shivansh/docs/image.png).

Summary and Key Takeaways

• Virtual Memory abstracts physical memory limits by creating an illusion of large, contiguous address space backed by secondary storage.
• Demand Paging loads pages into RAM only when explicitly requested, minimizing upfront memory allocation.
• Page Faults trigger a multi-step OS interrupt handling routine to fetch missing pages from disk into available RAM frames.
• Page Replacement Algorithms (FIFO, Optimal, LRU, Clock) dictate which page to evict when physical memory is exhausted.
• Thrashing occurs when page fault overhead exceeds actual instruction execution time, leading to severe CPU underutilization.
• Paging vs. Segmentation: Paging uses fixed-size blocks with internal fragmentation and is transparent to users; segmentation uses variable-size logical units with external fragmentation and visible structure.
• File Systems organize persistent secondary storage through attributes, operations, access methods (sequential, direct, indexed), and hierarchical tree structures.