Virtual Memory: Paging, Segmentation, Demand Paging & Thrashing

TAKEAWAYS:

• Virtual memory allows systems to use disk storage as an extension of RAM, enabling execution of larger programs than physical memory permits.
• Paging divides memory into fixed-size blocks (pages/frames) while segmentation groups logically related data into variable-sized segments.
• Demand paging loads pages into memory only when needed, reducing initial load time and memory usage.
• Page replacement algorithms (FIFO, LRU, OPT) determine which page to evict when memory is full, directly impacting system performance.
• Thrashing occurs when excessive paging slows down the system, requiring careful tuning of page replacement policies.
• Swapping and memory-mapped files are practical applications of virtual memory in modern operating systems.

---

Core Concepts: Virtual Memory Basics

Virtual memory is a memory management technique that gives an application the illusion of having a large, contiguous memory space, even when the physical RAM is insufficient. It achieves this by:

• Using disk storage as an extension of RAM.
• Translating virtual addresses (used by programs) to physical addresses (used by hardware).
• Loading only the necessary parts of a program into memory at any given time.

How Virtual Memory Works

1. Virtual Address Space: Each process sees its own private address space, isolated from others.
2. Page Table: Maps virtual pages to physical frames in RAM.
3. Hardware Support: The MMU (Memory Management Unit) translates virtual addresses to physical addresses.
4. Disk Backing Store: Pages not in RAM are stored on disk (swap space).

---

Paging: Fixed-Size Memory Division

Paging divides both physical memory (frames) and virtual memory (pages) into fixed-size blocks (typically 4KB). This simplifies memory allocation and management.

Key Terms:

• Page: Fixed-size block of virtual memory.
• Frame: Fixed-size block of physical memory.
• Page Table: A data structure that maps virtual pages to physical frames.
• Page Table Entry (PTE): Contains:
  • Valid bit: Indicates if the page is in RAM.
  • Frame number: Physical location of the page.
  • Protection bits: Read/write/execute permissions.
  • Reference bit: Tracks if the page was accessed recently.
  • Dirty bit: Indicates if the page was modified.

Address Translation in Paging

When a process generates a virtual address, the system breaks it into:

• Page number: Used as an index in the page table.
• Offset: Used to locate the exact byte within the page.

Virtual Address = (Page Number, Offset)
Physical Address = (Frame Number, Offset)

|---------------------|

---

Segmentation: Variable-Size Memory Division

Unlike paging, segmentation divides memory into variable-sized logical units (segments), each representing a part of the program (e.g., code, data, stack, heap). This provides better memory utilization but complicates management.

Key Terms:

• Segment: Logical division of a program (e.g., code segment, data segment).
• Segment Table: Maps segment numbers to their base and limit addresses.
• Base Address: Starting physical address of the segment.
• Limit: Size of the segment.

Address Translation in Segmentation

A virtual address in segmentation consists of:

• Segment number: Index into the segment table.
• Offset: Location within the segment.

Virtual Address = (Segment Number, Offset)
Physical Address = Base Address + Offset

---

Demand Paging: Load Pages on Demand

Demand paging is a technique where pages are loaded into memory only when they are needed, rather than loading the entire program at once. This reduces memory usage and speeds up program startup.

How Demand Paging Works:

1. A process starts execution with no pages in memory.
2. When a page is accessed, a page fault occurs.
3. The OS loads the required page from disk into a free frame.
4. The process resumes execution.

Advantages of Demand Paging:

• Reduced I/O: Only necessary pages are loaded.
• Faster startup: Programs begin execution immediately.
• Efficient memory usage: More processes can run concurrently.

Disadvantages:

• Page faults: Can cause delays if pages are frequently accessed from disk.
• Complexity: Requires careful management of page tables and replacement policies.

---

Page Replacement Algorithms

When a page fault occurs and no free frames are available, the OS must evict a page from memory to make space. The choice of which page to replace is critical and is determined by the page replacement algorithm.

Common Page Replacement Algorithms

---

Worked Example: Page Replacement in a System

Scenario: A system has 3 frames and loads pages in the following order: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Let’s compare FIFO and LRU algorithms.

FIFO Page Replacement

