Editing Page replacement algorithm (section)

==Marking algorithms==
{{confusing section|date=December 2015}}

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 (a period of operation or a sequence of requests) 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 size h, where <math>h \leq k</math>, then ALG is <math> \tfrac{k}{k-h+1}</math>-competitive. So every marking algorithm attains the <math> \tfrac{k}{k-h+1}</math>-competitive ratio.

LRU is a marking algorithm while FIFO is not a marking algorithm.