主記憶と 次記憶 オペレーティングシステム 第 回仮想記憶管理 () htt://www.info.kindai.ac.j/os 8 号館 階 N- 内線 559 takasi-i@info.kindai.ac.j プロセッサ 主記憶 プログラム データ 次記憶 プログラム データ -7 秒 倍 - 秒 プロセッサは 次記憶を直接読むことはできない 使用するプログラム, データは主記憶上にコピー メモリ管理技法 メモリ管理技法 割り付け技法 (lacement) プログラム, データのメモリ上への割り付け位置を決定 フェッチ技法 (fetch) プログラム, データを 次記憶から主記憶への読み込み時期を決定 置き換え技法 (relacement) 空き領域作成のために 次記憶に追い出すデータの決定 割り付け技法 (lacement) 割り付け技法 連続割り付け (contiguous allocation) プログラム, データをメモリ上の連続した領域に置く 非連続割り付け (noncontiguous allocation) プログラム, データをメモリ上に分割して置くデータ データ 割り付け技法 フェッチ技法 (fetch) 連続割り付け (contiguous allocation) 非連続割り付け (noncontiguous allocation) 単一連続割り付け (single artition allocation) 固定区画割り付け (static artition allocation) 可変区画割り付け (dynamic artition allocation) ページング (aging) セグメンテーション (segmentation) 単一ユーザ 複数ユーザ フェッチ技法 (fetch) 要求時フェッチ (demand fetch) プログラムが参照したときにデータを読み込む プリフェッチ (refetch) 参照前に予めデータを読んでおく
置き換え技法 (relacement) 置き換え技法 (relacement) 空き領域作成のために 次記憶に追い出すデータの決定主記憶 次記憶主記憶に読み込みプログラム 空き無しデータ データ プログラム データ プログラム プログラム プログラム データ データ 置き換え技法 (relacement) 置き換え技法 (relacement) 空き領域作成のために 次記憶に追い出すデータの決定主記憶 次記憶 プログラム 書き込みプログラム データ データ プログラム プログラム プログラム データ データ データ どのデータを 次記憶に追い出すか? 仮想記憶 置き換え技法 スワップイン, スワップアウトに時間がかかる ( 主記憶へのアクセスの約 倍 ) スワップ操作 可能な限り低頻度に 可能な限り低コストに 主記憶上に無い場合 仮想アドレス ペー ペー フラグ ジ ジ枠 V P C 主記憶上 に無し ページングの動作 主記憶ページ 7 6 に空き無し 次記憶 ページ 5 6 7 ページフォルト発生 ページングの動作 次記憶 主記憶上に無い場合 主記憶 仮想アドレス ページ ページ 7 6 ペー ペー フラグ ジジ枠 V P C を空けるために 5 をページアウト 6 7 主記憶上に無い場合 仮想アドレス 実アドレス ペー ペー フラグ ジ ジ枠 V P C 主記憶上 主記憶上 の位置 に有り ページングの動作 主記憶ページ 7 6 次記憶からページイン 次記憶ページ 5 6 7
ページングの動作 次記憶 主記憶上に無い場合 主記憶 仮想アドレス ページ ページ 999 7 ページフォルト発生 6 ペーペーフラグ ジジ枠 V P C はページアウトしたばかり 5 6 前回のページアウトが 7,6,7 のどれかであれば ページフォルトは起きなかった ページアウトするページ ページアウトしたページを再度参照するとページフォルトが起こる ページアウトするページは近い将来に参照されないページがいい どのページが 近い将来に参照されない? 置き換えアルゴリズム OPT(otimal) 今後最も長い期間使用されないページを選択 FIFO(first in first out) 最も早く主記憶に読み込んだページを選択 LRU(least recently used) 最も長い期間使用されていないページを選択 LFU(least frequently used) 最も参照回数の少ないページを選択 OPT(otimal) OPT(otimal) 今後最も長い期間使用されないページを選択 主記憶 ページ 読み込み 前回使用 参照回数 次回使用 回前 5 回前 回 回後 7 回前 7 回前 回 5 回後 7 回前 回前 回 7 回後 6 回前 回前 回 回後 OPT OPT 参照ページ 参照ページ
OPT 参照ページ ページフォルト 7 回 OPT の長所 OPT の長所と短所 最適なアルゴリズム : ページフォルト率が最低 OPT の短所 将来のページ参照が分かる必要あり 実用性は無し = OPT を採用している OS は存在しない ( 他のアルゴリズムとの比較用 ) 参照の局所性 (locality of reference) 参照の局所性 (locality of reference) 主記憶へのアクセスは一部のアドレスに集中する可能性が高い時間局所性 最近参照されたページは近い将来に再度参照される可能性が高い空間局所性 あるページが参照されると近くのページも近い将来に参照される可能性が高い 時間局所性 時間局所性 最近参照されたページは近い将来に再度参照される可能性が高い sum = ; for (int i:=; i<n; ++i) { sum := sum + a[i]; } for ループ内では変数 i, sum が繰り返し参照される 空間局所性 空間局所性 あるページが参照されると近くのページも近い将来に参照される可能性が高い sum = ; for (int i:=; i<n; ++i) { sum := sum + a[i]; } for ループ内では a[], a[],, a[n] が順に参照される 時間局所性今後アクセアクセスされてから時間が経つにつれスアクセスされる確率は下がっていくされる確率(未知)
局所性を利用した置き換え 多くのプログラムには時間局所性がある 最近参照されたページは近い将来に再度参照される可能性が高い 最近参照されていないページは近い将来に再度参照される可能性は低い あまり参照されていないページをページアウトする FIFO(first in first out) FIFO(first in first out) 最も早く主記憶に読み込んだページを選択 主記憶 ページ 読み込み 前回使用 参照回数 次回使用 回前 5 回前 回 回後 7 回前 7 回前 回 5 回後 7 回前 回前 回 7 回後 6 回前 回前 回 回後 FIFO 参照ページ FIFO 参照ページ FIFO 参照ページ ページフォルト 9 回 FIFO の実装 FIFO の実装 キューでページを管理する 参照ページ (FIFO キュー ). 番上のページを消す. ページを上にシフト. 番下にページを加える 5
FIFO の実装 参照ページ FIFO の長所 実装が簡単 FIFO の短所 FIFO の長所と短所 頻繁に使用するページでもページアウトされる Belady の異常 (Belady s anomaly) が起こる FIFO の短所 ページ は頻繁にアクセス 参照ページ 頻繁にアクセスされるページがページアウトしてしまう 通常は少 多 Belady の異常 (Belady s anomaly) 数 ページフォルト数 Belady の異常 (Belady s anomaly) 多 少 FIFO では 数が増加したのにページフォルト数が増加してしまう場合がある Belady の異常参照ページ 枠数 枠数 ページフォルト 9 回 ページフォルト ページフォルト 回 ページフォルト Belady の異常 参照ページ 6
LRU(least recently used) LRU(least recently used) 最も長い期間使用されていないページを選択 主記憶 ページ 読み込み 前回使用 参照回数 次回使用 回前 5 回前 回 回後 7 回前 7 回前 回 5 回後 7 回前 回前 回 7 回後 6 回前 回前 回 回後 LRU 参照ページ LRU 参照ページ LRU 参照ページ ページフォルト 7 回 LRU の長所 LRU の長所と短所 頻繁にアクセスするページはページアウトされない Belady の異常が起こらない LRU の短所 各ページの参照時刻の記録が必要 カウンタ, スタック, 参照ビット等のハードウェア支援が必要 LRU の実装 各ページへのアクセス時のカウンタ値を記録 最小のカウンタ値のページをページアウト 各ページへアクセス時に にセット のページを優先的にページアウト スタックによる実装 各ページへのアクセス時にスタックの先頭に移動 スタックの末尾のページをページアウト 7
ページへアクセスするときカウンタを増加 アクセスしたページにカウンタ値を記録 ページへアクセスするときカウンタを増加 アクセスしたページにカウンタ値を記録 カウンタ 5 ページ カウンタ カウンタ 56 ページ にアクセス ページ カウンタ 5 ページへアクセスするときカウンタを増加 アクセスしたページにカウンタ値を記録 ページへアクセスするときカウンタを増加 アクセスしたページにカウンタ値を記録 カウンタ 6 ページ にアクセス ページ カウンタ 5 カウンタ値が 最小のページをページアウト カウンタ ページ カウンタ 67 ページ にアクセス 6 ページへアクセスするとき にセット 参照ビットが のページを優先的にページアウト 必要に応じて全ページの参照ビットを にリセット ページへアクセスするとき にセット 参照ビットが のページを優先的にページアウト 必要に応じて全ページの参照ビットを にリセット ページ 参照ビット ページ にアクセス ページ 参照ビット 8
ページへアクセスするとき にセット 参照ビットが のページを優先的にページアウト 必要に応じて全ページの参照ビットを にリセット ページへアクセスするとき にセット 参照ビットが のページを優先的にページアウト 必要に応じて全ページの参照ビットを にリセット ページ にアクセス ページ 参照ビット 参照ビットが のページを ページアウト ページ 参照ビット ページ にアクセス スタックによる実装 スタックによる実装 スタックでページを管理する 参照ページ (FIFO キュー ) ページフォルト 参照したページを一番下に移動 スタックによる実装 スタックによる実装 スタックでページを管理する参照ページ (FIFO キュー ) ページフォルト. 番上のページを消す. ページを上にシフト. 番下にページを加える LRU の実装 実装方法長所短所 カウンタ LRU を実現 参照ビットハードウェアが不要 ハートウェアが必要参照に時間が掛かる LRU の近似 スタック LRU を実現ハードウェアが必要 LFU(least frequently used) LFU(least frequently used) 最も参照回数の少ないページを選択 主記憶 ページ 読み込み 前回使用 参照回数 次回使用 回前 5 回前 回 回後 7 回前 7 回前 回 5 回後 7 回前 回前 回 7 回後 6 回前 回前 回 回後 9
ージフォルト率主記憶上に存在するページの割合ペ : 回 : 回 : 回 LFU : 回 : 回 : 回 LFU 参照ページ 参照ページ LFU 参照ページ ページフォルト 7 回 LFU の長所 LFU の長所と短所 頻繁にアクセスするページはページアウトされない Belady の異常が起こらない LFU の短所 参照に時間がかかる 各ページの参照回数の記録が必要 カウンタ等のハードウェア支援が必要 置き換え技法の長所と短所 技法長所短所 OPT FIFO LRU LFU 最適 実装が簡単 参照の少ないページがページアウト 参照の少ないページがページアウト 未来の参照が分からなければならない 頻繁に参照されるページがページアウト ハードウェアが必要 ハードウェアが必要..5 ページフォルト曲線.5..5 を境にページフォルト率は急激に上昇 ランダムな参照 局所的な参照
CPU プロセス プロセス ( 優先度低 ) IO 装置 マルチプロセスの実行中の動作 CPU が使えるので実行開始 優先度が低い方は実行中断 遊び マルチプロセスにすれば CPU の遊び時間を減らせる 実行プロセス数と処理効率 CPUの遊び時間がPU減り効率が上がる処ページスワップが理多くなる効率入力待ち等で効率が低い実行プロセス数C実行プロセスが増え過ぎると効率が下がるスラッシング (thrashing) スラッシング (thrashing) スラッシング (thrashing) 主記憶の容量が充分に無いため 次記憶への参照が繰り返し行われる状態スラッシングの原因 非常に多くのプロセスが並行動作 非常に大きな記憶領域を必要とするプロセスが動作 ワーキングセット (working set) ワーキングセット (working set) プロセスが活発に参照するページの集合 頻繁に参照プロセス あまり参照しない ページ ワーキングセット ワーキングセットと ワーキングセット > 頻繁にページフォルトが発生 スラッシング 各プロセスにワーキングセット以上のを割り当てる 動的ページ置き換え 動的ページ置き換え 各プロセスに割り当てるのサイズを動的に変える ページフォルト発生頻度 : 大 増加ページフォルト発生頻度 : 並 変更無しページフォルト発生頻度 : 小 減少 全てのプロセスでページフォルトが多発する場合は優先度の低いプロセスを停止する
ージフォルト率数ペ動的ページ置換え を増やす上限下限を減らす ワーキングセットによる動的ページ置換え ワーキングセット = 最近の w 時間以内にアクセスされたページ ページ : 5 時刻 t-w 時刻 t 時刻 t のワーキングセット : 5 時間 w : ウィンドウサイズ ワーキングセットによる動的ページ置換え ウィンドウサイズ w = 参照ページ ページフォルト ワーキングセットによる動的ページ置換え w 時間アクセスされなかったページは消去ウィンドウサイズ w = 参照ページ ページフォルト を に減少 ワーキングセットによる動的ページ置換え ウィンドウサイズ w = 参照ページ ページフォルト を に増加 ワーキングセットによる動的ページ置換え ウィンドウサイズ w = 参照ページ を に減少 を に増加
ージフォルト率数ペ置換え技法 まとめ 主記憶上のデータのうち どれを二次記憶に追い出すか決定する 今後使わないデータを追い出す 参照の局所性を利用して今後使わないデータを推定 置き換えアルゴリズム OPT(otimal) 今後最も長い期間使用されないページを選択 FIFO(first in first out) 最も早く主記憶に読み込んだページを選択 LRU(least recently used) 最も長い期間使用されていないページを選択 LFU(least frequently used) 最も参照回数の少ないページを選択 置き換え技法の長所と短所 動的ページ置換え 技法長所短所 OPT FIFO LRU LFU 最適 実装が簡単 参照の少ないページがページアウト 参照の少ないページがページアウト 未来の参照が分からなければならない 頻繁に参照されるページがページアウト ハードウェアが必要 ハードウェアが必要 を増やす上限下限を減らす