Sensitivity Analysis of Cache Partition in CLOCK-Pro Page Replacement and its Comparison with Adaptive CLOCK-Pro

Abstract

With the ever-growing performance gap between memory systems and disks, and rapidly improving CPU performance, virtual memory (VM) management becomes increasingly important for overall system performance. However, one of its critical components, the page replacement policy, is still dominated by CLOCK, a replacement policy developed almost 40 years ago. While pure LRU has an unaffordable cost in VM, CLOCK simulates the LRU replacement algorithm with a low cost acceptable in VM management. Over the last three decades, the inability of LRU as well as CLOCK to handle weak locality accesses has become increasingly serious, and an effective fix becomes increasingly desirable. This dissertation work is focused on an improved CLOCK replacement policy, called CLOCK-Pro. By additionally keeping track of a limited number of replaced pages, CLOCK-Pro works in a similar fashion as CLOCK with a VM-affordable cost. CLOCKPro improves weaknesses of CLOCK especially in weak locality of references by using

reuse distance also known as IRR.

For

weak locality workloads CLOCK-Pro and adaptive CLOCK-Pro always performs better than CLOCK page replacement algorithm. CLOCK-Pro page replacement policy increases hit rate up to 40% and adaptive CLOCK-Pro increases hit rate up to 43%. Performance gain is more in case of purely weak locality workloads (such as looping pattern) and performances are comparable in case of strong locality workloads (such as temporally clustered workloads). Again, if the number of distinct pages is nearly equal to cache size CLOCK algorithm also performs better for weak locality workloads.