Evaluating Impact of Pruned Metadata on Low Inter reference Recency Set (LIRS) Page Replacement Policy

Abstract

To combat the problem of growing performance gap between system and rapidly improving CPU performance, virtual memory system has been becoming increasingly important for all memory management system. Virtual memory system needs an efficient page replacement algorithm to decide which page to be swapped out at page fault. Least Recently Used (LRU) is the one, which captures locality of reference but does not exploit frequency effectively. To minimize the deficiencies presented in LRU Jiang and Zhang [7] proposed a LIRS algorithm which aims at maintaining two key pieces of data access history- the recency and IRR. In this algorithm, the metadata of all accessed blocks in recent past are not maintained on the cache. And the pruning operation is performed to minimize space overhead. Due to such pruning operation, the algorithm can store only one history information of accessed block and cannot work always correct because of the constraint timing scope.

This dissertation, lets us to exploit the impact of pruned metadata on LIRS algorithm by maintaining metadata about all pages accessed in the past.

When workload has high reference locality, Derived LIRS has significantly superior performance than LIRS in terms of hit rate. Derived LIRS has higher hit rate up to 32.22% in comparison to LIRS. This is because Derived LIRS employs several history information items whereas the LIRS scheme uses only one history information item. However, Revised LIRS shows poorer performance on same traces due to the dominance of unused blocks in the cache.