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

Transcription

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

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

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

4 システムコール ( プリミティブ ) システムコールはユーザプログラムと OS とのインターフェイス 割り込み命令によって実現 C,C++ などのプログラミング言語向けインターフェイスを提供 Unix 系ではマニュアル 2 章がシステムコール 3 章が言語ライブラリ 2 章の open/read/write/close はシステムコール 3 章の fopen/fread/fwrite/fclose はシステムコールを使用し ライブラリレベルでバッファを処理 2019/4/15 第 2 回オペレーティングシステム 4

5 システムコールの仕組み ユーザプログラム (4) 引数のコピー (3) 割込みハンドラ システムコール表 ディスパッチャ (1) システムコール関数の呼出し (#k) (2) trap 命令の発行 システムコール処理ルーチン #1 システムコール処理ルーチン #2. システムコールライブラリ関数 システムコール処理ルーチン #k (5) システムコール処理の実行 ユーザモード カーネルモード (6) 返戻値のコピー システムコール処理ルーチン #n (7) プロセスのスケジュール (1) システムコール関数の呼出し (2) ライブラリ関数内で trap 命令を発行 - レジスタにシステムコール番号 (3) カーネルモードに移行割込みハンドラを起動 (4) システムコール引数を検査しカーネル内へコピー (5) システムコール番号と関数ポインタの表から呼び出しルーチンを特定処理ルーチンの実行 (6) システムコール処理結果をユーザ空間へコピー (7) 適切なプロセスのスケジュール 2019/4/15 第 2 回オペレーティングシステム 5

6 カーネル空間 ユーザ空間 プロセス管理 プロセスとは? プログラムの実行単位 次のような資源を使用 CPU 時間 メモリ ファイル I/O デバイス OS によるプロセス管理の例 プロセス生成 削除 プロセス停止 再開 プロセス間同期 プロセス間通信 デッドロック処理 ユーザプログラムコード ユーザデータ領域ユーザヒープ領域ユーザスタック領域 プロセス状態格納領域 カーネルプログラムコード カーネル作業領域 2019/4/15 第 2 回オペレーティングシステム 6

7 カーネル空間 ユーザ空間 プロセス管理 プロセスごとに仮想空間を割り当て 他のプロセスのメモリへのアクセス禁止 バグ等でプロセスが異常終了しても 他のプロセスには影響なし プロセスの種類 ( 後述 ) 権限による分類 ユーザプロセス スーパーユーザープロセス 形態による分類 システムプロセス デーモンプロセス サーバープロセス ユーザプログラムコード ユーザデータ領域ユーザヒープ領域ユーザスタック領域 プロセス状態格納領域 カーネルプログラムコード カーネル作業領域 2019/4/15 第 2 回オペレーティングシステム 7

8 仮想記憶の仕組み ページサイズ 1,024 バイトの場合 論理ページ番号 10bits オフセット 仮想メモリ 0x0 0x0400 0x0800 0x0c00 0x1000 0x1400 0x1800 アクセスパターン 0x0200 0x0900 0x0d00 #define V 1 #define I 0 struct PTBL { int valid; int pno; }; Struct PTBL[10] = { {V, 1}, {I, 0}, {V, 0}, {I, 0}, {V, 2}, {I, 0}, }; プロセスのページ表ポインタ V I V I V I I I I I 物理ページ番号 物理メモリ Load Reg10, [0x1010] if (PTBL[0x1010>>10].valid) PhysMem[(PTBL[0x1010>>10].pno<<10)+0x1010&0x3ff] else 割り込み 2019/4/15 第 2 回オペレーティングシステム 8

9 プロセスと仮想記憶 プロセスのページ表ポインタ 仮想メモリ 0x0 0x0400 0x0800 0x0c00 0x1000 0x1400 0x1800 論理ページ番号 10bits ページ表 物理ページ番号 オフセット 物理メモリ V 1 0 I V 0 I 1 V 2 I 2 I I I 3 I 4 ページ表 V 1 I V 4 I V 3 I I I I I 物理ページ番号 2019/4/15 第 2 回オペレーティングシステム 9

10 権限による分類 ユーザプロセス プロセスの種類 一般ユーザ スーパーユーザプロセス ( ルート権限を有するプロセス ) 特権機能を使用可能 例 : 任意のユーザプロセスの停止 システム停止 2019/4/15 第 2 回オペレーティングシステム 10

11 形態による分類 プロセスの種類 システムプロセス デーモンプロセス オペレーティングシステムサービスを提供しているプロセスでスーパーユーザモード (CPU の特権モードとは違う ) で動いているプロセスの総称 システムプロセスでユーザからは見えないところで動いているプロセス = デーモンプロセス サーバプロセス クライアント サーバモデルに基づいたサービスを提供しているプロセス = サーバプロセス http デーモン http サーバ http システムプロセス 2019/4/15 第 2 回オペレーティングシステム 11

12 どんなプロセスが動いている? Linux の場合 top コマンド ps コマンド ps axwwwl Windows の場合 Ctl+Alt+Del して タスクマネジャーを選択 2019/4/15 第 2 回オペレーティングシステム 12

13 x86 系 Linux の仮想メモリ空間使用 0x x xc ユーザユーザ text, data,bss ユーザ text, data,bss 領域 text, data,bss 領域領域 mmap 領域 mmap 領域スタック mmap 領域スタックスタックカーネル領域カーネル領域カーネル領域 text: プログラムコード data: 初期データ bss: 初期データのない領域 0xffffffff 2019/4/15 第 2 回オペレーティングシステム 13

14 login プロセス プロセス メモリイメージ login プログラム exec( /bin/sh,.); mmap 領域 スタック カーネル領域 2019/4/15 第 2 回オペレーティングシステム 14

15 login プロセス プロセス メモリイメージ login プログラム exec システムコールが実行されると exec( /bin/sh,.); mmap 領域 スタック カーネル領域 2019/4/15 第 2 回オペレーティングシステム 15

16 /bin/sh プロセス プロセス メモリイメージ メモリイメージが書き換わり 新たなプロセスが実行 sh プログラム pid = fork(); if (pid == 0) { exec(cmd, ); } else {. } mmap 領域 スタック カーネル領域 2019/4/15 第 2 回オペレーティングシステム 16

17 /bin/sh プロセス プロセス メモリイメージ sh プログラム pid = fork(); if (pid == 0) { exec(cmd, ); } else {. } fork システムコールが実行されると mmap 領域 スタック カーネル領域 2019/4/15 第 2 回オペレーティングシステム 17

18 メモリイメージ プロセス /bin/sh プロセス ( 親プロセス ) sh プログラム pid = fork(); if (pid == 0) { exec(cmd, ); } else {. } メモリが複製 /bin/sh プロセス ( 子プロセス ) sh プログラム pid = fork(); if (pid == 0) { exec(cmd, ); } else {. } mmap 領域 スタック カーネル領域 mmap 領域 スタック カーネル領域 2019/4/15 第 2 回オペレーティングシステム 18

19 メモリイメージ プロセス /bin/sh プロセス ( 親プロセス ) sh プログラム pid = fork(); if (pid == 0) { exec(cmd, ); } else {. } /bin/sh プロセス ( 子プロセス ) sh プログラム pid = fork(); if (pid == 0) { exec(cmd, ); } else { 複製元 ( 親プロセス ):forkシステムコールの返り値は 子プロセスのID (identifier: 識別子 ) 複製先 ( 子プロセス ):forkシステムコールの返り値は 0. } mmap 領域 スタック カーネル領域 mmap 領域 スタック カーネル領域 2019/4/15 第 2 回オペレーティングシステム 19

20 login プロセス プロセス shell プロセス ls プロセス ユーザ text, data,bss 領域 ユーザ text, data,bss 領域 ユーザ text, data,bss 領域 mmap 領域 スタック カーネル領域 exec システムコールにより shell プログラムが起動 mmap 領域 スタック カーネル領域 fork システムコールによってプロセスを生成さらに exec システムコールで ls プログラムを起動 mmap 領域 スタック カーネル領域 2019/4/15 第 2 回オペレーティングシステム 20

21 補足 fork() について オープン済みのファイル記述子は共有 vfork() メモリ保護によりアクセス時にコピー (copy on write) 現在ではobsolete( 既に古い ) 現在はfork() がメモリ保護を用いたcopy on writeで実現されている code data stack 共有 コピー コピー code data stack fork() 時のデータ領域とスタック領域をコピー code data stack 共有 共有 コピー code data stack スタック領域のみコピー ( データ領域へのアクセスに注意が必要 ) 古典的な fork() 特殊な fork() スレッド ( 後述 ) 2019/4/15 第 2 回オペレーティングシステム 21

22 カーネル空間 カーネル空間 ユーザ空間 A ユーザ空間 B プロセス実行の切り替え Linux/Unix では コマンド実行毎にプロセス作成 プロセス実行の切り替え = プロセスコンテキストスイッチ コンテキストスイッチ ユーザプログラムコードユーザデータ領域ユーザヒープ領域ユーザスタック領域プロセス状態格納領域 コンテキストスイッチ時に OS は何をするか? ユーザプログラムコードユーザデータ領域ユーザヒープ領域ユーザスタック領域プロセス状態格納領域 カーネルプログラムコード カーネルプログラムコード カーネル作業領域 カーネル作業領域 2019/4/15 第 2 回オペレーティングシステム 22

23 Process Control Block (PCB) とプロセス切り替え PCB にプロセス毎に必要な情報を格納する プロセスの状態 CPU レジスタ プライオリティ等の CPU スケジューリング情報 ページテーブル等のメモリ管理情報 etc プロセスコンテキストの様子 2019/4/15 第 2 回オペレーティングシステム 23

24 メモリ空間とセクション code (text) data bss heap auto 変数 リターンアドレス 引数など auto 変数 リターンアドレス 引数など 演算ユニット プログラムカウンタ (PC) レジスタ フレームポインタ 各領域のアドレス CPU 切り換え時に必要な情報を保存 補足 code (text) data bss heap auto 変数 リターンアドレス 引数など auto 変数 リターンアドレス 引数など コード ( テキスト ) 領域 プログラム データ領域 data 初期化された静的変数 大域変数 bss 初期化されない静的変数 大域変数 heap 動的確保変数 スタック領域 auto 変数 制御情報 2019/4/15 第 2 回オペレーティングシステム 24

25 プロセスの状態 New プロセス生成中 Running 実行中 Waiting 何かの事象待ち Ready 実行可能. Terminated 実行終了 2019/4/15 第 2 回オペレーティングシステム 25

26 プロセススケジューリングキュー プロセススケジューリングキューの種類 Job queue 全プロセスリスト Ready queue 実行可能状態のプロセスリスト Device queues I/O 待ち状態プロセスリスト 2019/4/15 第 2 回オペレーティングシステム 26

27 プロセスの実行とキュー Ready queue PCB PCB head CPU で実行 tail I/O queue head tail registers... registers... プロセスの実行中に起こること プロセスがI/O 要求 割り当てられたCPU 時間 (Time slice) が経過 子プロセスを生成 割り込みが発生 2019/4/15 第 2 回オペレーティングシステム 27

28 補足 高 次に実行状態 最高優先度の実行可能キュー null 優先度. 最低優先度の実行可能キュー 実行状態 null 待ちキュー 待ちイベントが発生したら 実行可能状態へ null 2019/4/15 第 2 回オペレーティングシステム 28

29 スケジューラの種類 長期スケジューラ (job scheduler) バッチシステムでは ジョブ ( プロセス ) が投入されると それらは 2 次記憶に配置 (spool 呼ぶ ) スプールされたジョブの中からいくつかのジョブを取り出して実行可能キューに投入 短期スケジューラ (CPU scheduler) どのプロセスを次に実行するか決定す 2019/4/15 第 2 回オペレーティングシステム 29

30 短期スケジューラ 短期スケジューラ プロセスが待ち状態になるときに 次に実行すべきプロセスを決めるために起動 プロセスが実行を続けている場合でも Time Slice 毎に起動 処理が速いことが必要条件 100ミリ秒毎に10ミリ秒もかかると 10/(100+10)= 9% がオーバヘッドになってしまう普通は数十から数百マイクロ秒のオーダ 2019/4/15 第 2 回オペレーティングシステム 30

31 長期スケジューラ 秒あるいは分毎に実行される マルチプログラミングの度合いを制御 同時に実行するプロセスの数を決定 プロセス数を一定にするならば 長期スケジューラはプロセスが消滅したときにのみ実行 遅くても良い プロセスの性質に応じてスケジューリングする I/O-bound プロセス I/O 処理多 CPU 使用少 CPU-bound プロセス CPU 使用多 ( 数値計算など ) 2019/4/15 第 2 回オペレーティングシステム 31

32 TSS におけるスケジューラ TSS(Time Sharing System) は長期スケジューラなし 長期スケジューラの替わりに中期スケジューラがある場合あり マルチプログラミングの度合いを減らすために 実行可能プロセスを実行可能キューから取り出し (swap out) 2019/4/15 第 2 回オペレーティングシステム 32

33 プロセス生成一般論 (1/2) プロセスはプロセスを生成することができる 親プロセス : 生成側 子プロセス : 作られた側 子プロセスはさらにその子プロセスを生成可能 それにより プロセスのツリー形成 資源の共有可能性 親と子供は全ての資源を共有 子プロセスは親プロセスの一部の資源を共有 親子で共有する資源なし 実行関係 親と子供は同時に実行 親プロセスは子プロセスの終了を待つことが可能 2019/4/15 第 2 回オペレーティングシステム 33

34 プロセス生成一般論 (2/2) メモリ空間 子プロセスは親プロセスのメモリ空間の複製を保持 子プロセスはプログラムを読み込み実行 UNIX 系の例 fork システムコール 子プロセスははじめ親プロセスのメモリ空間の複製を保持 実装上は共有 &Copy on Write 子プロセスは親プロセスのファイルディスクリプタの複製を保持 exec システムコール プログラムを指定されたファイルから読み出し実行 2019/4/15 第 2 回オペレーティングシステム 34

35 プロセスの終了一般論 プロセスは最後に exit システムコールをして プロセスを終了 exit システムコール時に終了コードを渡すことが可能 親プロセスは 子プロセスの終了を wait システムコールで待機が可能 その際 子プロセスの終了コードの取得が可能 プロセス終了時にするべきこと プロセスが保持している資源の解放 : メモリ領域 I/O バッファなど 親プロセスは abort システムコール (Unix 系の場合 kill) で子プロセスを終了させることが可能 親プロセスが終了すると子プロセスも終了させられるシステムも存在 Cascading termination Linux の場合は? 親プロセスが終了すると子プロセスは init プロセスが親に 2019/4/15 第 2 回オペレーティングシステム 35

36 UNIX におけるプロセスツリー カーネルの初期化が終了すると /sbin/init プログラムを探し プロセスを起動 init プロセスは以下の処理を実行 /etc/rc.d/rc.sysinit スクリプトの実行 /etc/inittab スクリプトの実行 /etc/rc.d/rc.local スクリプトの実行 init プロセスの下に新たなプロセスが生成 2019/4/15 第 2 回オペレーティングシステム 36

37 スレッド Thread of Control プロセス内での一連の実行の流れ 単にスレッドとも プロセス内に複数スレッドを動かすような実行モデル = マルチスレッドモデル 多くの研究がなされたのは マルチスレッドモデルは共有メモリ型並列コンピュータが一般に使えるようになった 1970 年後半から 1980 年代 2019/4/15 第 2 回オペレーティングシステム 37

38 補足 プロセスメモリ data code プロセス スレッド register func2() stack func1() main() スレッド 単一スレッド int func1() {... } int func2() {... } int main() { thread_create(func1); thread_create(func2); } スレッド int func2() {... } int func1() { func2(); } int main() { func1(); } マルチスレッド スレッド スレッドの Context( 管理実体 ) は小さい 切替が高速 但し 共有データのアクセスに注意が必要 プログラムから見るとプログラム中の関数が別の処理として動作 register register register メモリ data code stack main() stack func1() stack func2() 2019/4/15 第 2 回オペレーティングシステム 38

39 スレッドの実現方法 ユーザレベルスレッド ユーザライブラリで実現 カーネルレベルスレッド オペレーティングシステムがカーネルで実現 2019/4/15 第 2 回オペレーティングシステム 39

40 ユーザレベルスレッド ユーザモードで動作するライブラリで実現 多くの場合 setjmp()/longjmp() で実装 フレーム情報の保存と復元 各スレッドは別の起点フレームを保持 カーネルレベルスレッドより軽量 高速のコンテクスト切り換え 大量のスレッド生成が可能 スケジューリングの方針等の変更が手軽 threadc threadb threada 2019/4/15 第 2 回オペレーティングシステム 40 main

41 ユーザレベルスレッド スケジューリングの面倒をカーネルが見ない 処理を横取りできない or 横取りの実現が面倒 入出力等でスレッドが待ち状態になると 同一プロセス内の他の実行可能スレッドが実行不可能 (I/O ブロック ) システムコールライブラリの wrapper 等で対処 実行コアが複数でも並列に実行不可能 threadc threadb threada 2019/4/15 第 2 回オペレーティングシステム 41 main

42 カーネルレベルスレッド カーネル内でプロセスと同様の手法でスレッドを管理 サイズ : スレッド制御ブロック (Thread Control Block)< PCB スレッドはカーネルによるスケジューリングの対象 コンテクストスイッチ等の操作は カーネルモードで実行 カーネルモードとユーザモードの切り替えオーバヘッドが発生 ただし プロセスの切替よりは軽量 メモリ空間の切りえは不要だから 2019/4/15 第 2 回オペレーティングシステム 42

43 マルチスレッド実現モデル Many-to-One( 多対 1 モデル ) 複数のユーザレベルスレッドがカーネルで実現されているスレッドひとつに対応 One-to-One(1 対 1 モデル ) ひとつのユーザスレッドがカーネルで実現されているスレッドひとつに対応 Many-to-Many( 多対多モデル ) 複数のユーザレベルスレッドが複数のカーネルレベルスレッドに対応 2019/4/15 第 2 回オペレーティングシステム 43

44 マルチスレッドのモデル Many-to-One( 多対 1 モデル ) 一つのカーネルスレッドで複数のユーザスレッドを稼働 ライブラリでスケジューリングするため高速 カーネルの処理待ちできるのは 一つのスレッドのみ I/O でブロック process スケジューラ ユーザレベルスレッド 実装 Solaris Green Thread, GNU Portable Thread k カーネルレベルスレッド 2019/4/15 第 2 回オペレーティングシステム 44

45 マルチスレッドのモデル process One-to-One (1 対 1 モデル ) 一つのカーネルスレッドでただ一つのユーザスレッドが稼働 実装 他のスレッドの I/O ブロックと無関係 複数プロセッサで稼働 スレッド生成 管理のオーバヘッドが発生 Linux, Windows k k k k ユーザレベルスレッド カーネルレベルスレッド 2019/4/15 第 2 回オペレーティングシステム 45

46 マルチスレッドのモデル Many-to-Many( 多対多モデル ) 複数のユーザスレッドをその数以下のカーネルスレッドで稼働 カーネルスレッドの数はアプリケーションやマシンに応じて決定 スレッドをどう割り付けるかの制御が必要 process スケジューラ ユーザレベルスレッド k k k カーネルレベルスレッド 2019/4/15 第 2 回オペレーティングシステム 46

47 マルチスレッドのモデル 2 レベルモデル 多対多モデルのバリエーション 一部のユーザレベルスレッドを特定のカーネルスレッドに固定 (pin down) process ユーザレベルスレッド 実装 IRIX, HP-UX, Tru64 UNIX Solaris (before ver. 9) スケジューラ k k k カーネルレベルスレッド 2019/4/15 第 2 回オペレーティングシステム 47

48 Linux Threads POSIX Pthread が提供されている スレッドライブラリの標準規格 (IEEE c) 多くのUnix 系システムで実装 Pthread 実現方法 clone() システムコール 2019/4/15 第 2 回オペレーティングシステム 48

49 マルチスレッドの利点 (1/2) 並列コンピュータ上でのプロセッサの有効利用 共有メモリ型並列コンピュータ上で プロセッサを有効利用が可能 マルチコアを活用可能 マルチコアの時代 半導体集積度が向上したが クロックを上げられない ( リーク電流 & 熱問題 ) 余った回路の使い道としてチップ内に複数プロセッサを搭載 2019/4/15 第 2 回オペレーティングシステム 49

50 マルチスレッドの利点 (2/2) 資源を共有可能 ファイルディスクリプタやメモリ領域の共有 メモリ管理のための構造体の共有 TLB の共有が可能 TLB の共有によりコンテキストスイッチ時に TLB flush が不必要 応答性の向上 例えばマルチスレッド WEB ブラウザでは イメージを読み込んでいるスレッドとユーザの入力を同時に処理が可能 シングルスレッドの場合は select を使った event driven 処理 2019/4/15 第 2 回オペレーティングシステム 50

51 スレッド利用の場面 サーバプロセスの応答性の向上 サーバプログラム 要求ごとにスレッドを生成し 処理と結果の応答を担当 例 :HTTPサーバ それぞれ別のスレッドでリクエストを処理 ウィンドウシステム それぞれ別のスレッドでイベントを待つ処理 2019/4/15 第 2 回オペレーティングシステム 51

52 スレッド利用の場面 CPU 処理と入出力処理の分割 プロセス P の処理を 計算を行うスレッド (Th1) と入出力を行うスレッド (Th2) に分割 Th1 と Th2 は 1 つのプログラムを実行 入出力待ちの間,Th2 は待ち状態になるが Th1 の処理は継続 Th2( 入出力 ) Th1( 計算 ) 依頼 入出力待ち 通知 2019/4/15 第 2 回オペレーティングシステム 52

53 スレッド利用の場面 並列計算 並列計算機を使って高速計算 例 : 行列の掛け算 各行を別スレッドで計算 メモリ空間を共有するので プロセス間通信するより高速 = 2019/4/15 第 2 回オペレーティングシステム 53

54 ( 補足 ) カーネルもマルチ化の時代 従来型のカーネル (SMP) マルチカーネル (AMP) VS OS Image OS Image OS Image OS Image 2019/4/15 第 2 回オペレーティングシステム 54