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:
“When people put their ballots in the boxes, they are, by that act, inoculated against the feeling that the government is not theirs. They then accept, in some measure, that its errors are their errors, its aberrations their aberrations, that any revolt will be against them. It’s a remarkably shrewed and rather conservative arrangement when one thinks of it.”
—John Kenneth Galbraith (b. 1908)