Design, Implementation, and Performance Evaluation of a Detection-Based Adaptive Block Replacement Scheme.
A new buffer replacement scheme, called DEAR (DEtection-based Adaptive Replacement), is presented for effective caching of disk blocks in the operating system. The proposed DEAR scheme automatically detects block reference patterns of applications and applies different replacement policies to different applications depending on the detected reference pattern. The detection is made by a periodic process and is based on the relationship between block attribute values, such as backward distance and frequency gathered in a period, and the forward distance observed in the next period. This paper also describes an implementation and performance measurement of the DEAR scheme in FreeBSD. The results from performance measurements of several real applications show that, compared with the LRU scheme, the proposed scheme reduces the number of disk I/Os by up to 51 percent (with an average of 23 percent) and the response time by up to 35 percent (with an average of 12 percent) in the case of single application executions. For multiple application executions, the results show that the proposed scheme reduces the number of disk I/Os by up to 20 percent (with an average of 12 percent) and the overall response time by up to percent (with an average of 8 percent).
Introduction
The speed gap between the processor and disks is becoming wider as VLSI technologies advance at
an enormous rate. To overcome this speed gap, buffer caches [1] are used to keep in main memory
This paper was presented in part at the USENIX 1999 Annual Technical Conference and at the Fourth IEEE
International Workshop on Multi-Media Database Management Systems.
y Department of Computer Engineering, Seoul National University, Seoul 151-742, Korea; e-mail:
choijm@ssrnet.snu.ac.kr, symin@dandelion.snu.ac.kr, cho@ssrnet.snu.ac.kr.
z Department of Computer Engineering, Hong-Ik University, Seoul 121-791, Korea; e-mail: noh@cs.hongik.ac.kr.
disk blocks that are likely to be accessed in the near future. Since the size of buffer cache is limited,
an effective scheme is needed to decide which block should be kept in the cache. To this end, study
of effective block replacement has been the focus of much research both in the systems and database
areas [2, 3, 4, 5, 6, 7].
Many traditional block replacement algorithms assume that past is a good predictor of the future.
For example, the LRU replacement algorithm assumes that disk blocks that were referenced recently
are more likely to be referenced in the near future than those referenced far back in the past.
Similarly, the LFU replacement algorithm assumes that disk blocks that were referenced frequently
are more likely to be referenced in the near future than those referenced sparsely. One common
problem with these approaches is that the underlying assumptions are not always correct since
actual disk block reference patterns of applications can differ widely depending on applications.
To address the problem above, a number of block replacement schemes have recently been proposed
that make use of user-level hints such as application-controlled file caching [8] and informed
prefetching and caching [9]. User-level hints in these schemes provide information about which
blocks are good candidates for replacement, allowing different replacement policies to be applied
to different applications.
However, to obtain user-level hints, users need to accurately understand the characteristics of
the block reference patterns of applications. This requires considerable effort from users limiting
the applicability. For simple reference patterns such as a sequential reference pattern, a heuristic
method can be used to detect the pattern without user-level hints and an appropriate replacement
policy can be used to improve the buffer cache performance [10]. Also for implicit I/Os that are
used to manage paged virtual memory, their reference pattern can be deduced by the compiler and
an appropriate replacement policies can be used based on the deduced pattern [11].
In this paper, we propose a new replacement scheme called DEAR (DEtection based Adaptive
Replacement) for general file caching. Without any help from the user or the compiler, the DEAR
scheme dynamically detects the reference pattern of each application and classifies the pattern as
sequential, looping, temporally-clustered, or probabilistic. After the detection, the scheme applies
an appropriate replacement policy to the application. As the reference pattern of an application
may change during its execution, the DEAR scheme periodically detects the reference pattern and
applies a different replacement policy, if necessary.
We implemented the DEAR scheme in FreeBSD 2.2.5 and evaluated its performance with several
real applications. The scheme is implemented at the kernel level without any modification to
the system call interface, so the applications may run as-is. Performance measurements with real
applications show that in the case of single application executions the DEAR scheme reduces the
number of disk I/Os by up to 51% (with an average of 23%) and the response time by up to 35%
(with an average of 12%), compared with the LRU buffer management scheme in FreeBSD. For
multiple applications, the reduction in the number of disk I/Os is by up to 20% (with an average
of 12%) while the reduction in the overall response time is by up to 18% (with an average of 8%).
We also compared the performance of the DEAR scheme with that of application-controlled file
caching [8] through trace-driven simulations with the same set of application traces used in [8].
The results show that the DEAR scheme without any use-level hints performs comparably to
application-controlled file caching for the traces considered.
The rest of the paper is organized as follows. In Section 2, we explain the DEAR scheme in detail.
Then, we describe the implementation of the DEAR scheme in FreeBSD in Section 3. In Section 4,
we evaluate the performance of the DEAR scheme. Finally, we conclude this paper with a summary
and discussions of future work in Section 5.
2 The DEAR Scheme
Recent research has shown that most applications show regular block reference patterns and that
these patterns vary depending on the nature of the application. For example, a large class of
scientific applications show a looping reference pattern where blocks are referenced repeatedly with
regular intervals [12]. On the other hand, many database applications show a probabilistic reference
pattern with different probabilities for index blocks and data blocks [13]. Unix applications tend
to show either a sequential or a temporally-clustered reference pattern [8, 14]. Applications that
deal with continuous media generally show a sequential or a looping reference pattern [15].
From these observations, we classify an application's reference pattern into one of the following: se-
quential, looping, temporally-clustered, or probabilistic reference pattern. In the proposed DEAR
Detect the reference pattern based on
the relationship between the block
attribute values and the forward distance,
both as seen at .
Calculate the forward distance of the
blocks referenced between and .
Update the block attributes of the blocks
Update the block attributes of the blocks
referenced between and .
referenced between and .

