記憶管理(2)

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