A low-overhead high-performance unified buffer management scheme that exploits sequential and looping references
Jong Min Kim, Jongmoo Choi, Jesung Kim, Sam H. Noh, Sang Lyul Min, Yookun Cho, Chong Sang Kim
Abstract
In traditional file system implementations, the Least Recently Used
(LRU) block replacement scheme is widely used to manage the buffer
cache due to its simplicity and adaptability. However, the LRU
scheme exhibits performance degradations because it does not make
use of reference regularities such as sequential and looping
references. In this paper, we present a Unified Buffer Management
(UBM) scheme that exploits these regularities and yet, is simple to
deploy. The UBM scheme automatically detects sequential and looping
references and stores the detected blocks in separate partitions of
the buffer cache. These partitions are managed by appropriate
replacement schemes based on their detected patterns. The
allocation problem among the divided partitions is also tackled
with the use of the notion of marginal gains. In both trace-driven
simulation experiments and experimental studies using an actual
implementation in the FreeBSD operating system, the performance
gains obtained through the use of this scheme are substantial. The
results show that the hit ratios improve by as much as 57.7% (with
an average of 29.2%) and the elapsed times are reduced by as much
as 67.2% (with an average of 28.7%) compared to the LRU scheme for
the workloads we used.