記 憶 管 理（２） オペレーティングシステム 第10回

復 習 実際のメモリよりも，大きなプログラムを実行したい 実行に伴い，その時，その時で必要な部分だけがメモリにあれば良い オーバレイ 復　習 実際のメモリよりも，大きなプログラムを実行したい 実行に伴い，その時，その時で必要な部分だけがメモリにあれば良い オーバレイ どこが必要なのかの指示をプログラマが行う 仮想記憶 必要になった部分をOSがメモリに格納する

ペ ー ジ 置 換 え（１） デマンドページング ページが必要になったときに，補助記憶装置から実記憶に読み込む ページイン しかし，読み込む場所（空きページ枠）がない場合は?!

ペ ー ジ 置 換 え（２） 空きページ枠がない 適当なページ枠を選ぶ しかし，ページが読み込まれている その内容を必要に応じて，補助記憶装置に書き出す ページアウト 空けたページ枠に，読み込む,

ペ ー ジ 置 換 え（３） ページアウトするページの選択 これから使いそうにないページ 今後，使わないページ ページアウト直後に再度ページインすることになるようなページは選びたくない 将来の予測 困難

ペ ー ジ 置 換 え（４） FIFOアルゴリズム(First In First Out) もっとも古くに実記憶に読み込まれたページを選ぶ 実記憶に長く存在するページは，今後はもう使わないであろう

ペ ー ジ 置 換 え（５） LRUアルゴリズム(Least Recently Used) もっとも以前に使われたページを選ぶ 頻繁に使われるページは，今後も使われるであろう（“局所参照”という性質） 使われなくなって時間が経過したページは，今後は使われないであろう

ペ ー ジ 置 換 え（６） 他にもいろいろある 実際は，もっと複雑

ペ ー ジ 置 換 え（７） 4ページ分（0～3）の大きさのプログラム 実記憶のページ枠は3 次の順で各ページが必要になるものとする  0 → 1 → 2 → 0 → 3 → 0 → 2 → 1 → 2

ペ ー ジ 置 換 え（８） FIFO 直前にページアウトした ページをページイン 下のものほど， 長く実記憶にある ページ枠ではない ページアウト（ページ交換） ページ0が ページアウト

ペ ー ジ 置 換 え（９） LRU 実記憶にあるページ 下のものほど， 参照されてから 時間が経過している ページアウト（ページ交換） 参照されてから，最も時間が 経過しているページが ページアウト

ペ ー ジ 置 換 え（１０） LRUの方が，ページ置換えの回数が少ない ような例としているだけ，かも知れない FIFOだと，ページ枠の数を増やしても，ページ交換の回数が増える場合がある LRUだと，そのようなことはない

ペ ー ジ 置 換 え（１１） LRUの背景 メモリ参照の局所性 プログラムは，いつもプログラム全体を参照するわけではない 一部だけを参照する その一部が実行に伴い移動する このようにプログラムを作ると 効率的に実行されることになる プログラム全体（命令とデータ） この部分だけ を参照する この部分だけ を参照する この部分だけ を参照する この部分だけ を参照する この部分だけ を参照する

ス ラ ッ シ ン グ（１） 多重プログラミング環境 多重度（並行実行するプロセスの数）を上げる 各プロセスへのページ枠が減る

ス ラ ッ シ ン グ（２） ページ交換の回数が増える さらに多重度を上げる CPUは，もっぱらページ交換のために使われる プロセスの実行が進まない

ス ワ ッ ピ ン グ（１） 多重プログラミング環境 すべてのプログラムを主記憶に格納できない

ス ワ ッ ピ ン グ（２） プログラムAが実行中 プログラムBを実行しようとする スワップアウト 空いたところに，Bを読み込む スワップイン

問 題 ページアウト，スワップアウト 必要に応じて，補助記憶装置に書き出す つまり，“書き出さない”場合がある ページインは，単に上書き 問　題 ページアウト，スワップアウト 必要に応じて，補助記憶装置に書き出す つまり，“書き出さない”場合がある ページインは，単に上書き 書き出す必要の有無は？

ヒ ン ト 命令しかないページは？ データのあるページは？ 実記憶（主記憶）にある間に，書き換えられたかどうか！ この情報も管理する

た だ し 多重プログラミング環境 ページ枠に，別のプロセスの命令・データ ページ枠の内容を消去してから， ページインしなければならない

記憶管理の他の重要な機能 多重プログラミング環境 別のプログラムが，自分のデータを読み書き 別のプログラムのデータを読み書き 禁止する（保護） ただし，禁止だけではない（情報共有）

記憶装置の階層化（１） 第2回 仮想記憶は 　　メモリ 　　 HDD の2階層 容量 読み書きの時間 メモリ 小 短い HDD 大 長い

記憶装置の階層化（２） キャッシュメモリ CPUのデータ転送速度と主記憶装置の読み書き速度に差をうめる

記憶装置の階層化（３） 読み書きの速度 容量 値段 早いもので大容量が理想であるが… 全体としてのバランス

ま　と　め

ま と め（１） 空きページ枠がないとき，どのページ枠を空けるか これから使いそうにないページが格納されているページ枠を選ぶ 将来の予測は困難

ま と め（２） FIFO LRU 他にもある 最前未使用(NRU)アルゴリズム，セカンド・チャンスアルゴリズム，ワーキングセット法，…

ま と め（３） プロセスへのページ枠の割当てが少ない ページ置換えが頻発 プロセスの実行時間が少なくなる スラッシング

ま と め（４） 記憶装置の階層化 キャッシュメモリ メモリ HDD 読み書きの速度，容量，価格 キャッシュは後でも出てくる