OS Week 11

    Cards (17)

    • 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.
    See similar decks