Virtual Memory Quiz - Chapters 20-22

Lecture Agenda - November 19

• Reminders:
  • Read Chapters 20-22 (Virtual Memory Module 8)
  • Project 4 Demo due Wednesday, November 20 (Driving Simulation using threads and concurrency)
  • Project 5 Deliverable 3 due November 20 (Implementing a Simple File System)
  • Quiz tomorrow
  • Attendance required

Topics Covered Last Time

• Demand Paging
• Page Replacement
• FIFO (First-In, First-Out)
• Optimal Algorithm

Topics Covered Today

• Page Replacement Algorithms
  • FIFO
  • Optimal (MIN)
  • LRU (Least Recently Used)
  • LRU Approximations
• Policies for managing memory allocation
• PollEv.com/gkwatny9
• Send gkwatny9 to 22333

FIFO Page Replacement

• Reference String: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
• Page Frames: Specific example table showing page replacements with 15 faults.

FIFO Algorithm Details

• Easy to implement using single pointer to oldest page in memory.
• When a page is replaced, advance pointer.
• Locality Principle: A positive in FIFO. Most instructions execute sequentially. Likelihood of referencing a page from the distant past decreases with time. Large data structures often referenced sequentially.

Optimal (MIN) Algorithm

• Replaces page that won't be used for longest period of time.
• Difficult to implement in real time: Requires future knowledge of page references.
• 4 frames, example: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, resulting in 6 page faults.

LRU (Least Recently Used) Algorithm

• Replaces the least recently used page.
• Implementation:
  • Requires a queue (ordered list) containing page numbers.
  • When a page is referenced, move it to back (end) of the queue.
  • Queue always ordered (most recently used to least recently used).
  • If non-resident page referenced, remove page at front of queue and place new page at the end.
• Example with 4 frames: A specific example demonstrating the replacement process with 12 page faults.

LRU Implementation Details Including Alternatives

• Detailed description of how LRU is implemented using a queue.
• Alternative Method: Discusses using a counter to track page reference times.
  • Every page entry has a related time reference
  • When a page is referenced, copy the clock time to the PTE's time reference field.
  • When a page needs replacing, check time references to select appropriate page.

How to Approximate LRU

• Uses information collected as a process executes to approximate LRU behaviour.
• Page tables: Connection between virtual addresses and physical addresses is a significant tool.

Page Table Bits

• Specific PTE bits relevant for LRU algorithms (example Intel PTE)
  • Present (Valid) bit
  • Writeable bit
  • Accessed/Used bit
  • Dirty/Modified bit

When to Apply Page Replacement

• Page fault occurs (no free frames in memory)
• Algorithm finds page to evict.
• Keeps frequently used pages in memory.

Clock Algorithms

• Use Page Table Entry (PTE) bits & a circular queue of pages.
• Pointer around like a clock.
• Only do work at page fault time.

Second Chance Algorithm

• Requires reference bit per page and organized in an ordered page list (Clock Algorithm).
• If page needs replacement, and reference bit = 1, set bit to 0 and leave in memory.

Enhanced 2nd Chance

• Priority-based replacement: Uses referenced and modified bits.
• Different priority levels: Distinct categories based on usage. (ex. 00 least used to 11 most used)

Page Buffering

• LRU algorithms perform well in memory minimizing page faults but high implementation overhead and hardware required.
• FIFO is simple but it doesn't consider page reference frequency.
• Ways to improve FIFO: Adding a 2nd chance policy or similar.

Page Buffering, Including Variable Allocation

• Process gets maximum number of frames (Resident Set).
• FIFO list is created to efficiently manage frames.
• Page Fault: An evicted page is put on a clean or modified list managed by the OS.
• Example of variable allocation: An excerpt from the document explaining the variable allocation (also discussed in more detail in Resident Set Management).

Fetch Policy

• Demand Paging: Only brings pages into memory when referenced, many page faults at beginning. Principle of locality; more references to recently loaded pages means fewer faults.
• Prepaging: Brings pages into memory that might be referenced following a page fault. Exploits the characteristic that sequential pages are loaded in secondary storage together, improves load speed.

Resident Set Management

• How many pages to keep in main memory for a given process.
• Trade-offs: Smaller allocation means more processes can be held but more faults.
• Certain size, beyond adding more frames, won't improve fault rate.

Policies for Resident Set Size

• Fixed allocation: Assigns fixed number of frames to the process.
• Variable allocation: The number of page frames assigned to the processes changes over time, usually to try and hold the working set (important pages).

Replacement Scope

• Global: The replacement strategy considers all unlocked pages in main memory.
• Local: Only looks at resident set pages related to the process that has experienced the fault.

Test your understanding of Virtual Memory concepts as outlined in Chapters 20-22. This quiz covers page replacement algorithms, specifically FIFO, Optimal, and LRU. Make sure to review the examples and algorithms discussed in class to prepare effectively.