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

Transcription

1 1.PFLab( 加藤研 ) のウェブサイトからダウンロードできます 2. 紙資料も配布します オペレーティングシステム 加藤真平東京大学大学院情報理工学系研究科 shinpei@is.s.u-tokyo.ac.jp 218/6/4 第 8 回オペレーティングシステム 1

2 講義概要 受講生に求める基礎知識 C 言語の理解 コンピュータアーキテクチャの基礎の理解 メモリ管理 割り込み CPUモード 参考図書 Silberschatz, Galvin, and Gagne, Operating System Concepts 8th Edition, Wiley 成績 試験の点数で決定 試験は持ち込み不可 授業に出席していた人で試験の結果が悪い人は追試験あり 出席をとるが出席点はなし 218/6/4 第 8 回オペレーティングシステム 2

3 講義スケジュール ( 予定 ) 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) 1. 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 218/6/4 第 8 回オペレーティングシステム 3

4 メモリ管理 プログラム実行までの道のり Swapping 連続メモリ領域割り当て Paging Segmentation Segmentation with Paging 218/6/4 第 8 回オペレーティングシステム 4

5 Static vs dynamic $ cc static foo.c $ file a.out a.out: ELF 32-bit LSB executable, Intel 8386, version 1 (SYSV), for GNU/Linux 2.6.8, statically linked, not stripped $ size a.out text data bss dec hex filename c28e a.out $ cc foo.c $ file a.out a.out: ELF 32-bit LSB executable, Intel 8386, 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 a.out foo.c #include <stdio.h> int main() { printf( Hello n ); return ; } Static Link の問題点 ファイルサイズの肥大化 全てのコマンドがstatic linkされていたら ライブラリにバグがあった時 リンクしなおす必要 全てのコマンドをリンクしなおしていたら 218/6/4 第 8 回オペレーティングシステム 5

6 補足 静的再配置 (static relocation) 配置は主記憶へのロード時 ロード後のプログラムの位置変更は不可能 動的再配置 (dynamic relocation) プログラム実行中に再配置 ロード後のプログラムの位置変更は可能 再配置可能なコード 再配置レジスタ ベースレジスタ 番地 α 番地 α+p 番地 n 番地 α+a 番地 主記憶 OS 領域ユーザ領域 A 未使用領域アドレス変換機構 α 218/6/4 第 8 回オペレーティングシステム 6

7 プログラム実行までの道のり メモリの使用量を減らす工夫 Dynamic Linking 実行時にライブラリのリンク リンク時には 実行時にライブラリリンクするためのルーチンとリンク ファイルとして保存される実行イメージ小 $ cc foo.c $ size a.out $ file a.out $ cc static foo.c $ size a.out $ file a.out 218/6/4 第 8 回オペレーティングシステム 7

8 プログラム実行までの道のり メモリの使用量を減らす工夫 Dynamic Loading サブルーチンが呼ばれるまでメモリ上にコピーなし 必要ないルーチンは呼ばれないのでメモリ使用率高 $ cc foo.c $ size a.out $ file a.out $ cc static foo.c $ size a.out $ file a.out 218/6/4 第 8 回オペレーティングシステム 8

9 プログラム実行までの道のり メモリの使用量を減らす工夫 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 $ file a.out 218/6/4 第 8 回オペレーティングシステム 9

10 dtest.c #include <stdio.h> #include <dlfcn.h> int main(int argc, char **argv) { int (*f)(void); void *dl; char *error; int val; } Dynamic Linking 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 ; Makefile mylib.c int mylib() { return 1; } 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 $ make $./dtest mylib.so 218/6/4 第 8 回オペレーティングシステム 1

11 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 再配置が必要ならば再配置 初期化関数を呼び出し 218/6/4 第 8 回オペレーティングシステム 11

12 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 218/6/4 第 8 回オペレーティングシステム 12

13 メモリの使われ方 #include <stdio.h> #include <stdlib.h> #define SIZE (124*8192) int a; int b = 1; int main() { int *cp; char ia[size]; bss data スタック x x4 ユーザ text, data,bss 領域 mmap 領域 } cp = malloc(sizeof(int)); return ; heap xc スタック カーネル領域 このプログラムは segmentation fault スタックサイズに注意 $ ulimit -a ulimit は bash のシェルコマンド xffffffff 218/6/4 第 8 回オペレーティングシステム 13

