Information Technology Reference
In-Depth Information
C- The memory size.
ci - Physical size of the super (and base) pages
buffers. Σ ci≤ C.
si - Target size of each buffer.
Qi- Queue (FCFS) that saves demoted Super-
Pages (or base-pages), which are a fraction
of bigger Super-pages.
Ti1 - The most recent pages in the memory of
every Super (or base) page, which were ac-
cessed only once.
Bi1 - The most recent pages in the history of ev-
ery Super (or base) page, which were ac-
cessed only once.
Ti2 - The most recent pages in the memory of
every Super (or base) page, which were ac-
cessed more than once.
Bi2 - The most recent pages in the history of ev-
ery Super (or base page), which were ac-
cessed more than once.
Pi - Tunable parameter - the recommended size
of Ti1.
sizei - Super-Page size in base pages.
boundi=β·sizei/size1
count(x) - The number of times that Super-Page
x was referenced.
ranki - Determines which queue removes an
entry. ranki=α⋅difi+(1-α)⋅reci, where difi
is the difference between si and ci; i. e.
max(0, sizei·(ci-si)) and reci is the relative
recency of the LRU of Super-Page i among
the LRU of the other Super-Pages.
threshold - threshold for promoting a partially
occupied (candidate) super-page to a fully
occupied super-page.
SP(xj) - The superpage which the base page xj
belongs to. xj =SP(xj) iff xj does not belong
to any super-page (a solitary base page).
ω(x) - The number of occupied base pages in
super-page x.
α,β,γ - Parameters that should be set according
to the data characteristic; where 0≤α≤1,
β≥1 and 0≤γ≤½.
The algorithm AMSQM is:
AMSQM
(c, Stream of base pages requests:
x
1
,x
2
,..,x
n
)
•
c
1
=
c
2
=...=
c
k
=0
For each x
•
j
◦
Call
HandleSuperPage
(
x
j
,|
SP(x
j
)|
)
◦
If ω(
SP(x
j
)
)≥
threshold·size
|SP(xj)|
Promote
◦
SP(x
j
)
if the access type is “write”, recursively
•
demote
SP(x
j
)
to clean base/super pages
and move them to the suitable Q lists.
HandleSuperPage
(
x
j
,i)
If
•
SP(x
j
)
is in T
i
1
,
If x
◦
j
is valid
Move
▪
SP(x
j
)
to be the MRU of
T
i
2
◦
Else
▪
Fetch x
j
to the cache.
▪
Move
SP(x
j
)
to be the MRU of
T
i
1
If (count(
◦
SP(x
j
)
)=
bound
i
)
count(
▪
SP(x
j
)
)=γ·
bound
i
◦
Else
▪
count(
SP(x
j
)
)= count(
SP(x
j
)
)+1
•
If
SP(x
j
)
is in T
i
2
or
Q
i
If x
◦
j
is invalid
Fetch x
▪
j
to the cache.
◦
Move
SP(x
j
)
to be the MRU of T
i
2
◦
count(
SP(x
j
)
)= count(
SP(x
j
)
)+1
•
If
SP(x
j
)
is in B
i
1
If the size of B
◦
i
1
is at least the size
of B
i
2
δ=1
▪
Else
◦
▪
δ=|B
i
2
|/|B
i
1
|
◦
P
i
=min(
P
i
+δ,
c
i
)
Call
◦
Release
(
x
j
,i)
Fetch x
◦
j
to the cache.
◦
Move
SP(x
j
)
to be the MRU of T
i
2
◦
count(
SP(x
j
)
)= count(
SP(x
j
)
)+1
•
If
SP(x
j
)
is in B
i
2
If the size of B
◦
i
2
is at least the size of B
i
1
Search WWH ::
Custom Search