オペレーティングシステム 11 4.4 ページ置き換えアルゴリズム 4.5 ページ置き換えアルゴリズムのモデル化 前提 一度でも書き込みがあると修正 (modified,dirty) ビットを 1 にする リセットされない 参照されると参照ビットを 1 にする 定期的に 又はページフォルト時に OS への割込みが起こり 参照ビットは に戻される Operating System 216 4.4 Page Replacement Algorithms ページフォルトをするとページ選択を行う必要がある 取り除くページの選択 取込むページのスペース確保 変更されたページの保存 ディスクへ保存 変更がなければ ( 例えばプログラムコード ) 書き戻さないで良い 修正 (modified,dirty) ビットによる判断 利用頻度が高いページを追い出すと おそらくすぐにページが呼び戻されることになる それはオーバーヘッドになる ページ置き換えアルゴリズムの応用 キャッシュメモリ ウェブサーバー Operating System 216 2 4.4.1 Optimal page Replacement Algorithm ( 最適ページ置き換えアルゴリズム ) 最も遠い将来に参照されるページを追い出す 遠い は実行される命令個数 最適しかし実装不可能 擬似的な方法 一度実行してプロセスのページ参照の履歴を記録 これは非実用的であるが 他のアルゴリズムと最適解との比較の際に利用出来る Operating System 216 4
4.4.2 Not Recently Used Page Replacement Algorithm(NRU) 各ページは参照ビット R 修正ビット M を装備 ページが参照 (R) または修正 (M) されるとセットする R はクロック割込みごとにリセットする 最近の状況を記録 R M ビットに応じてクラス化 :OS が R M を初期設定 クラス : 参照も修正もされない クラス 1: 参照なし 修正あり クラス 2: 参照あり 修正なし クラス : 参照 修正あり 最下位のクラス ( クラス から ) からランダムにページを削除 頻繁に使用されるページより 最近参照されず 修正されないページを追い出す Operating System 216 5 4.4.4 Second Chance Page Replacement Algorithm ( セカンドチャンス置き換えアルゴリズム ) 頻繁に使用されるページを追い出さないように FIFO を修正 古いページのビット R を調べ R=1 ならクリアし そのページをページリストの最後尾に連結 メモリ内にロードされた時刻を現在時刻に更新する その後検索を続行 R= ならリプレース R=, M=1( ダーディ ) ならディスク書き出し R=1 なら R= にして最後尾に連結 このアルゴリズムは前回のクロックで参照されなかったページを探し追い出す もし 1 周すべてを探して全て R=1 の場合 A は R= なのでリプレースされる Operating System 216 7 4.4. First-In First-Out Algorithm ( 先入れ先出しページ置き換えアルゴリズム ) ページがロードされた順に並んでいるリスト ( キュー ) を用意し ページフォルトの際はキューの先頭 ( 一番古い ) から追い出す = 最初に置き換え対象となる 数字は来た時刻 最後尾から追加 Operating System 216 6 4.4.5 The Clock Page Replacement Algorithm ( クロックページ置き換えアルゴリズム ) セカンドチャンス置き換えアルゴリズムは 絶えずリスト上でページを移動させるので 非効率である クロック置き換えでは環状リストを用い ページフォルト発生時に最も古いページを調べる セカンドチャンスと考え方は同じだが リストの移動がない R= M= なら単に置き換え R= M=1( ダーディ ) ならディスク書出し 置き換え R=1 なら R= にして針を進める Operating System 216 8
4.4.6 Least Recently Used(LRU) ページ置き換えアルゴリズム 最近使用されないページは今後も使用されないと予想 最も長い間使用されなかったページを追い出す 全ページのリストを管理する必要がある ( 次ページ ) 先頭は最近使用したページ 末尾は最後に使用 考え方としては一番簡単だが メモリ参照の度にリスト更新が必要 Operating System 216 9 LRU ページ置き換えアルゴリズム 特殊なハードを用いて LRU を実現 1 命令実行毎に +1 されるカウンタ ( 時計と思うと良い ) メモリ参照時にカウンタの値をページテーブルエントリに保存 ページフォルト時に各ページエントリのカウンタ値を調べる 最も小さいカウンタ値 ( 最も古い ) のページを選択し リプレース 1 2 1A,B,C,D の順にアクセス C:5 C:5 C:9 2E をアクセス A 追い出し D:6 D:6 D:6 その場所に E を追加 A:2 E:7 E:7 C をアクセス 時刻更新 B:4 B:4 B:4 E:7 A:2 ( ページの後の数字が時刻 ) Operating System 216 11 途中から抜き取り出来るキューによる LRU ページがロードされた順に並んでいるリスト ( キュー ) を用意して アクセスが来た場合 : キューにない : キューの先頭 ( 一番古い ) のページを追い出す キューにある : キューから抜き取り 最後尾 ( 一番新しい ) に付ける 古い新しい A,B,C,D の順にアクセス A B C D E をアクセス A 追い出し 追い出し新規 B C D E C をアクセス 最後尾に B D E C Operating System 216 1 LRU ページ置き換えアルゴリズム 前頁とは違うハードウェアで実現 nxn ビット行列 : 1. k ページ参照で k 行をすべて 1( 青 ) k 列をすべて ( 茶 ) 2. 各行の 1 の数を調べ 最も小さい値の行が最も過去に参照されたページとなる 例 : ページ参照列 12212 -- と来て次に 4 が来た時にどのページを置換えるか 1 2 2 1 2 リプレース 1 2 Operating System 216 12
4.4.7 LRU のソフトウェアによるシミュレーション NFU アルゴリズムを修正すると LRU をソフトウェアでシミュレート出来る エージング 参照ビットはクロックティック ( 例 2msec) 毎にリセットされ 参照で 1 がセットされる 参照ビット R の加算の前にカウンタを右 1bit シフト ビット R をカウンタの最左端に加算最近参照されないページはカウンタの上位にゼロが並び値は小さい ( ページ リプレース ),2,4,5 ページが参照された,1,4 ページが参照された,1,,5 ページが参照された,4 ページが参照された 1,2 ページが参照された リプレース 1 教科書 Operating System 216 間違い 1 k の決定 このアルゴリズムを適用するには k の値を前もって決定しなければならない 近似による k の決定 : ワーキングセットの定義変更 最近 ある時間内に参照されたページのセット 回数 (k) 実行時間 ( プロセス毎の ) カレント仮想時間 : プロセスが開始後に実際に使用した CPU 時間 最終的なワーキングセットの定義 最近の τ 仮想時間に参照されたページのセット Operating System 216 15 4.4.8 ワーキングセットページ置き換えアルゴリズム プロセスが使用中のページセットを ワーキングセット と呼ぶ ワーキングセットのページを常にメモリに維持できれば 参照の局所性 ( 時間 場所 ) からページフォルトを削減出来る 逆にワーキングセットをメモリに持ちきれないと頻繁にページフォルトが発生する ( スラッシング ) ワーキングセットモデル はプロセスのワーキングセットを記録し 実行前のプリページング ( ページフォルトになる前に予めページを持って来る ) 実行中のページ置き換えに利用する方式である 時刻 t において 最近 k 回の参照で使用された全ページのセット w(k,t) が存在する w の k に対する漸近的挙動によりワーキングセットの内容は k に対して穏やかに変化するので プロセスの再開時に参照するページを推定できる つまり ページフォルトが発生すると そのプロセスのワーキングセットに属さないページを追い出す! w(k,t) は単調非減少関数 ページ数は有限なので k が増加しても w(k,t) は有限 k Operating System 216 14 ワーキングセットページ置き換えアルゴリズム ワーキングセットにないページを発見し 追い出す ページフォルト時にページテーブルを探査し, 追い出すページを決定する. 例 (1)R=: 最近参照されない k1 = 224-162 > τ なら追い出し候補 k1 = 224-162 < τ なら候補外 (2)R= : 最近参照されない k2 = 224-121 > τ なら追い出し候補 k2 = 224-121 < τ なら候補外年齢 k1<k2 から (2) が追い出される 前提条件 : R,M ビットはハードウェアでセット クロック割り込みが周期的に発生,R= カレント仮想時間 最後に使用された時間が 年齢 となり 年齢の大きな物が追い出し候補となる このクロックティック中に参照されたページは R=1 し カレント仮想時間を最後に使用された時間にセット (2) (1) Operating System 216 16
4.4.9 WSClock ページ置き換えアルゴリズム (1) ワーキングセット アルゴリズムの欠点 : 毎回テーブル全体の走査が必要 環状リストと時計を利用 : 最初 リストは空 ページロードでリストに追加 クロックティック毎に全ページの R を にセット ページフォルト発生時に矢印のページをまず調べる R=1 の場合 クロックティック間に参照があったので このページは理想的な追い出し候補にはならない (a)(b) カレント仮想時間を書き込み R= に R= の場合 (c) 224-121 > τ なら候補 M= なら (d) へ M=1 ならページをディスクに書き戻す予定をして次へ 224-121 < τ なら保留 224 (d) 新たなページをロード Operating System 216 17 4.4.1 Review of Page Replacement Algorithms ページ置き換えアルゴリズムのまとめ P1 P17 Operating System 216 19 ワーキングセットページ置き換えアルゴリズム (2) 一周後の結果 (2 つの場合がある ) と処置 少なくともひとつの書き戻しが予定された 書き戻し候補を書き出しクリーンにする 書き戻しは予定されない つまり全ページがワーキン グセットに含まれる 任意のクリーンページを要求 Operating System 216 18 4.5 ページ置き換えアルゴリズムのモデル化 4.5.1 Belady の異常振る舞い FIFO ではページフレームの増加でもページフォルトは減少しない場合がある ページ参照系列 : 1214124 の例 ページフレーム 4 ページフレーム Operating System 216 2
4.5.2 スタックアルゴリズム 概念的にはプロセスのメモリアクセスは仮想ページ番号のリスト (( メモリ ) 参照列 ) で特徴付け出来る ページングシステムは以下の 項目で特徴付け出来る 実行中プロセスのメモリ参照列 ページ置き換えアルゴリズム メモリ内の利用可能なページ数 :m M[n] 配列 M は全仮想ページ数 n 個のエントリを持つ 上位 m 個が実ページフレームに存在するページ 下位 n-m 個は 1 回参照されたが ページアウトされ 現在メモリにないページ 手順 参照列を順に見て行く 参照したページ番号を最上位に移動 ( なければ最上位に挿入 ) あとは適宜下にシフト これは正確な LRU アルゴリズムを表す ( 途中から抜き取り出来るキューによる LRU と同じ ) 4.5. 距離列 より抽象的な参照列の表現として参照列を 距離 で表す 確率密度関数 : 参照距離 d のエントリに関して 距離とは : 参照されたページのある場所とスタックの最上位との距離 前頁最後の場合 ( 参照は 1) だと一つ前の状態を見て となる M にない場合は となる 4 1 7 5 6 2 ページフレーム数 k でページフォルトはほとんど起きない 仮想空間分だけページフレームを増やさないとページフォルトが減らない Operating System 216 2 メモリ状態を記録する内部配列 M LRU などでの特徴的性質 : M(m,r) M(m+1,r) ページフレーム数 m のメモリで r 回の参照後に M の上位部分に含まれるページ集合は また ページフレーム m+1 のメモリのそれに必ず含まれる この性質を持つアルゴリズムをスタックアルゴリズムと言う ( 最適ページ置き換えや LRU など ) Belady の異常な振る舞いが起きない FIFO にはこのような性質がない 時系列 配列 M[n] m ページフレーム数 n-m 一回参照後ページアウト Operating System 216 22 4.5.4 ページフォルト率の予測 ページフォルト率の予測参照列におけるページフレーム数 m のときに生じるページフォルトの回数を与える 2 Fm 2 1 14 11 9 8 F n m C k m 1 C 18 16 14 12 1 8 ベクトル Cd:d は参照距離距離別出現頻度 ベクトル Fm:m ページフレーム数ページフレーム数 m のページフォルト回数 Operating System 216 24 k 順次減少する 6 4 2 1 2 4 5 6 7