LRU Approximations for Paging
Pure LRU and LFU are prohibitively expensive to implement.
- most references are hidden by the TLB
- OS typically sees less than 10% of all references
- can’t tweak your ordered page list on every reference
Most systems rely on an approximation to LRU for paging.
- periodically sample the reference bit on each page
visit page and set reference bit to zero
run the process for a while (the reference window)
come back and check the bit again
- reorder the list of eviction candidates based on sampling