OSDI 2000 Abstract
A Low-Overhead High-Performance Unified Buffer Management Scheme that Exploits Sequential and Looping References
Jong Min Kim, Jongmoo Choi, Jesung Kim, Seoul National University; Sam H. Noh, Hong-Ik
University; and Sang Lyul Min, Yookun Cho, and Chong Sang Kim, Seoul National University
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.
|