***************************
Chapter 9: Virtual Memory
***************************

Overview
===========

**Virtual memory** allows a system to execute processes that may not be completely in main memory.  
It provides an abstraction that gives each process the illusion of having a large, continuous address space.

Goals:
- Efficient memory utilization  
- Process isolation and protection  
- Ability to run large programs  
- Support for multitasking and increased CPU utilization  

------------------------------
Background
------------------------------

- Physical memory is limited; virtual memory expands it by using disk space.
- The **logical address space** is larger than the **physical address space**.
- The **Memory Management Unit (MMU)** translates virtual addresses to physical addresses at runtime.
- Virtual memory enables **partial loading** of processes — only the needed parts (pages) are kept in RAM.

**Benefits**
  - Allows more processes to run simultaneously.
  - Simplifies program development (no need to manage limited memory manually).
  - Enables sharing and protection of memory.

------------------------------
Demand Paging
------------------------------

**Definition**
  - A technique where pages are loaded into memory **only when needed** during program execution.

**Key Concepts**
  - **Page fault:** Occurs when a page referenced by a process is not in memory.
  - **Valid-invalid bit:** Used to indicate if a page is in memory (valid) or not (invalid).

**Steps in Handling a Page Fault**
  1. Check if the address is valid.
  2. Locate the required page on disk.
  3. Find a free frame in physical memory.
  4. Load the page into the free frame.
  5. Update the page table.
  6. Restart the instruction that caused the fault.

**Performance**
  - Effective Access Time (EAT):  
    ::

       EAT = (1 - p) * memory_access_time + p * page_fault_time

    where *p* = probability of page fault.  
  - Lower page-fault rate ⇒ better performance.

------------------------------
Copy-on-Write (COW)
------------------------------

**Definition**
  - An optimization strategy where parent and child processes initially share the same memory pages.

**How It Works**
  - Upon a `fork()` system call, both processes share pages marked as **read-only**.
  - When one process modifies a page, a **copy** is made (hence “copy-on-write”).
  - Reduces memory usage and process creation time.

**Advantages**
  - Efficient process creation.
  - Minimizes unnecessary duplication.
  - Increases overall system performance.

------------------------------
Page Replacement Algorithms
------------------------------

When a page fault occurs and there are no free frames, the OS must select a page to replace.

**Goals**
  - Minimize the number of page faults.
  - Maintain good system performance.

**Common Algorithms**
  - **FIFO (First-In, First-Out):**
    - Replace the oldest loaded page.
    - Simple but can lead to *Belady’s anomaly* (more frames → more faults).

  - **Optimal:**
    - Replace the page that will not be used for the longest period.
    - Theoretical minimum number of page faults.
    - Not practical (requires future knowledge).

  - **LRU (Least Recently Used):**
    - Replace the page that hasn’t been used for the longest time.
    - Approximates optimal behavior.
    - Requires tracking recent usage (time stamps or counters).

  - **LFU (Least Frequently Used):**
    - Replace the page used the fewest times.
    - Can perform poorly if usage changes over time.

  - **Clock (Second-Chance):**
    - Circular list of pages with reference bits.
    - Gives each page a “second chance” before replacement.

**Comparison Table**

.. list-table:: Page Replacement Algorithm Comparison
   :widths: 20 60
   :header-rows: 1

   * - **Algorithm**
     - **Description / Notes**
   * - FIFO
     - Simple but can suffer from Belady’s anomaly.
   * - Optimal
     - Theoretical best; not implementable in practice.
   * - LRU
     - Approximates optimal; commonly used.
   * - LFU
     - Replaces least used pages; may not adapt quickly.
   * - Clock
     - Efficient approximation of LRU using reference bits.

------------------------------
Thrashing
------------------------------

**Definition**
  - A condition where the system spends more time swapping pages than executing processes.

**Causes**
  - Too many processes competing for too little memory.
  - High page fault rate.
  - Inadequate frame allocation.

**Effects**
  - Drastic drop in CPU utilization.
  - Continuous paging activity.
  - Severe system slowdown.

**Solutions**
  - Reduce the degree of multiprogramming.
  - Use **working-set model** to allocate sufficient frames.
  - Apply **page-fault frequency (PFF)** control mechanisms.

------------------------------
Summary
------------------------------

.. list-table:: Virtual Memory Summary
   :widths: 25 60
   :header-rows: 1

   * - **Concept**
     - **Key Points**
   * - Virtual Memory
     - Provides an illusion of large memory using disk space.
   * - Demand Paging
     - Loads pages only when needed; uses page faults.
   * - Copy-on-Write
     - Shares memory until modification occurs.
   * - Page Replacement
     - Determines which page to evict on a fault.
   * - Thrashing
     - Occurs when excessive paging reduces performance.

**Key Takeaways**
  - Virtual memory separates logical from physical storage.
  - Demand paging improves efficiency but must minimize page faults.
  - Replacement algorithms balance simplicity and performance.
  - Thrashing must be controlled for stable system operation.