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 democrat is a young conservative; the conservative is an old democrat. The aristocrat is the democrat ripe, and gone to seed,—because both parties stand on the one ground of the supreme value of property, which one endeavors to get, and the other to keep.”
—Ralph Waldo Emerson (1803–1882)