オペレーティングシステム

オペレーティングシステム

加藤 真平

東京大学 大学院情報理工学系研究科

shinpei@is.s.u-tokyo.ac.jp

PFLab（加藤研）のウェブサイトからダウンロードできます。 ⇒http://www.pf.is.s.u-tokyo.ac.jp/ja/classes/

講義概要

• 受講生に求める基礎知識

– C言語の理解

– コンピュータアーキテクチャの基礎の理解

• メモリ管理、割り込み、CPUモード

• 参考図書

– Silberschatz, Galvin, and Gagne, Operating System

Concepts 8th Edition,

Wiley

• 成績

講義スケジュール（予定）

1. OSの概要（4/8） 2. プロセス管理（4/15） 3. プロセス間交信、スレッド（4/22） 4. プロセス同期（5/13） 5. CPUスケジューリング 1（5/20） 6. CPUスケジューリング 2 & トランザクション処理（5/27） 7. メモリ管理1（6/3） 8. 休講予定（6/10） 9. メモリ管理2&I/Oシステム（6/17） 10. I/Oシステム（6/24） 11. ファイルシステム（7/1） 12. プロテクション＆セキュリティ (7/8) 13. バッチシステム＆分散システム&まとめ（7/22）

アドレス変換の例

• 例:ページサイズ＝4KB=2

12

，

仮想アドレス空間＝16bit（16ページ=4bit）

