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

(1)

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

加藤真平

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

[email protected]

PFLab（加藤研）のウェブサイトからダウンロードできます。 ⇒http://www.pf.is.s.u-tokyo.ac.jp/ja/classes/

(2)

講義概要

• 受講生に求める基礎知識

– C言語の理解

– コンピュータアーキテクチャの基礎の理解

• メモリ管理、割り込み、CPUモード

• 参考図書

– Silberschatz, Galvin, and Gagne, Operating System Concepts 8th

Edition,

Wiley

• 成績

– 試験の点数で決定

– 試験は持ち込み不可

– 授業に出席していた人で試験の結果が悪い人は追試験あり

• 出席をとるが出席点はなし

(3)

講義スケジュール（予定）

1. OSの概要（4/8） 2. プロセス管理（4/15） 3. プロセス間交信、スレッド（4/22） 4. プロセス同期（5/13） 5. CPUスケジューリング 1（5/20）

6. CPUスケジューリング 2 & トランザクション処理&メモリ管理１（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）

(4)

Pthread

(1/2)

• int pthread_create(pthread_t *thread, pthread_attr_t * attr, void * (*start_routine)(void *), void * arg); • void pthread_exit(void *retval);

• int pthread_join(pthread_t th, void **thread_return); • int pthread_detach(pthread_t th);

• pthread_t pthread_self(void);

• int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutex‐attr_t *mutexattr); • int pthread_mutex_lock(pthread_mutex_t *mutex));

• int pthread_mutex_trylock(pthread_mutex_t *mutex); • int pthread_mutex_unlock(pthread_mutex_t *mutex); • int pthread_mutex_destroy(pthread_mutex_t *mutex);

• int pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *cond_attr); • Int pthread_cond_signal(pthread_cond_t *cond);

• int pthread_cond_broadcast(pthread_cond_t *cond);

• Int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);

• int pthread_cond_timedwait(pthread_cond_t *cnd, pthread_mutex_t *mtx, const struct timespec *at); • int pthread_cond_destroy(pthread_cond_t *cond);

(5)

Pthread (2/2)

• ipthread_attr_init, pthread_attr_destroy, pthread_attr_setdetachstate, pthread_attr_getdetachstate, pthread_attr_setschedparam, pthread_attr_getschedparam, pthread_attr_setschedpolicy,

pthread_attr_getschedpolicy, pthread_attr_setinheritsched, pthread_attr_getinheritsched, pthread_attr_setscope, pthread_attr_getscope pthread_attr_init, pthread_setschedparam, pthread_getschedparam, pthread_equal

(6)

Bounded Buffer using pthread (1/3)

#include <stdlib.h> #include <stdio.h> #include <pthread.h> #define N_ITEM 8 #define N_PRODUCER 4 #define N_CONSUMER 4 #define BSIZE 8 int buf[BSIZE]; int count; int in, out; int waiting; pthread_mutex_t bbmutex; pthread_cond_t bbcond; pthread_barrier_t pbarrier; void bbinit() { pthread_mutex_init(&bbmutex, NULL); pthread_cond_init(&bbcond, NULL); in = out = waiting = 0; main() { int i, cc; pthread_t pth[N_PRODUCER+N_CONSUMER]; void *retval; pthread_barrier_init(&pbarrier, 0, N_PRODUCER+N_CONSUMER); for (i = 0; i < N_PRODUCER; i++) {

cc = pthread_create(&pth[i], NULL, producer, 0); if (cc != 0) { perror("main"); exit(-1); }

}

for (i = 0; i < N_CONSUMER; i++) {

cc = pthread_create(&pth[i + N_PRODUCER], NULL, consumer, 0); if (cc != 0) { perror("main"); exit(-1); }

}

for (i = 0; i < (N_PRODUCER + N_CONSUMER); i++) { pthread_join(pth[i], &retval);

pthread_detach(pth[i]);

if (cc != 0) { perror("main"); exit(-1); } }

(7)

Bounded Buffer using pthread (2/3)

void *producer(void *arg) { int ret = 0;

int i;

pthread_barrier_wait(&pbarrier);

for (i = 0; i < (N_CONSUMER*N_ITEM)/N_PRODUCER; i++) put(i); pthread_exit(&ret);

return 0; }

