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

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

加藤 真平

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

[email protected]

１．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/9） 2. プロセス管理（4/16） 3. プロセス間交信＆スレッド（4/23） 4. プロセス同期（5/7） 5. プロセス同期（5/14） 6. CPUスケジューリング （5/21） 7. CPUスケジューリング （5/28） 8. メモリ管理（6/4） 9. メモリ管理＆I/Oシステム（6/11） 10. I/Oシステム（6/18） 11. ファイルシステム（6/25） 12. プロテクション＆セキュリティ (7/2) 13. バッチシステム＆分散システム＆まとめ（7/9） 14. 試験（7/23） 論文も読んでみましょう。 ACM SOSP USENIX OSDI USENIX ATC USENIX NSDI ACM ASPLOS

メモリ管理

• プログラム実行までの道のり

• Swapping

• 連続メモリ領域割り当て

• Paging

• Segmentation

Static vs dynamic

• Static Linkの問題点

– ファイルサイズの肥大化 – ライブラリにバグがあった時、リ_{ンクしなおす必要}

$ cc –static foo.c $ file a.out

a.out: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), for GNU/Linux 2.6.8, statically linked, not stripped

$ size a.out

text data bss dec hex filename

499682 1928 6948 508558 7c28e a.out #include <stdio.h> int main() { printf(“Hello¥n”); return 0; } foo.c $ cc foo.c $ file a.out

a.out: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), for GNU/Linux 2.6.8, dynamically linked (uses shared libs), not

stripped $ size a.out

text data bss dec hex filename

補足

• 静的再配置(static relocation)

– 配置は主記憶へのロード時 • ロード後のプログラムの位置変更は不可能

• 動的再配置(dynamic relocation)

– プログラム実行中に再配置 • ロード後のプログラムの位置変更は可能 • 再配置可能なコード – 再配置レジスタ • ベースレジスタ OS領域 ユーザ領域 未使用領域 0 番地 n 番地 主記憶 α番地 α+p 番地 アドレス変換機構 α A α+A 番地

プログラム実行までの道のり

メモリの使用量を減らす工夫

• Dynamic Linking – 実行時にライブラリのリンク – リンク時には、実行時にライブラリリンクする ためのルーチンとリンク – ファイルとして保存される実行イメージ小 $ cc foo.c $ size a.out $ file a.out $ cc –static foo.c $ size a.out

プログラム実行までの道のり

メモリの使用量を減らす工夫

• Dynamic Loading

– サブルーチンが呼ばれるまでメモリ上

にコピーなし

– 必要ないルーチンは呼ばれないのでメ

モリ使用率 高

$ cc foo.c $ size a.out $ file a.out $ cc –static foo.c $ size a.out $ file a.out

プログラム実行までの道のり

メモリの使用量を減らす工夫

• Shared Libraries – Dynamic Linking機能を利用してライブラリを提供 – ライブラリのバグフィックスに対応可能 – プログラムのリンク時にshared librariesを使うかリ ンクしてしまうか決定

• Linux gnu Cコンパイラの場合、defaultはshared libraries $ cc foo.c $ size a.out $ file a.out $ cc –static foo.c $ size a.out

Dynamic Linking

#include <stdio.h> #include <dlfcn.h>