14 オーバレイ (Overlays) プロセスのメモリ領域が足りない時に メモリ領域を処理に応じて複数の目的で使用 以下の例では Pass1 プログラムがメモリにロードされて実行 その後 今度は pass2 プログラムを同じメモリ領域にロードして実行 218/6/4 第 8 回オペレーティングシステム 14

15 補足 プログラムを 6 つのモジュールに分割 M1 は M2, M4, M6 から 使用される関数 データを包含 M2 は M3 から使用 モジュール M2 (3K) モジュール M1 (2K) モジュール M4 (2K) モジュール M6 (4K) モジュール M3 (1K) モジュール M5 (3K) プログラム全体を主記憶に置くには15Kの領域が必要 ( ある時点で ) 必要なモジュールのみを主記憶に置くのであれば : M1, M2, M3 (6K) M1, M4, M5 (7K) M1, M6 (6K) モジュール化はユーザが決定 実現の手間が大きい 218/6/4 第 8 回オペレーティングシステム 15

16 Swapping メモリが足りなくなり プロセスが動けなくなったとき プロセスイメージを一時的に 2 次記憶に退避 (swap out) その代りに 2 次記憶上に退避していたプロセスイメージを主記憶に復元 (swap in) 218/6/4 第 8 回オペレーティングシステム 16

17 補足 待ち状態でメモリ CPU を有効に活用 スワップアウト 待ち状態プロセスの待避 2 次記憶 ( バッキングストア ) 主記憶の内容やレジスタ等を退避 スワップイン 退避したプロセスを主記憶に復元 CPU スケジューラとの連携 番地 n 番地 スワップイン 主記憶 OS 領域ユーザ領域プロセス1 プロセス2 未使用領域 バッキングストア スワップアウト プロセス 2 プロセス 1 218/6/4 第 8 回オペレーティングシステム 17

18 連続メモリ領域の管理方法 2 つのメモリ領域 カーネルが使用 : 主記憶になければならない ユーザプロセスが使用 Multiple-partition allocation Hole 割り当て可能な連続するメモリ領域 様々なサイズの hole が発生 プロセスがメモリ上に作られるとき そのプロセスイメージが収まるに十分なメモリ領域を割り当て カーネルは割り当てた領域 フリー領域を管理 a) allocated partitions b) free partitions (hole) OS OS OS OS process 5 process 5 process 5 process 5 process 9 process 9 process 8 process 1 process 2 process 2 process 2 process 2 218/6/4 第 8 回オペレーティングシステム 18

19 動的連続メモリ領域割り当て問題 フリーな hole から大きさ n のメモリ領域をどのように探すか? First-fit: 要求しているサイズに最初にマッチしたholeを割り当て Best-fit: 要求しているサイズにマッチする一番小さいholeを割り当てリストはサイズ順に並べられている必要あり Worst-fit: 一番大きいholeを割り当て First-fit, best-fit が worst-fit より良 218/6/4 第 8 回オペレーティングシステム 19

20 Fragmentation External Fragmentation トータルメモリ領域はあるが 連続領域としては存在しない Internal Fragmentation 割り当てられたメモリは要求したメモリよりも大きく 使用しない無駄なメモリ領域がある Reduce external fragmentation by compaction メモリの内容を移動してコンパクション I/O problem I/O が使用しているメモリ領域は他の目的に使用不可能 218/6/4 第 8 回オペレーティングシステム 2

21 補足 主記憶をいくつかの固定サイズの区画 (partition) に区分 ジョブスケジューラによる割り付け システムに到着したジョブ (=プロセス) はジョブキューへ 十分な大きさの区画があればそこへジョブをロード 無ければ空き区画ができるまで待機 ジョブが終了すると, 使用していた区画を解放 中大小 218/6/4 第 8 回オペレーティングシステム 21

22 補足 必要とする容量より大きく最も近い大きさの区画を選択 各区画にキューを用意 ジョブの大きさでロードする区画があらかじめ決定 絶対番地形式でも適用可 空き区画があっても 利用できないことも 区画 1+ 区画 2 3K 区画 区画 1 のジョブキュー 8K 5K 番地 主記憶 OS 領域 区画 1 (1K) 区画 2 のジョブキュー 空き区画があるにもかかわらず使用不可の状況 15K 12K 16K 区画 2 (2K) 外部断片化 (external fragmentation) 区画 3 のジョブキュー 24K 27K 区画 3 (3K) n 番地 218/6/4 第 8 回オペレーティングシステム 22

