EELRU

Abstract

Despite the many replacement algorithms proposed throughout the years, approximations of Least Recently Used (LRU) replacement are predominant in actual virtual memory management systems because of their simplicity and efficiency. LRU, however, exhibits well-known performance problems for regular access patterns over more pages than the main memory can hold (e.g., large loops). In this paper we present Early Eviction LRU (EELRU). EELRU is a simple adaptive replacement algorithm, which uses only the kind of information needed by LRU-how recently each page has been touched relative to the others. It exploits this information more effectively than LRU, using a simple on-line cost/benefit analysis to guide its replacement decisions. In the very common situations where LRU is good, EELRU is good because it behaves like LRU. In common worst cases for LRU, EELRU is significantly better, and in fact close to optimal as it opts to sacrifice some pages to allow others to stay in memory longer. Overall, in its worst case, EELRU cannot be more than a constant factor worse than LRU, while LRU can be worse than EELRU by a factor almost equal to the number of pages in memory.