``CLOCK-Pro: an effective improvement of the CLOCK replacement", Song Jiang, Feng Chen, and Xiaodong Zhang Proceedings of 2005 USENIX Annual Technical Conference (USENIX'05), Anaheim, CA, April 10-15, 2005. 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, page replacement policy is still dominated by CLOCK, a replacement policy developed at least 35 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 have become increasingly serious, and an effective fix on it becomes demanding. However, almost all the major improved replacement algorithms are built on LRU and have a cost at least equivalent to LRU. Inspired by our previously proposed I/O buffer cache replacement algorithm, LIRS, we propose 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. Meanwhile, it brings all the much-needed performance advantages from LIRS into CLOCK. CLOCK-Pro also eliminates the only tunable parameter in LIRS and makes itself a policy adapting to the changing access loca- lity to serve a broad spectrum of workloads. Measurements from an implementation of CLOCK-Pro in Linux Kernel 2.4.21 show that the execution times of some commonly used programs can be reduced up to 47%.Back to the Publication Page.
Back to the HPCS Main Page at the Ohio State University.