23 補足 キューは1つで各ジョブは再配置可能 再配置方法 CPUスケジューリング等の組み合わせ 静的再配置 動的再配置 スワッピングの利用 FCFS 優先度スケジューリング 主記憶 番地 OS 領域 ジョブキュー 区画 1 (1K) ジョブ 4 15K ジョブ 3 8K ジョブ 2 3K ジョブ 1 9K 区画 2 (2K) 区画 3 (3K) n 番地 218/6/4 第 8 回オペレーティングシステム 23

24 補足 FCFS で割当て ジョブ 1: 区画 1 ジョブ 2: 区画 3 ジョブ 3 には : 1. 空いた区画の中で収まる最小区画 区画 2 区画内の空き領域が大きい : 内部断片化 (internal fragmentation) 2. 収まる最小区画を選択し空くまで待機 区画 1 ジョブ 4 は区画 2 で実行可能だが待機 (FCFS) しかし方法 1 が優れているとは必ずしもいえない ジョブ 1: 短, ジョブ 3: 長の場合 待った方が良い? FCFS スケジューラの修正 割当て待ちはスキップして次のジョブをスケジュール ジョブ 3 をスキップしてジョブ 4 に区画 2 を割り当て 218/6/4 第 8 回オペレーティングシステム 24

25 可変区画割付け 固定区画割付けの問題点 断片化による主記憶利用率の低下 区画を可変サイズで管理 システム起動時 : ユーザ領域全体で 1 区画 ジョブが到着毎に 十分な大きさの空き領域を探索 必要な分だけ割付け 残りは空き領域 空き領域と使用中領域のリストを保持 218/6/4 第 8 回オペレーティングシステム 25

26 可変区画割付け OS OS OS OS OS 5K 25K 35K JOB1 (2K) JOB2 (1K) JOB3 (16K) JOB1 終了 5K 25K 35K 未使用 (2K) JOB2 (1K) JOB3 (16K) JOB4 割付 5K 18K 25K 35K JOB4 (13K) 未使用 (7K) JOB2 (1K) JOB3 (16K) 5K 18K JOB2 終了 35K JOB4 (13K) 未使用 (17K) JOB3 (16K) 5K 18K JOB5 割付 28K 35K JOB4 (13K) JOB5 (1K) 未使用 (7K) JOB3 (16K) ユーザ領域 : 5K ジョブ 1: 2K ジョブ 2: 1K ジョブ 3: 16K ジョブ 4: 13K ジョブ 5: 1K 1~5 の順で到着 FCFS スケジューリングの場合 51K 55K 未使用 (4K) 51K 55K 未使用 (4K) 51K 55K 未使用 (4K) 51K 55K 未使用 (4K) 51K 55K 未使用 (4K) 218/6/4 第 8 回オペレーティングシステム 26

27 可変区画割付け 可変区画割付けで主記憶の利用率は向上 内部断片化はほとんどなし? しかし外部断片化は生じ得る (c) において 7K+4K=11K の空き領域 ジョブ5を実行するのに十分な大きさ 連続領域でないのでロード不可 解決策 : コンパクション 218/6/4 第 8 回オペレーティングシステム 27

28 コンパクション (compaction) 7K+4K の連続領域 5K 25K OS JOB1 (2K) JOB1 終了 5K 25K OS 未使用 (2K) 5K JOB4 割付 18K 25K OS JOB4 (13K) 未使用 (7K) 5K 18K コンパクション OS JOB4 (13K) 未使用 (11K) JOB5 割付 5K 18K OS JOB4 (13K) JOB5 (1K) 使用中領域を詰めて 1 つの大きな空き領域 断片化の問題は解消 動的再配置が必要 最適化中のシステム停止 JOB2 (1K) JOB2 (1K) JOB2 (1K) 29K 28K 29K 35K 35K 35K JOB2 (1K) JOB2 (1K) 39K 39K 51K 55K JOB3 (16K) 未使用 (4K) 51K 55K JOB3 (16K) 未使用 (4K) 51K 55K JOB3 (16K) 未使用 (4K) 55K JOB3 (16K) 55K JOB3 (16K) ジョブ 2 の終了を待たずに割当て可 218/6/4 第 8 回オペレーティングシステム 28

