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

Figure 2. The structure of block bable with three levels (BGD, BMD, and BTE)

overview

that entry. Purging the table of old blocks involves
removing all blocks with access indices smaller
than some given index. This operation entails tra-
versing the table, top level first, identifying access
indices smaller than the given index, removing
the corresponding sub-trees, and reclaiming the
memory. Since such an operation is only needed to
be performed occasionally, the incurred overhead
is very small.

In DiskSeen, the buffer cache (main memory)
is divided into two areas, prefetching and cach-
ing areas. The caching area corresponds to the
traditional buffer cache and it is managed by
the existing OS kernel policies (e.g. the 2Q al-
gorithm in Linux). The prefetching area is used
to maintain prefetched data blocks in DiskSeen.
A block could be prefetched into the prefetching
area based on access information recorded in the
block table, or as directed by file-level prefetch-
ing. If a block resident in the prefetching area is
accessed by an on-demand request, it is moved
into the caching area. DiskSeen distinguishes on-
demand requests from file-level prefetch requests
and makes prefetch decision based on on-demand
accesses, because only on-demand requests reflect
applications' actual access patterns.
In DiskSeen, file-level prefetching is still en-
abled. However, the low level prefetching is con-
ducted concurrently to mitigate the inadequacies of
file-level prefetching. DiskSeen generally respects
the decisions made by a file-level prefetcher, but
it also attempts to identify and correct inaccurate

the deSign of diSKSeen

As a disk-level prefetch policy, DiskSeen sits
between the file system and the disk drive. Disk-
Seen intercepts the requests issued from upper-
level components, tracks the disk access history,
and maintains the information in the block table.
By analyzing the history access information,
DiskSeen identifies the relationship between data
blocks and predicts the blocks to be accessed
in the future. Finally, DiskSeen prefetches data
blocks into memory to achieve performance
improvement.