Figure

1: Detection process: two-stage pipeline with one-level look-behind.
scheme, the detection of an application's reference pattern is made by associating attributes of
blocks with their forward distances 1 . An attribute of a block can be anything that can be obtained
from its past reference behavior including backward distance, frequency, inter-reference gap
[5], and k-th backward distance [3]. In this paper, we consider only two block attribute
types: backward distance, which is the time interval between the current time and the time of the
last reference 2 , and frequency, which is the number of past references to the block.
The detection is performed by a monitoring process that is invoked periodically. At the time of its
i-th invocation (we denote this time by m i
), the monitoring process calculates the forward distances
(as seen from the standpoint of m
) of the blocks referenced between m
. These forward
distances are associated with block attribute values by two ordered lists, one according to backward
distance and the other according to frequency. Each ordered list is divided into a fixed number of
sublists of equal size. Based on the relationship between the attribute value of each sublist and the
average forward distance of blocks in the sublist, the block reference pattern of the application is
deduced.
After the detection, the block attributes of the blocks referenced between m
are updated
for the next detection. As shown in Figure 1, the detection process is essentially a two-stage pipeline
with one-level look-behind since the detection at m i
is made based on the relationship between the
block attribute values and the forward distance at m i\Gamma1 .
As an example, consider Figure 2. Assume that the detection period is 10 as measured in the number
1 The forward distance of a block is defined as the time interval between the current time and the time of the next
reference to the block.
2 In this paper, we assume that the (virtual) time is incremented on each block reference.
average
forward
average
forward
average
forward
average
forward
(a) (b) (c)
backward
backward
backward
backward
backward
backward
distance
distance
distance
distance
distance
time
sublist sublist
backward distance
sublist
sublist
sublist
sublist
frequency
bdbdbdfrfrfraverage
forward
average
forward

Figure