29 可変区画割付け : 空き領域管理 空き領域の大きさ 位置情報をリストで保持 種々の大きさの空き領域が散在 ジョブ到着時にリストを探索 空き領域が大きい時は余りを空き領域 ジョブ終了時に領域を空き領域リストに追加 別の空き領域が隣接していれば連結 できるだけ大きい空き領域 218/6/4 第 8 回オペレーティングシステム 29

30 可変区画割付け : 空き領域割当て どの空き領域を使う? 先頭一致 (first-fit) 最初の十分な大きさの領域 最良一致 (best-fit) 最も大きさの適合する領域 高速 リストの最後の方に, 大きな領域 ( 断片化の回避 ) 大きな空き領域を残す 小さな空き領域の多発 最悪一致 (worst-fit) 最大の空き領域 余った領域は割と大きい 小さな空き領域の回避 218/6/4 第 8 回オペレーティングシステム 3

31 仮想記憶 物理メモリ量以上のメモリを仮想的に作成 仮想的にみえるので仮想記憶 仮想アドレス : 仮想記憶上のアドレス 物理アドレス : 物理メモリ上のアドレス 未使用 218/6/4 第 8 回オペレーティングシステム 31

32 仮想記憶 主記憶より大きな記憶領域 2 次記憶の利用 オーバレイ 仮想記憶 入れ替え 入れ替え 個々のモジュールのアドレス空間を意識 最適な入れ替えが可能 プログラム全体で一つの空間と認識 入れ替えの無駄が起きる可能性 218/6/4 第 8 回オペレーティングシステム 32

33 仮想記憶 各プロセスに独立したアドレス空間 全て同じ大きさ 実アドレス空間 real address space 主記憶のアドレス空間 最初は連続しているが 仮想 ( 論理 ) アドレス空間 virtual address space 仮想記憶のアドレス空間 プロセス / プログラムが参照するアドレス 連続した 1 つの空間に 見せかける 番地 n 番地 主記憶 OS 領域 プロセス 1 の一部 プロセス 2 の一部 バッキングストア プロセス 1 プロセス 2 218/6/4 第 8 回オペレーティングシステム 33

34 仮想記憶 32bitの仮想アドレス空間 最大 4GB 論理的に必要なメモリ空間 4GB プロセス数 番地 アドレス変換プログラムの k 番地 主記憶の k 番地 主記憶 OS 領域 プロセス 1 の一部 主記憶には一部だけ 仮想空間の残りの部分は 2 次記憶のスワップ領域 大容量のディスクを使って広大なメモリを持っているように 見せかける n 番地 プロセス 2 の一部 バッキングストア プロセス 1 プロセス 2 218/6/4 第 8 回オペレーティングシステム 34

35 仮想記憶の全体構成 CPU 仮想アドレス MMU ( メモリ管理ユニット ) 物理アドレス 主記憶 必要な部分を主記憶に保存 ( プロセス切り替えでも入れ替えない ) xff...ff 仮想アドレスから適切な物理アドレスへ変換 各プロセスに広いアドレス空間独立した空間 xx...xx 2 次記憶 主記憶に入らない当面の使用無し 2 次記憶へ プロセスの仮想アドレス空間 218/6/4 第 8 回オペレーティングシステム 35

36 動的アドレス変換 仮想アドレスと実アドレスの対応 バイトやワード単位? 主記憶以上の領域が必要 ブロック単位で対応 セグメンテーション セグメント 可変長のブロック ページング ページ 固定長のブロック 218/6/4 第 8 回オペレーティングシステム 36

37 動的アドレス変換 仮想アドレス v = b: ブロック番号 アドレス変換テーブル ( 対応表 ) のインデックス d: ブロック先頭からのオフセット アドレス変換テーブルベースレジスタ x 仮想アドレス空間上のブロックがどこにあるか b b d アドレス変換テーブル x 仮想アドレス v ブロック番号相対位置. b b. d ( 通常プロセス毎に存在 ) d b + d 実アドレス r b r 主記憶.. 218/6/4 第 8 回オペレーティングシステム 37

