記憶管理(2)

記 憶 管 理(2)
オペレーティングシステム
第10回
復 習




実際のメモリよりも,大きなプログラムを実行した
い
実行に伴い,その時,その時で必要な部分だけ
がメモリにあれば良い
オーバレイ
 どこが必要なのかの指示をプログラマが行う
仮想記憶
 必要になった部分をOSがメモリに格納する
ペ ー ジ 置 換 え(1)



デマンドページング
ページが必要になったときに,補助記憶装置か
ら実記憶に読み込む
 ページイン
しかし,読み込む場所(空きページ枠)がない場
合は?!
ペ ー ジ 置 換 え(2)




空きページ枠がない
適当なページ枠を選ぶ
 しかし,ページが読み込まれている
その内容を必要に応じて,補助記憶装置に書き
出す
 ページアウト
空けたページ枠に,読み込む,
ペ ー ジ 置 換 え(3)


ページアウトするページの選択
 これから使いそうにないページ
 今後,使わないページ
 ページアウト直後に再度ページインすることに
なるようなページは選びたくない
将来の予測
 困難
ペ ー ジ 置 換 え(4)



FIFOアルゴリズム(First In First Out)
もっとも古くに実記憶に読み込まれたページを選
ぶ
実記憶に長く存在するページは,今後はもう使わ
ないであろう
ペ ー ジ 置 換 え(5)

LRUアルゴリズム(Least Recently Used)

もっとも以前に使われたページを選ぶ


頻繁に使われるページは,今後も使われるであ
ろう(“局所参照”という性質)
使われなくなって時間が経過したページは,今後
は使われないであろう
ペ ー ジ 置 換 え(6)

他にもいろいろある

実際は,もっと複雑
ペ ー ジ 置 換 え(7)

4ページ分(0~3)の大きさのプログラム

実記憶のページ枠は3

次の順で各ページが必要になるものとする
0→1→2→0→3→0→2→1→2
ペ ー ジ 置 換 え(8)

FIFO
直前にページアウトした
ページをページイン
下のものほど,
長く実記憶にある
ページ枠ではない
ページアウト(ページ交換)
ページ0が
ページアウト
ペ ー ジ 置 換 え(9)

LRU
実記憶にあるページ
下のものほど,
参照されてから
時間が経過している
参照されてから,最も時間が
ページアウト(ページ交換)
経過しているページが
ページアウト
ペ ー ジ 置 換 え(10)


LRUの方が,ページ置換えの回数が少ない
 ような例としているだけ,かも知れない
FIFOだと,ページ枠の数を増やしても,ページ交
換の回数が増える場合がある
 LRUだと,そのようなことはない
ペ ー ジ 置 換 え(11)


LRUの背景
メモリ参照の局所性
 プログラムは,いつもプログラム全体を参照す
るわけではない
このようにプログラムを作ると
効率的に実行されることになる
 一部だけを参照する
 その一部が実行に伴い移動する
この部分だけ
この部分だけ
この部分だけこの部分だけ
この部分だけ
プログラム全体(命令とデータ)
を参照する
を参照する
を参照する を参照する
を参照する
ス ラ ッ シ ン グ(1)

多重プログラミング環境

多重度(並行実行するプロセスの数)を上げる

各プロセスへのページ枠が減る
ス ラ ッ シ ン グ(2)

ページ交換の回数が増える

さらに多重度を上げる

CPUは,もっぱらページ交換のために使われる
 プロセスの実行が進まない
ス ワ ッ ピ ン グ(1)

多重プログラミング環境

すべてのプログラムを主記憶に格納できない
ス ワ ッ ピ ン グ(2)




プログラムAが実行中
プログラムBを実行しようとする
主記憶を空けるために,Aが格納されている主記
憶の内容を必要に応じて,補助記憶装置に書き
出す
 スワップアウト
空いたところに,Bを読み込む
 スワップイン
問 題



ページアウト,スワップアウト
 必要に応じて,補助記憶装置に書き出す
つまり,“書き出さない”場合がある
 ページインは,単に上書き
書き出す必要の有無は?
ヒント

命令しかないページは?

データのあるページは?

実記憶(主記憶)にある間に,書き換えられたか
どうか!
 この情報も管理する
ただし

多重プログラミング環境

ページ枠に,別のプロセスの命令・データ

ページ枠の内容を消去してから,
ページインしなければならない
記憶管理の他の重要な機能

多重プログラミング環境
 別のプログラムが,自分のデータを読み書き
 別のプログラムのデータを読み書き
 禁止する(保護)
 ただし,禁止だけではない(情報共有)
記憶装置の階層化(1)


第2回
仮想記憶は
メモリ
HDD
の2階層
容量
メモリ
小
読み書きの
時間
短い
HDD
大
長い
記憶装置の階層化(2)



キャッシュメモリ
CPUのデータ転送速度と主記憶装置の読み書き
速度に差をうめる
CPUと主記憶装置の間におかれる高速記憶装
置
記憶装置の階層化(3)

読み書きの速度
容量
値段

早いもので大容量が理想であるが…

全体としてのバランス


ま と め
ま と め(1)



空きページ枠がないとき,どのページ枠を空ける
か
これから使いそうにないページが格納されている
ページ枠を選ぶ
将来の予測は困難
ま と め(2)



FIFO
LRU
他にもある
 最前未使用(NRU)アルゴリズム,セカンド・チャ
ンスアルゴリズム,ワーキングセット法,…
ま と め(3)

プロセスへのページ枠の割当てが少ない

ページ置換えが頻発

プロセスの実行時間が少なくなる

スラッシング
ま と め(4)

記憶装置の階層化
 キャッシュメモリ
 メモリ
 HDD
読み書きの速度,容量,価格

キャッシュは後でも出てくる
