O perating s ystems t hree e asy p ieces

ciple of locality

[D70], which basically is just an observation about pro-

grams and their behavior. What this principle says, quite simply, is that

programs tend to access certain code sequences (e.g., in a loop) and data

structures (e.g., an array accessed by the loop) quite frequently; we should

thus try to use history to figure out which pages are important, and keep

those pages in memory when it comes to eviction time.

And thus, a family of simple historically-based algorithms are born.

The Least-Frequently-Used (LFU) policy replaces the least-frequently-

used page when an eviction must take place. Similarly, the Least-Recently-