38 Paging プロセスの論理アドレス空間は物理メモリ上連続である必要なし 物理メモリを固定長のブロックにして管理 このブロックは フレーム ブロックの長さは 2 のべき乗 (512bytes から 8Kbytes が主流だが 最近は 128MBytes にできるマシンも ) 論理メモリ領域も同じサイズに分割 この単位はページ 全てのフリーフレームを管理 n ページ必要なプログラムを動かすには n 個のフリーフレームを確保して ページテーブルをセット Internal fragmentation 218/6/4 第 8 回オペレーティングシステム 38

39 補足 主記憶 ( ページフレームの集まり ) paging 主記憶を固定長ブロックに分割 ページフレーム 仮想アドレス空間も, 同サイズのページに分割 動的アドレス変換を使用 ページ単位で主記憶 -2 次記憶間のやりとり 二次記憶 ページイン ページアウト 仮想アドレス空間 ( ページの集まり ) 218/6/4 第 8 回オペレーティングシステム 39

40 補足 主記憶 ( ページフレームの集まり ) ページフォルト page fault 主記憶に存在しないページをアクセスしたときに発生する割込み ハードウェアの機能 割込みハンドラ ページイン (OS の処理 ) 二次記憶 ページイン ページアウト 仮想アドレス空間 ( ページの集まり ) 218/6/4 第 8 回オペレーティングシステム 4

41 補足 ページイン (page in) ページを 2 次記憶から主記憶上のページフレームに移動 ページアウト (page out) ページを 2 次記憶へ退避 空きページフレームが足りなくたった時 ページイン後, 内容を変更していない ページの解放のみ 二次記憶 主記憶 ( ページフレームの集まり ) ページイン ページアウト 仮想アドレス空間 ( ページの集まり ) 218/6/4 第 8 回オペレーティングシステム 41

42 ハードウエアによるアドレス変換機構 Memory-Management Unit (MMU) Page Mapping Tableによる変換 各エントリは物理アドレスと属性を保持 属性 :Access Permission, Modified, Referenceなど Access Permission 論理ページ番号 ユーザモードにおけるread/write 特権モードにおけるread/write オフセット メモリ プロセスのページ表ポインタ V V I 属性 フレーム番号 218/6/4 第 8 回オペレーティングシステム 42

43 補足 有効ビットが : ページフォルトが発生 (OS に遷移 ) 2 次記憶から主記憶の空いたページフレームに転送 そのページフレーム番号 f を PTE に設定. 有効ビットを 1 仮想アドレス v 仮想ページ番号 b 相対位置 ( オフセット ) d 主記憶 b ページテーブル 1 yyy a b d d 実アドレス r b ページテーブルエントリ (PTE) 1 xxx b r = f ページサイズ + d r = f << n d ( ページサイズ : 2 n ) 218/6/4 第 8 回オペレーティングシステム 43

44 補足 仮想アドレス v=(p, d) p : ページ番号 d : ページ内オフセット ブロック = ページアドレス変換テーブル = ページテーブル ページ番号 p のページテーブルエントリ (PTE) を参照 有効ビット 2 次記憶アドレス ページフレーム番号 f 有効ビット ( サイズは1bit) 1ならページが主記憶に存在 なら2 次記憶に存在 ( ページアウト ) ページの共有 = 2 次記憶アドレスとページフレーム番号の共有 他に保護属性等の情報 ( 全てのアクセスはPTE 経由 ) 218/6/4 第 8 回オペレーティングシステム 44

45 ページテーブルと物理アドレス 仮想空間 (64KB:16bit), 物理メモリ (32KB:15bit), ページ 4KB 仮想アドレススペース 物理メモリアドレス 仮想アドレス -4K 4-8K 8-12K 12-16K 16-2K 2-24K 24-28K 28-32K 32-36K 36-4K 4-44K 44-48K 48-52K 52-56K 56-6K 6-64K x x x 1 7 x x x x x 6-4K 4-8K 8-12K 12-16K 16-2K 2-24K 24-28K 28-32K ページ内オフセット = 12bit MMU (4KB x 16) 物理アドレス 218/6/4 第 8 回オペレーティングシステム 45

46 アドレス変換の例 例 : ページサイズ =4KB=2 12, 仮想アドレス空間 =16bit(16 ページ =4bit) 仮想アドレス : x1f4 = ページテーブルベースレジスタ 1 番目の PTE ページテーブル (16エントリ) xxxx : 主記憶 xf4 6K=4K*15 218/6/4 第 8 回オペレーティングシステム 46

