Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10332512 | Journal of Computer and System Sciences | 2005 | 31 Pages |
Abstract
We develop tight or nearly tight bounds on the fault rates achieved by popular paging algorithms such as LRU, FIFO, deterministic Marking strategies and LFD. These bounds show that LRU is an optimal online algorithm, whereas FIFO and Marking strategies are not optimal in general. We present an experimental study comparing the page fault rates proven in our analyses to the page fault rates observed in practice.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Susanne Albers, Lene M. Favrholdt, Oliver Giel,