Adaptive Page Replacement Algorithm--AWL

Virtual memory page replacement algorithm is an important component of virtual memory manager. LRU is the common page replacement strategry,and is used in Windows, Unix, Linux systems. But in some cases, LRU algorithm causes many page faults, so improving LRU page replacement algorithm can reduce page faults, and therefore improve the performance of the system. In this paper, we classify page reference sequences into LRU-friendly page reference sequences, LRU-unfriendly page reference sequences, unfriendly page reference sequences. The classification is based on the analysis of page reference sequences'effect on LRU algorithm by using LRU reference distribution chart.We present a page replacement algorithm adapting between adaptive WFL and LRU algorithms. Experiments using several LRU-unfriendly page reference sequences show that the AWL algorithm is superior to LRU algorithm, and using several LRU-friendly, unfriendly page reference sequences show that the AWL algorithm approximates to LRU algorithm. AWL algorithm is also superior to other LRU improved algorithms.