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

Figure 1. The LRU stack is structured for the
DULO replacement algorithm

bank is used to prepare a collection of blocks
to be sequenced, and its size ranges from 0 to a
maximum value, BANK_MAX .
Suppose in the beginning the staging section
of an LRU stack consists of only the correlation
buffer (the size of the sequencing bank is 0), and
the eviction section holds the rest of the stack.
When a block leaves the eviction section and a
block enters the correlation buffer at its top, the
bottom block of the correlation buffer enters the
sequencing bank. When there are BANK_MAX
blocks leaving the eviction section, the size of
sequencing bank is BANK_MAX. We refill the
eviction section by taking the blocks in the bank,
forming sequences out of them, and inserting
them into the eviction section in a desired order.
There are three reasons for us to maintain two
interacting sections and use the bank to conduct
sequence forming: (1) The newly admitted blocks
have a buffering area to be accumulated for
forming potential sequences. (2) The sequences
formed at the same time must share a common
recency, because their constituent blocks are from
the same block pool --- the sequencing bank in
the staging section. By restricting the bank size,
we make sure that the block recency will not be
excessively compromised for the sake of spatial
locality. (3) The blocks that are leaving the stack
are sorted in the eviction section for a replace-
ment order reflecting both their sequentiality and
their recency.

it would be fetched together next time when they
are read from disk. Specifically, a random block
is a sequence of size 1. (2) Sorting the sequences
in the LRU stack according to their recency
(temporal locality) and size (spatial locality), with
the objective that sequences of large recency and
size are placed close to the LRU stack bottom.
Because the recency of a sequence changes while
new sequences are being added, the order of the
sorted sequence should be adjusted dynamically
to reflect the change.

Structuring lru Stack

To facilitate the operations presented above,
DULO partitions the LRU stack into two sec-
tions (shown in Figure 1 as a vertically placed
queue). The top part is called staging section
used for admitting newly fetched blocks, and the
bottom part is called eviction section used for
storing sorted sequences to be evicted in their
orders. The staging section is again partitioned
into two segments. The first segment is called
correlation buffer , and the second segment is
called sequencing bank . Its role is to filter high
frequency references and to keep them from
entering the sequencing bank, so as to reduce the
consequential operational cost. The sequencing

block table: a data Structure
for dual locality

To complement the missing spatial locality in
traditional caching systems, we introduce a data
structure in the OS kernel called block table . The
block table is analogous in structure to the multi-
level page table used for process address transla-
tion. However there are clear differences between
them because they serve different purposes: (1)
The page table covers virtual address space of a
process in the unit of page and page address is an