VM & Paging

Virtual Memory and Paging Overview

1. Introduction to Virtual Memory

  • Virtual memory allows the execution of processes that may not be completely in physical memory.

  • Paging is a mechanism that helps implement virtual memory.

2. Paging Process

  • Key Steps:

    • Check if an entry exists in the Translation Lookaside Buffer (TLB).

    • Check if the page is present in DRAM (Dynamic Random Access Memory).

    • If both checks fail, initiate a page fault.

  • Address Composition:

    • Virtual addresses are composed into physical addresses.

    • Process involves both hardware and software components to manage memory accesses.

3. Page Faults

  • Definition:

    • A page fault occurs when a requested page is not found in physical memory (indicated by page-table mapping).

  • Process of Handling Page Faults:

    • A hardware interrupt signals the operating system to address the fault.

    • Control is transferred to the interrupt service handler which manages the fault.

    • Code example of an interrupt handler:
      PageFaultHandler() { // handler code }

  • Resolution:

    • The OS initiates a disk read to bring the missing page into memory.

    • Updates the page table entry accordingly and restarts the faulted process.

    • Sometimes involves replacing an existing page, which leads to invalidating its page-table entry.

4. Page Replacement

  • Memory Limitation:

    • Physical memory cannot hold all pages; thus, page eviction is necessary when loading a new page.

  • Page Replacement Algorithm:

    • Strategies determine which page to evict to free up memory for the new page.

5. Page Replacement Algorithms

  • Optimal Page Replacement (OPT):

    • Theoretical algorithm that minimizes page faults.

    • Evicts the page that will not be used for the longest time in the future.

    • Example reference string: 5, 3, 3, 5, 2, 4, 4, 3, 2.

    • Current memory state: 5, 3, 2, 4, determine which to evict.

  • Challenge with OPT:

    • Requires knowledge of future references, making it impractical in real scenarios.

  • 1. First-in First-out (FIFO):

    • Maintains a queue of pages in the order they were brought in.

    • On page fault, evicts the page at the head of the queue.

    • Example reference string demonstrating faults: 1, 2, 3, 4, 1, 1, 5, 1, 1, may lead to inefficient evictions.

  • 2. Least Recently Used (LRU):

    • Evicts the least recently used page based on recent access.

    • Complexity arises in keeping the list updated during memory accesses.

    • Solutions include approximating LRU to simplify operations.

  • 3. Not Recently Used (NRU):

    • Uses reference bits (R for referenced and M for modified).

    • Pages are categorized based on the state of R and M bits, and the lowest class page is evicted.

  • 4. Approximate LRU Using Counters:

    • Each physical page has an associated counter initialized to 0.

    • At timed intervals, bits are shifted; reference bits are used to update the counter.

    • Evict based on the lowest counter value simulating LRU behavior.

  • 5. Second Chance Replacement (Clock Algorithm):

    • Enhanced FIFO: If a page’s reference bit is set, it is given a second chance, moved to the end of the queue.

    • If not set, it is replaced.

6. Summary of Page Replacement Algorithms

  • Key algorithms: OPT, FIFO, NRU, Second-Chance/Clock, LRU, Approximate LRU.

  • Most operating systems opt for Second Chance or its variations for efficiency.

7. Belady’s Anomaly

  • Definition:

    • A counterintuitive phenomenon where increasing physical memory leads to more page faults with certain algorithms.

  • Example of Belady's Anomaly:

    • FIFO with reference string: 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4 shows increased faults from 3 to 4 frames.

  • Algorithms That Do Not Suffer Belady’s Anomaly:

    • Stack algorithms, such as OPT and LRU.

8. Modeling Paging Behavior

  • Characterized by:

    • Reference string

    • Physical memory size

    • Replacement algorithm.

9. Visualizing Paging as a Stack

  • Pages are metaphorically stacked, with referenced pages at the top and less recently used ones at the bottom.

  • For example, referencing a page will move it to the top of the stack, representing its recent use.

10. Distance String

  • Represents the distance from the top of the stack for each element of the reference string.

  • Example calculation of distance strings when pages are referenced.

11. Vectors C and F

  • Vector C: Defines frequency of distances of each page from the stack top.

  • Vector F: Number of page faults expected given a reference string for various frame sizes.

  • Relationship showing that as the number of frames increases, page faults can only decrease or remain same.

12. Paging Issues

  • Working Set Principle:

    • Keep essential pages in memory to prevent thrashing and improve efficiency.

    • Locality of reference is critical for effective paging.

  • Fragmentation in Paging:

    • Virtual memory allows non-contiguous memory allocation, minimizing fragmentation.

  • Internal Fragmentation exists and can be minimized by smaller page sizes.

13. Example in Practice

  • Example of managing code with virtual address space (VAS), page table entries, and interaction with OS during memory allocation to illustrate paging concepts in real-world scenarios.