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

Figure 4. An Example of Access Trails

dex gap smaller than T . We refer to the window
of 2S blocks, centered at the start block, as the
trail extent . Actually the sequence detected in the
sequence-based prefetching can be viewed as a
special trail in which all blocks are on the same
side of start block and have contiguous LBNs.
The limited window size, S , enforces to search
for a trail in a small area on disk, so that prefetch-
ing such a trail is efficient and the penalty for a
mis-prefetching would be small. In our prototype,
S is set 128. If a program accesses data over a
large area, multiple trails would be formed to
track each set of proximate accesses, rather than
forming an extended trail, to avoid expensive disk
head movements.Also note that the trail detection
brings low cost because, for a given access index
of one block in a trail, at most one access index of
its following block is likely to be within T . This
is because, due to the existence of buffer cache,
a block would not need to be reloaded from disk
until it is evicted from memory, which only hap-
pens after a large amount of other data blocks are
read from disk into memory. Thus, two consecutive
disk accesses to the same block would normally
have a large gap, in terms of access indices.
Figure 4 illustrates an example of access trails.
Access index threshold T is assumed to be 256.
There are four trails starting from block B 1 , one
current trail and three history trails. Trail 1 ( B 1 ,
B 3 , B 4 , B 5 ) corresponds to the on-going continuous
block accesses. Sequence-based prefetch would
not be activated because B 2 is skipped over. Trail 1

is overlapped with two history trails, Trails 2 and 3.
Note that Trail 4 runs in the reverse direction.

Matching Trails

Unlike sequence-based prefetching, which pre-
dicts sequential disk access based on current
on-going tail, history-aware prefetching predicts
disk accesses based on access history, which is
unnecessary to be strictly sequential. In DiskSeen,
when the sequence-based prefetching cannot de-
tect a pure sequence for activating prefetching,
history-aware prefetching can take advantage of
history information, if available, and prefetch
more accurately. The general idea is to use the
current trail to match history trails, so that we can
identify blocks for prefetching by following the
matched history trails.
When there is an on-demand access of a disk
block that is not in any current trail extent, we
start tracking a new trail from that block. In the
meantime, we examine the history trails consisting
of blocks visited by the current trail in the same
order. As shown in Figure 4, when the current
trail extends from B 1 (80000) to B 3 (80001), two
history trails are identified: Trail 2 ( B 1 (60000),
B 3 (60200)) and Trail 3 ( B 1 (40000), B 3 (40001)).
However, when Trail 1 extends to B5, only Trail
3 can match the current trail. In this way, we can
identify the repeated disk accesses by matching
the current trail with the history trails.