記憶管理（2）

記憶管理（２）
オペレーティングシステム
第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を実行しようとする
主記憶を空けるために，Aが格納されている主記
憶の内容を必要に応じて，補助記憶装置に書き
出す
 スワップアウト
空いたところに，Bを読み込む
 スワップイン
問題



ページアウト，スワップアウト
 必要に応じて，補助記憶装置に書き出す
つまり，“書き出さない”場合がある
 ページインは，単に上書き
書き出す必要の有無は？
ヒント

命令しかないページは？

データのあるページは？

実記憶（主記憶）にある間に，書き換えられたか
どうか！
 この情報も管理する
ただし

多重プログラミング環境

ページ枠に，別のプロセスの命令・データ

ページ枠の内容を消去してから，
ページインしなければならない
記憶管理の他の重要な機能

多重プログラミング環境
 別のプログラムが，自分のデータを読み書き
 別のプログラムのデータを読み書き
 禁止する（保護）
 ただし，禁止だけではない（情報共有）
記憶装置の階層化（１）


第2回
仮想記憶は
メモリ
HDD
の2階層
容量
メモリ
小
読み書きの
時間
短い
HDD
大
長い
記憶装置の階層化（２）



キャッシュメモリ
CPUのデータ転送速度と主記憶装置の読み書き
速度に差をうめる
CPUと主記憶装置の間におかれる高速記憶装
置
記憶装置の階層化（３）

読み書きの速度
容量
値段

早いもので大容量が理想であるが…

全体としてのバランス


まとめ
まとめ（１）



空きページ枠がないとき，どのページ枠を空ける
か
これから使いそうにないページが格納されている
ページ枠を選ぶ
将来の予測は困難
まとめ（２）



FIFO
LRU
他にもある
 最前未使用(NRU)アルゴリズム，セカンド・チャ
ンスアルゴリズム，ワーキングセット法，…
まとめ（３）

プロセスへのページ枠の割当てが少ない

ページ置換えが頻発

プロセスの実行時間が少なくなる

スラッシング
まとめ（４）

記憶装置の階層化
 キャッシュメモリ
 メモリ
 HDD
読み書きの速度，容量，価格

キャッシュは後でも出てくる


Download Report