Virtual Memory & Page Replacement: Concepts, Algorithms & Real-World Impact

TAKEAWAYS:

• Virtual memory maps logical addresses to physical memory using page tables, enabling programs to run even when RAM is full.
• Page replacement algorithms (FIFO, LRU, OPT) determine which page to evict when a page fault occurs, balancing speed and accuracy.
• Thrashing occurs when excessive page faults degrade system performance, requiring careful tuning of page frames.
• Demand paging loads pages only when needed, reducing initial memory usage but increasing page faults.
• Real-world systems (e.g., Android’s memory management, cloud VMs) use these techniques to optimize resource usage.

---

1. What is Virtual Memory?

Virtual memory is a memory management technique that allows a computer to use disk storage as an extension of RAM. It creates an illusion of a large, contiguous memory space (virtual address space) while the system physically uses smaller, fragmented RAM (physical memory).

Why Use Virtual Memory?

• Efficient memory usage: Programs can run even if RAM is full by swapping unused pages to disk.
• Protection & isolation: Each process gets its own virtual address space, preventing interference.
• Simplified programming: Developers write code assuming unlimited memory, while the OS handles constraints.

Key Components

┌───────────────────────────────────────────────────────┐
│                Virtual Address Space                  │
│  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐  │
│  │   Page 0    │  │   Page 1    │  │   Page N    │  │
│  └─────────────┘  └─────────────┘  └─────────────┘  │
└───────────────────────────────────────────────────────┘
                     ↓
┌───────────────────────────────────────────────────────┐
│                Physical Memory (RAM)                  │
│  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐  │
│  │   Frame 1   │  │   Frame 2   │  │   Frame 3   │  │
│  └─────────────┘  └─────────────┘  └─────────────┘  │
└───────────────────────────────────────────────────────┘
                     ↓
┌───────────────────────────────────────────────────────┐
│                Disk (Swap Space)                      │
│  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐  │
│  │   Swap File │  │   Swap File │  │   Swap File │  │
│  └─────────────┘  └─────────────┘  └─────────────┘  │
└───────────────────────────────────────────────────────┘

• Page: Fixed-size block of virtual memory (e.g., 4KB).
• Frame: Fixed-size block of physical memory (same size as a page).
• Page Table: Maps virtual pages to physical frames.
• Page Fault: Occurs when a requested page is not in RAM (must be loaded from disk).

How Address Translation Works

1. CPU generates a logical (virtual) address.
2. The MMU (Memory Management Unit) splits it into:
   • Page number (used as an index in the page table).
   • Offset (used to locate the exact byte within the page).
3. The page table entry (PTE) gives the frame number (if the page is in RAM).
4. The physical address is formed by combining the frame number and offset.

┌─────────────┐       ┌─────────────┐       ┌─────────────┐
│ Logical     │──────▶│ Page Table │──────▶│ Physical    │
│ Address     │       │ (Maps      │       │ Address     │
│ (e.g., 0x1234)│     │ virtual →  │       │ (e.g., 0x5678)│
└─────────────┘       │ physical)  │       └─────────────┘
                      └─────────────┘

---

2. Demand Paging

Demand paging loads pages into memory only when they are needed, reducing initial memory usage.

How It Works

1. A process starts with no pages in RAM.
2. When a page is accessed (e.g., instruction fetch, data read), a page fault occurs.
3. The OS:
   • Checks if the page is on disk (valid reference).
   • If yes, loads it into an empty frame.
   • If no frames are free, a page replacement algorithm evicts a page.

Advantages

• Reduced memory usage: Only necessary pages are loaded.
• Faster startup: Programs begin execution without loading entire code/data.

Disadvantages

• Page faults increase overhead: Disk I/O is slow (~milliseconds vs. RAM access in nanoseconds).
• Thrashing: Excessive page faults can degrade performance.

---

3. Page Replacement Algorithms

When a page fault occurs and no free frames are available, the OS must evict a page to make space. The choice of algorithm affects performance.

