Computer Science Events
[PAST EVENT] Shaochang Liu, Computer Science - Thesis Defense
Abstract:
With the growth of data-intensive applications, the demand for memory is rapidly increasing, while main memory capacity remains limited. Effective page reclamation is crucial for maintaining application performance under high memory pressure. In Linux, the default Two-Queue LRU (2QLRU) page replacement policy categorizes pages into active and inactive lists based on access recency, with all pages being reclaimed from the inactive list. However, this default policy has several drawbacks. First, it considers only recency without historical access information, limiting its ability to accurately assess page importance. Second, it relies on evictable characteristics that are not updated promptly, which can lead to the selection of reclaim candidates that are not immediately reclaimable. As the reverse mapping (rmap) process is unavoidable and significantly time-consuming for all page reclaim candidates, having high quality and immediately reclaimable candidates is critical for effective page reclamation.
To address these challenges, an alternative policy, Multi-Generational LRU (MGLRU), has been adopted to optimize page reclamation process. Unlike the default 2QLRU policy, MGLRU incorporates a frequency metric into the selection process for reclaim candidates, offering additional protection for frequently accessed pages, even if they have not been used recently. Additionally, MGLRU proactively scans page table entries (PTEs) and updates page flag bits frequently, which offers more accurate evitable information. As a result of these optimizations, the reclaim candidates selected by MGLRU are more likely to be successfully reclaimed, thereby reducing unnecessary rmap operations.
To quantitatively evaluate the differences between the two policies, we develop a profiler to break down the page reclamation process and capture page reclaim records. For the reclaim process breakdown, we count the cycles of each major reclaim stage and the number of distinct page reclaim operations. For the reclaim record capture, we mainly log the page frame number, virtual address, page type, and NUMA node ID for each reclaimed page. These metrics enable us to analyze detailed reclaim decisions and reclaim quality, in addition to evaluating the end-to-end application performance under page reclamation process. We evaluate the performance of MGLRU and 2QLRU by running a set of HPC, in-memory database, and graph processing benchmarks with our profiler. The results indicate that although MGLRU achieves its design goal of reducing rmap overhead and increasing reclaim success rates in most test cases, these improvements do not always translate to better application performance.
Sponsored by: Computer Science