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

Figure 3. Architecture of DiskSeen.

predictions made by the file-level prefetcher based
on its knowledge of the deep access history. To
this end, the requests from file-level prefetchers
are dispatched to DiskSeen, instead of directly
to the disk drive, and DiskSeen decides how to
handle these requests. On-demand requests are
forwarded directly to disk driver by DiskSeen. We
refer to disk requests from `above' DiskSeen (e.g.,
application or file-level prefetchers) as high-level
requests and the data blocks requested by file-level
prefetcher as prefetch candidates .

status, such as resident bit. With a block size of
4K Bytes, the 31-bit access index can distinguish
accesses to 8 TBytes of disk data.
As time elapses, the counter approaches to
its maximum value. To handle this situation,
when the range for used access index exceeds
7/8 of the maximum index range, we remove the
indices whose values are in the first half of the
used range in the block table, such that the values
can be gradually updated. This progressive index
clearing takes place very infrequently and incurs
minimal overhead in practice.

recording access indices

coordinating with file-
level prefetching

As mentioned previously, DiskSeen uses the
block access indices as virtual access times. Block
access indices are read from a counter that incre-
ments whenever a block is read into the caching
area on demand. When a request is completed,
either via a hit in the prefetching area or via the
completion of a disk I/O operation, the current
reading of the counter, the access index , is used
as the access time of the block to be recorded in
the corresponding BTE in the block table. Each
BTE holds the most recent access indices, to a
maximum of four. In our prototype, the size of a
BTE is 128 bits. Each access index takes 31 bits
and the other 4 bits are used to indicate block

As mentioned previously, traditional file-level
prefetching may perform ineffectively due to lack
of low-level knowledge. By tracking the actual
use of blocks prefetched by file-level prefetcher,
DiskSeen can measure the effectiveness of high-
level prefetchers and correct inaccurate prefetch-
ing decisions.
When a prefetch candidate block is read into
the prefetching area, we set the status of the block
as prefetched in its BTE. This status bit is unset
only when an on-demand access of the block
occurs. When the file-level prefetcher requests