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:
“A radical is a man with both feet firmly planted in the air. A conservative is a man with two perfectly good legs, who, however, has never learned to walk forward. A reactionary is a somnambulist walking backwards. A liberal is a man who uses his legs and his hands at the behest ... of his head.”
—Franklin D. Roosevelt (1882–1945)