ページテーブル(16エントリ） ページテーブル ベースレジスタ ₀ 1 仮想アドレス： 0x1f40 = 0001 111101000000 0xf40

アドレス変換の例

• 例:ページサイズ＝4KB=2

12

，

仮想アドレス空間＝16bit（16ページ=4bit）

仮想アドレス： 0x1f40 = 0001 111101000000 : 0 1 60K=4K*15 : 0 1 0x1f40 他のページフレームは •別のページに割り当て •別のプロセスのページ に割り当て •未使用 xxxx

ページテーブルの置き場所

• 主記憶に置く？

– ページテーブルベースレジスタ → 実アドレス

• ページテーブルのアクセス

– 動的アドレス変換なし

• メモリアクセスをするために，更にページテーブルへのメモリ

アクセスが生じ速度が低下

➡仮想記憶をサポートするCPUに

TLB

• Translation Look-aside Buffer

– ページテーブルエントリの一部を置く高速なバッファ

• 一般的には連想メモリ(64〜256エントリ程度)で実現

– 並列検索機能 → 任意の一部のエントリを配置 – 大容量の連想メモリの実現は困難

• アドレス変換の際は，まず連想メモリを調査

• なければ主記憶のテーブル（TLBミス）

– 単に広いアドレス空間を使うだけでコスト発生

TLB

• Nレベルページマッピングテーブル（後述） をハードウェアで実現している場合 • CPUはTLBだけを持つ場合 – ソフトウェア（カーネル）でページテー ブルを管理 – TLBエントリに存在しないと、割り込み が発生 • カーネルは、TLBエントリを設定する – どういう方法があるか？

ページテーブルの大きさ

• ページサイズが4KBの場合

– ４GBの仮想アドレス空間全てをカバー

• 2

32

_{/4K=1Mエントリ/プロセス}

• メモリ空間を圧迫

– 64bitの仮想アドレス空間の場合

• 2

64

_{/4K=4Pエントリ=4Gエントリ×1024×1024}

• 主記憶に置くのは無理

• 全エントリ(=全仮想空間)を使うことは滅多になし

多重レベルページング セグメンテーションとの併用

Hierarchical Page Tables

• 論理アドレス空間を複数のページテーブルで管理する • 2レベルページテーブル

• 3レベルページテーブル

page number page offset

p_i p_{2 d}

10 10 12

page offset

仮想記憶の管理

• Demand Paging

• プロセス生成

• Page Replacement

• フレーム割り当て

• Thrashing

Demand Paging

• 必要に応じてページをメモリにロード • ハードウエアによる支援 – ページエントリにvalid-invalid bit属性がある – Valid-invalid bitが0の時、当該フレームをア クセスするとページ例外が発生 1 1 1 1

Page Fault

1. あるページが始めて参照 2. ページ例外が起こりカーネルに制御が移動 3. カーネルは、カーネル内のテーブルを参照 それがinvalidのとき、メモリ参照例外 メモリにロードされていないとき、空きフレームを確保 4. ディスクからメモリにロード 5. validation bit = 1. 6. 実行を再開

空きフレームがない時どうする？

• Page replacement

– あまり使われていないページを探し、その領域を２次記憶

（swap領域）にコピー（その領域を使用）

Demand Pagingの性能

• Page Fault Rate 0



p



1.0

– if p = 0 no page faults

– if p = 1, every reference is a fault

• Effective Access Time (EAT)

EAT = (1

–

p) * memory access

+ p * (page fault overhead

+ [swap page out ]

+ swap page in

+ restart overhead)

• Memory access = 100 ナノ秒, paging overhead = 25 ミリ秒とすると

– EAT = (1 – p) * 100 + p * 25 milli = 100 + 24,999,900*p

Demand Pagingの性能

• インストラクション（正確には異なるメモリ領域のアクセス）を1,000回実 行する毎にpage faultが起きると仮定するとp=0.001となり、一回の実行時間 は、約25マイクロ秒必要 • 実際には、ページが一度ロードされたら、そのページはメモリに存在(page outされない限り)

Demand Pageおよび仮想記憶の利点

• プロセス起動が高速化

– 起動前にプロセスイメージ全てをメモリ上に確保してディス

クからコピーしないから

– Copy-on-Writeによる子プロセス生成の高速化

• 次のスライドで説明

• 物理メモリ消費を低減

• Memory-Mapped Files

Copy-on-Write(COW)

• 子プロセス生成のシナリオ

– 親プロセスは、forkシステムコールで子プロセスを生成

• このときForkシステムコールは、親プロセスのコピーを生成

– 多くの場合、子プロセスは、execシステムコールを発行して親

プロセスとは違うプログラムを実行

• Forkシステムコールで生成された子プロセスは、親プロセスのイ

メージをコピーする代わりに、親のプロセスイメージ（ページ）

を共有

• どちらかのプロセスがページに書き込むとき、そのページをコ

ピー

Memory-Mapped Files

• Memory-mapped file I/O とは、ファイルの内容をメモリにマップ

することにより、メモリの読み書きでファイルの内容をアクセ

スできるようにする機能

• Readシステムコールでファイルの内容を読み込み、writeシステ

ムコールで書き込むという煩わしさがなくなると共に余分な

データコピーも減少

• 複数のプロセスにより

同一ファイルをメモリ上で

アクセス可能

空きフレームがない時どうする？

• Page replacement

– あまり使われていないページを探し、その領域を２次記憶

（swap領域）にコピーすることで、その領域を使用

Page Replacement

• ユーザプロセスがページを必要とする時、フリーフレームがないと・・・ – 使用しているページのフレームをswapデバイスにコピー – ページを必要としているプロセスのフレームとして使用 • どのページ（フレーム）を選択するか？ – この説明は後述 • 使用されていたフレームをディスクにコピーするかどうかの判断は？ – ページをページエントリにはmodify (dirty) bit属性が存在

• ページに書き込みにいくと、modify bitがセット

• カーネルは、このbitをみて、ページをディスクに書かなければいけな いか決定

ページ（論理ページ）：仮想メモリ上のブロック フレーム（物理ページ）：物理メモリ上のブロック

Basic Page Replacement

• ディスク上に保存してあるページを探索 • 空きフレームを:

– 空きフレームを見つけたら、そのフレームを使用

– 空きフレームがなければ、page replace algorithmを使って追い出すフレー ムを決定（これをvictimフレームと呼ぶ）

– Victimページをディスクに書き、ページテーブルを変更

• ディスク上のページの内容を空きフレームにコピーしページテーブルを変更 • プロセスを再開

Page Replacement Algorithms

• Page faultが少なくなるようなアルゴリズムを使いたい

• これ以降いくつかのpage replace algorithmsを紹介するが、いずれも以下のアクセス パターンにおけるpage faultの数を調査

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

• もちろんpage faultの回数は、どのくらいの物理フレームがあるかに依存

First-In-First-Out (FIFO) Algorithm

• アクセスパターン: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

• 3 frames

• 4 frames

9 page faults 10 page faults

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

1 1 2 1 2 3 4 2 3 4 1 3 4 1 2 5 1 2 5 1 2 5 1 2 5 3 2 5 3 4 5 3 4

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

1 1 2 1 2 3 1 2 3 1 2 3 1 2 3 5 2 3 5 1 3 5 1 2 5 1 2 4 1 2 4 5 2

補足

ページフォルト 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (FIFOキュー) • ページ番号0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4の順でアクセス – この列の名称：参照ストリング • ページフレーム数は３ • この例の場合ページフォルトは９回 ページフォルト ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (FIFOキュー) 0 0 0 3 1 1 1 2 2 ページフォルト ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (FIFOキュー) 0 0 0 3 3 1 1 1 0 2 2 2 ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (FIFOキュー) 0 0 0 3 3 3 1 1 1 0 0 2 2 2 1 ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (FIFOキュー) 0 0 0 3 3 3 4 1 1 1 0 0 0 2 2 2 1 1 ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (FIFOキュー) 0 0 0 3 3 3 4 4 4 4 4 4 1 1 1 0 0 0 0 0 2 2 2 2 2 2 1 1 1 1 1 3 3

Belady

’

s Anamoly

• FIFOでページフレーム数を増やすとかえってページ

フォルト数が増えることも

ページフォルト 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} 0 0 0 0 0 0 4 4 4 4 3 3

