HitShield: Enhanced Swap Eviction Scheme for Multi-Generational LRU

The least recently used (LRU) algorithm is one of the page replacement algorithms used in the swap mechanism of the Linux kernel. The LRU algorithm has evolved through various modifications and developments, ranging from pseudo LRU to LRU/2, and the multi-generational LRU (MGLRU) is currently being discussed and implemented in recent kernels. MGLRU is a variant of the LRU algorithm that improves upon the limitation of using previous memory access records in traditional inactive and active lists. It was officially merged into the kernel 6.1 and continues to be actively improved since then. This paper introduces the HitShield mechanism, which addresses one of the drawbacks of MGLRU: the lack of consideration for the state of the folio during eviction. HitShield is designed by modifying the internal functions of MGLRU, where a counter is maintained in the function that updates the generation of the folio. When eviction occurs, if HitShield of the folio is activated, it is protected from eviction once by promoting it to the youngest generation, similar to a second-chance algorithm. The implementation of HitShield has demonstrated performance improvements ranging from 1.79% to 6.21% in the situation with insufficient memory of the 7-Zip benchmark, from 2.63% to 12.1% in kernel build tasks, and from 0.83% to 9.02% across workloadAto F inYahoo! cloud serving benchmark (YCSB). Additionally, the number of swap-in and swap-out reduced approximately 2.04% to 3.34% and 1.4% to 3.36% in the 7-Zip benchmark, 2.04% to 14.06% and 2.25% to 8.94% in kernel build tasks, and 71.71% to 89.9% and 71.06% to 88.94% in YCSB, respectively. It is anticipated that the HitShield technique can contribute to solving the folio placement problem between compute express link (CXL) and DRAM in future CXL memory expansion environments.