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

Transcription

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

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

4 デッドロック 資源を排他的利用しているプロセス集合において あるプロセスが 他のプロセスが排他的利用している資源を確保しようとして待ち状態になること S と Q を初期値が 1 であるセマフォア P 0 P 1 wait(s); wait(q); wait(q); signal(s); signal(q) wait(s); signal(q); signal(s); 2018/5/14 第 5 回オペレーティングシステム 4

5 飢餓状態 (Starvation) 半永久的なブロッキング プロセスが停止したままセマフォアのキューから取り除かれることがない状態 P0 P1 P2 while(1) { Wait(S) Signal(S) } while(1) { Wait(S) Signal(S) } while(1) { Wait(S) Signal(S) } P0 と P1 がセマフォ S をとりあうと P2 は永遠に wait このような P2 の状態が飢餓状態 これは飢餓状態の一例である 実行したくても実行できない場合を飢餓状態と呼ぶ CPU スケジューリングにおいても飢餓状態が発生する場合がある 2018/5/14 第 5 回オペレーティングシステム 5

6 共有資源とは? 共有資源問題 プロセス スレッド間で交信のために使用するメモリ領域 ファイル プリンタ グラフィックス 共有資源に対する排他的利用 Bounded-Buffer 問題 Readers and Writers 問題 複数共有資源の排他的利用 Dining-Philosophers 問題 2018/5/14 第 5 回オペレーティングシステム 6

7 Bounded-Buffer 問題 共有メモリ semaphore full=0, empty=n, mutex=1; do { produce an item in nextp wait(empty); wait(mutex); add nextp to buffer signal(mutex); signal(full); } while (1); do { wait(full) wait(mutex); remove an item from buffer to nextc signal(mutex); signal(empty); consume the item in nextc } while (1); 2018/5/14 第 5 回オペレーティングシステム 7

8 共有データ semaphore mutex=1, wrt=1; int readcount = 0; wait(wrt); writing is performed signal(wrt); Readers-Writers 問題 Reader Processes は同時に実行 Writer Processes は共有資源の修正なので 排他的に実行 Writer Processes だけでなく Reader Processes とも排他的実行 wait(mutex); readcount++; if (readcount == 1) wait(wrt); signal(mutex); reading is performed wait(mutex); readcount--; if (readcount == 0) signal(wrt); signal(mutex): このプログラムでは Writer Processがwriteしたくても reader processが次から次に実行されると 待たされてしまう! 2018/5/14 第 5 回オペレーティングシステム 8

9 Dining-Philosophers 問題 複数資源を同時に取得しなければいけないような場合 ナイーブなプログラムだとデッドロックが発生 共有データ semaphore chopstick[5]; 初期値は 全て 1 これはデッドロックを起こすプログラム 解決は後ほど Philosopher i: do { wait(chopstick[i]) wait(chopstick[(i+1) % 5]) eat signal(chopstick[i]); signal(chopstick[(i+1) % 5]); think } while (1); 2018/5/14 第 5 回オペレーティングシステム 9

10 同期構文導入の動機 セマフォアによるプログラミングは煩雑 Bounded-Buffer 問題 Readers-Writers 問題 Dining-Philosophers 問題 セマフォアによるプログラミングは構造化されていないためにプログラマが使用を間違えるとバグの温床 例えば wait(s);. と書くべきところを signal(s); signal(s); wait(s); このような問題を如何に容易にエレガントに記述できる言語機能を提供できるか研究. 2018/5/14 第 5 回オペレーティングシステム 10

11 Critical Regions タイプ T を持つ共有メモリ領域 v を以下のように宣言 : v: shared T 変数 v は以下のような文 S の中でのみアクセス可能 region v when B do S B は boolean 式 B が偽の時 真になるまで待機 S を実行中他のプロセスは v をアクセス不可能 struct buffer { int pool[n]; int count, in, out; }; region buffer when (count < n) { pool[in] = nextp; in = (in+1) % n; count++; } region buffer when (count > 0) { nextc = pool[out]; out = (out+1) % n; count--; } 2018/5/14 第 5 回オペレーティングシステム 11

12 Monitors モニタ内の手続きは 一時期に一つのプロセスのみ実行 monitor monitor-name { shared variable declarations procedure body P1 ( ) {... } procedure body P2 ( ) {... } procedure body Pn ( ) {... } { initialization code } } 2018/5/14 第 5 回オペレーティングシステム 12

13 Monitors モニタ内で実行しているプロセスが wait するために condition 変数を使用 condition x, y; Condition 変数には wait, signal 操作が定義 x.wait(); 他のプロセスにより x.signal() 操作が実行されるまで wait x.signal(); wait しているプロセスが動作 プロセスが wait していなければ何もしない 2018/5/14 第 5 回オペレーティングシステム 13

