Background
LRU (least recently used) algorithm is a basic cache replacement algorithm,
which relies on an additonal data structure, called LRU stack, to keep track of
data accesses on each data block. Data block replacement decisions are timely
made based on dynamically recorded data access information for each
data block in the LRU stack. However, LRU
cannot be directly implemented
in any critical path of computer systems, such as operating systems
and latency-sensitive data processing systems, due to its
high overhead on space and time delay. An approximation of LRU, called Clock, is
commonly used in practice. Clock inherits the merits and limits of LRU.
The LIRS caching algorithm fundamentally addresses the limits of
LRU, and retains its merits. An approximation of the
LIRS algorithm is desirable.
The Clock-pro Algorithm
Clock-pro is an approximation of LIRS, which uses the clock structure to
implement the LIRS principle.
The Usage of Clock-pro
Clock-pro has directly influenced the upgrades of replacement algorithms in
commonly used operating systems and data processing systems,
such as Linux, BSD and others.