1. Load 1 → Frames: [1]
2. Load 2 → Frames: [1, 2]
3. Load 3 → Frames: [1, 2, 3]
4. Load 4 → Evict 1 (oldest) → Frames: [2, 3, 4]
5. Load 1 → Evict 2 → Frames: [3, 4, 1]
6. Load 2 → Evict 3 → Frames: [4, 1, 2]
7. Load 5 → Evict 4 → Frames: [1, 2, 5]
8. Load 1 → Already in memory.
9. Load 2 → Already in memory.
10. Load 3 → Evict 5 → Frames: [1, 2, 3]
11. Load 4 → Evict 1 → Frames: [2, 3, 4]
12. Load 5 → Evict 2 → Frames: [3, 4, 5]

Total Page Faults: 9

LRU Page Replacement

1. Load 1 → Frames: [1]
2. Load 2 → Frames: [1, 2]
3. Load 3 → Frames: [1, 2, 3]
4. Load 4 → Evict 1 (least recently used) → Frames: [2, 3, 4]
5. Load 1 → Evict 2 → Frames: [3, 4, 1]
6. Load 2 → Evict 3 → Frames: [4, 1, 2]
7. Load 5 → Evict 4 → Frames: [1, 2, 5]
8. Load 1 → Already in memory.
9. Load 2 → Already in memory.
10. Load 3 → Evict 5 → Frames: [1, 2, 3]
11. Load 4 → Evict 1 → Frames: [2, 3, 4]
12. Load 5 → Evict 2 → Frames: [3, 4, 5]

Total Page Faults: 9 (Same as FIFO in this case, but LRU often performs better in real scenarios.)

---

Thrashing: The Performance Killer

Thrashing occurs when a system spends more time paging (swapping pages between RAM and disk) than executing programs. This happens when:

• The working set (set of pages a process actively uses) is larger than the available memory.
• The page replacement algorithm cannot keep up with demand.

Symptoms of Thrashing:

• High page fault rate.
• Degraded system performance (slow response times).
• Increased CPU idle time (waiting for I/O).

Solutions to Thrashing:

1. Increase the number of frames: Allocate more physical memory.
2. Use a better page replacement algorithm: LRU or OPT (if feasible).
3. Reduce the working set: Optimize programs to use fewer pages.
4. Use more efficient algorithms: Clock algorithm (a variant of LRU).

---

In the Real World

Virtual memory is everywhere in modern computing, from mobile apps to cloud services. Here’s how it’s used in real-world systems:

1. Mobile Apps (WhatsApp, Pathao)

• Concept Used: Demand Paging + Virtual Memory
• How It Works:
  • When you open WhatsApp, only the essential parts of the app (e.g., login screen) are loaded into RAM.
  • As you chat or access media, additional pages (e.g., message history, images) are loaded on demand.
  • If RAM runs low, the OS evicts less frequently used pages (e.g., old chat logs) to make space.
• Why It Matters:
  • Allows multiple apps (WhatsApp, Pathao, Facebook) to run smoothly on devices with limited RAM (e.g., 3GB on a mid-range smartphone).
  • Prevents crashes when switching between apps frequently.

2. Cloud Services (Google Cloud, AWS)

• Concept Used: Virtual Memory + Swapping
• How It Works:
  • Cloud providers use virtualization to give each virtual machine (VM) its own virtual memory space.
  • If a VM’s working set exceeds its allocated RAM, the hypervisor (e.g., VMware, KVM) swaps pages to disk (swap space).
  • Example: A VM running a database may have 8GB of RAM allocated, but only 4GB is physically available. The rest is backed by disk storage.
• Why It Matters:
  • Enables multi-tenancy: Multiple customers can run VMs on the same physical server without interfering.
  • Allows elastic scaling: VMs can handle sudden spikes in demand by using disk storage temporarily.

3. Online Banking (Nabil Bank, Global IME)

• Concept Used: Paging + Memory Protection
• How It Works:
  • When you log in to your bank’s website or mobile app, the server runs multiple processes (e.g., transaction processing, authentication).
  • Each process runs in its own virtual address space, isolated from others (security).
  • If a process (e.g., a fraud detection script) needs more memory than available, the OS pages out inactive pages to disk.
• Why It Matters:
  • Ensures security: A bug in one process (e.g., a misconfigured script) cannot crash the entire system.
  • Improves responsiveness: Even if one user triggers a memory-intensive task, others experience minimal slowdown.

4. E-Commerce (Daraz, Amazon)