47 アドレス変換の例 例 : ページサイズ =4KB=2 12, 仮想アドレス空間 =16bit(16 ページ =4bit) 仮想アドレス : x1f4 = x1f4 1 他のページフレームは 別のページに割り当て 別のプロセスのページに割り当て 未使用 xxxx 2 次記憶 15 : : 6K=4K*15 15 xff4 仮想アドレス空間 主記憶 218/6/4 第 8 回オペレーティングシステム 47

48 ページテーブルの置き場所 主記憶に置く? ページテーブルベースレジスタ 実アドレス ページテーブルのアクセス 動的アドレス変換なし メモリアクセスをするために, 更にページテーブルへのメモリアクセスが生じ速度が低下 仮想記憶をサポートする CPU に TLB(Translation Look-aside Buffer) を置く 218/6/4 第 8 回オペレーティングシステム 48

49 TLB Translation Look-aside Buffer ページテーブルエントリの一部を置く高速なバッファ 一般的には連想メモリ (64~256 エントリ程度 ) で実現 並列検索機能 任意の一部のエントリを配置 大容量の連想メモリの実現は困難 アドレス変換の際は, まず連想メモリを調査 なければ主記憶のテーブル (TLB ミス ) 単に広いアドレス空間を使うだけでコスト発生 218/6/4 第 8 回オペレーティングシステム 49

50 TLB N レベルページマッピングテーブル ( 後述 ) をハードウェアで実現している場合 CPU は TLB だけを持つ場合 ソフトウェア ( カーネル ) でページテーブルを管理 TLB エントリに存在しないと 割り込みが発生 カーネルは TLB エントリを設定する どういう方法があるか? Hierarchical Paging Hashed Page Tables Inverted Page Tables 218/6/4 第 8 回オペレーティングシステム 5

51 ページテーブルの大きさ ページサイズが4KBの場合 4GBの仮想アドレス空間全てをカバー 2 32 /4K=1Mエントリ/ プロセス メモリ空間を圧迫 64bitの仮想アドレス空間の場合 2 64 /4K=4Pエントリ =4Gエントリ 主記憶に置くのは無理 全エントリ (= 全仮想空間 ) を使うことは滅多になし 多重レベルページングセグメンテーションとの併用 218/6/4 第 8 回オペレーティングシステム 51

52 Hierarchical Page Tables 論理アドレス空間を複数のページテーブルで管理する 2 レベルページテーブル page number page offset p i p 2 d レベルページテーブル page offset P 3 p i p 2 d 32 4 レベルページテーブル page offset P 3 p i p 2 d /6/4 第 8 回オペレーティングシステム 52 P 4

53 補足 1 段目ページ番号 2 段目ページ番号 pt1 pt2 offset 第 1 段ページテーブルのサイズは 2 1 主記憶に常駐可 主記憶 全仮想空間のページ表は 125 枚 実際に使っているのは 3 枚 アクセスしないアドレス空間のテーブルは不要 有効ビット : 次の段のテーブルは主記憶か? 仮想記憶に配置 /6/4 第 8 回オペレーティングシステム 53

54 補足 1 段目ページ番号 2 段目ページ番号 pt1 pt2 offset ページ化セグメンテーションとも 主記憶 二次元のアドレス セグメントとその中の一次元アドレス 任意のサイズのページテーブル 目的に応じたセグメント コード領域 スタック領域 /6/4 第 8 回オペレーティングシステム 54

55 Hashed Page Tables 仮想ページ番号をキーとしてハッシュでテーブル引き 218/6/4 第 8 回オペレーティングシステム 55

56 Inverted Page Table Page table entryの一つ一つは物理メモリページに対応 各エントリには仮想アドレスのページ番号と属性を格納 ページテーブルサイズは小さくなるが サーチ時間が長 ハッシュテーブルを使用 218/6/4 第 8 回オペレーティングシステム 56

57 仮想記憶の管理 Demand Paging プロセス生成 Page Replacement フレーム割り当て Thrashing 218/6/4 第 8 回オペレーティングシステム 57

58 Demand Paging 必要に応じてページをメモリにロード ハードウエアによる支援 ページエントリに valid-invalid bit 属性がある Valid-invalid bit が の時 当該フレームをアクセスするとページ例外が発生 Frame # valid-invalid bit page table 218/6/4 第 8 回 オペレーティングシステム 58

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

