Conservative Algorithms
An algorithm is conservative, if on any consecutive request sequence containing k or fewer distinct page references, the algorithm will incur k or fewer page faults.
If ALG is a conservative algorithm with a cache of size k, and OPT is the optimal algorithm with a cache of . Then ALG is -competitive. So every conservative algorithm attains the -competitive ratio.
LRU, FIFO and CLOCK are conservative algorithms.
Read more about this topic: Page Replacement Algorithm
Famous quotes containing the word conservative:
“The radical invents the views. When he has worn them out the conservative adopts them.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)