Information Technology Reference
In-Depth Information
the order of incoming requests to the hard disk.
In specific,
sequential
disk accesses are much
more efficient than
random
disk accesses, often
in orders of magnitude. The reason is that, when
sequentially accessing disk data that are continu-
ously located on the disk track, only one disk head
movement (seek and rotation) is needed to read
a large amount of data. In contrast, randomly ac-
cessing disk data that are dispersed over the disk
platters, each data access requires a costly disk
seek and/or rotation, which is extremely ineffi-
cient. In order to optimize disk performance, many
research works have been done to organize
large
and
sequential
disk accesses, and
prefetching
is
an important technique to achieve this objective.
In this chapter, we will present an efficient disk-
level prefetch scheme, called DiskSeen, which
can effectively improve the disk performance by
creating large and sequential disk accesses.
The effectiveness of prefetch policies is de-
termined by two factors, accurate prediction on
future data accesses and actual time cost of indi-
vidual accesses. Many previous research works
are focused on improving the accuracy of predic-
tion on data accesses (e.g. Li, Chen, Srinivasan,
& Zhou, 2004). However, two factors make the
later factor increasingly more important. First,
the hard disk is a non-uniform-access device,
as described previously. Since sequential data
accesses without disk head movement is at least
one order of magnitude faster than random data
accesses, prefetching data blocks in a random pat-
tern would be much less efficient than prefetching
data blocks in a sequential pattern. Accordingly,
the penalty of mis-prefetching for sequential data
accesses is much lower than that for random ac-
cesses. Second, as the processors are becoming
increasingly more powerful, computation during
an application's execution would account for a
decreasing percentage. In other words, applica-
tions are becoming increasingly I/O bound, and
less opportunity would be left to hide long disk
access latency behind computations. As a result,
the importance of efficient sequential prefetching
is more pronouncing relative to that of prefetching
randomly located data blocks.
It's also worth pointing out here, although
many sophisticated prefetching algorithms have
been proposed (e.g. Griffioen & Appleton, 1994;
Kroeger & Long, 2001), general-purpose operat-
ing systems only provide sequential prefetch-
ing, which predicts and prefetches sequentially
accessed data blocks, or similar variants. This
design is a rational choice in practical systems,
due to two reasons. First, extra overhead may be
introduced in these complicated prefetch policies,
and potential implementation difficulty has to be
avoided in practice. Imposing excessive overhead
in a general system is undesirable. Second, the
relative penalties for incorrectly prefetching a
sequential block are much lower, compared to
prefetching a random block, which involves more
disk I/O. In this chapter, the prefetch policies are
bacKground
prefetching
Prefetching, speculatively reading data from the
hard disk by predicting future requests, is an
effective technique to improve overall system
performance. This is due to two reasons. First,
since the execution of an application is usually
interleaved by
computation
and
data access
, by
performing disk accesses in parallel with computa-
tion, the high disk access latency can be effectively
hidden behind computations. Second, prefetch-
ing usually attempts to organize large sequential
data accesses on the hard disk, thus each time a
large number of data blocks can be read into the
memory with only one disk access. As a result,
the long disk head seek and rotation latency can
be amortized over a large amount of data blocks,
and the average access cost per block is reduced.
As a critical optimization technique, prefetching is
widely adopted in most existing operating systems
as a standard component.
Search WWH ::
Custom Search