Application of both Temporal and Spatial Localities in the Management of Kernel Buffer Cache - Advanced Operating Systems and Kernel Applications - page 109

I/O requests directly from applications and has the
power to shape the requests into a desirable I/O
request stream, I/O scheduling and prefetching
only work on the request stream passed on from
the buffer cache and have very limited ability to
re-catch the opportunities lost in the buffer cache
management. Hence, in the worst case, a stream
filled with random accesses makes I/O scheduling
and prefetching largely ineffective, because no
spatial locality is left for them to exploit.
Concerned with the lack of ability to exploit
spatial locality in buffer cache management, the
solution to the deteriorating disk bottleneck is a
new buffer cache management scheme that ex-
ploits both temporal and spatial localities, which
is named as Du al LO cality scheme ( DULO ).
DULO introduces dual locality into the caching
component in an operating systems by tracking
and utilizing disk placements of in-memory pages
in its buffer cache management. The objective is
to maximize the sequentiality of I/O requests that
are serviced by disks. For this purpose, DULO
gives preference to random blocks for staying in
the cache, while sequential blocks that have their
temporal locality comparable to those random
blocks are replaced first. With the filtering effect
of the cache on I/O requests, DULO influences
the I/O requests made by applications so that more
sequential block requests and less random block
requests are passed to the disk thereafter. The disk
is then able to process the requests with stronger
spatial locality more efficiently.

compromise the weight of temporal locality in a
replacement decision, the role of temporal local-
ity must be appropriately retained in the decision.
For example, we may give randomly accessed
blocks more privilege of staying in cache due to
their weak spatial locality (weak sequentiality),
even though they have weak temporal locality
(large recency). However, we certainly cannot
keep them in cache forever if they do not have
sufficient re-accesses that indicate temporal local-
ity. Otherwise, they would pollute the cache with
inactive data and reduce the effective cache size.
The same consideration also applies to the block
sequences of different sizes. We prefer to keep a
short sequence because it only has a small number
of blocks to amortize the cost of an I/O operation.
However, how do we make a replacement decision
when we encounter a not-recently-accessed short
sequence and a recently-accessed long sequence?
The challenge is essentially how to make the
tradeoff between temporal locality (recency) and
spatial locality (sequence size) with the goal of
maximizing disk performance.

the dulo Scheme

We now present the DULO scheme to exploit both
temporal locality and spatial locality simultane-
ously and seamlessly. Because Least Recently
Used (LRU) or its variants are the most widely
used replacement algorithms, the DULO scheme
is designed by using the LRU algorithm and its
data structure --- the LRU stack, as a reference
point.
In LRU, newly fetched blocks enter into its
stack top and replaced blocks leave from its
stack bottom. There are two key operations in
the DULO scheme: (1) Forming sequences. A
sequence is defined as a number of blocks whose
disk locations are close to each other and have been
accessed sequentially in a series without interrup-
tion during a limited time period. Additionally, a
sequence is required to be stable so that blocks in

challengeS with
dual locality

Application of dual locality in the cache man-
agement raises challenges that do not exist in a
traditional system. In the current cache manage-
ments, replacement algorithms only consider
temporal locality (a position in a queue in the case
of LRU) to make a replacement decision. While
introduction of spatial locality necessarily has to