Information Technology Reference
In-Depth Information
will be swap out before a page with a smaller
“reuse distance”.
that according to their experiments 2Q gives an
improvement of 5-10% in hit ratio over LRU for
a wide variety of applications and buffer sizes
and never damaging. But these results were not
convincing enough.
Recently, N. Megiddo and S. Modha took
the 2Q algorithm and make the size of A1 and
Am adaptive. They proposed a new “online”
tunable algorithm called ARC (Stands for Adap-
tive Replacement Cache) (Megiddo and Modha,
2003a), (Megiddo and Modha, 2003b), (Megiddo
and Modha, 2004). The unique capability of this
algorithm is its ability to adapt itself “online”
according to the systems properties e.g. from
the Stack Depth Distribution (SDD) model to
the Independence Reference Model (IRM) and
vice versa.
The main concept of ARC is having two lists
of active pages (one for the frequently used pages
and one for the most recent pages) and to endow
the list that is performing the best with a larger
memory space. The two lists that ARC maintains
are variably-sized lists called L1 and L2. L1 con-
tains the pages that have been accessed only once
and L2 contains the pages that have been accessed
twice or more. The algorithm always holds that
0≤L1+L2≤2C, where C is the number of pages
in the memory. L1 consists of two buffers - T1
which consists of the most recent pages in the
memory and B1 which consists of the history of
the most recent pages that were in the memory.
Similarly L2 is partitioned into T2 and B2. In ad-
dition p which always holds p≤c, is the automatic
adaptive parameter of the algorithm which sets
the target size for T1.
The algorithm in a simplify version is for any
page request:
the arc page replacement
algorithm
We focused in the above section at CLOCK, be-
cause CLOCK dominates the Operating Systems
market; however some other methods seem to
suffer from two acute problems:
(i) The need for parameters tuning (e.g 2Q
(Johnson and Shasha, 1994)) and LRFU
(Lee at. Al, 2001)) and/or
(ii) Non-constant complexity (e.g. LRU-K
(O'Neil et al., 1993),
LRFU (Lee at. al, 2001),CLOCK (Corbato,
1968) and GCLOCK (Nicola et al., 1992)).
CLOCK also has a Non-constant complexity,
so we prefer to adapt more modern algorithm to
the Super-Paging environment.
(O'Neil at el., 1993) found in their experiments
that LRU-2 (LRU-K where K=2) achieves most
of the advantages of their method. This result
motivated Johnson and Shasha to develop 2Q
(Johnson and Shasha, 1994), an algorithm which
is similar in its performance to LRU-2, and still
works in a constant time. 2Q in its simplified
version has two buffers A1 and Am, where A1
is managed as a FIFO queue, whereas Am as a
regular LRU queue. At the first reference to a
page, 2Q places the page in A1 queue. If the page
is re-referenced while it is in A1, the algorithm
will assume it is probably a hot page. So, if a page
in A1 is referenced, it will be moved to the Am
queue, and if a page is not referenced while it is
in A1, it the algorithm will assume that the page
is probably a cold page and 2Q will remove the
page from the memory. 2Q's main disadvantage
is its offline property - 2Q requires two static
parameters tuning (Kin and Kout) before run-
ning. Tuning these parameters can be sometime
a very difficult task. Johnson and Shasha reported
•
If the requested page is in T
1
or in T
2
:
Move the page to the MRU of T
◦
2
.
•
If the requested page is in B
1
:
◦
If |B
1
|≥|B
2
|
δ
▪
1
=1
◦
Else
Search WWH ::
Custom Search