オペレーティングシステム 復習：仮想メモリ 復習：アドレス変換の例

復習：仮想メモリ
・ 各プロセスがそれぞれ、たとえば32ビット(4GB)の
仮想的なメモリ空間を持つ
仮想メモリ
FFFFFFFF
・ 物理メモリは固定長の
ページフレームごとに
各プロセスに割り当て
られる
オペレーティングシステム
物理メモリ
(e.g., 512MB)
第8回 仮想記憶
プロセスAの プロセスBの
仮想メモリ
仮想メモリ
空間
空間
(32ビット)
(32ビット)
情報工学科
2004年11月30日
寺岡文男
プロセスCの
仮想メモリ
空間
(32ビット)
00000000
復習：アドレス変換の例
• 16ビットの仮想アドレス空
間(64kバイト)
• 32kバイトの物理メモリ
• 4kバイトのページサイズ
– 仮想アドレス：0
→ 物理アドレス:8192
• 0はページフレーム2
– 仮想アドレス:8192
→ 物理アドレス:24576
• 8192はページフレーム6
仮想アドレス
空間
64k
×
60k
×
56k
×
52k
×
48k
7
44k
×
40k
物理アドレス
5
空間
36k
×
32k
32k
×
28k
28k
×
24k
24k
3
20k
20k
4
16k
16k
0
12k
12k
6
8k
8k
1
4k
4k
2
0
0
割込み処理と例外処理
• 割込み処理と例外処理の似ている点
– 処理ルーチンがOS内部のテーブルに登録されていて、原
因に対応したルーチンが実行される
– プロセスは割込みや(復旧可能な)例外には気づかない
• 異なる点
– 割込みは実行中のプロセスと無関係に(非同期に)発生する
• デバイスの状態変化など
– 例外はプロセスが実行した命令によって発生する
• ページフォルト、0での除算など
例外(Exception)処理
• CPUが命令実行中に例外(exception)が発生したとき
の処理
– 例外：ページフォルト(後述)、0で除算した、など
• 例外の種類によって実行するルーチンがOS内部の
テーブルに登録されている
• 例外の種類によってそれぞれの処理ルーチンが実行
される
– ページフォルトの場合はページをディスクから読込む
– 0で除算した場合はプロセスを強制終了する
• 復旧可能な場合は、例外を起こした命令から再実行
される
– プロセスは(続行可能な)例外の発生に気づかない
ページフォルト
• ページフレームに対応付けられていないページのアド
レスをアクセスしたらどうなるか?
– e.g., アドレス32780 (ページ8)
• MMUはCPUに通知する: トラップと呼ぶ
– トラップとは、CPUが実行した命令によって例外が発生した
ことをOSに知らせる仕組み。
• cf. 割込みとは、ハードウェアの状態変化(動作終了など)
をOSに知らせる仕組み。
– トラップ処理ルーチンに制御が移る。
• このトラップを「ページフォルト」 (page fault)と呼ぶ。
1
ページフォルト
• ページフォルトが発生すると、
– CPUは何かしらの方法でスワップアウトするページフレーム
を選び、内容をディスクに退避する。
• たとえばページフレーム1を退避
– ページフォルトを起こしたページの内容をディスクから読込
み、退避したページフレームにロードする。
• ページ8の内容を4k∼8kのページフレームへロード
– 対応付けを変更する。
• ページ8の「×」→「1」に変更
– ページフォルトが発生した命令を再実行する。
• 仮想アドレス:32780 → 物理アドレス:4180
MMUの仕組み
物理アドレス：24580
1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
ページ
フレーム
番号
ページ
テーブルの
インデックス
7
6
5
4
3
2
1
0
000
000
011
100
000
110
001
010
ページテーブル
0
15 000 0
0
14 000 0
1
13 000 0
1
12 000 0
1
11 111 1
1
10 000 0
1
9 101 1
1
8 000 0
present/absent bit
・ ページテーブル
インデックスが
4ビット → 16エントリ
・ オフセットが12ビット
→ 4096のアドレス
コピー
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
仮想アドレス：8196
ページテーブルの課題
• ページテーブルは巨大になる可能性あり
– 仮想アドレス空間が32ビットでページサイズが4KBだと、
100万ページになる
• 232 = 4G, 4G/4K = 1M
– 100万エントリのページテーブルが必要
– ページテーブルはプロセスごとに必要
• プロセスごとに独立した仮想アドレス空間をもつ。
• 変換は高速でなければならない
– メモリアクセスごとにアドレス変換が発生
– 1つのCPU命令で数回のメモリアクセスが必要な場合もある
• 命令コード、オペランド
2つの極端な方法 (2/2)
• ページテーブル全体をメインメモリに置く。
– ページテーブルの先頭を示すレジスタをハードウェアに追
加すればよい。
– 利点
• コンテキストスイッチ時にはレジスタ1つの書き換えで済
む。
– 欠点
• 命令実行時のページテーブルエントリのアクセスに数回
のメモリ参照が必要。
• いろいろな改良型がある
– マルチレベルページテーブル
物理アドレス
(15bits = 32KB)
仮想アドレス
(16bits = 64KB)
2つの極端な方法 (1/2)
• 高速なハードウェアレジスタのアレイによる1つのペー
ジテーブル。
– 1つのレジスタが1つの仮想ページに対応
– プロセス起動時にメインメモリからページテーブルのコピー
が読み込まれる
– 利点
• ページテーブル参照のためのメモリ参照無し
– 欠点
• 高価
• コンテキストスイッチごとにページテーブル全体の書き換
えが必要 → 性能に悪影響
マルチレベルページテーブル
• たとえば、32ビットの仮想アドレスを以下のように
分割
– 10ビットのPT1フィールド
• 1024エントリのトップレベルページテーブル
– 10ビットのPT2フィールド
• 1つのセカンドレベルページテーブルにつき1024エントリ
– 12ビットのオフセット
• ページサイズは4KB
• 未使用の領域のページテーブルエントリを持つ必要
がない。
• 2階層、3階層、など多段の階層化が可能
– 3階層程度が実用的
2
マルチレベルページテーブル
例：ページテーブルサイズ
• あるプロセスが、4MBのテキスト、4MBのデータ、
4MBのスタックからなる場合
10bits
PT1
2
1
0
・
・
・
・
・
・
・
・
・
0
テキストの
４MBのための
ページテーブル
• CPU依存だが含まれる情報はほぼ共通。
– ページフレーム番号
– present/absent bit
• 1ならこのエントリは有効。0ならメモリ上に無い
– protection bits
• たとえば、read, write, execute が可能かを示す3ビット
– modified bit
• 書き込まれると1になる。(dirty bitとも呼ばれる)
• 書き戻しをするかを判断
– referenced bit
• 参照されると1になる。(read/writeを問わず)
• ページ置き換えの参考に使われる。
– caching disabled bit
• デバイスのレジスタにマップされている空間のため
TLBの例
ページ19∼21にループ
ページ129と130に主に使われるデータ (e.g., 配列)
ページ140に配列のインデックス
ページ860と861にスタック
1
virtual page
modified
– 4K 個のページテーブルエントリで済む
• トップレベル：1K個
• セカンドレベル：1K × 3 個
protection
140
1
RW
TLB
• TLB: Translation Lookaside Buffer
• ページングでは、ページテーブルのアクセスのために
余分なメモリ参照が必要
→ パフォーマンス低下
• 観察によると、多くのプログラムは少数のページを頻
繁に参照する。
→ 少数のページテーブルエントリが頻繁に参照され、
他はあまり参照されない。
• ページテーブルエントリのバッファをMMU内部に設け
る。
→ ページテーブルを参照せずにアドレス変換可能
– 通常TLBのエントリは64以下
TLBの動作
• TLBの1行が1ページに対応
• 次のようなプロセスのTLBは以下の例のようになる
valid
• 2階層のページテーブル
データの
スタックの
４MBのための ４MBのための
ページテーブル ページテーブル
ページテーブルエントリ
–
–
–
–
• 32ビットの仮想アドレス、4KBページサイズ
• 4MBのテキスト、4MBのデータ、4MBのスタックから
なるプロセスの場合
• フラットなページテーブル
– 1M 個のページテーブルエントリが必要
• 232 = 4G, 4G/4K = 1M
1023
・
・
・
12bits
offset
セカンドレベル ページテーブル
トップレベル
ページテーブル
1023
10bits
PT2
• MMUに仮想アドレスが示される
• ハードウェアはTLBにエントリがあるかをチェック
– エントリがあり、プロテクションも適合していれば、TLBにあ
るページフレーム番号を利用
– プロテクションに適合していないとprotection faultが発生
page frame
31
1
20
0
R X
38
1
130
1
RW
29
1
129
1
RW
62
1
19
0
R X
50
1
21
0
R X
45
1
860
1
RW
14
1
861
1
RW
75
• なければ通常のページテーブル参照を行い、TLBエ
ントリを置き換える
– 置き換えられるTLBエントリのmodified bitが1の場合はこの
ビットだけ書き戻す。
3
ページ置き換えアルゴリズム
• ページフォルトが発生したら、OSはメモリから消去す
るページを選択しなければならない
– 消去するページがメモリ上で変更されている場合はディスク
に書き戻す必要がある。
– メモリ上で変更されていなければ書き戻しは必要ない。
• 参照頻度が少ないページを選択するのがよい
– 頻繁に参照されるページを消去すると、すぐにまた読込む
必要が生じ、システムパフォーマンスを大きく低下させてし
まう
• 効率よいページ置き換えアルゴリズムが必要
NRUアルゴリズム (1/2)
• NRU: Not Recent Used
• 仮想記憶をサポートするマシンは通常各ページにR
ビットとMビットという情報ビットを持つ
– R (Reference): ページが参照されると 1 になる
– M (Modified): ページに書込みがあると 1 になる
• 参照や書込みによりハードウェアが自動的に設定
• 定期的にOSがRビットをクリア
– 定期的: たとえばクロック割込みごと
– 最近参照されたかを判断するため
FIFOアルゴリズム
• FIFO: First-in, First-Out
• OSはメモリ上にあるページのリストを管理。
• リストの先頭には一番古いページ。
• ページフォルトが起きたら、リストの先頭にあるページ
を消去し、読み込んだページをリストの最後に加える。
• FIFOそのものは使われていない
– 頻繁に参照されているページを削除してしまう可能性があ
る
• さまざまな改良アルゴリズムがある
最適ページ置換えアルゴリズム
• 各ページに、今から何命令後にこのページが参照さ
れるかという情報をラベルとしてつける
• 最も数字の大きいものを選択する
• 理想的だが実現不可能
– ページフォルト発生時に、OSは各ページが次にいつ参照さ
れるかを知ることはできない
– 1回目の実行でメモリ参照の軌跡を記録しておけば、2回目
の実行で実現することは可能
• 特定の入力についてのみ有効
• ページ置き換えアルゴリズムの評価には有用である
が、現実のシステムでは役に立たない
NRUアルゴリズム (2/2)
• ページテーブルエントリのRビットとMビットの値によっ
て4つのクラスに分類
– class 0: not referenced, not modified
– class 1: not referenced, modified
• クロック割込みによりRビットがクリアされた場合
– class 2: referenced, not modified
– class 3: referenced, modified
• クラスの小さいものからランダムに選択。
• 理解しやすい、適度に実装しやすい、最適ではないが
十分な性能
Second Chanceアルゴリズム
• FIFOの改良版
• 直前のクロックインターバルに参照されなかったペー
ジのうち、最も古いものを選択
– リストの先頭にあり、かつRビットが0なら消去
– Rビットが1なら、これをクリアしてリストの最後に付け替え、
次を探す
• リストにあるすべてのページのRビットが1の場合、
FIFOアルゴリズムに戻る
– すべてのページのRビットをクリアしてリストの最後に付け替
え、最終的にはもともと先頭にあったページを消去する
• リストの付け替えを行うので非効率
4
Clockアルゴリズム
• Second Chanceの改良版
– アルゴリズムは同じで実装が異なるだけ
• 線形リストではなく、循環リストを使う
– リスト上でのページの付け替えが無くなり、ポインタの移動
だけで済む
LRUアルゴリズム
• LRU: Least Recently Used
• ページフォルトが起きたとき、最も長い時間参照され
ていないページを消去する。
• 理論的には実現可能だが、実際は困難。
– メモリ上のすべてのページをリストで管理し、最も最近参照
されたページを先頭にする。
– メモリ参照ごとにリストを更新しなければならない。
– 特殊なハードウェアで実現する方法や、ソフトウェアでLRU
に近い方式を実現する方法もある。
ソフトウェアでのLRUの実現 (1)
• NFU (Not Frequently Used)
ソフトウェアでのLRUの実現 (2)
• Agingと呼ばれる方法 (NFUの改良)
– Rビットを加算する前にカウンタを右に1ビットシフトする
– Rビットを最左端(MSB)に加える
– 各メモリページごとにソフトウェアカウンタを用意
– クロック割込みごとにRビットの値をカウンタに加算
• クロック割込み間隔内でアクセスされればR=1, そうでな
ければR=0
– カウンタはアクセスの頻度を示すことになる
– ページフォルト発生時にはカウンタの値が最小のページを
置き換える
• 問題点
– 過去の影響が消えない
• 少し前までアクセスされたが最近はアクセスされない
ページが置き換えられない
ソフトウェアでのLRUの実現 (3)
• AgingとLRUの違い
– tick 4でのページ3と5では、どちらが最後にアクセスされた
かわからない
• 1つのtick内での事象は判別不可能
– カウンターが有限である
• カウンターのビット数のtickより前は判定できない
• tickが20msのとき、実際は8ビットあれば十分
160ms間アクセスされていなければ、重要でないと
判断できる
– ページフォルト時にはカウンタが最小のものを削除する
0
1
2
3
4
5
ページ0-5の
Rビット
1 0 10 11
11 0 01 0
1 10 1 01
10 00 1 0
0 11 00 0
10000000
00000000
11000000
10000000
11100000
11000000
11110000
01100000
01111000
10110000
10000000
00000000
10000000
10000000
tick 0
01000000
00000000
11000000
01000000
tick 1
00100000
10000000
01100000
10100000
tick 2
00010000
01000000
10110000
01010000
tick 3
10001000
00100000
01011000
00101000
tick 4
デマンドページング
• プロセス実行開始時にはメモリ上にはページがない。
• CPUの最初の命令フェッチによりページフォルトが発
生し、OSが該当するページを読み込む。
• 次に広域変数の参照、スタックの使用などで次々と
ページが読み込まれる。
• しばらくすると必要とする大部分のページがメモリ上
に読み込まれ、ページフォルトの頻度が減る。
• 要求に応じてページが読み込まれるので、デマンド
ページング (demand paging) と呼ばれる。
5
ワーキングセットモデル
Thrashing
• 多くのプログラムはある実行段階(phase)では限られ
た少数のページのみを参照することが多い。
• 利用可能メモリがワーキングセットより小さいと、ペー
ジフォルトが頻発し、実行が遅くなる
– 参照の局所性 (locality of reference) と呼ばれる。
– そのようなページの集合をワーキングセット (working set)
と呼ぶ。
– 1命令の実行は数ナノ秒に対し、ディスクからのページの読
込みは10ミリ秒のオーダー。
• プロセス全体のページアウト後、再度ページインされ
るときは、ワーキングセットを読み込んでからプロセ
スの実行を再開する
• 数命令ごとにページフォルトを起こすようなプロセスの
状態を thrashing と呼ぶ[Denning 1968]。
– そうでないと、ワーキングセットがすべてそろうまで頻繁に
ページフォルトが発生し、実行効率が落ちる。
– プロセスを実行状態にする前にある程度のページをロード
しておくことをプリページング (prepaging)と呼ぶ
• このアプローチをワーキングセットモデルと呼ぶ
[Denning 1970]
ワーキングセット
• ある時刻 t において最近 k 回の参照で使用された
ページの集合 w(k, t)
– k = 1 の参照で使用されたページは k > 1 の参照でも使用さ
れる → w(k, t) は k の単調増加
• ワーキングセットの内容は k の値にはあまり影響され
ない
ワーキングセット
• OSはどのページがワーキングセットに含まれるかを
把握し、ページフォルト時にはワーキングセットに含ま
れないページを消去
– どのページがワーキングセットに含まれ、どのページが含ま
れないかを決定する的確な方法が必要
• ワーキングセットを決定する方法の例：
– 長さ k のシフトレジスタを用意
– メモリ参照ごとに左にシフトし、最右端に参照されたページ
番号を記録
– ページフォルト時にはシフトレジスタの内容をソートし、重複
したページ番号を消す
– シフトレジスタにある k 個のページ番号がワーキングセット
となる
– 処理が重いため実用的ではない
– ワーキングセットの内容を変えない k の値の範囲は大きい
とも言える
• プロセスのストップ時のワーキングセットに基づき、再
開後にどのページが必要になるか推測可能
– これらのページをプリページングすればよい
ワーキングセット
• 近似のため、過去 k 回の参照ではなく実行時間を用
いる
• 近似的な定義：過去仮想時間のτ秒間に参照された
ページの集合
– 仮想時間(virtual time)とはCPUの実行時間
ワーキングセットアルゴリズム
現在
仮想時刻
最終使用時刻 Rビット
2084
1
2003
1
スキャン
• ワーキングセットに基づくページ置換えアルゴリズム
– ページフォルト発生時には、ワーキングセットに含まれない
ページをページアウトする。
2204
1980
1213
1
0
2014
2020
1
1
2032
1
1620
0
ページテーブル
の一部
・Rビットはハードウェアが自動的にセット
・クロック割込みごとにRビットはクリア
・ページフォルトが発生すると、ページ
テーブルをスキャン
if (R = = 1)
現在の仮想時刻を最後の参照
時刻として設定;
if (R = = 0 and age > τ)
このページを削除 // スキャンは続行
if (R = = 0 and age ≦ τ)
最小時刻のページを記録しておく
(削除の候補として)
age = 現在仮想時刻 − 最終使用時刻
・ページフォルトごとにページテーブル全体を
スキャンする必要がある。
6
WSClockアルゴリズム (1/2)
WSClockアルゴリズム (2/2)
• ワーキングセットを考慮したクロックアルゴリズム
[Carr and Hennessey 1981]
• ディスクへのwriteがスケジュールされるページ数には
上限を設ける
– 実装しやすく効率もよい → 現実に広く使われている
• ページテーブルエントリを環状リストで保持
– ディスクトラフィックを減らすため
• 1周したときの2つの状態
– 最初、リストは空
– ページがロードされるとエントリが追加される
– 各エントリは、最終使用時刻、Rビット、Mビットをもつ
• ページフォルト発生時、ポインタの指すエントリから
チェック
– R = 1 なら R=0 にして次へ
– R = 0 かつ age > τかつ M = 0 なら置換え
– R = 0 かつ age > τかつ M = 1 ならディスクへのwriteをスケ
ジュールして次へ
– 少なくとも1つのページのwriteがスケジュールされている
– writeがスケジュールされているページがない
• 前者の場合
– writeがスケジュールされていたらスキャンを続行
– やがてwriteが終了すればページはcleanになる
– 最初に見つかったcleanページを置換える
• 後者の場合 (すべてがワーキングセットに含まれる)
– M = 0 のページを置換え
– M = 0 のページがなければ、現在のページを置換え
ページ置換えアルゴリズム
WSClockアルゴリズムの例
1620 0 1
2084 1 1
1620 0 1
2032 1 1
2003 1 1
2020 1 0
1980 1 0
2014 1 0
2084 1 1
2003 1 1
1213 0 0
最終使用時刻
1213 0 0
2020 1 0
1980 1 0
2014 0 0
1213 0 0
2204
現在
仮想時刻
1620 0 1
2084 1 1
2032 1 1
2003 1 1
2020 1 0
Rビット Mビット
1980 1 0
アルゴリズム
2032 1 1
2014 0 0
コメント
Optimal
実装不可能、ベンチマークに有用
NRU (Not Recently Used)
実装は容易だが、未熟
FIFO
重要なページを置換える可能性
Second chance
FIFOを大きく改良
Clock
Second chanceの一実装法。現実的
LRU (Least Recently Used)
優秀だが、厳密な実装は困難
NFU (Not Frequently Used)
LRUの未熟な近似
Aging
LRUをよく近似した効率的方法
Working set
実装にはコストが高い
WSClock
優秀で効率的なアルゴリズム
新しいページ 2204 1 0
ページングに関するOSの動作 (1)
• プロセス生成時
–
–
–
–
初期のプログラム領域とデータ領域を決定
ページテーブルをメモリ上に作成
ディスク上にスワップ領域を確保
ページテーブルとスワップ領域の情報をプロセステーブル
に記録
• プロセス実行開始時
– MMUをリセットし、TLBをフラッシュ
– ページテーブルを最新にする
– ある程度のページを前もって読み込んでおく
ページングに関するOSの動作 (2)
• ページフォルト発生時
– どの仮想アドレスがページフォルトを起こしたかをハード
ウェアレジスタを読み込んで判定
– 必要なページがディスクのどこにあるかを計算
– 利用可能なページフレームを探す。なければ置換
– ページを読み込む
– ページフォルトを起こした命令を再実行
• プロセス終了時
– ページテーブル、ページ、ディスクスペースを解放
– 共有ページに関しては、最後のプロセスの場合はメモリ上
およびディスク上のページを解放
7
ページフォルトの処理 (1)
ページフォルトの処理 (2)
1. ハードウェアがOSにトラップをかける。プログラムカ
ウンタは自動的にスタックに退避される
2. アセンブラルーチンが実行され、レジスタや状態情
報を退避。OSを呼び出す。
3. OSはページフォルトが発生したと判断し、どの仮想
ページが必要かを判断する。
4. ページフォルトを起こした仮想アドレスがわかると、
アドレスの有効性やプロテクションとの整合性を
チェックする。エラーがあればプロセスにはシグナル
が送られる。正常なら利用可能なページフレームを
探す。なければページ置換えアルゴリズムを実行す
る。
5. 選択したページがdirtyなら、ディスクへの転送がスケ
ジュールされ、コンテキストスイッチが発生する。この
フレームはビジー状態になり、他の用途に使われない
ようにする。
6. ページフレームがcleanになったら、必要なページの
ディスクアドレスを見つけ、ディスクからの読込みをス
ケジュールする。読み込み終了までページフォルトを
起こしたプロセスはブロックされる。
7. 読込み終了の割込みがあるとページテーブルを更新
し、フレームは通常の状態に戻る。
ページフォルトの処理 (3)
8. フォルトを起こした命令の状態が元に戻され、プログ
ラムカウンタはその命令を指すようにリセットされる。
9. フォルトを起こしたプロセスがスケジュールされ、OS
はアセンブラルーチンにリターンする。
10. このルーチンはレジスタや状態情報を再度設定し、
ページフォルトが発生しなかったかのように実行を再
開する。
8