Optimal Algorithm

• 最も長い間使われないページを置き換え

• 4 frames

• どうやって未来のことがわかるのか?

• このアルゴリズムは開発したアルゴリズムの比較用に使用

6 page faults

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

1 1 2 1 2 3 4 1 2 3 1 2 3 4 1 2 3 4 1 2 3 5 1 2 3 5 1 2 3 5 1 2 3 5 4 2 3 5 4 2 3 5

補足

ページフォルト 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4}

• 最初のページ３へのアクセス時

– ページ２はページ0, 1よりも以降に再参照されるのでページ２を選択

• 最初のページ４へのアクセス時

– ページ3はページ0, 1よりも以降に再参照されるのでページ3を選択

• この例の場合，ページフォルト数は７回

ページフォルト ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページフォルト ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4}

補足

ページフォルト 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 ページフォルト ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 0 0 0 0 0 ページフォルト ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 0 0 0 0 0 0 0 ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 0 0 0 0 0 0 0 0 0 0 ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 0 0 0 0 0 0 0 0 0 0 0 0 未来が予測できないと 実現不可能

• 4フレームの場合

– ページフォールトは６回

• ４のアクセス時に３を出す理由は？

• 2回目の３のアクセス時に０を出す理由は？

Least Recently Used (LRU) Algorithm

• アクセスパターン: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

• Counter implementation

– 各ページエントリがカウンタを持ち、ページがアクセスされ

るたびにクロックの値をコピー

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

1 1 2 1 2 3 4 1 2 3 1 2 3 4 1 2 3 4 1 2 5 4 1 2 5 4 1 2 5 4 1 2 5 3 1 2 4 3 5 2 5 3

補足

• Least Recently Used

• 過去，最も長い間使用されていないページを置き換え

• 過去の履歴から判断

• 時間的局所性を持つプログラムに適す

– 一般的には当てはまる

• 最もよく使用されるページ置換え方法

– 正確に実現するのはオーバヘッド大 or ハードウェアの高コスト化 – 実際には近似アルゴリズムを利用 • 正確さとオーバヘッドのトレードオフ

補足

ページフォルト 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (LRU)

• 3フレームの場合

– ページフォルト数は１０回 ページフォルト ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (LRU) 0 0 0 3 1 1 1 2 2 ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (LRU) 0 0 0 3 3 3 4 4 4 0 1 1 0 0 0 0 0 0 2 2 1 1 1 1 ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (LRU) 0 0 0 3 3 3 4 4 4 2 2 2 1 1 1 0 0 0 0 0 0 3 3 2 2 2 1 1 1 1 1 1 4

