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

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

加藤 真平

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

[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

デッドロック

• 資源を排他的利用しているプロセス集合において、あるプロセ

スが、他のプロセスが排他的利用している資源を確保しようと

して待ち状態になること

• SとQを初期値が1であるセマフォア

P

₀

P

₁

wait(S);

wait(Q);

wait(Q);

wait(S);





signal(S);

signal(Q);

signal(Q)

signal(S);

飢餓状態 (Starvation)

P0

while(1) {

Wait(S)

…

Signal(S)

}

P0とP1がセマフォSをとりあうと、P2は永遠にwait このようなP2の状態が飢餓状態

P1

while(1) {

Wait(S)

…

Signal(S)

}

P2

while(1) {

Wait(S)

…

Signal(S)

}

これは飢餓状態の一例である。実行したくても実行できない場合 を飢餓状態と呼ぶ。CPUスケジューリングにおいても飢餓状態が 発生する場合がある。

• 半永久的なブロッキング

• プロセスが停止したままセマフォアのキューから取り除かれる

ことがない状態

共有資源問題

• 共有資源とは？

– プロセス・スレッド間で交信のために使用するメモリ領域

– ファイル

– プリンタ

– グラフィックス

• 共有資源に対する排他的利用

– Bounded-Buffer問題

– Readers and Writers 問題

• 複数共有資源の排他的利用

Bounded-Buffer 問題

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);

• 共有メモリ

Readers-Writers問題

• 共有データ semaphore mutex=1, wrt=1; int readcount = 0; wait(wrt); … writing is performed … signal(wrt); wait(mutex); readcount++; if (readcount == 1) wait(wrt); signal(mutex); … reading is performed … wait(mutex); readcount--; if (readcount == 0) signal(wrt); signal(mutex): • Reader Processesは同時に実行 • Writer Processesは共有資源の修正なので、排他的に実行

• Writer Processesだけでなく、Reader Processesとも排他的実行

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 … • 複数資源を同時に取得しなければいけないような場合、ナイーブな プログラムだとデッドロックが発生 これはデッドロックを起こすプログラム。 解決は後ほど

同期構文導入の動機

• セマフォアによるプログラミングは煩雑

– Bounded-Buffer 問題

– Readers-Writers問題

– Dining-Philosophers 問題

• セマフォアによるプログラミングは構造化されていないために

プログラマが使用を間違えるとバグの温床

• 例えば

wait(S);

signal(S);

….

….

signal(S);

wait(S);

• このような問題を如何に容易にエレガントに記述できる言語機

能を提供できるか研究

と書くべきところを

Critical Regions

• タイプTを持つ共有メモリ領域vを以下のように宣言: v: shared T • 変数vは以下のような文Sの中でのみアクセス可能 region v when B do S Ｂはboolean式。Ｂが偽の時、真になるまで待機 Ｓを実行中他のプロセスはvをアクセス不可能

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--;

struct buffer { int pool[n];

int count, in, out; };

Monitors

• モニタ内の手続きは、一時期に一つのプロセスのみ実行

monitor monitor-name {

shared variable declarations

procedure body P1 (…) { . . . } procedure body P2 (…) { . . . } procedure body Pn (…) { . . . } { initialization code }

Monitors

• モニタ内で実行しているプロセスがwaitするためにcondition変数を使用 condition x, y; • Condition変数には、wait, signal操作が定義 – x.wait(); 他のプロセスによりx.signal()操作が実行されるまでwait – x.signal()； waitしているプロセスが動作 プロセスがwaitしていなければ何もしない

補足

モニタbuffer内で使用する局所データ （共有データ等）の宣言 共有データ等を操作する関数の定義 ⇒同時に複数のプロセスが実行できないようになっている （モニタに入るのは１プロセスのみ） 初期化コード monitor buffer { int no_of_data;

condition empty, full; get() { if (no_of_data == 0) empty.wait; バッファからデータを取り出す; full.signal; } C++/Java風に記述 put() { if (no_of_data >= N) full.wait; バッファにデータを格納する; empty.signal; } no_of_data = 0; }

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; }

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(); } } dp.pickup(0); …. eat … dp.putdown(0); dp.pickup(1); …. eat … dp.putdown(1); このプログラムでは、ある哲学者は飢餓状態