int main(int argc, char **argv) {

int (*f)(void); void *dl;

char *error; int val;

if (argc != 2) error_exit(“The library name must be specified¥n"); dl = dlopen(argv[1], RTLD_NOW);

if ((error = dlerror()) != NULL) error_exit(error); f = (int (*)(void)) dlsym(dl, "mylib");

if ((error = dlerror()) != NULL) error_exit(error); val = f();

printf("return value = %d¥n", val);

dlclose(dl); return 0; } dtest.c int mylib() { return 10; } mylib.c

all: mylib.so dtest dtest: dtest.c

cc -o dtest dtest.c -ldl mylib.so: mylib.o

ld -shared -o mylib.so mylib.o mylib.o: mylib.c

cc -fPIC -c mylib.c Makefile

$ make

Linuxにおける共有ライブラリ(1/2)

• バイナリファイルはELF (Executable and Linking Format)

• カーネルは、execvシステムコール内において – ファイル(ここではa.outとする)のフォーマットを検査 • 128バイト読んで決定 – ELFならば/lib/ld-linux.soを実行 – /lib/ld-linux.soプログラム内でa.outが使用する共有ライブラリを調べ、 • SHAREでライブラリをメモリマップすることにより、物理的には一 つのイメージのみ使用 – メモリマップに関しては、メモリマップドファイルを参照あるい は、man mmap • 再配置が必要ならば再配置 • 初期化関数を呼び出し

Linuxにおける共有ライブラリ(2/2)

• 最近のアプリケーションは沢山の共有ライブラリを使用 例： $ ldd ‘which emacs’ $ ldd /usr/lib/mozilla-XXX/mozilla-bin • 沢山の共有ライブラリを動的にリンクするのは時間が必要 • Linuxでは、prelinkというコマンドによって、共有ライブラリのアドレス解決 をあらかじめしておくということが可能 – Prelinkはデーモンで起動 • 時々、負荷が上がるのはprelinkが動いているかもしれない？ • /etc/prelink.confで定義されているダイナミックリンクライブラリのロ ードアドレス決め、あらかじめ参照関係を解決 • 参考 – man prelink – man readelf – man objdump – glibc source – prelink source

メモリの使われ方

カーネル領域 mmap領域 ユーザ text, data,bss 領域 スタック 0x00000000 0x40000000 0xc0000000 0xffffffff #include <stdio.h> #include <stdlib.h> #define SIZE (1024*8192) int a; int b = 10; int main() { int *cp; char ia[SIZE]; cp = malloc(sizeof(int)); return 0; } スタックサイズに注意 bss data スタック heap このプログラムは segmentation fault

オーバレイ（Overlays）

• プロセスのメモリ領域が足りない時に、メモリ領域を処理に応じて複数の目 的で使用 • 以下の例では、 – Pass1プログラムがメモリにロードされて実行 – その後、今度はpass2プログラムを同じメモリ領域にロードして実行

補足

• プログラムを６つのモジュールに分割

– M1はM2, M4, M6から 使用される関数・データ を包含 – M2はM3から使用

• プログラム全体を主記憶に置くには150Kの領域が必要

• （ある時点で）必要なモジュールのみを主記憶に置くので

あれば:

– M1, M2, M3 (60K) – M1, M4, M5 (70K) モジュール化はユーザが決定 ⇒実現の手間が大きい モジュールM1 (20K) モジュールM4 (20K) モジュールM5 (30K) モジュールM2 (30K) モジュールM3 (10K) モジュールM6 (40K)

Swapping

• メモリが足りなくなり、プロセスが動けなくなったとき

• プロセスイメージを一時的に2次記憶に退避(swap out)

• その代りに、2次記憶上に退避していたプロセスイメージを主記

憶に復元(swap in)

補足

バッキングストア

• 待ち状態でメモリ・CPUを有効に活用

• スワップアウト

– 待ち状態プロセスの待避 – 2次記憶（バッキングストア） • 主記憶の内容やレジスタ等を退避

• スワップイン

– 退避したプロセスを主記憶に復元

• CPUスケジューラとの連携

OS領域 ユーザ領域 未使用領域 0 番地 n 番地 主記憶 プロセス1 プロセス2 プロセス1 プロセス2 スワップイン スワップアウト

連続メモリ領域の管理方法

• ２つのメモリ領域 – カーネルが使用：主記憶になければならない – ユーザプロセスが使用 • Multiple-partition allocation – Hole – 割り当て可能な連続するメモリ領域。様々なサイズのholeが発生 – プロセスがメモリ上に作られるとき、そのプロセスイメージが収まるに十 分なメモリ領域を割り当て – カーネルは割り当てた領域、フリー領域を管理 a) allocated partitions b) free partitions (hole)