補足

ページフォルト 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (LRU)

• 4フレームの場合

– ページフォルトは8回

• 2ページと4ページに無駄な出し入れ

– 履歴なので実現可能 ページフォルト ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (LRU) 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 4 ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (LRU) 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 4 4 4 4 ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (LRU) 0 0 0 0 0 0 0 0 0 0 0 4 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 4 4 4 4 3 3

ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (FIFO) 0 0 0 1 2 3 0 0 0 1 4 4 1 1 2 3 0 1 1 1 4 2 2 2 3 0 1 4 4 4 2 3 3

FIFO vs LRU

ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4}

9回

10回

FIFO vs LRU

10回

8回

ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (LRU) 0 0 0 0 0 0 0 0 0 0 0 4 1 1 1 1 1 1 1 1 1 1 1 ページフォルト ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ 参照ストリング _{0 1 2 3 0 1 4 0 1 2 3 4} ページ枠の内容 (FIFO) 0 0 0 0 0 0 1 2 3 4 0 1 1 1 1 1 1 2 3 4 0 1 2 2 2 2 2 3 4 0 1 2 3 3 3 3 4 0 1 2 3 4

LRUの実現：カウンタ

• CPUにカウンタを用意 (ハードウェア)

– 主記憶参照の度にカウンタをインクリメント

• ページテーブルの各エントリにカウンタ保存フィールド

– メモリ参照の度に，カウンタの値を保存フィールドに記録 (ハ

ードウェア)

• ページフォルト時

– ページテーブルで最小カウンタのページを探索

LRUの実現：スタック

• アクセスされたページ番号をスタックで保持

– アクセスされたページのページ番号をスタックトップに置

くように管理 (ハードウェア)

• ページアウト時には，そのページ番号をスタックから削除

– ページフォルト時は，スタックの底のページ番号を選択

– ページテーブルの検索が不要

LRUの実現：行列

• n×nビットの行列を用意 (n: ページフレーム数)

– 初期値は全てを0

– ページフレームkの参照時

• k行を全て1, k列を全て0 • 行を2進数とみて最小 → 最長不使用 (追い出し)

0 1 2 3 0 0 1 0 0 1 0 0 0 0 2 1 1 0 0 0 1 2 3 0 0 1 0 0 1 0 0 0 0 2 1 1 0 1 0 1 2 3 0 0 1 1 0 1 0 0 1 0 2 0 0 0 0 0 1 2 3 0 0 1 1 1 1 0 0 1 1 2 0 0 0 1 0 1 2 3 0 0 0 0 0 1 1 0 1 1 2 1 0 0 1 0 1 2 3 0 0 0 0 0 1 1 0 0 0 2 1 1 0 1 3 1 1 0 0 0 1 2 3 0 0 0 0 0 1 1 0 0 0 2 1 1 0 0 3 1 1 1 0 0 1 2 3 0 0 0 0 1 1 1 0 0 1 2 1 1 0 1 3 0 0 0 0

LRUの実現：行列

0 1 2 3 0 0 1 1 1 1 0 0 0 0 2 0 0 0 0 3 0 0 0 0 0 1 2 3 0 0 0 1 1 1 1 0 1 1 2 0 0 0 0 3 0 0 0 0

• 参照列

– 0, 1, 2, 3, 2, 1, 0, 3, 2, 3

LRUの近似：参照ビット

• ページに関する状態ビット（統計値の収集）

– ページテーブルエントリ中に保持

• 参照ビット(R)と変更ビット(M)

– ハードウェアがメモリアクセス時に該当ビットをセット

• ソフトウェアがリセットするまで1

– ソフトウェア的なシミュレートも可能

• 参照時：ページフォルト…表に記録、RO設定 • 変更時：ROのためページフォルト…表に記録

LRU Approximation Algorithm

• Reference bitを使ったアルゴリズム

– 各ページエントリにreference bit（初期値0）