デッドロック問題

• System Model

• Deadlock Characterization

• Methods for Handling Deadlocks

• 資源を排他的利用しているプロセス集合において、あるプロセスが、他のプ ロセスが排他的利用している資源を確保しようとして待ち状態になること • 例

セマフォアA,Bは1で初期化している

P₀ P₁ wait (A); wait(B) wait (B); wait(A)

• Deadlock Prevention • Deadlock Avoidance • Deadlock Detection

• Recovery from Deadlock

補足

• 複数の資源R1, R2を同時に要求するプロセスP１とＰ２

– R1とR2を同時に使用できない場合は待ち状態に

• P1がR2をP2がR1を使用する時，両者とも永久に待ち状態

– Ｐ１： P(r2); P(r1); R1とR2の使用; V(r1); V(r2) – Ｐ２： 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); }

補足

• 複数の資源R1, R2を同時に要求するプロセスP１とＰ２

– R1とR2を同時に使用できない場合は待ち状態

• P1がR2をP2がR1を使用する時，両者とも永久に待ち状態

– Ｐ１： P(r2); P(r1); R1とR2の使用; V(r1); V(r2) – Ｐ２： P(r1); P(r2); R1とR2の使用; V(r2); V(r1) 資源→プロセス 資源がプロセスに割付けられ ている状態 プロセス→資源 プロセスが資源を要求してい るが，まだ未割当て プロセスP2 資源R1 プロセスP1 資源R2

循環待機

システムモデル

• リソース型： R

₁

, R

₂

, . . ., R

_m

CPU cycles, memory space, I/O devices

• リソース型 R

_i

に対してW

_i

がインスタンス

• 各プロセスは以下のプリミティブでリソースを使用

– request

– use

デッドロックの性質

• Mutual exclusion:

一つのプロセスのみがリソースを使用できること状態

• Hold and wait:

一つのプロセスが一つ以上のリソースを保持したうえで、 他のプロセスが保持するリソースを獲得するためにwaitしている状態

• No preemption:

あるリソースは、それを保持するプロセスがタスクを完了 したのちに自発的に行うことでのみ開放できるという状態

• Circular wait:

次の条件をみたすプロセスの集合

_{P

₀

_{, P}

₁

_,

_…

_{, P}

_n

_}

が存在す る状態 P₀ がP₁の保持するリソースをwaitしており、 P₁ は P₂, …, P_n–1 が保持するリ ソースをwaitし、 P₂ は・・・、 P_nは P₀のもつリソースをwait 以下の₄つの状態が同時に満たされているときデッドロックが生じる

リソース割り当てグラフ

• Vは二種類に分かれる

– P = {P

₁

, P

₂

,

…

, P

_n

}：

システム内すべてのプロセスからな

る集合

– R = {R

₁

, R

₂

,

…

, R

_m

}：

システム内すべてのリソースからな

る集合

• P

_i

によるR

_j

の要求を表す辺：

P

_i



R

_j

• R

_j

のP

_i

への割り当てを表す辺：

R

_j



P

_i

頂点の集合Vと辺の集合E

リソース割り当てグラフ

• プロセス

• 4つのインスタンスをもつリソース

• P

_i

がR

_j

を要求

• P

_i

は R

_j

を保持している

P_i R_j P_i R_j

循環グラフになっているが

デッドロック状態ではない場合

基本性質

• グラフに閉路あり

– デッドロックなし

• グラフに閉路あり

– リソースの種類一つにつき、それらのインスタンスはただ一

