OS Week 11

• Page Replacement Policy: Evict the page that will be needed again furthest in the future is impossible but can be used theoretically.
• All realistic policies will be approximately the same.
• The penalty for guessing incorrectly in a page replacement policy is that the page that should have been evicted is not evicted, causing a potential loss of data.
• Clock Replacement Policy: Keep a ‘referenced’ and ‘dirty’ bit for each page is located in the MMU and/or write protection.
• Beginning at the page frame after the last eviction, if the frame is NOT referenced, evict it.
• If the frame IS referenced, mark it as not referenced and advance to the next page frame.
• Least Recently Used (LRU) algorithm assumes past access is a good predictor of future access and evicts the page that hasn’t been accessed (read or written) longest.
• LRU can be implemented with a stack.
• The distance string technique only works for ‘stack’ algorithms.
• It is provable that the set of pages in memory with n page frames is a strict subset of pages in memory with (n + 1) page frames.
• LRU is a stack, FIFO is not.
• LRU can be implemented with a stack.
• LRU is a stack, FIFO is not.
• Not Frequently Used (NFU) algorithm is an approximation of LRU that is low overhead and keeps a counter for each page in memory.
• On each clock interrupt, shift the page’s reference bit into the counter and clear the page’s reference bit.
• To evict a page in NFU, select the page with the lowest value in the counter.
• Proactively keep a pool of available page frames to minimize allocation latency in NFU.