– ページがアクセスされるとreference bitを1にセット

– Reference bitが0のページがvictim page

LRU Approximation Algorithm

• Second chanceアルゴリズム

– reference bitを使用

– Victim pageにしようとしているページのreference bitが1の時

• reference bitを0に

• ページをメモリに残しておく

• clock orderで次のページにもこの規則を適用 • reference bitが0ならばvictim pageに

LRU Approximation Algorithm

最前未使用(NRU)アルゴリズム

• 最近使っていないもの (Not Recently Used)

– プロセス開始時には全てのページビットは0 – 定期的 (クロック割込等) に R ビットを 0

• ページフォルト時

– 全ページのR/Mビットを調査 – 最も低いクラスから無作為に追い出し class 0 参照されておらず、変更もされていない

セカンドチャンスアルゴリズム

• FIFOの修正

– 最も古いページ (リストの先頭) のRビットを参照

• 0: そのまま追い出し • 1: リストの末尾に繋ぎ、R=0にする – 全てのページがR=1の時、一巡後にFIFOに A (0) (3)B (7)C (8)D (12)E (14)F (15)G (18)H A B C D E F G H

クロックアルゴリズム

• リストのエントリ 入れ換えなし – つまり「循環リスト」 – 最初に主記憶に入れた並び順 • 最も古いページの ページ番号を指すポインタ – ポインタが指すページの 参照ビットが • ０： 選択し針を進める • １： 参照ビットをクリアし 針を進める A B D I J L K C E Dを 追出し Kを 追出し

低使用頻度(NFU)アルゴリズム

• 使用頻度の少ないもの (Not Frequently Used)

– 各ページに対応するソフトウェアカウンタ

– クロック割込 or ページフォルト毎に

• メモリの全ページを調査 • Rビット分カウンタ加算 (R=1なら加算)

– カウンタの最も小さいものが追い出し候補

V … R ページ番号 カウンタ 1 1 10 1 0 6 0 0 0 1 0 8 1 1 5 0 0 0 V … R ページ番号 カウンタ 1 1 10 1 0 6 0 0 0 1 0 8 1 1 5 0 0 0 V … R ページ番号 カウンタ 1 0 11 1 0 6 0 0 0 1 0 8 1 0 6 0 0 0

カウンタ カウンタ カウンタ カウンタ カウンタ

エージングによる擬似LRU

• NFUは途中でresetなし

– 昔の影響を受けすぎるから (ex. 2パスコンパイラ)

• クロック割込 or ページフォルト毎に

– 1bit右にシフトして、最左端ビットに加算

R 1 0 1 カウンタ 1000 0000 0000 0000 1000 0000 R 1 1 0 カウンタ 1100 0000 1000 0000 0100 0000 R 1 1 0 カウンタ 1110 0000 1100 0000 0010 0000 R 1 0 0 カウンタ 1111 0000 0110 0000 0001 0000 R 0 1 1 カウンタ 0111 1000 1011 0000 1000 1000

フレーム割り当て

• プロセスを実行するのに必要な最小ページ数が存在

• 例えば、データのコピー

• プログラムが入っているページ • スタックページ • コピー元のページ • コピー先のページ

• もし、フレームが３つしかなかったらどうなる？

• フレーム割り当て法

割り当て法（３つ）

1. Equal allocation

– 例：100フレーム，5プロセスのとき，各プロセスに20フ

レーム割り当て

2. Proportional allocation

– プロセスのサイズに従って割り当て

m s p a m s S p s i i i i      



for allocation frames of number total process of size 5 64 137 10 127 10 64 1 2       a s s m i

Global vs. Local Allocation

• Global replacement

–

各

プロセスは置き換えるページフレームを選ぶ際，すべて

のページフレームから選択可能

•

あるプロセスが他のプロセスのフレームを取得可能

• Local replacement

– それぞれのプロセスは置き換えるページフレームを選ぶ際，

決められたページフレームの集合からのみ選択可能

補足

• 複数プロセスにそれぞれ仮想アドレス空間