2: Example of block reference pattern detection.
of block references made by the associated application. Also assume that between m
, and b 6
were referenced in the given order (see

Figure

2-(b)). Finally, assume that at m i\Gamma1
the backward distance and frequency of the six distinct
blocks b 4
were 15, 12, 25, 4, 20, 9 and 6, 4, 5, 2, 1, 1, respectively (see Figure 2-
(a)). Note that these distinct blocks have forward distances of 1, 2, 3, 4, 6, 7, respectively as
seen at m i\Gamma1
. From the information about the block attribute values and the forward distance,
the DEAR scheme constructs two ordered lists, one according to backward distance and the other
according to frequency (see Figure 2-(c)). Each list is divided into a number of sublists of equal
size (3 sublists of size 2, in this example). Then various rules for detecting reference patterns,
which are explained below, are applied to the two lists. In this particular example, blocks with
higher frequency have smaller forward distance, which allows us to deduce that the block reference
pattern of the given application follows a probabilistic reference pattern. The detection rules for
the probabilistic reference pattern and the other reference patterns can be more formally stated as
follows:
Sequential Pattern: A sequential reference pattern has the property that all blocks are referenced
one after the other and never referenced again. In this pattern, the average forward distance
of all the sublists is 1. Therefore, a reference pattern is sequential if Avg fd(sublist bd
Avg fd(sublist fd(sublist fd(sublist
sublist bd
and sublist fr
are the i-th sublist for the backward distance and frequency block
attribute types, respectively, and Avg fd(sublist) is the average forward distance of blocks
in sublist.
Looping Pattern: A looping reference pattern has the property that blocks are referenced repeatedly
with a regular interval. In this pattern, a block with a larger backward distance
has a smaller forward distance. Therefore, a reference pattern is looping if the following
relationship holds: if fd(sublist bd
fd(sublist bd
Temporally-clustered Pattern: A temporally-clustered reference pattern has the property that
a block referenced more recently will be referenced sooner in the future. Thus, a block with
a smaller backward distance has a smaller forward distance. Therefore, a reference pattern
is temporally-clustered if the following relationship holds: if fd(sublist bd
Avg fd(sublist bd
Probabilistic Pattern: A probabilistic reference pattern has a non-uniform block reference behavior
that can be modeled by the Independent Reference Model (IRM) [16]. Each block b i
has a stationary probability p i
and all blocks are independently referenced with the associated
probabilities. Under the stationary and independent condition, the expected forward distance
of b i
is proportional to 1=p i
. Thus, a block with a higher frequency has a smaller forward
distance. Therefore, a reference pattern is probabilistic if the following relationship holds: if
fd(sublist fr
fd(sublist fr
In the DEAR scheme, different replacement policies are used for different applications depending
on the detected reference pattern. For the sequential and looping reference patterns, the MRU
replacement policy is used where the block with the smallest backward distance is always selected
for replacement. For the temporally-clustered reference pattern, the LRU replacement policy, which
replaces the block with the largest backward distance, is used. Finally, for the probabilistic reference
pattern, the LFU replacement policy that replaces the block with the lowest reference frequency is
used.
1. read()/write()
2. bread()/bwrite()
5. vfs_strategy()
3. getnewbuf()/
System Call Interface
Virtual File System
Buffer Cache
4. new_interface .
Unix File System Network File System Log-structured File System
ACM
ACM
ACM

Figure

3: Overall structure of the DEAR scheme in FreeBSD 2.2.5.
3 Implementation of the DEAR Scheme in FreeBSD

Figure

3 shows the overall structure of the buffer cache manager for the DEAR scheme as implemented
in FreeBSD 2.2.5. The DEAR scheme applies different replacement policies to different
applications. This requires a split of the buffer cache management module into two parts, one for
block allocation and the other for block replacement. The module responsible for block allocation
is the System Cache Manager (SCM). There is one SCM in the system. The module responsible
for block replacement is the Application Cache Manager (ACM). There is one ACM for each ap-
plication. This organization is similar to that proposed for application-controlled file caching [8].
Both of the modules are located in the VFS (Virtual File System) layer and collaborate with each
other for buffer allocation and block replacement.
An ACM is allocated to each process when the process is forked. When a block is referenced from
the process, the associated ACM is called by the bread() or bwrite() procedure in the SCM (1)
to locate the information about the referenced block using a hash table, (2) to update the block
attribute that is changed by the current reference, (3) to place the block into a linked list that
maintains the blocks referenced in the current detection period, and (4) to adjust the replacement
order according to the application-specific replacement policy. To maintain the replacement order,
the current implementation uses the linked list data structure for the LRU and MRU replacement
policies and the heap data structure for the LFU replacement policy.
Application K
Application
ACM
Application
(2) send a replacement request
using the application-specific block replacement policy
(3) select a victim block
(1) request new buffer space
allocate new buffer space
deallocate buffer space
of the victim block

Figure

4: Interaction between ACM and SCM.
After the steps (1)-(4) are performed, a check is made to see whether the current detection period
is over. If so, the monitoring process explained in the previous section is invoked to detect the
application's reference pattern. The detected reference pattern dictates the replacement policy of
the ACM. If none of the detection conditions previously explained is satisfied, the default LRU
replacement policy is used.
The structure of information maintained for each block by the ACM is !vnode #, block #,
backward distance, frequency, forward distance, hp, bp, fp, cp?. The pointer hp is used
to place the block into the hash table that is used to locate the information about the currently
referenced block. The pointers bp and fp are used to place the block into the ordered lists for the
backward distance and frequency block attribute types, respectively, which are constructed when
the monitoring process is invoked. Finally, the pointer cp is used to place the block into the list of
blocks referenced in the current detection period. This data structure is the main space overhead
of the DEAR scheme.
The main time overhead of the DEAR scheme is that needed to order the blocks according to
each block attribute value, which has an O(n log n) time complexity where n is the number of
distinct blocks referenced in the detection period. This operation is invoked once at the end of
each detection period for each block attribute type. Other time overheads include those needed
to calculate the forward distance, backward distance, and frequency of blocks at the end of each
detection period, which has a time complexity of O(n) where n is the number of distinct blocks
referenced in the detection period.
The ACM and SCM interact with each other as depicted in Figure 4. When an application misses
in the buffer cache, the ACM for the application makes a request to the SCM for additional buffer
space (step (1) in Figure 4). If the SCM does not have any free buffer space, it sends a replacement
request to one of the ACMs (step (2)). This operation is performed in the getnewbuf() procedure
in the SCM, and the first choice is an ACM associated with an application whose current reference
pattern is sequential. If there is no such application, the SCM simply chooses the ACM of the
application with the global LRU block. This strategy is similar to the one used in the application-controlled
file caching [8]. The selected ACM decides the victim block to be replaced using its
current replacement policy (step (3)) and deallocates its space to the SCM (step (4)). The SCM
allocates this space to the ACM that requested the space (step (5)).
Performance Evaluation
In this section, we present the results of the performance evaluation of the DEAR scheme. We first
describe the experimental set-up. Then, we give the results of reference pattern detection followed
by the performance measurement results for both single applications and multiple applications. We
also give results from sensitivity analysis for different cache sizes, detection periods, and numbers
of sublists. Finally, we compare the performance of the DEAR scheme with that of application-controlled
file caching [8].
4.1 Experimental Set-up
The experiments were conducted with FreeBSD 2.2.5 on a 166MHZ Intel Pentium PC with 64MB
RAM and a 2.1GB Quantum Fireball hard disk. The applications we used are described below and
are summarized in Table 1.
cscope Cscope is an interactive C-source examination tool. It creates an index file named cscope.out
from C sources and answers interactive queries like searching C symbols or finding specific
functions or identifiers. We used cscope on kernel sources of roughly 9MB in size and executed
queries that search for five literals.

Table

1: Characteristics of the applications.
Application Description Input data (MB)
cscope C-source examination tool C code
glimpse information retrieval tool text files (5-50)
utility text files (4.5)
link UNIX link editor object files (2.5)
cpp C preprocessor C code (1-10)
gnuplot GNU plotting utility numeric data (8)
postgres1 relational DB system two relations (7.5-15)
postgres2 relational DB system four relations (0.05-15)
glimpse Glimpse is a text information retrieval utility. It builds indexes for words and performs
fast searching. Text files of roughly 50MB in size were indexed resulting in about 5MB of
indexes. A search was done for lines that contain the keywords multithread, realtime, DSM,
continuous media, and diskspace.
sort Sort is a utility that sorts lines of text files. A 4.5MB text file was used as input, and this file
was sorted numerically using the first field as the key.
link Link is a UNIX link-editor. We used this application to build the FreeBSD kernel from about
2.5MB of object files.
cpp Cpp is the GNU C-compatible compiler preprocessor. The kernel source was used as input
with the size of header files and C-source files of about 1MB and 10MB, respectively.
gnuplot Gnuplot is a command-line driven interactive plotting program. Using 8MB raw data,
the program plotted three-dimensional plots four times with different points of view.
postgres1 and postgres2 Postgres is a relational database system from the University of California
at Berkeley. PostgresSQL version 6.2 and relations from a scaled-up Wisconsin benchmark
were used. Postgres1 is a join between the hundredthoustup and twohundredthoustup relations
while postgres2 is a join among four relations, namely, fivehundredup, twothoustup,
twentythoustup, and twohundredthoustup. The sizes of fivehundredup, twothoustup, twen-
tythoustup, hundredthoustup, and twohundredthoustup are approximately 50KB, 150KB,
1.5MB, 7.5MB, and 15MB, respectively.
4.2 Detection Results
seq seq loop loop loop loop
seq loop loop
Detection Result
prob prob prob prob prob prob
prob prob prob
Detection Result200600100014001800
logical
block
number
virtual time
(a) cscope1003005007000 500 1000 1500 2000 2500 3000 3500 4000 4500 5000
logical
block
number
virtual time
(b) cpp

Figure

5: Block reference patterns and detection results for cscope and cpp.

Figure

5 shows the results of the detection by the DEAR scheme for the cscope and cpp applications.
In each graph, the x-axis is the virtual time that increments on each block reference and the y-axis
is the logical block numbers of those referenced at the given time. The detection results are given at
the top of the graph assuming a detection period of 500 references. For cscope, the DEAR scheme
initially detects a sequential reference pattern but changes its detection to a looping reference
pattern after the sequentially referenced blocks are re-accessed. This behavior results from cscope
always reading the file cscope.out sequentially whenever it receives a query about the C source. For
cpp, the DEAR scheme detects a probabilistic reference pattern throughout the execution since as
we can see from the graph, some blocks are more frequently accessed than others. This reference
pattern results from the characteristic of cpp that header files are more frequently referenced than
files.

Figure

6 shows the detection results of the other applications. Although the result shows that the
DEAR scheme performs reasonably well for the other applications, it also reveals the limitation of
the current DEAR scheme, notably for the sort and postgres2 applications. They have either parallel
or nested reference streams, which indicates a need for the proposed DEAR scheme to address more
general reference patterns with arbitrary control structures such as parallel, sequence, and nested.
Detection Result
seq seq loop loop loop loop loop
seq
loop
Detection Result
seq seq seq loop
undetect loop50015002500
logical
block
number
virtual time
(a) glimpse200600100014001800
logical
block
number
virtual time
(b) sort
Detection Result
seq seq loop loop
seq loop loop
loop
Detection Result
seq loop loop loop loop loop
loop1003005000 500 1000 1500 2000 2500 3000 3500 4000 4500 5000
logical
block
number
virtual time
(c) link1003005007009000 500 1000 1500 2000 2500 3000 3500 4000 4500 5000
logical
block
number
virtual time
(d) gnuplot
Detection Result
seq seq loop loop loop loop loop loop loop prob prob
Detection Result
prob seq prob loop prob prob
undetect50015002500
logical
block
number
virtual time
logical
block
number
virtual time
(f) postgres2

Figure

reference patterns and detection results for the other applications.
QPPPP QPPPP
QRPPP QRPPP
QTPPP QTPPP
a#OEo/oof"o/oo#"a#OEo/oof"o/oo#"
deardear
@@@f#@@@f#OE#OE#"
(a) Number of Disk I/Os
QPPQPP
QRPQRP
QTPQTP
QVPQVP
a#OEo/oof"o/oo#"a#OEo/oof"o/oo#"
r.@to/oo#.@H".f#""I r.@to/oo#.@H".f#""I lrulru
deardear
@@@f#@@@f#
@@OEo/oo#<@@OEo/oo#<
#OEo/oo#OEo/oo#".
(b) Response Time

Figure

7: Single application performance.
4.3 Performance Measurements: Single Applications
We compared the performance of each application under the DEAR scheme with not only that
under the LRU scheme built in FreeBSD but also with those under the LFU and MRU schemes.
For this purpose, we implemented the DEAR scheme as well as the LFU and MRU schemes in
FreeBSD. We measured both the number of disk I/Os and the response time of each application
for a 6MB buffer cache with block size set to 8KB. For the DEAR scheme, we set the length of the
detection period to 500 and the number of sublists in the ordered lists to 5 for both the backward
distance and frequency block attribute types. The performance of the DEAR scheme for different
cache sizes, different detection periods, and different numbers of sublists in the ordered lists is
discussed in Section 4.5.

Figure

7 shows the number of disk I/Os and the response time of the four schemes. The values
reported here are the average of three separate executions and before each execution, the system
was rebooted to eliminate any effects resulting from prior buffer cache contents. From the results
we observe the following:
ffl The DEAR scheme performs almost as good as the best of the other three schemes for all
the applications we considered. Also, when compared with the LRU scheme in FreeBSD, the
number of disk I/Os is reduced by up to 51% (for the cscope application) with an average of
23% and the response time by up to 35% (also for the cscope application) with an average of
%.
ffl For the link application, there is no performance difference among the four schemes. This is
because the input data to the link application is small (2.5MB), and thus all the blocks reside
in the buffer cache after they are initially loaded.
ffl Postgres1 and postgres2 do not show as much improvement in the response time as that in the
number of disk I/Os when using the DEAR scheme. This is because of the constant synchronization
between the client (the psql utility that provides the user interface) and the server
(the postgres process that performs the query processing and database management). For
the gnuplot application, much time was spent for user mode computation and thus reduction
in the number of disk I/Os has a limited impact on the response time.
ffl Except for the above three applications, the ratio between the reduction in the number of
disk I/Os and that in the response time is consistent. This indicates that the DEAR scheme
incurs little extra overhead over those in the other schemes.
The last point is more evident in Figure 8 where the response time is divided into three components:
I/O stall time, system time, and user time. For the LRU scheme of FreeBSD, the system time
consists of VFS processing time, buffer cache management time, disk driver processing time, disk
interrupt handling time and, data copy time from buffer cache to user space. On top of those, the
DEAR scheme requires additional processing time such as the time for sorting blocks according to
block attribute values and also for maintaining block attribute values and forward distances. From

Figure

8, we can notice that the system times of the two schemes are comparable meaning that the
DEAR scheme incurs little additional overheads.
4.4 Performance Measurements: Multiple Applications
In real systems, multiple applications execute concurrently competing for limited buffer space. To
test the DEAR scheme in such an environment, we ran several combinations of two or more of
the applications with a buffer cache of 6MB and measured the total number of disk I/Os and the
overall response time for both the DEAR scheme and the LRU scheme in FreeBSD. Again, we set
the length of the detection period to 500 and the number of sublists in the ordered lists to 5.
QPPQPP
lru lru dear dear lru lru dear dear lru lru dear dear lru lru dear dear lru lru dear dear lru lru dear dear lru lru dear dear lru lru dear dear
a#OEo/oof"o/oo#"a#OEo/oof"o/oo#"
r.@to/oo#.@Hs.f#""I r.@to/oo#.@Hs.f#""I iOo@""OEOE@"o/oo#.iOo@""OEOE@"o/oo#.
"^TM"".#@"o/oo#."^TM"".#@"o/oo#.
.'@''o/oo#.'@"o/oo#.
#'.``R#'."R
#OEo/oo#OEo/oo#OE#OE#"
OEo/oo#<OEo/oo#<

Figure

8: Decomposition of response time.
QPPPPQPPPP
QRPPPQRPPP
QTPPPQTPPP
QVPPPQVPPP
QXPPPQXPPP
a#OEo/oof"o/oo#"a#OEo/oof"o/oo#"
deardear
(a) Number of Disk I/Os
UPUP
QPPQPP
QUPQUP
a#OEo/oof"o/oo#"a#OEo/oof"o/oo#"
o-.'OEOE@r.@to/oo#.@Hs.f#''``I o-.'OEOE@r.@to/oo#.@Hs.f#""I lrulru
deardear
(b) Overall response time

Figure

9: Multiple application performance.

Table

2: Performance comparison between the LRU-SEQ and the DEAR schemes.
Scheme Response Time (seconds)
cs+sort gli+link cs+wc gli+wc
LRU 70.96 89.87 81.27 89.97
DEAR 66.61 74.29 62.88 82.36
The results in Figure 9 show that the number of disk I/Os is reduced by up to 20% (for the
cscope+sort+link case) with an average of 12% and the overall response time by up to 18% (for
the glimpse+link case) with an average of 8%.
In the multiple application case, there are two possible benefits from using the proposed DEAR
scheme. The first is from applying different replacement policies to different applications based on
their detected reference patterns. The second is from giving preference to blocks that belong to an
application with the sequential reference pattern when a replacement is needed. To quantify these
two different types of benefit, we performed an experiment where even the LRU replacement policy
gives preference to blocks belonging to an application with the sequential reference pattern, which
we call the LRU-SEQ replacement policy.

Table

2 shows the results of the LRU-SEQ scheme for the 6MB buffer cache size. In the case
of cscope+sort and glimpse+link, there is little difference between the LRU and the LRU-SEQ
schemes, since the reference pattern of the four component applications is not sequential in the
steady state. Replacing sort and link with wc, whose reference pattern is sequential, produces
a significant difference in the response time between the LRU and the LRU-SEQ schemes. This
results from the LRU-SEQ scheme allocating more buffer space to cscope (or glimpse) by replacing
blocks of the wc application earlier than the usual LRU order. Still, there is a substantial difference
in the response time between the LRU-SEQ scheme and the DEAR scheme indicating that the
benefit from applying different replacement policies tailored for different applications is significant.
4.5 Sensitivity Analysis
Cache Size Tables 3 and 4 compare the performance of the DEAR scheme against the LRU

Table

3: Single application performance for various buffer cache sizes.
Application Scheme Response Time (seconds)
cscope DEAR 16.99 14.90 12.87 11.17
LRU 19.79 19.79 19.77 19.77
glimpse DEAR 39.12 35.68 33.73 32.87
link DEAR 28.19 23.38 23.38 23.38
cpp DEAR 132.94 94.42 91.61 91.36
gnuplot DEAR 43.54 42.26 41.39 41.19
postgres1 DEAR 38.37 36.16 34.22 32.17
postgres2 DEAR 74.57 72.51 71.15 68.45
LRU 82.93 74.93 74.75 73.93
scheme for various buffer cache sizes for the single and multiple application cases, respectively. The
results from the single application case show that as long as the total number of distinct blocks
accessed by an application is greater than the number of blocks in the buffer cache, there is a
substantial difference in the response time between the DEAR and the LRU schemes. However,
when the number of distinct blocks of an application is smaller than the number of blocks in
the buffer cache, all the blocks are cached in the buffer cache and the two schemes show similar
performance. This behavior is most visible for the link application that has the smallest number
of distinct blocks (about 310 blocks).
For the multiple application case, the case where the total number of distinct blocks accessed by
the component applications is smaller than the number of blocks in the buffer cache does not occur
and the DEAR scheme shows consistently better performance than the LRU scheme.
Detection Period and the number of Sublists Determining the length of the detection
period is an important design issue that requires a trade-off. If the detection period is too long,
the scheme will not be adaptive to possible changes of the reference pattern within a detection
period. On the other hand, if the period is too short, the scheme would incur too much overhead

Table

4: Multiple application performance for various buffer cache sizes.
Applications Scheme Response Time (seconds)
cs+sort DEAR 70.4 66.6 62.9 53.5
LRU 71.5 70.9 69.9 67.3
gli+link DEAR 79.1 74.2 71.6 70.1
LRU 94.5 89.8 79.1 77.9
cpp+ps1 DEAR 222.2 216.7 209.8 202.4
gli+ps2 DEAR 145.6 139.8 132.5 128.3
cs+sort+link DEAR 116.1 112.7 106.7 101.8
LRU 121.3 118.0 112.8 105.3
LRU 246.3 245.3 225.9 222.9

Table

5: The effect of the detection period on the performance of the DEAR scheme for the single
application case.
Scheme Detection Response Time (seconds)
Period cscope glimpse sort cpp gnuplot postgres1 postgres2
100 12.85 33.70 13.72 98.81 40.92 34.62 76.56
DEAR 500 12.87 33.73 13.60 91.61 41.39 34.22 71.15
1000 13.52 36.26 13.88 91.78 41.66 34.53 72.41
2000 15.20 36.45 15.77 91.99 42.36 34.84 72.53

Table

The effect of the detection period on the performance of the DEAR scheme for the multiple
application case.
Scheme Detection Response Time (seconds)
Period cs+sort gli+link cpp+ps1 gli+ps2 cs+sort+link gli+sort+cpp
100 66.68 73.54 236.29 144.67 108.86 251.54
DEAR 500 66.61 74.29 216.73 139.88 112.73 235.56
1000 67.34 74.99 216.91 139.24 116.30 238.70
2000 68.70 81.69 219.38 139.34 116.84 241.41
to be practical. Moreover, if the period is too short, a short burst of references may mislead the
detection. For example, a probabilistic reference pattern may be mistaken for a looping reference
pattern when a small number of blocks are repeatedly accessed over two detection periods.
The above trade-off relationship is evident in Table 5 that gives the response time of all but the
link application as the detection period varies from 100 to 2000. We exclude the link application
since as we mentioned earlier all of its blocks fit into the buffer cache. Thus different detection
periods do not make any difference. For most of the remaining applications, the best performance
was obtained when the detection period is either 250 or 500. The results also show that even with
detection periods that are considerably smaller or larger than these optimal values, the DEAR
scheme performs better than the LRU scheme in FreeBSD. The exceptions are with the cpp and
postgres2 applications when the detection period is 100. In these two cases, the performance degradation
is considerably larger than the others at the detection period of 100. A careful inspection
of the results revealed that when the detection period is 100 the DEAR scheme mistakenly detects
both applications to have a looping reference pattern when in reality it was part of a probabilistic
reference pattern. The multiple application case shows a similar effect of the detection period on
the performance as we can see in Table 6.
For the sequential reference pattern, we can use a simpler detection rule that checks whether the
referenced block numbers are consecutive and this detection can be made early in the execution of
an application. We experimented with this optimization and Table 7 shows the results assuming
the buffer cache size is 6MB. In the experiment, the DEAR scheme with early detection tries to
identify a sequential reference pattern within 20 block references and if not successful, it reverts to
the original DEAR scheme with a detection period of 500.

Table

7: Performance of early detection of sequential reference patterns.
Response Time (seconds)
DEAR DEAR with Early Detection
cscope 12.87 12.82
glimpse 33.73 33.36
cscope+sort 66.61 65.45
glimpse+link 74.29 73.18
cscope+sort+link 112.73 108.19

Table

8: The effect of the number of sublists on the detection results of the DEAR scheme.
Application Detection Results
Number of sublists = 3 Number of Number of
cscope seq[3],loop[8] seq[3],loop[8] seq[3],loop[8]
glimpse seq[4],loop[8] seq[4],loop[8] seq[3],loop[9]
link seq[3],loop[5] seq[3],loop[5] seq[3],loop[5]
cpp prob[18] prob[18] prob[13],undetect[5]
gnuplot seq[1],loop[6] seq[1],loop[6] seq[1],loop[6]
postgres1 seq[5],loop[16] seq[5],loop[16] seq[5],loop[16]
postgres2 prob[13],loop[5],seq[2],undetect[1] prob[12],loop[4],seq[2],undetect[3] prob[11],loop[3],seq[2],undetect[5]
The results show that in the case of single application executions the DEAR scheme with early
detection shows little improvement over the original DEAR scheme. This is because the original
DEAR scheme can determine an appropriate replacement policy before block replacements are
made since there are more blocks in the buffer cache (about 750 blocks when the buffer cache size is
6MB and the block size is 8KB) than the detection period. For the multiple application executions,
the early detection scheme shows a larger improvement since early detection of sequential reference
patterns allows more effective buffer allocation but still the improvement is not significant.
The number of sublists used in the detection process can affect the detection results of the DEAR
scheme. Table 8 gives the detection results of the DEAR scheme as the number of sublists increases
from three to seven. From the results, we can notice that the number of sublists hardly affects the
detection results although there is a slight increase in the number of undetected cases as the number
of sublists increases due to a more strict detection rule. Remember that to detect a reference pattern
the associated detection rule should be held for all the sublists.
4.6 Comparison with Application-controlled File Caching
To compare the performance of the DEAR scheme with that of application-controlled file caching
(ACFC) [8], we performed trace-driven simulations with the same set of three application traces
used in [8]. Figure 10 shows the miss ratio of the three applications for the LRU, ACFC, DEAR,
and OPT (off-line optimal) schemes when cache size increases from 1MB to 16MB. The results for
the LRU, ACFC, and OPT schemes were borrowed from [8] and those for the DEAR scheme were
obtained by simulating the DEAR scheme with detection period equal to 500 and the number of
sublists in the ordered list equal to 5 for both backward distance and frequency block attribute
types. The results show that the miss ratio of the DEAR scheme is comparable to that of the ACFC
scheme, which utilizes user-level hints to guide the replacement decisions. The small difference
between the two schemes results from the misses that occur before the DEAR scheme has a chance
to detect the reference pattern.
5 Conclusions and Future Work
In this paper, we proposed a new buffer management scheme called DEAR (DEtection based
Adaptive Replacement) that automatically detects the block reference pattern of applications as
sequential, looping, temporally-clustered, or probabilistic without any user intervention. Based on
the detected reference pattern, the proposed DEAR scheme applies an appropriate replacement
policy to each application.
We implemented the DEAR scheme in FreeBSD 2.2.5 and measured its performance using several
real applications. The results showed that compared with the buffer management scheme in
FreeBSD the proposed scheme reduces the number of disk I/Os by up to 51% (with an average of
23%) and the response time by up to 35% (with an average of 12%) in the case of single application
executions. For multiple applications, the reduction in the number of disk I/Os is by up to 20%
(with an average of 12%) while the reduction in the overall response time is by up to 18% (with an
average of 8%).
We also compared the performance of the DEAR scheme with that of application-controlled file
caching [8] through trace-driven simulations. The results showed that the DEAR scheme performs
UU
QPQP
QUQU
so/oos.@#+@b.'@cf.@HmbIso/oos.@#+@b.'@cf".@HmbI
mo/oo""@r"o/oo#HEI mo/oo""@r"o/oo#HEI lrulru
deardear
acfcacfc
optopt
@Q@@@@R@@@@@@@@@T@@@@@@@@@@@@@@@@@@@@@X@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@QV@ Q@@@@R@@@@@@@@@T@@@@@@@@@@@@@@@@@@@@@X@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@QV
(a) cscope
QPQP
UPUP
so/oos.@#+@b.'@cf.@HmbIso/oos.@#+@b.'@cf".@HmbI
mo/oo""@r"o/oo#HEI mo/oo""@r"o/oo#HEI lrulru
deardear
acfcacfc
optopt
(b) linking kernel
QPQP
UPUP
WPWP
so/oos.@#+@b.'@cf.@HmbIso/oos.@#+@b.'@cf".@HmbI
mo/oo""@r"o/oo#@HEI mo/oo""@r"o/oo#@HEI lrulru
deardear
acfcacfc
optopt
@Q@@@@@@R@@@@@@@@@@@@@@@@@T@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@X@ Q@@@@@@R@@@@@@@@@@@@@@@@@T@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@X
(c) Postgres

Figure

10: Comparison with application-controlled file caching.
comparably to application-controlled file caching for the traces considered.
As we noted in Section 4.2, some applications have block reference behavior that cannot be characterized
by a single reference pattern. One direction for future research is to extend the current
DEAR scheme so that it can detect more complex reference patterns with parallel, sequence, and
nested structures as well as to develop appropriate replacement policies for them. Another direction
for future research is to study more advanced buffer allocation strategies for the DEAR
scheme than the simple strategy explained in Section 3. A good buffer allocation strategy for the
DEAR scheme should reward more to applications with larger reductions in the number of disk
I/Os while preventing any one application from monopolizing the buffer space. Other directions
for future research include applying the detection capability of the DEAR scheme to prefetching
and considering block attribute types other than backward distance and frequency.



--R

The Design of the UNIX Operating System.
"Data Cache Management Using Frequency-Based Replacement,"
"The LRU-K Page Replacement Algorithm for Database Disk Buffering,"
"On the Existence of a Spectrum of Policies that subsumes the Least Recently Used (LRU) and Least Frequently Used (LFU) Policies,"
"An Inter-Reference Gap Model for Temporal Locality in Program Behavior,"
"A Generalized Interval Caching Policy for Mixed Interactive and Long Video Workloads,"
"Flexible and Adaptable Buffer Management Techniques for Database Management Systems,"
"Application-Controlled File Caching Policies,"
"Informed Prefetching and Caching,"
"Adaptive Page Replacement Based on Memory Reference Behavior,"
"Automatic Compiler-Inserted I/O Prefetching for Out-of-Core Applications,"
"A Static Analysis of I/O Characteristics of Scientific Applications in a Production Workload,"
"Characterization of Database Access Pattern for Analytic Prediction of Buffer Hit Probability,"
"Mea- surements of a Distributed File System,"
"Design and Implementation of Symphony: An Integrated Multimedia File System,"
Operating Systems Theory.
--TR

--CTR
Yannis Smaragdakis, General adaptive replacement policies, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
performance evaluation;reference pattern;buffer cache;FreeBSD;replacement policy