Information Technology Reference
In-Depth Information
base pages. “Recency” algorithms cannot notice
this difference; therefore LRU will not be a good
choice in cases where just a small number of base
pages are indeed important. ARC, however, takes
into account the “frequency”; thus ARC can be a
better choice for these cases.
the decision for preempting reservation of a
super-page candidate or swapping out its base-
pages is taken based on the super-page “recency”
in the page lists and not based on the number of
currently resident base-pages that the super-page
consists of. This is actually a known technique of
information filtering in order to achieve a better
decision (Wang, 2008).
Hardware maintains only a single reference
bit; thus it is difficult to decide whether all (or at
least most) of the base-pages that the super-page
consists of are actually in use. Sometimes, only
a small percentage of the base pages should be in
the memory. Therefore,AMSQM manages several
queues for each super-page size, preventing from
cold super-pages to be retained in the cache oc-
cupying the space of some potential hotter smaller
super-pages or base pages.
Finally, in order to wisely balance the different
queues length, the algorithm counts the number
of times that each page has been referenced and
checks the relative “recency” of each super-page's
queue.
Similarly to ARC, AMSQM has B and T lists,
but AMSQM has T and B list for each super-page
size that is denoted as Ti1, Ti2, Bi1 and Bi2 where
i is the super-page size. Therefore, the pseudo-code
briefly should be:
gathering the accesses
When the size of page is small, an access to a
specific location by the readings/writings is not
significant. However, one can think that a gather
can imply an important page, while scattered
readings/writings will mean arbitrary accesses.
However, practically this assumption is not proved
as correct.
the amSqm page
replacement algorithm
The ARC page replacement algorithm has been
utilized to develop a new algorithm - Adaptive
Multiple Super-Pages Queues Management
(AMSQM) (Itshak and Wiseman, 2008) which is
an expansion of the ARC algorithm that supports
Super-Paging. AMSQM algorithm has two levels
- the high level manages the different Super-Page
queues (sizes and allocations); whereas the low
level is the internal management of each Super-
Page's queue. In addition, there is a special buffer
for each Super-Page size that collects fractions of
bigger Super-Pages. The purpose of these buf-
fers is in case of demotion, giving the demoted
Super-Pages a chance to get a better priority if
they are hot pages.
The suggested algorithm uses a reservation-
based scheme, in which region is reserved for a
super-page at the page fault time and the promotion
is done when the number of the super-page's popu-
lated base pages gets to a promotion threshold.
Since we would like a partially populated super-
page to have the opportunity of being promoted,
Find the super-page that contains the re-
quested page.
If the page is in Ti1 or Ti2, the size of lists
is good and no need to change it.
If the page is in Bi1, the size of Li1 should
be increased.
If the page is in Bi2, the size of Li2 should
be increased.
If the page is not in the memory, the size of
lists is good and no need to change it.
The detailed AMSQM algorithm in pseudo-
code is written herein below:
Let us define:
Search WWH ::




Custom Search