×

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.

MSC:

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