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:
“Almost always tradition is nothing but a record and a machine-made imitation of the habits that our ancestors created. The average conservative is a slave to the most incidental and trivial part of his forefathers’ glory—to the archaic formula which happened to express their genius or the eighteenth-century contrivance by which for a time it was served.”
—Walter Lippmann (1889–1974)