void *consumer(void *arg) { int ret = 0; int val;

int i;

pthread_barrier_wait(&pbarrier); for (i = 0; i < N_ITEM; i++) {

val = get(i); }

pthread_exit(&ret); return 0;

(8)

Bounded Buffer using pthread (3/3)

int get() { int val; pthread_mutex_lock(&bbmutex); retry: if (count > 0) { val = buf[out]; --count;

out = (out + 1) % BSIZE; if (waiting) { pthread_cond_signal(&bbcond); } } else { waiting++; pthread_cond_wait(&bbcond, &bbmutex); --waiting; goto retry; } pthread_mutex_unlock(&bbmutex); return val; }

void put(int val) {

pthread_mutex_lock(&bbmutex); retry: if (count < BSIZE) { buf[in] = val; count++; in = (in + 1) % BSIZE; if (waiting) { pthread_cond_signal(&bbcond); } } else { waiting++; pthread_cond_wait(&bbcond, &bbmutex); --waiting; goto retry; } pthread_mutex_unlock(&bbmutex); return; }

(9)

セマフォア(Semaphores)

• Semaphore S

– 整数型変数

• ２つのatomicな操作

wait (S):

signal (S):

while S



0 do no-op;

S--;

S++;

(10)

n Processesによるクリティカルセクション

• Shared data:

• Process Pi:

do {

wait(mutex);

critical section

signal(mutex);

remainder section

} while (1);

(11)

Busy Waitで良いの？

• 単一CPU上でBusy waitしたらどうなる？

(12)

Busy waitしないセマフォアの実装

• 2つのプリミティブを仮定: – block() は呼び出したプロセ スを一時的に停止 – wakeup(P) はブロックされ ていたプロセスPを実行を再開 • これらプリミティブはOSカーネルによって実現（プロセスの実行状態を変更するため） • Wait/signal処理はatomicに処理 typedef struct { int value; struct process *L; } semaphore; wait(S): S.value--; if (S.value < 0) {

add this process to S.L;

block(); }

signal(S):

S.value++;

if (S.value <= 0) {

(13)

同期ツールとしてのSemaphore

• P

_j

におけるBの実行をP

_i

におけるAの実行の後に

• semaphore flag の初期値は0

• Code:

P

_i

P

_j



A

wait(flag)

signal(flag)

B

(14)

セマフォアの種類

• Counting セマフォア

– 整数値を使用

• Binary セマフォア

– ０か１

• CountingセマフォアはBinaryセマフォアで実現

可能（以下説明）

(15)

バイナリセマフォアによる

カウンティングセマフォア実装

• データ構造&初期値:

binary-semaphore S1 = 1; binary-semaphore S2 = 0;

int C = initial value of semaphore S:

• wait operation • signal operation

S1: クリティカルセクション実現用 S2: プロセスwait用 wait(S1); C--; if (C < 0) { signal(S1); wait(S2); } signal(S1); wait(S1); C++; if (C <= 0) { signal(S2); else signal(S1); この段階で、signal操作側は、 S1に対するsignalは未発行

(16)

デッドロック

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

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

して待ち状態になること

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

P

₀

P

₁

wait(S);

wait(Q);

wait(S);



signal(S);

signal(Q);

signal(Q)

signal(S);

(17)

飢餓状態 (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スケジューリングにおいても飢餓状態が

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

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

ことがない状態

(18)

共有資源問題

• 共有資源とは？

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

– ファイル

– プリンタ

– グラフィックス

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

– Bounded-Buffer問題

– Readers and Writers 問題

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

(19)

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

• 共有メモリ

(20)

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は共有資源の修正なので、排他的に実行

(21)

Dining-Philosophers問題

• 共有データ semaphore chopstick[5]; Philosopher i: do { wait(chopstick[i]) wait(chopstick[(i+1) % 5]) … eat … signal(chopstick[i]); signal(chopstick[(i+1) % 5]); … think • 複数資源を同時に取得しなければいけないような場合、ナイーブな プログラムだとデッドロックが発生これはデッドロックを起こすプログラム。解決は後ほど

(22)

同期構文導入の動機

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

– Bounded-Buffer 問題

– Readers-Writers問題

– Dining-Philosophers 問題

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

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

• 例えば

wait(S);

signal(S);

….

signal(S);

wait(S);

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

能を提供できるか研究

と書くべきところを

(23)

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;

region buffer when (count > 0) { nextc = pool[out];

out = (out+1) % n; struct buffer {

int pool[n];

int count, in, out; };

(24)

Monitors

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

monitor monitor-name {

shared variable declarations

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

(25)

Monitors

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

(26)

補足

モニタ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; }

(27)

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

(28)

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

(29)

デッドロック問題

• 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

(30)

補足

• 複数の資源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);

(31)

補足

• 複数の資源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

循環待機

(32)

システムモデル

• リソース型： R

₁

, R

₂

, . . ., R

_m

CPU cycles, memory space, I/O devices

• リソース型 R

_i

に対してW

_i

がインスタンス

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

– request

– use

(33)

デッドロックの性質

• Mutual exclusion:

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

• Hold and wait:

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

• No preemption:

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

• Circular wait:

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

_{P

₀

_{, P}

₁

_,

_…

_{, P}

_n

_}

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

(34)

リソース割り当てグラフ

• 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

(35)

リソース割り当てグラフ

• プロセス

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

• P

_i

がR

_j

を要求

• P

_i

は R

_j

を保持している

P_i R_j P_i R_j

(36)

(37)

(38)

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

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

(39)

基本性質

• グラフに閉路あり

– デッドロックなし

• グラフに閉路あり

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

つの場合、デッドロック

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

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

.

(40)

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

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

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

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

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

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

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

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

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

– モデル検査

(41)

Deadlock Prevention

• Mutual Exclusion

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

• Hold and Wait

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

– 問題点

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

(42)

Deadlock Prevention (Cont.)

• No Preemption

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

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

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

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

占有を実行

• Circular Wait

–

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

(43)

Circular Wait != 十分条件

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

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

P3が終わればP1が動作... プロセスP2 プロセスP1 資源R2 プロセスP3 資源R1

(44)

デッドロックの回避

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

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

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

に検査

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

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

とが必要

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

(45)

デッドロックの回避

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

• 銀行家のアルゴリズム

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

(46)

デッドロックの回避

• 例：資源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 F＝

(47)

デッドロックの回避

• 例：資源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

(48)

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

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

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

• 手順

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

(49)

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

プロセス保持している資源数 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

(50)

デッドロック検出と回復

• 検出

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

• 資源割付グラフ

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

• 左図の一番下は

デッドロック

P1 R1 R2 P2 P3 R3 P4 P5 R4 P6 R5

(51)

R1 P1 P2 P4 R2 P3

デッドロックの検出

• グラフの簡約

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

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