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

number of blocks cannot effectively amortize a
disk head repositioning cost and so is inefficient.
If 2f > max , the prefetching window size is set
as max . This is because too aggressive prefetch-
ing imposes a high risk of mis-prefetching and
increases memory pressure on the prefetching
area. In our prototype, min is 8 blocks and max
is 32 blocks, which is also the default maximum
prefetch window size in Linux. In this way, we
can gradually increase the aggressiveness of
prefetching, if previously prefetched data blocks
are being accessed by on-demand requests, and
quickly reduce the aggressiveness of prefetching,
if otherwise.
Also note that the actual number of blocks
that are read into memory can be less than the
specified prefetch size, because blocks that are
already resident in memory are excluded from
prefetching. If many blocks in the prefetch scope
are already resident in memory, the window size
turns small, which in turn slows down or even
stops the prefetching.

and the reclamation queue. When a block reaches
the head of the reclamation queue, it is evicted
from memory. When a block is requested by an
on-demand request, it is moved to the caching
area.

history-aware prefetching

Sequence-based prefetching is based on currently
observed disk accesses and only works for se-
quential disk accesses. By exploiting deep history
information of disk accesses in the block table, we
can further conduct more comprehensive prefetch-
ing for disk accesses. In this section, we present
a history-aware prefetching for non-sequential
disk accesses.

Disk Access Trails

The basic idea of history-aware prefetching is to
match the current disk access sequence with the
history access sequence, if a match is found, we
can use the history accesses to predict the data
blocks to be accessed in the future. To this end,
we first present a data structure to describe the
access history.
We use trail to describe a sequence of blocks
that have been accessed with a small time gap
between each pair of adjacent blocks in the se-
quence and are located in a small region on disk.
Suppose blocks ( B 1 , B 2 , …, B n ) are a trail, where
0 < access_index ( B i ) - access_index ( B i-1 ) < T ,
and | LBN ( B i ) - LBN ( B 1 ) |< S , ( i = 2 , 3 , …, n ),
where T is the access index gap threshold. T is
the same as the one used in the sequence detec-
tion for the sequence-based prefetching. Each
data block maintains up to four access indices in
the corresponding BTE entry. Any access index
can be used to satisfy the given condition. This
means that, in a trail ( B 1 , B 2 , …, B n ) and B 1 is the
start block, all of the following blocks must be
on either side of B 1 within distance S , and any
two consecutive blocks must have an access in-

Managing Prefetched Blocks

For file-level prefetch policies, the data structure
for managing prefetched blocks is naturally affili-
ated to logic files. In the DiskSeen scheme, which
views the whole storage space as a single sequence
of blocks, each on-going prefetch is represented us-
ing a data structure called the prefetch stream . The
prefetch stream is a pseudo-FIFO queue, and the
prefetched blocks in the two windows are placed
in the order of their LBNs. In DiskSeen, multiple
prefetch streams may exist concurrently.
In order to manage blocks in the prefetching
area, we also maintain a global FIFO queue called
the reclamation queue . The length of reclamation
queue is determined by the size of prefetching
area. All prefetched blocks, which may belong to
various prefetch streams, are placed at the queue
tail in the order of their arrival. Thus, blocks in the
prefetch windows stay in both prefetch streams