最適ページ置換アルゴリズム

最適ページ置換アルゴリズム
R : ページ(自然数)の集合
 a : ページの列
 定義1: PFA(R, a) : アルゴリズムAで，初期
集合Rからアクセス系列aを実行したときに
発生するページ置換の数
 定義2: LP(S, a) :要素がSの元であるaの接
頭辞(prefix)で最長のものの長さ

命題

PFOPT(R1, a)  PFA(R2, a) + LP(R2 – R1, a)
R1

R2
これが証明されればR1 = R2として，
PFOPT (R, a)  PFA(R, a)
を得る
場合わけ

最初のアクセスによって場合わけ
a1
R1
R2
a1
a1
a1
Case a1  R1  R2





PFOPT(R1, a) = PFOPT(R’1, a’)
PFA(R2, a) = PFA(R’2, a’)
LP(R2 – R1, a) = LP(R’2 – R’1, a’)
帰納法の仮定
• PFOPT(R’1, a’)  PFA(R’2, a’) + LP(R’2 – R’1, a’)
PFOPT(R1, a)
= PFOPT(R’1, a’)
R1
 PFA(R’2, a’) + LP(R’2 – R’1, a’)
 PFA(R2, a) + LP(R2 – R1, a)
a1
R2
Case a1  R1 – R2

Page outされたページをyとする
• R1’ = R1
• R2’ = R2 + { a1 } – { y }
 R2’ – R1’ = R2 – R1 + { a1 } – { y }
R1
R2
a1
R1
R2
a1
y
Case a1  R1 – R2





PFOPT(R1, a) = PFOPT(R’1, a’)
PFA(R2, a) = PFA(R’2, a’) + 1
LP(R2 – R1, a)  LP(R’2 – R’1, a’)
帰納法の仮定
• PFOPT(R’1, a’)  PFA(R’2, a’) + LP(R’2 – R’1, a’)
PFOPT(R1, a)
R1
= PFOPT(R’1, a’)
a1
 PFA(R’2, a’) + LP(R’2 – R’1, a’)
 PFA(R2, a) – 1 + LP(R2 – R1, a)
 PFA(R2, a) + LP(R2 – R1, a)
R2
Case a1  R2 – R1

Page outされたページをxとする
• R1’ = R1 + { a1 } – { x }
• R2’ = R2
 R2’ – R1’ = R2 – R1 – { a1 } + { x }
R1
R2
a1
R1
R2
x
a1

以下の二つは容易
• PFOPT(R1, a) = PFOPT(R’1, a’) + 1
• PFA(R2, a) = PFA(R’2, a’)

中心命題
• LP(R2 – R1, a) = LP(R’2 – R’1, a’) + 1
LP(R2 – R1, a) = LP(R’2 – R’1, a’) + 1
…
a1
 R2 – R1, とくに R1
これがxでないことをいえばよい

実際，
 R1で，xはa中最も出現の遅いR1の元である．





PFOPT(R1, a) = PFOPT(R’1, a’) + 1
PFA(R2, a) = PFA(R’2, a’)
LP(R2 – R1, a) = LP(R’2 – R’1, a’) + 1
以上より，
PFOPT(R1, a)
= PFOPT(R’1, a’) + 1
 (PFA(R’2, a’) + LP(R’2 – R’1, a’)) + 1
= PFA(R2, a) + LP(R2 – R1, a)
Case a1  R1, a1  R2

Page outされたページをx, yとする
• R1’ = R1 + { a1 } – { x }
• R2’ = R2 + { a1 } – { y }
• x  R2 : R2’ – R1’ = R2 – R1 – { y } + { x }
a1
R1
R2
x
y



PFOPT(R1, a) = PFOPT(R’1, a’) + 1
PFA(R2, a) = PFA(R’2, a’) + 1
LP(R2 – R1, a)  LP(R’2 – R’1, a’)
• 証明は前のcaseと同様．ただしa1 R2 なので，右辺の + 1 がない


帰納法の仮定
• PFOPT(R’1, a’)  PFA(R’2, a’) + LP(R’2 – R’1, a’)
PFOPT(R1, a)
= PFOPT(R’1, a’) + 1
 PFA(R’2, a’) + LP(R’2 – R’1, a’) + 1
 PFA(R2, a) – 1 + LP(R2 – R1, a) + 1
= PFA(R2, a) + LP(R2 – R1, a)

Download Report