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

a prefetch candidate that is not yet resident in
memory, DiskSeen checks its prefetched status
bit, if it is set, DiskSeen would drop the prefetch
request, because this block has been previously
prefetched by the file-level prefetcher but not
been accessed by any on-demand request, which
suggests an inaccurate prefetch decision. In this
way, DiskSeen can identify and correct some of
the mis-prefetchings made by file-level prefetch
policies.
In order to coordinate multiple requests for the
same block, we designate a resident bit and a busy
bit in each BTE. When a block enters buffer cache,
the resident bit is set to 1, and it is reset to 0 when
it leaves the cache. Before a request is sent to the
disk scheduler, we check the blocks demanded
in the request against the corresponding BTEs to
determine whether the blocks are already in the
prefetching area. If true, which means the blocks
are hit in the prefetching area, we move them to
the caching area. The busy bit in each BTE serves
as a lock to coordinate simultaneous requests for
a particular block. A set busy bit indicates that a
disk service on the corresponding block is under
way, and succeeding requests for the block must
wait on the lock. In this way, we can avoid the
consistence problem caused by the situation that
multiple I/O requests are issued to the disk drive
for the same data block.

where K is set 8. The sequence detection is con-
ducted based on the current access information
maintained in the block table. For a block in a
high-level request, we examine the most recent
access indices of blocks physically preceding
the block to see whether it is the K th block in a
sequence. For example, for a block with LBN N ,
we will examine the blocks with LBNs of N-1 ,
N-2 , …, etc. Compared to disk service time, this
back-tracking operation in the block table is an ef-
ficient operation. Since accesses of a sequence can
be interleaved with accesses in other sequences,
the most recent access indices of the blocks in
the sequence are not necessarily consecutive. We
only require that access indices of the blocks be
monotonically decreasing during back-tracking.
However, if a very large gap of the access indices
exists between two contiguous blocks, it indicates
that one of the two blocks might not be accessed
before being evicted from the prefetching area,
if they were prefetched together as a sequence.
Thus these two blocks should not belong to the
same sequence. The access index gap threshold,
T , is set as 1/64 of the size of the system memory,
measured in blocks.

Sequence-Based Prefetching

Once we detect a sequence, we create two win-
dows, called the current window and the reada-
head window , whose initial sizes are set 8 blocks.
We prefetch 8 blocks immediately ahead of the
sequence into the current window, and the fol-
lowing 8 blocks into the readahead window. We
then track the number f of blocks that are hit in
the current window by high-level requests, and f
serves as a feedback to determine the prefetching
aggressiveness. When the blocks in the readahead
window start to be requested, a new readahead
window is created with size of 2f , and the exist-
ing readahead window becomes the new current
window. We set minimal and maximum window
sizes, min and max , respectively. If 2f < min , the
prefetching is stopped, because requesting a small

Sequence-based prefetching

Based on the data access history recorded in the
block table, DiskSeen identifies sequential data
accesses at disk level and prefetches data blocks
by predicting the data blocks to be accessed in
advance. The sequence detection and prefetching
in DiskSeen is similar in principle to that used by
the file-level prefetchers in Linux.

Sequence Detection

In DiskSeen, prefetching is activated when
accesses of K contiguous blocks are detected,