An Evaluation of Page Replacement Algorithm Based on Low Inter-Reference Recency Set (LIRS) Scheme on Weak Locality Workloads

Abstract

The performance of page replacement algorithms used by cache management of OS is very much important. This situation further more complicates due to limitations of faster memory and I/O system. Among various page replacement algorithms LRU is simple and flexible. But the low overhead LRU misbehaves with weak locality of reference. Mainly weak locality workloads can be categorized into sequential pattern, loop with larger than cache size and probabilistic pattern. This weakness of LRU is only due to the bold assumption on recency factor. Recency factor is only not sufficient because frequency factor also plays important role according as the program behavior. Many modifications on LRU have done such as LRU-K, EELRU, LRFU etc. But unlike others LIRS improved the weaknesses of LRU by considering IRR factor, which is logically a combination of recency and frequency factor. IRR factor is also known as reuse distance and can be achieved by using recency value which is equal to number of distinct references between recent correlated access of a particular block. LIRS can be implemented by different approaches based on its principle. One by focusing on its principle called basic LIRS and another LIRS simulated through data structure which focuses on computational complexity. Both of them are evaluated by using variety of weak locality workloads which represents the memory reference pattern during the execution of program.