ページ置換とページフォルト
同じ参照列をFIFOとLRUで処理し、容量・参照順・変更済みページがI/Oを増やす条件を調べます。
説明
必要なページがメモリにないとき、OSはページを準備してから命令を再開します。空きフレームが足りなければ、今あるページの一部を追い出します。どのページを選ぶかで、その後のページフォルト回数が変わります。
小さな参照列でFIFOとLRUを比較し、容量を増やした場合も計算します。次に変更済みページの書戻し、作業に必要なページ数と容量の関係、ディスク読込みが平均時間へ与える影響を確かめます。初期状態は空で、最初の比較ではすべてディスクに保存済みのページを使います。
1参照列と空のメモリ
ページ1〜5を決められた順序で参照します。最初はメモリに何も入っていないので、初回参照には読込みが必要です。
sequence = [1,2,3,4,1,2,5,1,2,3,4,5]ページ参照列; print(sequence)条件を表示同じページを何度も参照する列です。参照回数12と、異なるページ数5を分けて考えます。メモリに残っているページなら次の参照はヒットになります。
2FIFOとLRUの置換規則
リストの左を追出し候補にします。FIFOは読込み時に末尾へ追加し、LRUはヒットしたページも末尾へ移します。missのときだけフォルト数を増やします。
def replace(seq, capacity, policy):置換の計算
frames = []; faults = 0; rows = []空のメモリと記録
for page in seq:順に参照
hit = page in frames常駐しているか
if not hit:フォルト時
faults += 1フォルト数を加算
if len(frames)==capacity: frames.pop(0)満杯なら左端を追出し
frames.append(page)新しいページを追加
elif policy=='LRU': frames.remove(page); frames.append(page)LRUではヒットでも更新
rows.append((page,'hit' if hit else 'miss',tuple(frames)))参照直後の状態
return faults,rows回数と履歴FIFOは最も前に読み込んだページ、LRUは最後に使ってから最も時間のたったページを選びます。この関数は参照履歴を正確に保持するモデルであり、実OSがそのままこのリストを使うという意味ではありません。
33フレームのFIFOを全件表示
容量3でFIFOを実行し、各参照後にどのページが残るか表示します。
faults,rows = replace(sequence,3,'FIFO')容量3のFIFO; print(*rows,sep='\n')各参照後の常駐ページ; print('faults',faults)フォルト総数フォルトは9回です。最初の1・2・3を読んだ後に4が来ると1を追い出します。次に必要な1をまた読み込むため、単に異なるページの数5を数えるだけでは読込み回数を求められません。
4容量を増やしたFIFOとLRU
容量3・4のそれぞれでFIFOとLRUを計算します。初期状態と参照列は同じです。
for policy in ('FIFO','LRU'):二つの規則
print(policy,[replace(sequence,size,policy)[0] for size in (3,4)])容量別の回数FIFOは9回から10回へ増え、LRUは10回から8回へ減ります。FIFOでは容量の増加で追出し順が変わり、かえってフォルトが増える参照列があります。この例はFIFOのBeladyの異常を示しており、常に容量を増やすと悪化するという意味ではありません。
5変更済みページを追い出す場合
ページ1を書き換えた後、容量2のメモリへページ2、3を順に読みます。FIFOの先頭1を追い出す際、変更済みかを調べます。
frames = [1,2]; dirty = {1}常駐ページと変更済み集合; victim = frames.pop(0)FIFOの追出し対象; writeback = victim in dirty書戻しが必要か; frames.append(3)新しいページを配置; print(victim,writeback,frames)追出しと新状態ページ1が追出し対象で、書戻しが必要です。変更前の内容が保存先にあっても、最新の内容を失わないため保存が必要になります。未変更のファイルページは元ファイルから再読込みできるため、そのまま捨てられる場合があります。
6作業に必要なページが容量を超える
1・2・3・4を繰り返す作業を、3フレームと4フレームで比較します。
working = [1,2,3,4]*3反復する作業集合; print([replace(working,n,'LRU')[0] for n in (3,4)])容量不足と収まる場合容量3では12回すべてフォルト、容量4では最初の4回だけです。繰り返し使う4ページを保持できないと、読み込んだページを次々に追い出す状態になります。ページ入替えに時間を取られて処理が進みにくい現象がスラッシングです。
7少数のページフォルトが平均アクセス時間に与える影響
通常アクセス100 ns、ディスク読込みの追加時間5 msとします。フォルト率を100万回に1回と、1000回に1回で比べます。
memory_ns = 100; disk_ns = 5_000_000時間の単位をそろえる; print([memory_ns+p*disk_ns for p in (0.000001,0.001)])フォルト率別の平均平均は105 nsと5100 nsです。後者は通常アクセスの51倍です。ここではフォルトごとに5 msを追加する条件で、待ちの重なりやバックグラウンド読込みは含めていません。単位をnsへそろえてから足しています。
8フォルト数とディスク読込み数
フォルトにはゼロ初期化やCOWなど、ディスクを読まない場合もあります。種別をまとめた記録からフォルト件数とディスク読込み件数を別々に数えます。
events = [('zero-fill',False),('file-read',True),('copy-on-write',False),('swap-in',True)]種別とディスク読込みの有無; print(len(events),sum(io for _,io in events))二つの件数を分けるフォルトは4件、ディスク読込みは2件です。最初の置換モデルでは全ミスをディスク読込みとして計算しましたが、実際の観測ではフォルトの種類や保存先、ページキャッシュの状態も確認する必要があります。
まとめ
ページ置換の回数は容量と参照順と規則で変わり、FIFOでは容量増加で悪化する場合もあります。
変更済みページの追出しは、読込みに加えて書戻しを必要とすることがあります。
ページフォルトのすべてがディスク読込みではないため、種類を分けて時間やI/O回数を評価します。
操作履歴と解説を振り返れます。
Python 3
sequence = [1,2,3,4,1,2,5,1,2,3,4,5]; print(sequence)[1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
def replace(seq, capacity, policy):
frames = []; faults = 0; rows = []
for page in seq:
hit = page in frames
if not hit:
faults += 1
if len(frames)==capacity: frames.pop(0)
frames.append(page)
elif policy=='LRU': frames.remove(page); frames.append(page)
rows.append((page,'hit' if hit else 'miss',tuple(frames)))
return faults,rowsfaults,rows = replace(sequence,3,'FIFO'); print(*rows,sep='\n'); print('faults',faults)(1, 'miss', (1,)) (2, 'miss', (1, 2)) (3, 'miss', (1, 2, 3)) (4, 'miss', (2, 3, 4)) (1, 'miss', (3, 4, 1)) (2, 'miss', (4, 1, 2)) (5, 'miss', (1, 2, 5)) (1, 'hit', (1, 2, 5)) (2, 'hit', (1, 2, 5)) (3, 'miss', (2, 5, 3)) (4, 'miss', (5, 3, 4)) (5, 'hit', (5, 3, 4)) faults 9
for policy in ('FIFO','LRU'):
print(policy,[replace(sequence,size,policy)[0] for size in (3,4)])FIFO [9, 10] LRU [10, 8]
frames = [1,2]; dirty = {1}; victim = frames.pop(0); writeback = victim in dirty; frames.append(3); print(victim,writeback,frames)1 True [2, 3]
working = [1,2,3,4]*3; print([replace(working,n,'LRU')[0] for n in (3,4)])[12, 4]
memory_ns = 100; disk_ns = 5_000_000; print([memory_ns+p*disk_ns for p in (0.000001,0.001)])[105.0, 5100.0]
events = [('zero-fill',False),('file-read',True),('copy-on-write',False),('swap-in',True)]; print(len(events),sum(io for _,io in events))4 2
演習完了