Competitive paging algorithms. (English) Zbl 0753.68018

The authors present a set of on-line algorithms for the paging problem, namely: the marking algorithm, the algorithm EATR, and algorithms that are competitive against several others. The marking algorithm can be interpreted as a randomized form of LRU. The algorithm EATR is a randomized algorithm for the uniform 2-server problem. The algorithms that are competitive against several others involve the combining of several on-line algorithms. The performance of these algorithms is within of a factor of two of the performance of both the LRU algorithm and the FIFO algorithm.


68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68N25 Theory of operating systems
68W10 Parallel algorithms in computer science
Full Text: DOI