– 追い出しの対象 (=割付けの候補）は？

A0 10 A1 8 A2 4 A3 7 A4 3 A5 5 A6 6 B0 4 B1 5 B2 2 B3 3 B4 6 

大域ページ置換



global replacement

 他のプロセスも含めて全 域から割り当て 

局所ページ置換



local replacement

A0 A1 A2 A3 A7 A5 A6 B0 B1 B2 B3 B4 A0 A1 A2 A3 A4 A5 A6 B0 B1 A7 B3 B4

ページングの利点

• 外部断片化がなし

• 主記憶の大きさに依存しないアドレス空間

– プロセス毎に独立

• 実際に使用するページのみを主記憶に配置

– 主記憶の利用効率の向上

– 主記憶容量を超える記憶領域

• マルチプログラミングの多重度増 ➡CPU利用率の向上

参照の局所性

• locality of reference

• 短期的なページアクセスに多く見られる傾向

– 少数のページを集中的にアクセス

• 長期に渡るとそうでない場合も

• 少量の高速メモリでも処理を高速化

– キャッシュ ー メモリ

– メモリ ー ２次記憶

– TLB ー ページ表

)

参照の局所性

1.0 1.0 0.5 0.5 ページフォルト率 各プロセスで主記憶に存 在するページの割合 ランダムなアクセス 局所的なアクセス

時間的局所性

• 最近アクセスされたページは近い将来にも

アクセスされる確率が高

– プログラムのループの部分

• コードは同じ部分を繰り返し参照 • 同じ制御変数を繰り返しアクセス

– 他にも関数の引数や局所変数

main() ... printf() ...

空間的局所性

• 近くのページがアクセスされる確率が高

– 配列の要素

– 関数呼び出しのないプログラムコード

– 制御スタック（関数呼出し時に伸び縮み）

• 関連する変数の領域を近くに配置

– 空間的局所性に寄与

for (i=0; i < SIZE; i++) {

main() ... printf() ... k[ ]

Segmentation

• ユーザから見るとメモリ領域は、様々な意味のある塊

– プログラム

– 変数

– スタック

• セグメントとはこのような塊

Logical View of Segmentation

1 3 2 4 1 4 2 3

Segmentation Architecture

• 論理アドレスはセグメント番号＋セグメント内オフセット

<segment-number, offset>

Segmentation with Paging

Intel ｘ86

Working-Set Model

•   working-set window

• WSS_i (working set of Process P_i) = もっとも最近の時間内にアクセスされたページ群 –  が小さすぎると，全体の網羅は不可能 –  が大きすぎると，局所的には網羅が可能 –  =   プログラム全体を包含 • D =  WSS_i 要求されるフレームの合計 • if D > m  Thrashing状態 – プロセスをサスペンド 参照回数 ＝１０の場合

補足

• working set model

• ワーキングセット

– プログラムが使用しているページの集合

– 主記憶にあればページフォルトは殆ど発生なし

• 効率よく実行するために主記憶に置きたい

• ワーキングセットモデル

– 各プロセスのワーキングセットを記録

– プロセス実行前に対応するメモリ中への存在を確認

• 時刻tにおけるW(t, w)の定義

– [t-w, t]の間にアクセスされるページ集合 – ここでの時間：他のプロセスが実行中の時間は含めず – W＝「ワーキングセットのウィンドウサイズ」

補足

•

ワーキングセットモデルでは，W(t, w) をワーキングセット

ウインドウサイズ _w t t-w

遷移 ワーキングセッ ト2 遷移

補足

• プログラムの典型的な実行パターン：

– ある部分をしばらく実行すると，次の部分移行

• ex) コンパイラのパス

– ワーキングセットモデルでは，これを考慮する必要あり

ワーキング ワーキング 遷移 ページ数

Thrashing

• Thrashing（スラッシング）

– プロセスが頻繁にページイン・アウトを繰り返すこと

• マルチプログラミングの多重度を向上

– CPU利用率／スループットが向上 • プロセス単体の処理時間：増加 • システム全体の性能：向上

• 多重度を上げすぎるとページフォールトが多発

