``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%.