Virtual Memory: Paging, Segmentation, Demand Paging & Thrashing

TAKEAWAYS:

• Virtual memory allows a system to use disk space as an extension of RAM, creating an illusion of a larger memory space than physically available.
• Paging divides memory into fixed-size blocks (frames/pages) while segmentation divides it into variable-sized logical units based on program structure.
• Demand paging loads pages into memory only when needed, reducing initial load time and improving efficiency.
• Thrashing occurs when excessive paging causes CPU to spend more time swapping than executing, degrading performance.
• Page replacement algorithms (FIFO, LRU, Optimal) determine which page to replace when memory is full.
• Working set model predicts future memory needs to minimize page faults and thrashing.

1. Introduction to Virtual Memory

Virtual memory is a memory management technique that uses disk storage as an extension of RAM, allowing systems to run programs larger than the available physical memory. It creates an illusion of a large, contiguous memory space by dynamically loading and swapping data between RAM and disk.

Why Virtual Memory?

• Efficient memory usage: Allows multiple processes to run simultaneously without requiring all their data to be in RAM at once.
• Protection and isolation: Each process operates in its own virtual address space, preventing interference.
• Simplified programming: Programs can use logical addresses without worrying about physical memory constraints.

Key Components

1. Logical Address (Virtual Address): Address generated by the CPU.
2. Physical Address: Actual address in RAM.
3. Page Table: Maps logical addresses to physical addresses.
4. Page Table Base Register (PTBR): Points to the start of the page table.
5. Page Table Length Register (PTLR): Specifies the size of the page table.

2. Paging: Fixed-Size Memory Division

Paging divides physical memory (RAM) and logical memory (process address space) into fixed-size blocks called frames and pages, respectively.

How Paging Works

1. Logical Address: Divided into:
   • Page Number (p): Used as an index into the page table.
   • Offset (d): Specifies the exact location within the page.
   • Formula: Logical Address = (p, d)
2. Page Table: Contains entries for each page, mapping it to a frame in RAM or disk (if swapped out).
3. Translation: The Memory Management Unit (MMU) uses the page table to convert logical addresses to physical addresses.

Page Table Example

Assume:

• Page size = 4 KB (2¹² bytes).
• Physical memory has 1024 frames (each 4 KB).
• A process has 5 pages.

Example:

• Logical address = 0x0A3F (hexadecimal).
• Page size = 4 KB = 4096 bytes = 2¹² bytes.
• Page number (p) = 0x0A3F / 4096 = 0 (integer division).
• Offset (d) = 0x0A3F % 4096 = 0x0A3F.
• Physical address = (Frame 100) * 4096 + 0x0A3F.

3. Segmentation: Variable-Size Memory Division

Unlike paging, segmentation divides memory into variable-sized logical units (segments) based on program structure (e.g., code, data, stack, heap).

How Segmentation Works

1. Logical Address: Divided into:
   • Segment Number (s): Identifies the segment (e.g., code, data).
   • Offset (d): Specifies the location within the segment.
   • Formula: Logical Address = (s, d)
2. Segment Table: Contains base and limit for each segment.
   • Base: Starting physical address of the segment.
   • Limit: Size of the segment.

Segment Table Example

Assume a process has 3 segments: code, data, and stack.

Example:

• Logical address = (1, 1500) (data segment, offset 1500).
• Check if offset ≤ limit: 1500 ≤ 2048 → Valid.
• Physical address = Base (5000) + Offset (1500) = 6500.

4. Demand Paging: Load Pages on Demand

Demand paging loads pages into memory only when they are needed, reducing initial load time and improving efficiency.

How Demand Paging Works

1. Initialization: Only a few pages (e.g., code segment) are loaded into memory.
2. Page Fault: When a process accesses a page not in memory, a page fault occurs.
3. Page Replacement: The OS loads the required page from disk into an empty frame or replaces an existing page using a page replacement algorithm.

Page Fault Handling Steps

1. Check if the reference is valid (e.g., not an illegal access).
2. Find an empty frame (if none, use a replacement algorithm).
3. Load the page from disk into the frame.
4. Update the page table.
5. Restart the instruction that caused the page fault.

Example:

• A process accesses address 0x1234 (page 2, offset 0x234).
• Page table shows page 2 is not in memory (Valid Bit = 0).
• OS loads page 2 from disk into an empty frame (e.g., frame 500).
• Update page table: Page 2 → Frame 500.
• Restart the instruction.

sequenceDiagram
  participant CPU
  participant OS
  participant Disk
  CPU->>OS: Accesses Page 2 (Page Fault)
  OS->>Disk: Load Page 2 from Disk
  Disk-->>OS: Returns Page 2
  OS->>OS: Update Page Table
  OS-->>CPU: Restart Instruction
  note over OS,CPU: Page Fault Handled

5. Page Replacement Algorithms

When a page fault occurs and no free frames are available, the OS must replace an existing page using one of these algorithms:

Example: FIFO Page Replacement

Assume:

• Memory has 3 frames: [1, 2, 3].
• Page reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

Total Page Faults: 8.

6. Thrashing: The Performance Killer

Thrashing occurs when a process spends more time paging (swapping pages in/out) than executing, leading to severe performance degradation.

Causes of Thrashing