• Concept Used: Virtual Memory + Caching
• How It Works:
  • When you browse Daraz, the backend servers handle thousands of requests simultaneously.
  • Product catalogs, user sessions, and cart data are stored in virtual memory, with frequently accessed data cached in RAM.
  • If RAM is full, the OS evicts rarely used pages (e.g., old product listings) to disk.
• Why It Matters:
  • Handles peak loads (e.g., Black Friday sales) without crashing.
  • Reduces latency: Frequently accessed products (e.g., bestsellers) load faster.

5. Traffic Management (NTC, Kathmandu Traffic Routes)

• Concept Used: Paging (Analogy)
• How It Works:
  • Imagine traffic lights as a page replacement algorithm:
    • FIFO: Lights change in a fixed order (e.g., East-West-North-South), regardless of traffic density.
    • LRU: Lights prioritize roads with recent congestion (like LRU keeping recently used pages in memory).
  • In reality, smart traffic systems (e.g., NTC’s adaptive signals) use real-time data (like OPT) to minimize wait times.
• Why It Matters:
  • Reduces thrashing (constant stopping/starting) by optimizing flow.
  • Improves throughput (more vehicles moved per hour).

---

Advanced Topics: Swapping and Memory-Mapped Files

Swapping

Swapping is a process-level virtual memory technique where entire processes are moved between RAM and disk. Unlike paging (which handles individual pages), swapping deals with process images.

How Swapping Works:

1. A process is swapped out (moved to disk) if it is idle or memory is needed.
2. When the process resumes, it is swapped in (loaded back into RAM).
3. The OS maintains a swap space (a dedicated disk area) for this purpose.

Advantages:

• Simplifies memory management for processes that are not actively running.
• Useful for batch processing (e.g., payroll systems).

Disadvantages:

• High overhead: Moving an entire process is slower than paging.
• Inefficient for interactive systems (e.g., gaming, web browsing).

Memory-Mapped Files

Memory-mapped files allow files to be treated as if they were in memory. This is useful for:

• Efficient file I/O: No need to explicitly read/write files using system calls.
• Shared memory between processes: Multiple processes can access the same file simultaneously.

How It Works:

1. A file is mapped into the virtual address space of a process.
2. When the process accesses the file, the OS loads the relevant pages into memory (using demand paging).
3. Changes to the file are automatically written back to disk.

Example: Editing a Large Text File

• Instead of reading the entire file into RAM, the OS loads only the pages you edit.
• If you scroll to a new section, the OS pages in the new content from disk.

---

Exam Tip

What to Expect in the Exam:

1. Definitions:

   • Be ready to define virtual memory, paging, segmentation, demand paging, thrashing, and page replacement algorithms.
   • Example: "What is thrashing? How does it affect system performance?"

2. Address Translation:

   • Explain how virtual addresses are translated to physical addresses in paging and segmentation.
   • Draw diagrams to show the process.

3. Page Replacement Algorithms:

   • Compare FIFO, LRU, OPT, and Clock algorithms.
   • Given a page reference string, calculate page faults for each algorithm.
   • Example: "For the reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, compute page faults using LRU with 4 frames."

4. Thrashing:

   • Explain what thrashing is and how to detect/prevent it.
   • Example: "A system is thrashing. What steps would you take to resolve it?"

5. Real-World Applications:

   • Relate concepts to mobile apps, cloud services, or banking systems.
   • Example: "How does WhatsApp use virtual memory to run smoothly on low-RAM devices?"

6. Short Answer Questions:

   • Be prepared for 1-2 mark questions like:
     • "What is the role of the MMU in virtual memory?"
     • "Differentiate between paging and segmentation."
     • "Why is demand paging better than loading the entire program into memory?"

7. Long Answer Questions (10+ marks):

   • Expect detailed explanations with diagrams, e.g.:
     • "Explain the working of demand paging with an example. What are its advantages and disadvantages?"
     • "Compare FIFO and LRU page replacement algorithms. Which one would you prefer for a system with limited RAM? Justify."

Common Mistakes to Avoid:

• Confusing paging and segmentation: Remember, paging uses fixed-size blocks, while segmentation uses variable-sized logical units.
• Ignoring the role of hardware: The MMU and TLB (Translation Lookaside Buffer) are critical in address translation.
• Overlooking thrashing: Always check if a question involves performance degradation due to excessive paging.
• Not drawing diagrams: For address translation, always draw a figure to show the process.

Quick Revision Checklist:

---