Application of both Temporal and Spatial Localities in the Management of Kernel Buffer Cache - Advanced Operating Systems and Kernel Applications - page 114

The anonymous pages that do not yet have
mappings on disk are treated as random blocks
until they are swapped out and are associated with
some disk locations. To map the LBN (Logical
Block Number) of a block into a one-dimensional
physical disk address, we use a technique described
in (Schindler et al. 2002) to extract track bound-
aries. To characterize accurately block location
sequentiality, all the defective and spare blocks
on disk are counted. We also artificially place
a dummy block between the blocks on a track
boundary in the mapping to show the two blocks
are non-sequential.
The experiment is conducted on a Dell desktop
with a single 3.0GHz Intel Pentium 4 processor,
512MB memory, and a Western Digital 7200 RPM
IDE disk with a capacity of 160GB. The read-ahead
mechanism built in the hard drive is enabled. The
operating system is Redhat WS4 with its kernel
updated to Linux 2.6.11. The file system is Ext2.
In the experiments, we change the memory sizes
available for benchmarks to observe their perfor-
mance with different memory sizes.

to 3.5%. At the same time, in DULO there are
57.7% sequences whose sizes are larger than 32,
compared with 33.8% in Linux. Accordingly, there
is a 20.1% execution time reduction by DULO. In
contrast, with the memory size of 192MB DULO
reduces random accesses from 15.2% to 4.2% and
increases sequences longer than 32 from 19.8% to
51.3%. Accordingly, there is a 53.0% execution
time reduction. The correlation clearly indicates
that the size of requested sequence is a critical fac-
tor affecting disk performance and DULO makes
its contributions through increasing sequence
sizes. Second, DULO increases the sequence
size without excessively compromising temporal
locality. This is demonstrated by the small differ-
ence of hit ratios between Linux and DULO. For
example, DULO reduces the hit ratios of PostMark
by 0.53%~ 1.6%, while it slightly increases the hit
ratio of BLAST by 1.1% ~ 2.2%. In addition, this
observation also indicates that reduced execution
times and increased server throughputs are results
of the improved disk I/O efficiency, rather than the
reduced I/O operations in terms of the number of
accessed blocks, which is actually the objective of
traditional caching algorithms. Third, sequential
accesses are important in leveraging the buffer
cache filtering effect by DULO. We observe that
DULO achieves more performance improvement
for BLAST than it does for PostMark and LXR.
BLAST has over 40% sequences whose sizes are
larger than 16 blocks, while PostMark and LXR
have only 30% and 15% such sequences. The
small portion of sequential accesses in PostMark
and LXR make DULO less capable of keeping
random blocks from being replaced because there
are not sufficient number of sequentially accessed
blocks to be replaced first.
Meanwhile, DULO has only limited or little
influence on the performance of workloads with
almost-all-sequential and a random accesses. Take
TPC-H and diff as examples. Workload TPC-H has
more than 85% of the sequences that are longer than
16 blocks. For this almost-all-sequential workload,
DULO can only slightly increase the sizes of short

Experiment Results on File Accesses

In the evaluation of impact of DULO on the per-
formance of file access, we select benchmarks
that represent different access patterns, including
almost-all sequential accesses ( TPC-H ), almost
all random accesses ( diff ), and mixed I/O access
patterns ( BLAST, PostMark, LXR ). DULO shows
the most performance advantages with bench-
marks that have considerable amount of both short
sequences and long sequences by increasing the
number of disk accesses to long sequences and
keeping data of short sequence in memory.
Here are insights on the experiment results.
First, the increases of sequence sizes are directly
correlated to the improvement of the execution
times or I/O throughputs. Let us take BLAST
as an example. With a memory size of 512MB,
Linux has 8.2% accesses whose sequence sizes
equal to 1, while DULO reduces this percentage