Lookahead Scheduling Requests for Efficient Paging

This paper studies the effect of scheduling (reordering) page requests on the page hit ratio. First, we define the residence interval of a page, the time duration during which the page resides in the cache continuously, for off-line page request sequences. Using the residence interval, we show how to reorder requests to reduce the number of page misses. In particular, we show two page replacement policies are useful to minimize some criteria. Second, we consider the “semi-online” model, which assumes that some future requests are known. This model is applicable in practice if unserviced requests are kept in a queue and reordered before execution. Then we develop an efficient semi-online algorithm which selects a page to be evicted from $k $ candidates, and analyze appropriate $k $. Third, the performance of our scheduling method is examined by simulation, by varying the mean inter-arrival time of requests and cache size. The results indicate that our method outperforms the popular $LRU $ (Least Recently Used) and “extended $LRU.$”