14 補足 モニタ buffer 内で使用する局所データ ( 共有データ等 ) の宣言 monitor buffer { int no_of_data; condition empty, full; get() { if (no_of_data == 0) empty.wait; バッファからデータを取り出す ; full.signal; put() { if (no_of_data >= N) full.wait; バッファにデータを格納する ; empty.signal; } no_of_data = 0; } } 共有データ等を操作する関数の定義 同時に複数のプロセスが実行できないようになっている ( モニタに入るのは 1 プロセスのみ ) 初期化コード C++/Java 風に記述 2018/5/14 第 5 回オペレーティングシステム 14

15 Dining Philosophers 問題 monitor dp { enum {thinking, hungry, eating} state[5]; condition self[5]; void pickup(int i) // following slides void putdown(int i) // following slides void test(int i) // following slides void init() { for (int i = 0; i < 5; i++) state[i] = thinking; } } 2018/5/14 第 5 回オペレーティングシステム 15

16 Dining Philosophers 問題 void pickup(int i) { state[i] = hungry; test(i); if (state[i]!= eating) self[i].wait(); } void putdown(int i) { state[i] = thinking; // test left and right neighbors test((i+4) % 5); test((i+1) % 5); } void test(int i) { if ( (state[(i + 4) % 5]!= eating) && (state[i] == hungry) && (state[(i + 1) % 5]!= eating)) { } state[i] = eating; self[i].signal(); 2018/5/14 第 5 回オペレーティングシステム 16 } dp.pickup(0);. eat dp.putdown(0); このプログラムでは ある哲学者は飢餓状態になりうる どういう場合か考えてみよう dp.pickup(1);. eat dp.putdown(1);

17 デッドロック問題 資源を排他的利用しているプロセス集合において あるプロセスが 他のプロセスが排他的利用している資源を確保しようとして待ち状態になること 例セマフォアA,Bは1で初期化している P 0 P 1 wait (A); wait(b) wait (B); wait(a) System Model Deadlock Characterization Methods for Handling Deadlocks Deadlock Prevention Deadlock Avoidance Deadlock Detection Recovery from Deadlock Combined Approach to Deadlock Handling 2018/5/14 第 5 回オペレーティングシステム 17

18 補足 複数の資源 R1, R2 を同時に要求するプロセス P1 と P2 R1 と R2 を同時に使用できない場合は待ち状態に P1 が R2 を P2 が R1 を使用する時, 両者とも永久に待ち状態 P1: P(r2); P(r1); R1 と R2 の使用 ; V(r1); V(r2) P2: P(r1); P(r2); R1 と R2 の使用 ; V(r2); V(r1) void thead1() { P(r1); P(r2); /* R1とR2を使用 */ V(r2); V(r1); } thead2 { P(r2); P(r1); /* R1とR2を使用 */ V(r1); V(r2); } 2018/5/14 第 5 回オペレーティングシステム 18

19 補足 複数の資源 R1, R2 を同時に要求するプロセス P1 と P2 R1 と R2 を同時に使用できない場合は待ち状態 P1 が R2 を P2 が R1 を使用する時, 両者とも永久に待ち状態 P1: P(r2); P(r1); R1 と R2 の使用 ; V(r1); V(r2) P2: P(r1); P(r2); R1 と R2 の使用 ; V(r2); V(r1) 資源 R1 プロセス P1 循環待機 資源 R2 資源 プロセス資源がプロセスに割付けられている状態 プロセス P2 プロセス 資源プロセスが資源を要求しているが, まだ未割当て 2018/5/14 第 5 回オペレーティングシステム 19

20 システムモデル リソース型 : R 1, R 2,..., R m CPU cycles, memory space, I/O devices リソース型 R i に対して W i がインスタンス 各プロセスは以下のプリミティブでリソースを使用 request use release 2018/5/14 第 5 回オペレーティングシステム 20

21 デッドロックの性質 以下の 4 つの状態が同時に満たされているときデッドロックが生じる Mutual exclusion: 一つのプロセスのみがリソースを使用できること状態 Hold and wait: 一つのプロセスが一つ以上のリソースを保持したうえで 他のプロセスが保持するリソースを獲得するために wait している状態 No preemption: あるリソースは それを保持するプロセスがタスクを完了したのちに自発的に行うことでのみ開放できるという状態 Circular wait: 次の条件をみたすプロセスの集合 {P 0, P 1,, P n } が存在する状態 P 0 が P 1 の保持するリソースを wait しており P 1 は P 2,, P n 1 が保持するリソースを wait し P 2 は P n は P 0 のもつリソースを wait 2018/5/14 第 5 回オペレーティングシステム 21

22 リソース割り当てグラフ 頂点の集合 V と辺の集合 E V は二種類に分かれる P = {P 1, P 2,, P n }: システム内すべてのプロセスからなる集合 R = {R 1, R 2,, R m }: システム内すべてのリソースからなる集合 P i による R j の要求を表す辺 :P i R j R j の P i への割り当てを表す辺 : R j P i 2018/5/14 第 5 回オペレーティングシステム 22

23 プロセス リソース割り当てグラフ 4 つのインスタンスをもつリソース P i が R j を要求 P i P i は R j を保持している R j P i Rj 2018/5/14 第 5 回オペレーティングシステム 23

24 リソース割り当てグラフの例 2018/5/14 第 5 回オペレーティングシステム 24

25 デッドロック状態 2018/5/14 第 5 回オペレーティングシステム 25

26 循環グラフになっているがデッドロック状態ではない場合 2018/5/14 第 5 回オペレーティングシステム 26

27 基本性質 グラフに閉路あり デッドロックなし グラフに閉路あり リソースの種類一つにつき それらのインスタンスはただ一つの場合 デッドロック リソースの種類一つにつき それらのインスタンスは複数ある場合 デッドロックの可能性あり. 2018/5/14 第 5 回オペレーティングシステム 27

28 デッドロック問題に対する手法 デッドロック予防 (Deadlock Prevention) デッドロック状態にならないように共有資源の使い方を決定 デッドロック回避 (Deadlock Avoidance) デッドロック状態になると検知したらそれを回避 多くのシステムではデッドロック回避手法は実装されていない OS 自身はデッドロックが生じないように注意深く設計 プログラムがデッドロックするかどうかをソースプログラム ( あるいは仕様 ) からあらかじめ検査する研究 モデル検査 2018/5/14 第 5 回オペレーティングシステム 28

29 Deadlock Prevention 4 つの状態が同時に生じないようにプログラミング Mutual Exclusion 資源によっては Mutual Exclusion を回避することは不可能 Hold and Wait この状態を作らないようにするには プロセスが資源を要求する時は そのプロセスは他の資源を占有しない 方法 1 実行前に使用する資源全てを占有 方法 2 プロセスが資源を要求する時は そのプロセスは何も資源を占有していないときに限定 問題点 リソースが利用性が低下 飢餓状態になる可能性 2018/5/14 第 5 回オペレーティングシステム 29

30 Deadlock Prevention (Cont.) No Preemption いくつかの資源を占有しているプロセスが ある資源を占有しようとして失敗したら 占有していた資源を解放 開放された資源は このプロセスの資源リストに追加 このプロセスは必要とする資源が開放されたら 再度資源の占有を実行 Circular Wait 全ての資源の total ordering を決め その順番に資源を占有 2018/5/14 第 5 回オペレーティングシステム 30

31 Circular Wait!= 十分条件 循環待ち デッドロック発生 R1 が 2 個の資源を持つ場合 プロセス P1 プロセス P3 資源 R1 資源 R2 P3 が終われば P1 が動作... P1 が R2 を解放する可能性 プロセス P2 2018/5/14 第 5 回オペレーティングシステム 31

32 デッドロックの回避 システムは いくつかのアプリオリな情報を利用可能であることが必要 それぞれのプロセスが必要なリソースの最大値をあらかじめ宣言 ( 単純かつ最も有用 ) Circular-wait 状態をさけるため リソースの確保状況を動的に検査 リソースの確保状況とは 利用可能な数とすでに確保されている数 プロセスからの要求の最大値によって定義 ここでは 詳細な話はしない 2018/5/14 第 5 回オペレーティングシステム 32

33 デッドロックの回避 スケジューリングによってデッドロックを回避 銀行家のアルゴリズム デッドロックを起こさない資源のプロセスへの割付け順を決定 ( 銀行家が資源の貸し出しを制御 ) 例 : 資源 A は 5 個, 資源 B は 2 個存在現在の空き資源数 F=(2 0) 残りの必要な資源数 R=((1 2) (2 0) (1 1)) 必要な資源の最大数 - 保持している資源数 = 残りの必要な資源数 R Ri F な Pi があれば安全 プロセス ある時点の実行状態 保持している資源数 U 必要な資源の最大数 N A B A B P P P /5/14 第 5 回オペレーティングシステム 33

34 デッドロックの回避 例 : 資源 A は 5 個, 資源 B は 2 個存在 現在の空き資源数 F=(2 0) 残りの必要な資源数 R=((1 2) (2 0) (1 1)) F= 初期値 :W=(2 0), S=( 偽偽偽 ) 1. WとRから要求を満足できるプロセスを探索 P2のみ 2. WとSを更新しP2 実行後の状態を計算 W=W+(0 1)=(2 0)+(0 1)=(2 1) S=( 偽真偽 ) 3. 1へ. ただし,P2を除く プロセス 保持している資源数 U 必要な資源の最大数 N A B A B P P P /5/14 第 5 回オペレーティングシステム 34

35 デッドロックの回避 例 : 資源 A は 5 個, 資源 B は 2 個存在 現在の空き資源数 F=(2 0) 残りの必要な資源数 R=((1 2) (2 0) (1 1)) W=(2 1), S=( 偽真偽 ) 1. WとRから要求を満足できるプロセスを探索 P3のみ 2. WとSを更新 プロセス 保持している資源数 U 必要な資源の最大数 N A B A B W=W+(1 1)=(2 1)+(1 1)=(3 2) S=( 偽真真 ) 3. 1 へ. ただし,P2,P3 を除く P P P1 にも割付可能 P S の要素全てが真になればシステムは安全 (P2, P3, P1 の順に実行すればよい ) 割付できないときは, 前の状態に戻して別の候補について調べる 2018/5/14 第 5 回オペレーティングシステム 35

36 デッドロックを回避する割り当て 通常はプロセスが実行に合わせて資源要求を出してくる それを受け入れて良いかどうかの判断が必要 資源を与えてなお デッドロック回避が可能 (= 安全 ) な実行順があるか? 手順 要求が残り必要な資源数 R を超えていないことを確認 要求が利用可能な資源数 F を超えていたら そのプロセスは待ち そうでなければ次ステップの確認 要求を割り当てた後の残り必要資源 R を計算 利用可能資源 F から 要求の分を引いて W を初期化 デッドロック回避が可能な実行順があるか調査 なければ そのプロセスは待ちにして残り必要資源 R の状態を元に戻す 2018/5/14 第 5 回オペレーティングシステム 36

37 デッドロックを回避する割り当て 総資源数 :A 5 個 B 2 個 プロセス 保持している資源数 U 必要な最大資源数 N 残り必要資源数 R A B A B A B P 資源要求列 P3: A 1 個 P2: A 1 個 待 1 P2 終了 3 P3 終了 P P1: A 1 個 待 4 P 残り資源 :A 個 B 個 P1: B 1 個 P3: B 1 個 P2: A 1 個 待待 2 待 5 6 ここでは 必要最大資源数が割り当てられたらすぐにプロセスが終了 P1: B 1 個 /5/14 第 5 回オペレーティングシステム 37

38 デッドロック検出と回復 P5 P1 R1 R2 P2 P3 R3 P4 R4 P6 検出 システムがデッドロック状態か? 資源割付グラフ 要求 (P R) 割付 (R P) 左図の一番下はデッドロック R5 2018/5/14 第 5 回オペレーティングシステム 38

39 デッドロックの検出 P1 R1 P2 グラフの簡約 あるプロセスの資源要求が満足されるとき, グラフは当該プロセスにより簡約可能という P4 R2 P3 矢印を削除可能 それでも循環待ちが残ればデッドロック状態 2018/5/14 第 5 回オペレーティングシステム 39

40 デッドロックからの回復 デッドロックを検出 循環待ちを解除しデッドロックから回復 具体的手法は以下のどちらか 1. デッドロック状態のプロセスを 1 つ異常終了 リスクはあるが最悪の事態は回避 2. デッドロック状態のプロセスを 1 つ前の状態に戻し (rollback), やり直し プログラムの実行状態を時々保存 ( チェックポインティング ) 2018/5/14 第 5 回オペレーティングシステム 40

41 演習問題銀行家のアルゴリズム 資源 A:10 個,B:5 個,C:7 個 ある実行時点の状態 プロセス 保持している資源数 必要な資源の最大数 A B C A B C P P P P P 途中の計算過程を必ず示すこと 2018/5/14 第 5 回オペレーティングシステム 41

42 ライブロック デッドロック状態になっていないが どのプロセスも資源を獲得できない状態 プロセス P0 が R0 をロック プロセス P1 が R1 をロック プロセス P0 が R1 をロックできないから R0 をリリースして R1 をロックしようとする プロセス P1 が R0 をロックできないから R1 をリリースして R0 をロックしようとする 2018/5/14 第 5 回オペレーティングシステム 42