OS process 5 process 8 process 2 OS process 5 process 2 OS process 5 process 2 OS process 5 process 9 process 2 process 9 process 10

動的連続メモリ領域割り当て問題

•

フリーなholeから大きさ

n

のメモリ領域をどのように探すか？

– First-fit: 要求しているサイズに最初にマッチしたholeを割り当て – Best-fit: 要求しているサイズにマッチする一番小さいholeを割り当て リストはサイズ順に並べられている必要あり – Worst-fit: 一番大きいholeを割り当て

• First-fit, best-fitがworst-fitより良

Fragmentation

• External Fragmentation

– トータルメモリ領域はあるが、連続領域としては存在しない

• Internal Fragmentation

– 割り当てられたメモリは要求したメモリよりも大きく、使用しない無駄 なメモリ領域がある

• Reduce external fragmentation by compaction

– メモリの内容を移動してコンパクション – I/O problem

補足

• 主記憶をいくつかの固定サイズの区画（partition）に区分

– ジョブスケジューラによる割り付け – システムに到着したジョブ（＝プロセス）はジョブキューへ – 十分な大きさの区画があればそこへジョブをロード • 無ければ空き区画ができるまで待機 • ジョブが終了すると，使用していた区画を解放 中 大 小

補足

• 必要とする容量より大きく最も近い大きさの区画を選択

– 各区画にキューを用意

• ジョブの大きさでロードする区画があらかじめ決定

– 絶対番地形式でも適用可 – 空き区画があっても、利用できないことも – 区画1+区画2≠30K区画 空き区画があるにもかかわらず使用不可の状況 → 外部断片化（external fragmentation） 0 番地 n 番地 主記憶 OS領域 区画1 (10K) 区画3 (30K) 区画2 (20K) 5K 8K 16K 12K 15K 27K 24K 区画1のジョブキュー 区画2のジョブキュー 区画3のジョブキュー

補足

• キューは1つで各ジョブは再配置可能

• 再配置方法・CPUスケジューリング等の組み合わせ

– 静的再配置・動的再配置 – スワッピングの利用 – FCFS・優先度スケジューリング 0 番地 主記憶 OS領域 区画1 (10K) 区画3 (30K) 区画2 (20K) ジョブキュー ジョブ1 9K ジョブ2 30K ジョブ3 8K ジョブ4 15K

補足

• FCFSで割当て

– ジョブ１：区画1 ジョブ2：区画３

• ジョブ3には：

1. 空いた区画の中で収まる最小区画 ⇒ 区画２ • 区画内の空き領域が大きい： 内部断片化（internal fragmentation） 2. 収まる最小区画を選択し空くまで待機 ⇒ 区画１ • ジョブ4は区画2で実行可能だが待機(FCFS) – しかし方法1が優れているとは必ずしもいえない • ジョブ１：短，ジョブ３：長の場合 … 待った方が良い？

• FCFSスケジューラの修正

– 割当て待ちはスキップして次のジョブをスケジュール • ジョブ3をスキップしてジョブ4に区画２を割り当て

可変区画割付け

• 固定区画割付けの問題点

– 断片化による主記憶利用率の低下

• 区画を可変サイズで管理

– システム起動時：ユーザ領域全体で１区画 – ジョブが到着毎に • 十分な大きさの空き領域を探索 • 必要な分だけ割付け、残りは空き領域

➡ 空き領域と使用中領域のリストを保持

可変区画割付け

• ユーザ領域: 500K

– ジョブ１: 200K – ジョブ２: 100K – ジョブ３: 160K – ジョブ４: 130K – ジョブ５: 100K

• 1～5の順で到着

• FCFSスケジューリ

ングの場合

