Marking Algorithms
Marking algorithms is a general class of paging algorithms. For each page, we associate it with a bit called its mark. Initially, we set all pages as unmarked. During a stage of page requests, we mark a page when it is first requested in this stage. A marking algorithm is such an algorithm that never pages out a marked page.
If ALG is a marking algorithm with a cache of size k, and OPT is the optimal algorithm with a cache of . Then ALG is -competitive. So every marking algorithm attains the -competitive ratio.
LRU and CLOCK are marking algorithms while FIFO is not a marking algorithm.
Read more about this topic: Page Replacement Algorithm
Famous quotes containing the word marking:
“Hair of man, man-hair, hair of
breast and groin, marking contour as
silverpoint marks in cross-
hatching ...”
—Denise Levertov (b. 1923)