Sequential File Prefetching in Linux - Advanced Operating Systems and Kernel Applications - page 218

Chapter 11
Sequential File
Prefetching in Linux

Fengguang Wu
Intel Corporation, China

abStract

Sequential prefetching is a well established technique for improving I/O performance. As Linux runs
an increasing variety of workloads, its in-kernel prefetching algorithm has been challenged by many
unexpected and subtle problems; As computer hardware evolves, the design goals should also be
adapted. To meet the new challenges and demands, a prefetching algorithm that is aggressive yet safe,
flexible yet simple, scalable yet efficient is desired. In this chapter, the author explores the principles of
I/O prefetching and present a demand readahead algorithm for Linux. He demonstrates how it handles
common readahead issues by a host of case studies. Both static, logic and dynamic behaviors of the
readahead algorithm are covered, so as to help readers building both theoretical and practical views
of sequential prefetching.

introduction

prefetching: to bring in data blocks for the upcom-
ing requests, and do so in large chunks.
The Linux kernel does sequential file prefetching
in a generic readahead framework that dates back
to 2002. It actively intercepts file read requests in
the VFS layer and transforms the sequential ones
into large and asynchronous readahead requests.
This seemingly simple task turns out to be rather
tricky in practice (Pai, Pulavarty, and Cao, 2004;
Wu, Xi, Li, and Zou, 2007). The wide deployment
of Linux --- from embedded devices to supercom-

Sequential prefetching, also known as readahead
in Linux, is a widely deployed technique to bridge
the huge gap between the characteristics of storage
devices and their inefficient ways of usage by ap-
plications. At one end, disk drives and disk arrays
are better utilized by large accesses. At the other,
applications tend to do lots of tiny sequential reads.
To make the two ends meet, operating systems do