OS JOB1 (200K) JOB2 (100K) JOB3 (160K) 未使用 (40K) OS 未使用 (200K) JOB2 (100K) JOB3 (160K) 未使用 (40K) JOB4 (130K) OS 未使用 (70K) JOB2 (100K) JOB3 (160K) 未使用 (40K) OS 未使用 (170K) JOB3 (160K) 未使用 (40K) JOB4 (130K) JOB5 (100K) OS JOB3 (160K) 未使用 (40K) JOB4 (130K) 未使用 (70K) JOB1 終了 JOB4 割付 JOB2 終了 JOB5 割付 550K 0 50K 250K 350K 510K 550K 0 50K 250K 350K 510K 550K 0 50K 250K 350K 510K 180K 550K 0 50K 350K 510K 180K 550K 0 50K 280K 350K 510K 180K

可変区画割付け

• 可変区画割付けで主記憶の利用率は向上

– 内部断片化はほとんどなし？

– しかし外部断片化は生じ得る

• (c)において70K+40K=110Kの空き領域 – ジョブ５を実行するのに十分な大きさ – 連続領域でないのでロード不可

⇒ 解決策：コンパクション

OS JOB1 (200K) JOB2 (100K) JOB3 (160K) 未使用 (40K) OS 未使用 (200K) JOB2 (100K) JOB3 (160K) 未使用 (40K) JOB4 (130K) OS 未使用 (70K) JOB2 (100K) JOB3 (160K) 未使用 (40K) JOB1 終了 JOB4 割付 コンパク ション JOB5 割付 0 50K 250K 350K 510K 0 50K 250K 350K 510K 0 50K 250K 350K 510K 180K 0 50K 290K 390K 180K 0 50K 280K 290K 390K 180K

コンパクション (compaction)

• 使用中領域を詰めて

１つの大きな空き領域

• 断片化の問題は解消

– 動的再配置が必要 – 最適化中のシステム停止 OS 未使用 (110K) JOB3 (160K) JOB4 (130K) JOB2 (100K) JOB5 (100K) OS JOB4 (130K) JOB3 (160K) JOB2 (100K) 70K+40Kの連続領域 ジョブ２の終了を待たずに割当て可

可変区画割付け: 空き領域管理

• 空き領域の大きさ・位置情報をリストで保持

– 種々の大きさの空き領域が散在

• ジョブ到着時にリストを探索

– 空き領域が大きい時は余りを空き領域

• ジョブ終了時に領域を空き領域リストに追加

– 別の空き領域が隣接していれば連結

– できるだけ大きい空き領域

可変区画割付け: 空き領域割当て

• どの空き領域を使う？

• 先頭一致（first-fit）

– 最初の十分な 大きさの領域

• 最良一致（best-fit）

– 最も大きさの 適合する領域

• 最悪一致（worst-fit）

– 最大の空き領域 ✓

高速

✓

リストの最後の方に，大

きな領域 (断片化の回避)

✓

大きな空き領域を残す

✓

小さな空き領域の多発

✓

余った領域は割と大きい

✓

小さな空き領域の回避

仮想記憶

• 物理メモリ量以上のメモリを仮想的に作成

• 仮想的にみえるので仮想記憶

• 仮想アドレス：仮想記憶上のアドレス

• 物理アドレス：物理メモリ上のアドレス

未使用

仮想記憶

• 主記憶より大きな記憶領域

– ２次記憶の利用 仮想記憶 オーバレイ 入れ替え 入れ替え •個々のモジュールの アドレス空間を意識 •最適な入れ替えが可能 •プログラム全体で一つの 空間と認識 •入れ替えの無駄が起きる 可能性

仮想記憶

バッキングストア OS領域 0 番地 n 番地 主記憶 プロセス1 の一部 プロセス1 プロセス2 プロセス２ の一部

• 各プロセスに独立したアドレス空間

– 全て同じ大きさ

• 実アドレス空間

– real address space

– 主記憶のアドレス空間

– 最初は連続しているが・・・

• 仮想(論理)アドレス空間

– virtual address space

– 仮想記憶のアドレス空間

– プロセス／プログラムが参照するアドレス – 連続した1つの空間に「見せかける」

仮想記憶