60 空きフレームがない時どうする? Page replacement あまり使われていないページを探し その領域を 2 次記憶 (swap 領域 ) にコピー ( その領域を使用 ) アルゴリズムは後述 218/6/4 第 8 回オペレーティングシステム 6

61 Demand Paging の性能 Page Fault Rate p 1. if p = 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 = 1 ナノ秒, paging overhead = 25 ミリ秒とすると EAT = (1 p) * 1 + p * 25 milli = ,999,9*p 218/6/4 第 8 回オペレーティングシステム 61

62 Demand Paging の性能 インストラクション ( 正確には異なるメモリ領域のアクセス ) を 1, 回実行する毎に page fault が起きると仮定すると p=.1 となり 一回の実行時間は 約 25 マイクロ秒必要 実際には ページが一度ロードされたら そのページはメモリに存在 (page out されない限り ) 例えば 8Kbyte page size で 128Kbytes のプログラムは 16 ページ 218/6/4 第 8 回オペレーティングシステム 62

63 Demand Page および仮想記憶の利点 プロセス起動が高速化 起動前にプロセスイメージ全てをメモリ上に確保してディスクからコピーしないから Copy-on-Write による子プロセス生成の高速化 次のスライドで説明 物理メモリ消費を低減 Memory-Mapped Files 218/6/4 第 8 回オペレーティングシステム 63

64 Copy-on-Write(COW) 子プロセス生成のシナリオ 親プロセスは fork システムコールで子プロセスを生成 このとき Fork システムコールは 親プロセスのコピーを生成 多くの場合 子プロセスは exec システムコールを発行して親プロセスとは違うプログラムを実行 Fork システムコールで生成された子プロセスは 親プロセスのイメージをコピーする代わりに 親のプロセスイメージ ( ページ ) を共有 どちらかのプロセスがページに書き込むとき そのページをコピー COW は 変更されるページだけコピーされるので より効率よいプロセス生成が可能 218/6/4 第 8 回オペレーティングシステム 64

65 Memory-Mapped Files Memory-mapped file I/O とは ファイルの内容をメモリにマップすることにより メモリの読み書きでファイルの内容をアクセスできるようにする機能 Read システムコールでファイルの内容を読み込み write システムコールで書き込むという煩わしさがなくなると共に余分なデータコピーも減少 複数のプロセスにより 同一ファイルをメモリ上で アクセス可能 218/6/4 第 8 回オペレーティングシステム 65

66 空きフレームがない時どうする? Page replacement あまり使われていないページを探し その領域を 2 次記憶 (swap 領域 ) にコピーすることで その領域を使用 218/6/4 第 8 回オペレーティングシステム 66

67 Page Replacement ユーザプロセスがページを必要とする時 フリーフレームがないと 使用しているページのフレームを swap デバイスにコピー ページを必要としているプロセスのフレームとして使用 どのページ ( フレーム ) を選択するか? この説明は後述 使用されていたフレームをディスクにコピーするかどうかの判断は? ページをページエントリには modify (dirty) bit 属性が存在 ページに書き込みにいくと modify bit がセット カーネルは この bit をみて ページをディスクに書かなければいけないか決定 ページ ( 論理ページ ): 仮想メモリ上のブロックフレーム ( 物理ページ ): 物理メモリ上のブロック 218/6/4 第 8 回オペレーティングシステム 67

68 Basic Page Replacement ディスク上に保存してあるページを探索 空きフレームを : 空きフレームを見つけたら そのフレームを使用 空きフレームがなければ page replace algorithm を使って追い出すフレームを決定 ( これを victim フレームと呼ぶ ) Victim ページをディスクに書き ページテーブルを変更 ディスク上のページの内容を空きフレームにコピーしページテーブルを変更 プロセスを再開 218/6/4 第 8 回オペレーティングシステム 68

69 Page Replacement Algorithms Page fault が少なくなるようなアルゴリズムを使いたい これ以降いくつかの page replace algorithms を紹介するが いずれも以下のアクセスパターンにおける page fault の数を調査 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. もちろん page fault の回数は どのくらいの物理フレームがあるかに依存 一般に物理フレームが多ければ page fault の回数は減少するが減少しない例も 218/6/4 第 8 回オペレーティングシステム 69