つの場合、デッドロック

– リソースの種類一つにつき、それらのインスタンスは複数あ

る場合、デッドロックの可能性あり

.

デッドロック問題に対する手法

• デッドロック予防(Deadlock Prevention)

– デッドロック状態にならないように共有資源の使い方を決定

• デッドロック回避(Deadlock Avoidance)

– デッドロック状態になると検知したらそれを回避

• 多くのシステムではデッドロック回避手法は実装されていない

• OS自身はデッドロックが生じないように注意深く設計

• プログラムがデッドロックするかどうかをソースプログラム

（あるいは仕様）からあらかじめ検査する研究

– モデル検査

Deadlock Prevention

• Mutual Exclusion

– 資源によっては、Mutual Exclusionを回避することは不可能

• Hold and Wait

– この状態を作らないようにするには、プロセスが資源を要求する時は、 そのプロセスは他の資源を占有しない – 方法１ • 実行前に使用する資源全てを占有 – 方法２ • プロセスが資源を要求する時は、そのプロセスは何も資源を占有していな いときに限定

– 問題点

• リソースが利用性が低下 • 飢餓状態になる可能性 ４つの状態が同時に生じないようにプログラミング

Deadlock Prevention (Cont.)

• No Preemption

– いくつかの資源を占有しているプロセスが、ある資源を占有

しようとして失敗したら、占有していた資源を解放

– 開放された資源は、このプロセスの資源リストに追加

– このプロセスは必要とする資源が開放されたら、再度資源の

占有を実行

• Circular Wait

–

全ての資源のtotal orderingを決め、その順番に資源を占有

Circular Wait != 十分条件

• 循環待ち → デッドロック発生

R1が２個の資源を持つ場合

P3が終わればP1が動作... P1がR2を解放する可能性 プロセスP2 プロセスP1 資源R2 プロセスP3 資源R1

デッドロックの回避

• それぞれのプロセスが必要なリソースの最大値をあらかじ

め宣言（単純かつ最も有用）

• Circular-wait状態をさけるため、リソースの確保状況を動的

に検査

– リソースの確保状況とは、利用可能な数とすでに確保されている数、 プロセスからの要求の最大値によって定義

システムは、いくつかのアプリオリな情報を利用可能であるこ

とが必要

ここでは、詳細な話はしない

デッドロックの回避

• スケジューリングによってデッドロックを回避

• 銀行家のアルゴリズム

– デッドロックを起こさない資源のプロセスへの割付け順を決定 （銀行家が資源の貸し出しを制御） プロ セス 保持している 資源数 U 必要な資源 の最大数 N A B A B P1 2 0 3 2 P2 0 1 2 1 ある時点の実行状態 必要な資源の最大数－保持している資源数 ＝残りの必要な資源数R Ri≦FなPiがあれば安全 例：資源Aは５個，資源Ｂは２個存在 現在の空き資源数 F=(2 0) 残りの必要な資源数 R=((1 2) (2 0) (1 1))

デッドロックの回避

• 例：資源Aは５個，資源Ｂは２個存在

