Exploiting Disk Layout and Block Access History for I/O Prefetch - Advanced Operating Systems and Kernel Applications - page 216

run of grep with DiskSeen increases the request
size by 28 times, compared to the stock Linux
kernel. We can also see that, with more aggressive
prefetching in the second run, the request size is
also effectively increased further. Also note that,
the increases of request size are not proportional
to their respective reductions in execution time.
This is due to many factors, such as the percentage
of computation and data accesses in a program.
However, this figure clearly shows that DiskSeen
effectively improves the efficiency of disk accesses
by increasing request sizes, as expected.

synthetic workloads and real applications such as
grep , CVS , TPC-H .

referenceS

Bryant, R. E., & O'Hallaron, D. R. (2003). Com-
puter Systems: A Programmer's Perspective.
Prentice Hall, pp.294.

Forum, M. P. I. (1997). MPI-2: Extensions to the
Message-Passing Interface, URL: http://www.
mpi-forum.org/docs/mpi-20-html/mpi2-report.
html

Gray, J., & Shenoy, P. J. (2000). Rules of Thumb
in Data Engineering. Proceedings of International
Conference on Data Engineering , 2000 , 3-12.

concluSion

For improving disk performance, prefetching plays
an important role in operating systems. Unfortu-
nately, the widely adopted file-level prefetching
has many intrinsic limitations, which cannot be
addressed at the logic file level. In this chapter,
we present a disk-level prefetching scheme, called
DiskSeen, to exploit the disk-specific information
and complement the traditional file-level prefetch
policies. By directly observing data accesses at
disk level, DiskSeen can identify sequential disk
accesses and perform more accurate sequence-
based prefetching. By exploiting block access
history, DiskSeen can effectively identify non-
sequential disk accesses that are repeated in
history and perform efficient block prefetching
with low overhead. Working at disk level, Disk-
Seen overcomes barriers imposed by file-level
prefetching such as prefetching data blocks across
file boundaries or across lifetimes of open files.
At the same time, DiskSeen complements rather
than replaces high-level prefetching schemes,
which help preserve the effectiveness of existing
file-level prefetching and correct its inaccurate
prefetch decision. The DiskSeen prototype imple-
mented in the Linux 2.6 kernel shows that such a
disk-level prefetching can significantly improve
the effectiveness of file-level prefetching, by
reducing execution times by 20%-53% for both

Griffioen, J., & Appleton, R. (1994). Reducing
file system latency using a predictive approach.
Proceedings of the USENIX Summer Conference,
June 1994, pp. 197-208.

Kroeger, T. M., & Long, D. D. E. (2001). Design
and implementation of a predictive file prefetch-
ing algorithm. Proceedings of the 2001 USENIX
Annual Technical Conference, January 2001.

Li, Z., Chen, Z., Srinivasan, S., & Zhou, Y. (2004).
C-Miner: Mining Block Correlations in Storage
Systems. Proceedings of 3rd USENIX Confer-
ence on File and Storage Technologies (FAST04),
March 2004.

Pai, R., Pulavarty, B., & Cao, M. (2004). Linux
2.6 Performance Improvement through Readahead
Optimization. Proceedings of the Linux Sympo-
sium, July 2004.

Papathanasiou, A. E., & Scott, M. L. (2005). Ag-
gressive Prefetching: An Idea Whose Time Has
Come. Proceedings of the Tenth Workshop on Hot
Topics in Operating Systems, June 2005.

Schindler, J., & Ganger, G. R. (2000). Automated
Disk Drive Characterization. Proceeding of 2000
ACM SIGMETRICS Conference, June 2000.