– CPU利用率の急激な減少 頻繁に使用するページ数＞ページフレーム総数

Thrashing

• なぜページングはうまくいく?

Locality model

– プロセスはある場所からほかの場所へ移動

– その場所は重複しているかも？

• Thrashingはなぜはっせいするのか?

バッキングストア

• どこにある？

– 一般にHDDの一部

• 固定領域・主記憶より大 • ファイル・主記憶より小 (部分的な待避) 主記憶 0

UNIXの仮想アドレス空間

• 多くのUNIXは左のような

配置（Linux, FreeBSD）

– 0〜3GBがユーザ プロセス空間 – exec直後のtext, dataバッキン グストアは実行ファイル自体 text

data

stack

0x0000000 0xC000000

bss

kernel text, data text

data

header symbol table

実行ファイル

（ディスク中）

ページテーブルは

Copy-on-Write

• data領域などは読み書き可能

– 実行可能ファイルをバッキングストアにして大丈夫？ – 書き換えちゃったら・・・？ – 同時に読み書きしたら・・・？ – 書き込みが行われた時にページを確保・コピー text data read read write text data header read-only read-only text data write text data header read-only read-only

プログラムコードやライブラリの共有

• プログラムの部分は一般に書き換え不可なので

主記憶の一部を共有して，省メモリ化が可能

:

0 1 15

:

0 1 15

:

0 1 15

sbrkシステムコール

• void *sbrk(増分)

– データ領域（アドレス空間）を「増分」バイト増やすシス

テムコール

• 主記憶を直ちに確保するわけではない text データ 決められた上限まで使用可 sbrk()等で明示的に拡張しない限り，「データ」 領域を超えてアクセスは不可能 sbrk(0)

malloc()/free() ープログラムから見たメモリ管理ー

• sbrkによってメモリを確保（mmapを使うことも…）

• free()された領域の管理 … リスト等で空き領域管理

– free()された空き領域 → 足りるならそこから確保 • first-fit, best-fit等の方法で – 空き領域がなければsbrk

• OSの機能（システムコール）を利用したライブラリ関数

– OSが提供するものと異なる実装を用いても○ • cf. K&Rの単純な実装例 – 割当て･解放，断片化，局所性等の性能は実装依存

mmapシステムコール

• 任意のファイル

を仮想アドレス空間にマップ

– ページフォルトで必要部分を（OSによって）読み込み

• void *mmap(void *start, size_t length,

int prot, int flags, int fd, off_t offset);

– start:このアドレスからマップ • ページサイズの整数倍, 0ならmmapに任せる – length:マップする長さ – prot:PROT_EXEC,PROT_READ,PROT_WRITE – flags:MAP_SHARED,MAP_PRIVATE（COW) – fd:マップするファイル記述子

マップする位置について

text data bss sbrk(0) こういう部分にも マップが可能 この部分のPTEは用意 しなくてよい（cf. 多段 ページテーブル）

/* stdio.h, sys/mman.h, unistd.h, sys/types.h, sys/stat.h, fcntl.hをインクルード */ main() { int fd; char *p; /* getpagesize() のファイルをあらかじめ用意 */ fd = open("output", O_RDWR|O_CREAT, 0600); if ((int)(p = mmap(0, getpagesize(),

PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0)) == -1) { perror("mmap"); exit(1); } printf("%c¥n", p[100]); p[0] = 'a'; p[100] = 'b';

Windowsの仮想アドレス空間

• x86 Windows の標準で

は2GBのユーザ空間

• 起動時オプションで

3GBを指定可能

• XP, Server 2003 は2GB

〜3GBの間で指定可能

0x00000000 0xC0000000 1GB system 3GB user space 2GB user space kernel, executive

process page table, hyper space

Page faultに関するその他

• Program structure

– int A [1024][1024];

– Program 1

for (j = 0; j < 1024; j++)

for (i = 0; i < 1024; i++)

A[i][j] = 0;

– Program 2

for (i = 0; i < 1024; i++)

for (j = 0; j < 1024; j++)

A[0][0]

A[0][1]

A[0][2]

….

A[1][0]

…..