– 現在の空き資源数 F=(2 0) – 残りの必要な資源数 R=((1 2) (2 0) (1 1)) ★ 初期値：W=(2 0), S=(偽 偽 偽） 1. WとRから要求を満足できるプロセスを探索 • P2のみ 2. WとSを更新しP2実行後の状態を計算 • W=W+(0 1)=(2 0)+(0 1)=(2 1) • S=(偽 真 偽) 3. １へ．ただし，P2を除く プロ セス 保持している 資源数 U 必要な資源の最大数 N A B A B P1 2 0 3 2 P2 0 1 2 1 P3 1 1 2 2 F＝

デッドロックの回避

• 例：資源Aは５個，資源Ｂは２個存在

– 現在の空き資源数F=(2 0) – 残りの必要な資源数R=((1 2) (2 0) (1 1)) ★ W=(2 1), S=(偽 真 偽） 1. WとRから要求を満足できるプロセスを探索 • P3のみ 2. WとSを更新 • W=W+(1 1)=(2 1)+(1 1)=(3 2) • S=(偽 真 真) 3. １へ．ただし，P2，P3を除く ➡ P1にも割付可能 Sの要素全てが真になればシステムは安全（P2, P3, P1の順に実行すればよい） プロ セス 保持している 資源数 U 必要な資源 の最大数 N A B A B P1 2 0 3 2 P2 0 1 2 1 P3 1 1 2 2

デッドロックを回避する割り当て

• 通常はプロセスが実行に合わせて資源要求を出してくる

– それを受け入れて良いかどうかの判断が必要 – 資源を与えてなお、デッドロック回避が可能（＝安全）な実行順があるか？

• 手順

– 要求が残り必要な資源数 R を超えていないことを確認 – 要求が利用可能な資源数 F を超えていたら、そのプロセスは待ち • そうでなければ次ステップの確認 – 要求を割り当てた後の残り必要資源 R を計算 • 利用可能資源 F から、要求の分を引いて W を初期化 • デッドロック回避が可能な実行順があるか調査 • なければ、そのプロセスは待ちにして残り必要資源 R の状態を元に戻す

デッドロックを回避する割り当て

プ ロ セ ス 保持している 資源数 U 必要な最大 資源数 N 残り必要資源数 R A B A B A B P1 2 0 3 2 1 2 P2 0 1 2 1 2 0 P3 1 1 2 2 1 1 総資源数：A 5個、B 2個 資源要求列 P3: A 1個 P2: A 1個 P1: A 1個 P1: B 1個 P3: B 1個 P2: A 1個 P1: B 1個 残り資源：A 個、B 個 2 0 ここでは、必要最大資源数が割 り当てられたらすぐにプロセス が終了 待 ○ 1 待 待 待 ○ 2 1 0 2 1 1 0 P2 終了 ○ 3 ○ 5 P3 終了 ○ 6 ○ 7 2 1 0 ○ 4 待 0 2

デッドロック検出と回復

• 検出

– システムがデッドロ ック状態か？

• 資源割付グラフ

– 要求 (P → R) – 割付 (R → P)

• 左図の一番下は

デッドロック

P1 R1 R2 P2 P3 R3 P4 P5 R4 P6 R5

R1 P1 P2 P4 R2 P3

デッドロックの検出

• グラフの簡約

– あるプロセスの資源要求が 満足されるとき，グラフは 当該プロセスにより簡約可 能という – 矢印を削除可能

• それでも循環待ちが残れば

デッドロック状態

デッドロックからの回復

• デッドロックを検出

– 循環待ちを解除しデッドロックから回復

– 具体的手法は以下のどちらか

1. デッドロック状態のプロセスを１つ異常終了

➡リスクはあるが最悪の事態は回避

2. デッドロック状態のプロセスを１つ前の状態に戻し

(rollback), やり直し

➡プログラムの実行状態を時々保存

（チェックポインティング）

演習問題 銀行家のアルゴリズム

• 資源Ａ：10個，B：5個，C：7個

プロセス 保持している資源数 必要な資源の最大数

Ａ

Ｂ

Ｃ

Ａ

Ｂ

Ｃ

P1

0

1

0

7

5

3

P2

2

0

0

3

2

2

P3

3

0

2

9

0

2

P4

2

1

1

2

2

2

Ｐ5

₀

₀

₂

₄

₃

₃

ある実行時点の状態

ライブロック

• デッドロック状態になっていないが、どのプロセスも

資源を獲得できない状態

– プロセスP0がR0をロック

– プロセスP1がR1をロック

– プロセスP0がR1をロックできないからR0をリリースしてR1

をロックしようとする

– プロセスP1がR0をロックできないからR1をリリースしてR0

をロックしようとする