Operating Systems Chapter on Paging

Lecture Agenda - November 14

• Reminders:
  • Read chapters 20-22 (Virtual Memory Module 8)
  • Project 4 - Driving Simulation (due 11/20): Demonstrates concurrency using threads.
  • Project 5 - Implement a Simple File System (2nd deliverable 11/20)
• Attendance: Attendance is required.
• Quiz Review: Review for Quiz will be held.
• Quiz: Quiz 11/20

File System Allocation Methods

• Indexed Allocation (Inode Example): Linux's inode is an example of indexed file block allocation.
• Small Number of Extents: The method stores the link to associated extents as the last element in a contiguous data segment.
• Virtual Addressing and Paging: Virtual addressing involving paging of tables leads to potential program memory access to retrieve data from memory cells (e.g., 1, 2, 3, and 4).

Demand Paging

• Basic Demand Paging Steps:

  • Code references a page not in memory
  • Page fault is triggered
  • Find the page location on disk
  • Locate a free frame: If available, use it. Otherwise, a page replacement algorithm selects a victim frame and removes its content.
  • Bring the desired page into the free frame, update tables.
  • Restart the process (and the faulted instruction). (Note: page not yet in the TLB).

• Diagram (Page Fault → Demand Paging): The image illustrates the process, including virtual address, physical address, MMU, page table, frame number, and offset, and the role of the Operating System (OS) and Page Fault Handler in loading the page from disk.

• Performance Evaluation: Effective access time is dependent on the probability of a fault. Access time is faster if no page faults. Time increases when faults occur and involves extra steps like disk reading or updating tables.

• Time Consuming Acts of a Page Fault:

  • Trap to OS (undefined address error)
  • Save registers and active state
  • Determine the interrupt cause (page fault)
  • Verify page reference legality
  • Obtain page location on storage device
  • Issue I/O read request
  • Queue for read servicing
  • Wait for device seek and latency
  • Begin transfer
  • CPU allocated to another task; I/O progresses
  • Receive interrupt from I/O done.
  • Return context; update tables showing the page location.
  • Wait for CPU allocation for faulted process
  • Restore context and execute the instruction again

• Summary of Operations: Service page fault interrupt, locate and swap in page, and restart process in 1-3 steps.

• Summary of Operations (Page Fault Time): - Time for steps 1 and 3 are software controlled (5-100 microseconds). Stage 2 is affected by hardware factors like HDD seek, latency to disk, and queue times (can be over 10 milliseconds and more significant).

• Demand Paging Example: Presents an example evaluating effective access time. Performance degradation factor from fault is illustrated; example provides a 10% degradation.

Page Replacement

• Why Replacement is Crucial: Replacement is important in caching, particularly in page management. Cost of improper replacement is significant, requiring disk accesses. Essential to prevent tossing out important memory.

• FIFO (First-In, First-Out): The oldest page is replaced first. Not efficient as heavily used pages might be replaced, but less useful ones might be kept.

• RANDOM: Replaced page is chosen randomly. Simple to implement in hardware but unpredictable.

• MIN (Minimum): A page that will not be referenced for the longest time is replaced. This is optimal but impossible to implement in practice, as the future is unknown.

• LRU (Least Recently Used): Replaces the page that hasn't been referenced in the longest time. Good approximation of MIN since program behavior often shows locality. LRU is used as approximation of MIN in practice but can vary computationally. LRU algorithm tracks the usage order via a list or similar structure.

• Page Replacement (1 & 2): When all frames are used and a fault occurs, a resident page is swapped out for a different page loaded from the disk. Modified pages are prioritized in order to reduce overhead of page replacement, as those pages need to be written back to disk.

LRU (Least Recently Used)

• Concept of LRU: Replace the page least recently used (LRU) in memory since it's less likely to be needed soon.

• Implementing LRU with a list: Pages are added to the head of a list whenever they're used, putting the least recently used page at the tail.

Example: FIFO

• Scenario: Illustrates the workings of the FIFO algorithm with examples of page reference streams and page faults.
• Result: FIFO replacement (with specifics of a page stream) is shown to result in a specific number of page faults

Example: MIN

• Scenario: Demonstrates how MIN manages pages and predicts which pages won't be used soon.

• Result: Illustrates the results and faults associated with replacing the page not used in the future in reference to a page stream

• Using Modified Bit: Diagram of how a modified bit and its presence bit flags will help determine whether disk writes are needed or pages have been updated recently and need to be saved to disk (if modified).

How Memory Management Works

Demand Paging as Caching

• Block Size and Page Location: Pages (e.g. 4KB); using TLB (Translation Lookaside Buffer) for fast access and page table traversal.
• Miss and Write Actions: Misses at lower memory levels involve disk access (write-through or write-back).
• Page Replacement Policies: LRU (Least Recently Used) and random are examples

Illusion of Infinite Memory

• Disk's Role: Disk acts as a large supplementary memory, exceeding physical memory, allowing concurrency and virtual addresses larger than physical memory

• Transparent Level of Indirection: Page tables allow data to be located anywhere and used transparently (on disk, memory) for processes.

• Performance Considerations: Accessing memory is a crucial concern for program performance.

Page Faults Versus the Number of Frames

• General Expectation: More frames reduce page faults. However, certain algorithms, like FIFO, exhibit Belady's anomaly. The number of faults can increase initially even if more frames are available

Page Replacement Algorithms

• Goal: Minimizing page faults. Understanding algorithm evaluations with respect to page reference strings and computing faults through testing. Numerical data are needed for string examples.

FIFO Algorithm

• Concept and Implementation: FIFO (First-In, First-Out) is implemented with a queue; pages are removed based on entry order.

• Illustrating Belady's Anomaly: Illustrates the counterintuitive phenomenon where the number of faults can increase even with more page frames available. Includes an example reference string to illustrate FIFO's use.

What could be the best we can do in terms of an algorithm?

Min (Optimal) Page Replacement Algorithm

• Optimal Replacement: Page with the longest time before it is referenced again is replaced. Ideally, this would lead to fewer faults overall. However, it's impossible to implement in practice because its use requires knowing the future. Includes an example where the algorithm is used and data is illustrated, showing how many page faults happen (a number) and why, in an example reference string

Min (Optimal) Page Replacement

• Illustrative Example: An example demonstrating Min optimal behavior, showing how page accesses relate to faults in different frames, leading to fewer (9) total page faults. This demonstrates how optimal replacement makes use of page reference streams.

Test your knowledge on key concepts of virtual addressing and paging in operating systems. This quiz covers page replacement algorithms, memory access during page faults, and the implications of different paging policies. Each question will help reinforce your understanding of memory management techniques.