Comparison Table

Worked Example: Page Faults with FIFO, LRU, and OPT

Page Reference String: 9, 3, 4, 5, 3, 9, 6, 7, 3, 9, 3, 4, 8, 7, 4, 3, 9, 3, 4, 7 Frames Available: 3

FIFO (First-In-First-Out)

• Evicts the oldest page when a new page must be loaded.
• Page Faults: 15 (see trace below).

Time: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Ref: 9 3 4 5 3 9 6 7 3  9  3  4  8  7  4  3  9  3  4  7
Mem: 9 9 9 5 5 5 5 5 3  3  3  3  8  8  8  3  3  3  4  4
Flt: Y Y Y Y Y Y Y Y Y  N  N  N  Y  Y  Y  N  Y  N  N  Y

Explanation:

• At time 13, page 8 is loaded, evicting 4 (oldest).
• At time 16, page 3 is already in memory (no fault).
• Total faults: 15.

LRU (Least Recently Used)

• Evicts the page not used for the longest time.
• Page Faults: 12 (better than FIFO).

Time: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Ref: 9 3 4 5 3 9 6 7 3  9  3  4  8  7  4  3  9  3  4  7
Mem: 9 9 9 5 5 3 3 3 7  7  7  4  4  4  8  8  8  3  3  3
Flt: Y Y Y Y Y Y Y Y Y  N  N  Y  Y  Y  Y  N  Y  N  N  Y

Explanation:

• At time 13, page 8 replaces 7 (LRU).
• At time 16, 3 is already in memory (no fault).
• Total faults: 12.

OPT (Optimal)

• Evicts the page that will not be used for the longest time (theoretical, not implementable).
• Page Faults: 9 (best possible).

Time: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Ref: 9 3 4 5 3 9 6 7 3  9  3  4  8  7  4  3  9  3  4  7
Mem: 9 9 9 5 5 5 5 5 3  3  3  3  3  3  8  8  8  8  4  4
Flt: Y Y Y Y Y Y Y Y Y  N  N  N  N  Y  N  Y  N  Y  N  Y

Explanation:

• At time 13, 5 is evicted (not used until time 15).
• At time 16, 5 is not in memory (fault).
• Total faults: 9.

---

4. Thrashing

Thrashing occurs when a process spends more time paging (swapping pages in/out) than executing. This happens when:

• The system runs out of free frames.
• Too many processes compete for limited memory.

Symptoms

• High CPU usage (constant disk I/O).
• Low throughput (fewer processes complete per unit time).
• Poor response time.

Solution: Working Set Model

• Allocate frames based on the working set (pages a process will use in the near future).
• Prevents thrashing by ensuring enough frames are available.

---

5. Real-World Applications

In the Real World

1. Android (Mobile OS)

   • Uses LRU-based page replacement to manage limited RAM on smartphones.
   • When apps are backgrounded, their pages are swapped to disk (swap space) if needed.
   • Example: When you switch between WhatsApp and YouTube, Android may evict WhatsApp’s pages to free RAM for YouTube.

2. Cloud Computing (AWS, Google Cloud)

   • Virtual machines (VMs) use demand paging to share physical servers efficiently.
   • If a VM’s page is not in RAM, it is fetched from disk (or another server’s cache).
   • Example: When you deploy a new VM on AWS, its initial pages are loaded on-demand, reducing startup time.

3. Online Banking (Nepal’s NMB Bank, GlobalPay)

   • Banks use virtual memory to handle thousands of transactions simultaneously.
   • When a customer requests a balance check, the bank’s OS loads only the relevant account pages into RAM.
   • Example: During Diwali season, when millions of transactions occur, banks rely on virtual memory to avoid crashes.

4. eSewa & Khalti (Digital Payment Apps)

   • These apps use demand paging to load only necessary modules (e.g., payment processing, user profiles) into memory.
   • If a user’s transaction history is rarely accessed, it may reside on disk until needed.
   • Example: When you pay your electricity bill via eSewa, the app loads the payment module into RAM, while other features remain on disk.

