Virtual Memory: Paging, Segmentation, Thrashing & Demand Paging

TAKEAWAYS:

• Virtual memory allows programs to use more memory than physically available by mapping logical addresses to physical frames.
• Paging divides memory into fixed-size blocks (pages/frames), while segmentation divides it into variable-sized logical units (segments).
• Thrashing occurs when the system spends more time swapping pages than executing processes, degrading performance.
• Page replacement algorithms (FIFO, LRU, Optimal) determine which page to replace when a page fault occurs.
• Demand paging loads pages into memory only when needed, reducing initial load time and memory usage.
• Working set model predicts future memory needs to minimize page faults and thrashing.

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) for each process, even when the physical RAM is fragmented or insufficient.

Why is Virtual Memory Needed?

• Limited Physical RAM: No system has enough RAM to hold all processes simultaneously.
• Process Isolation: Each process should not interfere with others.
• Efficient Memory Usage: Reuse memory by swapping unused parts to disk.
• Protection: Prevent processes from accessing memory they shouldn’t.

How Virtual Memory Works

1. Logical vs. Physical Addresses:
   • A process uses logical addresses (virtual addresses).
   • The Memory Management Unit (MMU) translates these to physical addresses (RAM locations).
2. Page Table: A data structure that maps logical pages to physical frames.
3. Page Fault Handling: If a page is not in RAM, the OS loads it from disk (page fault).

Paging: Dividing Memory into Fixed-Size Blocks

Paging divides both physical memory (frames) and logical memory (pages) into fixed-size blocks (typically 4KB or larger).

How Paging Works

1. Page Table Entry (PTE):

   • Contains the frame number where the page is stored.
   • Includes valid/invalid bit (indicates if the page is in RAM).
   • May include protection bits (read/write/execute permissions).
   • Reference bit: Tracks if the page was accessed recently (used in page replacement).
   • Modified bit: Indicates if the page was modified (needs to be written back to disk).

2. Address Translation:

   • A logical address is split into:
     • Page number (used as an index in the page table).
     • Offset (used to locate the exact byte within the page).
   • The MMU combines the frame number (from the page table) with the offset to get the physical address.

   Logical Address (32-bit)
   -------------------------
   | Page Number (20 bits) | Offset (12 bits)
   -------------------------
             |
             v
   Page Table Entry (PTE)
   -------------------------
   | Frame Number (20 bits) | Valid | Reference | Modified
   -------------------------
             |
             v
   Physical Address (32-bit)
   -------------------------
   | Frame Number (20 bits) | Offset (12 bits)
   -------------------------

Example: Paging in Action

Suppose:

• Physical memory has 16 frames (each 4KB).
• A process has 8 pages (each 4KB).
• The page table maps:
  • Page 0 → Frame 5
  • Page 1 → Frame 12
  • Page 2 → Frame 3 (not in RAM, page fault!)
  • Page 3 → Frame 8

If the CPU tries to access Page 2, Offset 1000, the MMU:

1. Checks the page table → Page 2 is invalid (not in RAM).
2. Triggers a page fault.
3. The OS loads Page 2 from disk into an empty frame (or replaces an existing one).
4. Updates the page table.
5. Retries the access.

Segmentation: Variable-Sized Logical Divisions

Unlike paging, segmentation divides memory into variable-sized logical units (segments), each representing a part of a program (e.g., code, data, stack, heap).

Segmentation Table

• Each process has a segment table mapping segment numbers to their base and limit.
• A logical address is split into:
  • Segment number (index into the segment table).
  • Offset (within the segment).

   Logical Address
   -------------------------
   | Segment Number | Offset
   -------------------------
             |
             v
   Segment Table Entry (STE)
   -------------------------
   | Base Address | Limit
   -------------------------
             |
             v
   Physical Address = Base + Offset (if Offset < Limit)

Example: Segmentation in a C Program

A C program has:

1. Code segment (instructions).
2. Data segment (global variables).
3. Stack segment (local variables, function calls).
4. Heap segment (dynamic memory allocation).

If a process tries to access data[1000]:

1. The segment number (e.g., 1 for data) is used to find the base address.
2. The offset (1000) is added to the base.
3. If the offset exceeds the limit, a segmentation fault occurs.

Paging vs. Segmentation

Demand Paging: Load Pages Only When Needed

Instead of loading an entire process into memory at once, demand paging loads pages only when they are accessed.

How Demand Paging Works

1. Initial Load: Only a few pages (e.g., code segment) are loaded.
2. Page Fault: When a page is accessed but not in RAM:
   • OS checks if the page is on disk.
   • If yes, loads it into an empty frame (or replaces a page).
   • Updates the page table.
3. Prepaging: Optionally loads adjacent pages (predictive loading).

Advantages of Demand Paging

• Reduced I/O: Only necessary pages are loaded.
• Faster Startup: Processes start executing sooner.
• Efficient Memory Usage: Unused pages stay on disk.

Disadvantages

• Page Fault Overhead: Loading a page from disk is slow (~1-10ms).
• Thrashing Risk: Too many page faults can degrade performance.

Page Replacement Algorithms

When a page fault occurs and no free frames are available, the OS must replace an existing page. Common algorithms:

1. First-In-First-Out (FIFO)

• Replaces the oldest page in memory.
• Simple but not optimal (may replace frequently used pages).

2. Least Recently Used (LRU)

• Replaces the least recently used page.
• Better than FIFO but requires hardware support (reference bits).

3. Optimal (OPT)

• Replaces the page that will not be used for the longest time.
• Theoretically optimal but impossible to implement (requires future knowledge).

4. Clock (Second Chance)

• A circular list of pages with a reference bit.
• If a page’s bit is 0, it is replaced.
• If 1, it gets a "second chance" (bit set to 0).

stateDiagram-v2
    [*] --> PageFault
    PageFault --> IsPageInMemory?
    IsPageInMemory? -->|Yes| AccessPage
    IsPageInMemory? -->|No| PageReplacement
    PageReplacement --> ChooseAlgorithm
    ChooseAlgorithm --> FIFO
    ChooseAlgorithm --> LRU
    ChooseAlgorithm --> OPT
    ChooseAlgorithm --> Clock
    FIFO --> ReplaceOldest
    LRU --> ReplaceLeastUsed
    OPT --> ReplaceOptimal
    Clock --> ReplaceIfBit0
    ReplaceOldest --> [*]
    ReplaceLeastUsed --> [*]
    ReplaceOptimal --> [*]
    ReplaceIfBit0 --> [*]

Thrashing: The Performance Killer

Thrashing occurs when:

• A process spends more time swapping pages than executing.
• The page fault rate is extremely high.
• The system becomes unresponsive.

Causes of Thrashing

1. Insufficient Frames: Too many processes competing for limited RAM.
2. Poor Page Replacement: Algorithm replaces useful pages too often.
3. High Locality: Processes access a small set of pages repeatedly (but not enough frames are allocated).

Solutions to Thrashing

1. Increase Frames: Allocate more physical memory.
2. Better Page Replacement: Use LRU or Clock instead of FIFO.
3. Working Set Model: Allocate frames based on a process’s active page set.
4. Prepaging: Load likely-to-be-used pages in advance.
5. Reduce Multiprogramming Degree: Run fewer processes simultaneously.

Working Set Model

The working set of a process is the set of pages actively used in a given time window (e.g., last 10,000 instructions).

How It Works

1. Monitor page references over a time window.
2. If a page is not referenced, it is likely not in the working set.
3. Allocate frames based on the working set size.

Advantages

• Reduces unnecessary page faults.
• Prevents thrashing by ensuring enough frames for active pages.

## In the Real World

Virtual memory is everywhere in modern computing. Here’s how it’s used in real-world systems:

1. Mobile Apps (WhatsApp, Pathao)

• Demand Paging: When you open WhatsApp, only the login screen is loaded initially. As you scroll, messages are loaded on demand.
• Page Replacement: If your phone runs out of RAM, WhatsApp pages (or even the entire app) may be swapped to disk, causing lag until they’re reloaded.

2. Cloud Services (Google, AWS)