バッキングストア OS領域 0 番地 n 番地 主記憶 プロセス1 の一部 プロセス1 プロセス2 プロセス２ の一部 • 32bitの仮想アドレス空間 – 最大4GB • 論理的に必要なメモリ空間 – 4GB×プロセス数 • 主記憶には一部だけ – 仮想空間の残りの部分は２次記憶 のスワップ領域 – 大容量のディスクを使って広大な メモリを持っているように「見せ かける」 アドレス変換 プログラムのk番地 ≠ 主記憶のk番地

仮想記憶の全体構成

0 0xff...ff 主記憶 0 xx...xx ２次記憶 CPU MMU (メモリ管理 ユニット) 仮想アドレス 物理アドレス 仮想アドレスから 適切な物理アドレスへ 変換 各プロセスに 広いアドレス空間 独立した空間 主記憶に入らない 当面の使用無し → 2次記憶へ 必要な部分を主記憶に保存 （プロセス切り替えでも 入れ替えない）

動的アドレス変換

• 仮想アドレスと実アドレスの対応

– バイトやワード単位？

• 主記憶以上の領域が必要

– ブロック単位で対応

• セグメンテーション – セグメント…可変長のブロック • ページング – ページ…固定長のブロック

動的アドレス変換

• 仮想アドレス v = • b: ブロック番号 → アドレス変換テーブル(対応表)のインデックス • d: ブロック先頭からのオフセット b d x アドレス変換テーブル アドレス変換テーブル ベースレジスタ b’ + d x b .. . . . . b’ b d 仮想アドレス v ブロック番号 相対位置 実アドレス r . . . . . . b’ d r 主記憶 仮想アドレス空間上の ブロックがどこにあるか

Paging

• プロセスの論理アドレス空間は物理メモリ上連続である必要なし

• 物理メモリを固定長のブロックにして管理

– このブロックは「フレーム」 – ブロックの長さは２のべき乗（512bytesから8Kbytesが主流だが、最近は 128MBytesにできるマシンも）

• 論理メモリ領域も同じサイズに分割

– この単位はページ

• 全てのフリーフレームを管理

• nページ必要なプログラムを動かすには、n個のフリーフレームを

確保して、ページテーブルをセット

• Internal fragmentation

補足

主記憶 (ページフレームの集まり) 二次記憶 仮想アドレス空間 ページイン ページアウト

• paging

• 主記憶を固定長ブロックに分割

– ページフレーム

• 仮想アドレス空間も，

同サイズのページに分割

• 動的アドレス変換を使用

• ページ単位で

主記憶-２次記憶間のやりとり

補足

主記憶 (ページフレームの集まり) 二次記憶 仮想アドレス空間 (ページの集まり) ページイン ページアウト

• ページフォルト

– page fault – 主記憶に存在しない ページをアクセスした ときに発生する割込み – ハードウェアの機能 – 割込みハンドラ • ページイン （OSの処理）

補足

主記憶 (ページフレームの集まり) 二次記憶 仮想アドレス空間 ページイン ページアウト

• ページイン（page in）

– ページを２次記憶から 主記憶上のページフレーム に移動

• ページアウト（page out）

– ページを２次記憶へ退避 – 空きページフレームが 足りなくたった時 – ページイン後，内容を 変更していない • ページの解放のみ

ハードウエアによるアドレス変換機構

Memory-Management Unit (MMU)

• Page Mapping Tableによる変換

– 各エントリは物理アドレスと属性を保持

• 属性：Access Permission, Modified, Referenceなど – Access Permission • ユーザモードにおけるread/write • 特権モードにおけるread/write プロセスのページ表ポインタ オフセット 論理ページ番号 フレーム番号 メモリ Ｖ Ｉ Ｖ

補足