5. Pathao & Daraz (Ride-Hailing & E-Commerce)

   • Pathao’s driver-matching algorithm uses virtual memory to handle millions of user requests efficiently.
   • Daraz’s order processing system loads product pages into RAM only when a customer views them.
   • Example: During Dashain sales, Daraz’s servers use virtual memory to handle spikes in traffic without crashing.

---

6. Worked Example: Thrashing in a Bank’s Loan Processing System

Scenario: A bank’s loan processing system has:

• Physical Memory (RAM): 100 frames.
• Active Processes: 50 loan applications, each requiring 50 pages.
• Page Fault Rate: Initially low, but increases as more loans are processed.

Problem: If the bank approves too many loans simultaneously, the system may thrash because:

1. Each loan process needs 50 pages → Total pages needed = 50 × 50 = 2500.
2. RAM has only 100 frames → Page faults skyrocket.
3. The CPU spends more time swapping pages than processing loans.

Solution:

• Use the working set model to allocate frames dynamically.
• Monitor page fault rates and increase RAM or reduce concurrent loan processes.

---

7. Exam Tip

What Examiners Look For

1. Definitions:

   • Clearly define virtual memory, page fault, thrashing, and demand paging.
   • Example: "Virtual memory is a technique that uses disk storage as an extension of RAM to allow programs to run with larger address spaces than physical memory."

2. Algorithms:

   • Trace page replacement for given reference strings (FIFO, LRU, OPT).
   • Compare algorithms in a table (page faults, overhead, thrashing risk).
   • Example: "For the reference string 1,2,3,4,1,2,5,1,2,3,4,5, FIFO with 3 frames causes 9 page faults, while LRU causes 7."

3. Real-World Applications:

   • Link concepts to mobile OSes (Android/iOS), cloud computing (AWS), or banking systems.
   • Example: "Android uses LRU page replacement to manage limited RAM on smartphones, evicting least recently used app pages when memory is full."

4. Thrashing:

   • Explain symptoms (high CPU, low throughput) and solutions (working set model, increasing frames).
   • Example: "Thrashing occurs when a system spends more time paging than executing. The working set model prevents this by allocating frames based on a process’s active pages."

5. Diagrams:

   • Draw address translation, page table entries, and page replacement traces.
   • Example:

 ```
 ┌───────────────────────────────┐
 │ Page Number | Frame Number   │
 │ (Virtual)   | (Physical)     │
 │ 0x123       | 0x456          │
 │ Present Bit | Dirty Bit      │
 │ Valid       | Modified       │
 └───────────────────────────────┘
 ```

Common Mistakes to Avoid

• Incorrect traces: Double-check every step in FIFO/LRU/OPT traces.
• Ignoring thrashing: Always mention its causes and solutions.
• Vague answers: Use numbers (e.g., "LRU reduces page faults by 30% compared to FIFO").
• Forgetting real-world ties: Examiners love connections to Android, cloud, or banking.

Sample Exam Questions & Answers

Q1: "Explain demand paging with a diagram. What are its advantages and disadvantages?" Answer:

┌─────────────┐       ┌─────────────┐       ┌─────────────┐
│ Process     │──────▶│ Page Fault │──────▶│ Load Page   │
│ Accesses    │       │ Occurs     │       │ from Disk   │
│ Page X      │       │ (Not in    │       │ into Frame │
│             │       │ RAM)       │       │             │
└─────────────┘       └─────────────┘       └─────────────┘

Advantages:

• Reduces memory usage (only necessary pages loaded).
• Faster program startup (no need to load entire code at once).

Disadvantages:

• Page faults increase overhead (disk I/O is slow).
• Risk of thrashing if too many page faults occur.

---

Q2: "Consider the page reference string 7,0,1,2,0,3,0,4,2,3,0,3,2 with 4 frames. Calculate page faults for FIFO and LRU." Answer:

---