• Virtualization: Cloud providers use virtual memory to give each virtual machine (VM) the illusion of dedicated RAM, even when multiple VMs share the same physical server.
• Example: AWS EC2 instances use KVM (Kernel-based Virtual Machine) to manage memory for multiple VMs, ensuring isolation and efficient usage.

3. Online Banking (Nabil Bank, Global IME)

• Segmentation: A banking app divides memory into segments:
  • Code (transaction logic).
  • Data (user accounts, balances).
  • Stack (temporary calculations).
• Thrashing Prevention: Banks use LRU caching to keep frequently accessed account data in RAM, reducing disk I/O.

4. E-Commerce (Daraz, Amazon)

• Demand Paging: When you browse Daraz, product pages are loaded only when you click them, not all at once.
• Page Replacement: If Daraz’s server runs low on RAM, it swaps out inactive product catalog pages to disk.

5. Nepali Government Services (eSewa, Khalti)

• Virtual Memory in APIs: When you pay a bill via eSewa, the backend system uses virtual memory to handle thousands of transactions simultaneously without crashing.
• Example: During Dashain, when millions of users access eSewa, the system dynamically allocates memory using demand paging to avoid thrashing.

Worked Example: Bank Loan Interest Calculation (Thrashing Scenario)

Suppose a bank’s loan processing system:

• Has 1GB RAM but runs 100 processes (each needing ~20MB).
• Uses FIFO page replacement.

Problem: The system starts thrashing because:

• Each process gets only 10MB frames (50% of its need).
• Pages are constantly swapped in and out.

Solution:

1. Increase Frames: Allocate 20MB per process (full working set).
2. Use LRU: Replace the least recently used loan data pages.
3. Prepaging: Load common loan forms (e.g., EMI calculator) in advance.

Result: Loan processing becomes faster and stable, even during peak hours.

## Exam Tip

This unit is highly practical and often tested with:

1. Memory Allocation Scenarios:

   • Given partitions and process sizes, draw how First-Fit, Best-Fit, and Worst-Fit would allocate memory (even though this is fixed partitioning, it tests your understanding of fragmentation).
   • Example Question:

     "Given partitions: 100KB, 500KB, 200KB, 300KB, 600KB. Allocate processes: 212KB, 417KB, 112KB, 426KB using First-Fit. Show external fragmentation."

2. Paging and Segmentation Comparisons:

   • Expect definition + one advantage/disadvantage for each.
   • Example:

     "Differentiate paging and segmentation. Which one is better for a C++ program? Why?" Answer: Segmentation is better for C++ because it supports logical divisions (code, data, stack, heap) naturally.

3. Page Replacement Algorithms:

   • Trace-based questions: Given a page reference string (e.g., 1, 2, 3, 4, 1, 2, 5), calculate page faults for FIFO, LRU, and OPT.
   • Example:

     *"For frames = 3, reference string = 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2:

     • FIFO page faults = 9
     • LRU page faults = 7
     • OPT page faults = 5"

4. Thrashing and Solutions:

   • Explain thrashing + three solutions (e.g., increase frames, use LRU, working set model).
   • Example:

     "A system is thrashing. How can the OS prevent it?" Answer:

     1. Increase physical memory.
     2. Reduce the number of processes (lower multiprogramming degree).
     3. Use a better page replacement algorithm (LRU).

5. Demand Paging vs. Prepaging:

   • Define both and give a real-world analogy (e.g., loading a YouTube video in chunks vs. buffering the whole thing).

Common Mistakes to Avoid

1. Confusing Paging and Segmentation:

   • Paging = fixed-size blocks, segmentation = variable-size logical units.
   • Never mix them up in definitions!

2. Ignoring Page Table Entries (PTE):

   • Always mention valid/invalid bit, reference bit, and modified bit in explanations.

3. Forgetting to Explain Thrashing:

   • Thrashing is not just "too many page faults"—it’s when the system spends more time swapping than executing.

4. Assuming All Algorithms Are Equal:

   • FIFO is worse than LRU, and OPT is theoretical. Know which is better in practice.

5. Not Drawing Diagrams:

   • Always sketch:
     • Page table entries.
     • Address translation (logical → physical).
     • Page replacement scenarios.

Summary Table: Key Concepts