ページテーブル b 仮想アドレス v 仮想ページ 番号 (オフセット)相対位置 実アドレス r b’ d 主記憶 b’ 1 xxx ０ ０ ０ a’ 1 yyy d b d b’ r = f × ページサイズ _{+ d} r = f << n | d (ページサイズ_{: 2}n₎

• 有効ビットが０: ページフォルトが発生（OSに遷移）

– ２次記憶から 主記憶の空いたページフレームに転送 – そのページフレーム番号 f をPTEに設定．有効ビットを１ ページテーブル

補足

• 仮想アドレス

v=(p, d)

– p : ページ番号 – d : ページ内オフセット

• ページ番号

p

のページテーブルエントリ(PTE)を参照

有効ビット 2次記憶アドレス ページフレーム番号 f • 有効ビット（サイズは１bit） • １ならページが主記憶に存在 • ０なら２次記憶に存在（ページアウト） • ページの共有 = ２次記憶アドレスとページフレーム番号の共有 • 他に保護属性等の情報（全てのアクセスはPTE経由） ブロック ＝ ページ アドレス変換テーブル ＝ ページテーブル

ページテーブルと物理アドレス

• 仮想空間 (64KB:16bit), 物理メモリ(32KB:15bit), ページ4KB 3 5 2 0 4 x x x 1 7 x x x x 0-4K 4-8K 8-12K 12-16K 16-20K 20-24K 24-28K 28-32K 32-36K 36-40K 40-44K 44-48K 48-52K 52-56K 仮想アドレス スペース 0-4K 4-8K 8-12K 12-16K 16-20K 20-24K 24-28K 28-32K 物理メモリ アドレス 仮想アドレス 011 101 010 000 100 000 000 000 001 111 000 000 000 000 000 110 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 1 101 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0

アドレス変換の例

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

12

，

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

0 xxxx 1 15 … … … ページテーブル(16エントリ） ページテーブル ベースレジスタ

:

0 1 15 主記憶 仮想アドレス： 0x1f40 = 0001 111101000000 １番目のPTE 0xf40 60K=4K*15

アドレス変換の例

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

12

，

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

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

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

• 主記憶に置く？

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

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

– 動的アドレス変換なし

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

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

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

TLB

• Translation Look-aside Buffer

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

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

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

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

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

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

TLB

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

ページテーブルの大きさ

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

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

• 2

32

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

• メモリ空間を圧迫

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

• 2

64

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

• 主記憶に置くのは無理

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

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

Hierarchical Page Tables

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

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

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

page number page offset

p_i p_{2 d} 10 10 12 page offset p_i p₂ d 10 10 12 P_３ 32 page offset p_i p₂ d 9 9 12 P_３ 8 P₄ 9

補足

• 第１段ページテーブルのサイズは210 – 主記憶に常駐可 • 全仮想空間のページ表は1025枚 – 実際に使っているのは3枚 – アクセスしないアドレス空間 のテーブルは不要 • 有効ビット：次の段のテーブルは主 記憶か？ – 仮想記憶に配置 1段目 ページ 番号 主記憶 pt2 pt1 offset 2段目 ページ 番号 0 1 2 3 4 1022 1023 0 1 2

補足

1段目 ページ 番号 主記憶 pt2 pt1 offset 2段目 ページ 番号 0 1 2 3 4 1022 1023 0 1 2 1023 • ページ化セグメンテーションとも • 二次元のアドレス – セグメントとその中の一次元ア ドレス – 任意のサイズのページテーブル • 目的に応じたセグメント – コード領域 – スタック領域

Hashed Page Tables

Inverted Page Table

• Page table entryの一つ一つは物理メモリページに対応

• 各エントリには仮想アドレスのページ番号と属性を格納

• ページテーブルサイズは小さくなるが、サーチ時間が長

• ハッシュテーブルを使用

仮想記憶の管理

• Demand Paging

• プロセス生成

• Page Replacement

• フレーム割り当て

• Thrashing

Demand Paging

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

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システムコールで生成された子プロセスは、親プロセスのイ

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

を共有

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

ピー

• COWは、変更されるページだけコピーされるので、より効率よい

プロセス生成が可能

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の回数は、どのくらいの物理フレームがあるかに依存