Characterizing Emerging Page Replacement Policies for Memory-Intensive Applications

For decades, page replacement in operating systems has referred to the process of moving pages between main memory and disk. During this time, most operating systems used the Clock LRU algorithm for replacement. However, the increased tiering of memory systems has led to the development of new paging algorithms to manage data movement between various memory technologies, algorithms that have often coopted methods from Clock LRU for page migration. At the same time, the Linux kernel has adopted a new Multi-Generational LRU (MG-LRU) algorithm for page replacement. As memory footprints and hierarchies grow, it is important to understand the key attributes of paging algorithms that determine their performance on various workloads and system configurations.This work presents the first characterization of multiple MG-LRU configurations on various memory-intensive workloads for SSD and ZRAM swap. Our experiments show that MG-LRU exhibits high performance variation across otherwise identical workload executions. We also show that the relative performance of MG-LRU compared to Clock LRU is highly variable across different configurations of the surrounding system. Finally, we confirm that simple adjustments to MG-LRU parameters are not a panacea to these issues. Broadly, our work illuminates the complex relationship between workloads, system configurations, and replacement policies and motivates further work to profile, re-invent, and ultimately optimize memory management in computer systems.