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

H values. Note that all these sequences share the
same current L value in their H value calcula-
tions. With a merge sorting of the newly ordered
sequence list and the ordered sequence list in the
eviction section, we complete the refilling of the
eviction section, and the staging section ends up
with only the correlation buffer.

promoted into the active list when it is accessed
as a file page, or it is accessed as a process page
and its reference is detected at the inactive list tail.
An active page is demoted to the inactive list if it
is determined to have not been recently accessed.
Linux uses an adaptive method to refill inactive
list with pages picked from active list. When the
page reclaiming at the tail of the inactive list
becomes difficult, more pages are picked from
active list to inactive list. performance reSultS

Implementation Issues To demonstrate the performance improvements

of DULO on a modern operating system, we
implement it in the recent Linux kernel 2.6.11.
To exhibit the impact of introducing spatial lo-
cality into replacement decisions under different
circumstances, we run two types of applications,
whose I/O operations are mostly file accesses
and VM paging respectively. As file system
fragmentation may have substantial impact on
system performance, we also test DULO on an
aged file system.

In our prototype implementation of DULO, we do
not replace the original Linux page frame reclaim-
ing code with a faithful DULO scheme imple-
mentation. Instead, we opt to keep the existing
data structure and policies mostly unchanged, and
seamlessly adapt DULO into them. We make this
choice, which has to tolerate some compromises
of the original DULO design, to serve the pur-
pose of demonstrating what improvements a dual
locality consideration could bring to an existing
spatial-locality-unaware system without changing
its basic underlying replacement policy.
In Linux, we partition the inactive list into a
staging section and an eviction section because the
list is the place where new blocks are added and
old blocks are replaced. To keep DULO effective
and make it cooperate well with existing policies
in Linux, both staging section and eviction sec-
tion need to have reasonable lengths, which are
now limited by inactive list. The length of evic-
tion section presents DULO's ability to control
the eviction order of the pages. The longer the
eviction is, the more power DULO has to protect
the high-cost random blocks from being evicted.
Different with other LRU variants, where newly
fetched pages enter the head of the only list, inac-
tive list provides a shorter evaluation period for
newly fetched pages, during which frequently
referenced ones are re-visited and promoted to
active list and unfrequently referenced ones are
evicted.

the dulo implementation

As many other Unix variants, Linux uses an LRU
variant as its replacement policy, which brings up
some implementation issues. So let's start with
a brief description of the implementation of the
Linux replacement policy.

Linux Caching

Linux adopts an LRU variant similar to the 2Q
replacement (Johnson el al. 1994). The Linux 2.6
kernel groups all the process pages and file pages
into two LRU lists called the active list and the
inactive list . As their names indicate, the active
list is used to store recently actively accessed
pages, and the inactive list is used to store those
pages that have not been accessed for some time.
A faulted-in page is placed at the head of the inac-
tive list. The replacement page is always selected
at the tail of the inactive list. An inactive page is