1. Insufficient Frames: Too many processes compete for limited memory.
2. Poor Page Replacement: Algorithms like FIFO may cause excessive swapping.
3. High Page Fault Rate: Processes keep accessing pages that are frequently swapped out.

Symptoms of Thrashing

• CPU utilization drops (waiting for I/O).
• Response time increases.
• System becomes unresponsive.

Solutions to Thrashing

1. Increase the number of frames (if possible).
2. Use better page replacement algorithms (e.g., LRU, Clock).
3. Reduce the number of processes running simultaneously.
4. Working Set Model: Allocate frames based on the working set (set of pages a process will use in the near future).

7. Working Set Model

The working set model predicts the set of pages a process will use in the near future and allocates frames accordingly to minimize page faults.

How It Works

1. Define a window (Δ): Time interval (e.g., 10,000 instructions).
2. Track page references: For each process, record pages accessed in the last Δ instructions.
3. Allocate frames: Ensure the working set fits in memory.

Example:

• Process P has a working set of pages {1, 2, 3, 4} over the last 10,000 instructions.
• If memory has only 3 frames, thrashing may occur.
• Solution: Allocate at least 4 frames to P.

8. Locality of Reference

Locality refers to the tendency of a process to access the same set of pages repeatedly over short periods. It is the basis for effective paging and caching.

Types of Locality

1. Temporal Locality: Recently used pages are likely to be used again soon (e.g., loops in code).
2. Spatial Locality: Pages near recently accessed pages are likely to be used soon (e.g., array traversal).

Example:

• A loop iterating over an array exhibits spatial locality (accessing consecutive memory locations).
• A recursive function exhibits temporal locality (repeatedly accessing the same stack frames).

9. Real-World Applications in Nepal

1. eSewa (Digital Payment System)

• Concept Used: Virtual Memory for Efficient Transaction Processing
• How?
  • eSewa handles thousands of transactions per second.
  • The OS uses demand paging to load only the necessary transaction data into memory, reducing latency.
  • Page replacement algorithms ensure frequently accessed transaction logs (e.g., recent payments) stay in RAM.

2. Daraz (E-Commerce Platform)

• Concept Used: Segmentation for User Session Management
• How?
  • Daraz’s backend divides user sessions into segments (e.g., cart, product browsing, checkout).
  • Virtual memory allows Daraz to handle millions of users without loading all their sessions into RAM simultaneously.
  • Thrashing prevention: The system monitors working sets to avoid excessive paging during peak hours (e.g., Dashain sales).

3. Ncell (Telecom Network)

• Concept Used: Paging for Mobile Data Routing
• How?
  • Ncell’s core network uses paging to manage data packets efficiently.
  • When a user requests data (e.g., streaming a video), the OS loads only the required pages of the data into buffers.
  • Page replacement ensures high-speed data delivery by prioritizing active connections.

4. Kathmandu Traffic Management (Simulated Example)

• Concept Used: Thrashing in Real-Time Systems
• How?
  • Imagine a traffic light control system where each intersection is a "process" competing for CPU time.
  • If the system thrashes (too many context switches due to poor scheduling), traffic lights may fail to update in time, causing jams.
  • Solution: Use priority-based scheduling and allocate sufficient memory (frames) to avoid thrashing.

10. Exam Tips

1. Understand the Difference Between Paging and Segmentation:

   • Paging uses fixed-size blocks; segmentation uses variable-sized segments.
   • Paging is hardware-based; segmentation is software-based.

2. Page Table Entries:

   • Always remember the Valid Bit, Reference Bit, and Modified Bit in page table entries.
   • Example: If Valid Bit = 0, it means the page is not in memory (page fault).

3. Page Replacement Algorithms:

   • Know the pros and cons of FIFO, LRU, and Optimal.
   • Be able to calculate page faults for a given reference string (e.g., FIFO with 3 frames).

4. Thrashing:

   • Define thrashing and explain why it happens.
   • Solutions: Increase frames, better algorithms, or reduce processes.

5. Working Set Model:

   • Understand how it predicts future memory needs.
   • Example: If a process’s working set is 5 pages, allocate at least 5 frames to avoid thrashing.

6. Real-World Scenarios:

   • Relate concepts to Nepalese apps (e.g., eSewa’s transaction handling, Daraz’s session management).
   • Example: "How does Daraz prevent thrashing during Dashain sales?" → Working set model + sufficient frames.

7. Diagrams:

   • Be ready to draw:
     • Paging vs. segmentation.
     • Page table structure.
     • Page replacement examples (FIFO, LRU).
     • Thrashing state diagram.

Worked Example: Calculating Page Faults with LRU

Problem: Given a page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 and 4 frames, calculate the number of page faults using LRU.

Solution: Initialize frames: [] (empty). Track last used time for each page.

Total Page Faults: 7.

Summary Table: Paging vs. Segmentation

Final Notes

• Virtual memory is essential for modern OS (e.g., Windows, Linux, macOS).
• Demand paging reduces memory usage and improves multitasking.
• Thrashing is a critical issue in real-time systems (e.g., traffic control, stock trading).
• Page replacement algorithms directly impact performance—LRU is often the best choice in practice.

Exam Tip: Always relate theory to real-world examples (e.g., eSewa, Daraz) in your answers. Examiners love practical connections!