Microsoft PowerPoint - 5_2-3IPC.pptx

Transcription

1 2.3.1 競合状態 (race condition) オペレーティングシステム プロセス間通信 Example Process A Process B i=0 i=0 while(i<10){ while(i>-10){ i++ i-- print A finished print B finished プロセス A スプーラディレクトリ ( ファイル印刷の待ち配列 ) ここまで印刷した shared memory Who will win? 変数 iを共有しているとする プロセス B 新たなファイル 2 つのプロセスが同時に共有変数にアクセスしようとする Operating System クリティカルリージョン (1) クリティカルリージョン (2) Race Conditions( 競合状態 ) Critical region / critical section 競合状態が起こり得る場所 ここに同時にはいらないよう制御する 解消するためには 2 つ以上のプロセスが共有データを同時に読み書きすることを防止する何らかの方法を見つけること Mutual exclusion( 相互排除 ) ある 1 つのプロセスが共有変数あるいは共有ファイルを使用中の時は 他のプロセスが同一の動作を行えない事を保証する何らかの方法 相互排除を行う事が出来る 4 つの条件 1. クリティカルリージョンに 2 つ以上のプロセスが同時に入ってはいけない 2. CPU の数と性能に関して一切仮定を設けてはならない 3. クリティカルリージョンの外で実行しているプロセスが他のプロセスをブロックしてはならない 4. クリティカルリージョンに入りたいプロセスが 永遠に待たされる事があってはならない Operating System Operating System

2 クリティカルリージョン (3) クリティカルリージョンを用いた相互排除 Operating System 2016 ビジーウェイトを用いた相互排除その 1 割り込みの不許可 ( ) 割り込みを許可しない方法 他のプロセスに切り替わらない ユーザプロセスに割り込み不許可の権限を与える事は現実的ではない 一つの CPU にしか効果がなく マルチプロセッサの場合は役に立たない OS カーネルはアトミックオペレーションを実現するためしばしばこの方法を使用する アトミックオペレーション 割り込みで切り替わる事なく処理される一連の操作の事 Operating System ビジーウェイトとスピンロック ビジーウェイト 変数がある値になるまでプログラム的に継続的にチェックする事 CPU 資源を消費するので通常は用いられない while(turn!= 0); //check if turn goes to 0 スピンロック ビジーウェイトを用いたロックの事 Operating System ビジーウェイトを用いた相互排除その 2 ロック変数 ( ) ソフトウェアによる解決方法 共有変数 turn( 初期値 0) が 0 の時 1 にセットしてクリティカルリージョンに入る turn をチェックする無限ループ while(turn!= 0); //check if turn goes to 0 turn = 1; //set turn to 1 (lock) [Critical section] turn = 0; //set turn to 0 (unlock) ここでプロセススイッチもしくは割り込みが起こり別プロセスに遷移し turn を 1 にしてしまう可能性がある 因みに turn の初期値は 0 である Operating System

3 ビジーウェイトを用いた相互排除その 3 完全な交互実行 ( ) while(turn!= 0) /*loop*/; critical_region(); turn = 1; noncritical_region(); process0 while(turn!= 1) /*loop*/; critical_region(); turn = 0; noncritical_region(); process1 turn にはクリティカルリージョンに入る事が出来るプロセスの番号が入っており つまり交互に実行する 片方のプロセスがもう一方のプロセスより非常に遅い場合 この方法は良い方法とは言えない プロセス 0 が速く いち早く 2 度目に入ろうとしてもプロセス 1 の番であり 待つ事になる この状況は 条件 3 を満たしていない プロセス 0 はクリティカルリージョンに入っていないプロセス 1 によってブロックされている Operating System 2016 Peterson の解決方法 turn 0 1 interested p0 によるクリティカルリージョン処理 p1 によるクリティカルリージョン処理 p0enter 即 return p1wait p0leave の return p1leave Operating System ビジーウェイトを用いた相互排除その 4 Peterson の解決方法 ( ) #define FALSE 0 #define TRUE 1 #define N 2 /* プロセス数 */ int turn; /* 誰の番か */ int interested[n]; /* 初期値は 0 (FALSE)*/ void enter_region(int process) { /* プロセスは 0 か 1 */ int other; /* 他のプロセス番号 */ other =1 process; /* 自分が 0 なら 1 1 なら 0 */ interested[process]=true; /* クリティカルリージョンに入りたい */ turn=process; /* フラグセット */ while(turn==process && interested[other]==true); /* ループで待つ ( 本体なし ) */ void leave_region(int process) { /*process who is leaving*/ interested[process]=false; /*indicate departure */ Operating System ビジーウェイトを用いた相互排除その 5 TSL(Test and Set Lock) 命令 (1) TSL RX, LOCK ハードウェアによる相互排除補助命令を利用する方法 TSL は メモリ内の共有変数 LOCK の内容をレジスタ RX にロードし LOCK の内容を 1 にするアセンブリ命令 読み出しと書き込み動作は不可分 ( 命令の途中で割り込まない ) である enter_region: TSL REG,LOCK LOCK の内容をレジスタ REG に書き LOCK を 1 にする CMP REG,#0 読んだ値 ( つまりレジスタ REG) が 0 か? JNE enter_region 0 でない ( つまり 1) 場合はループして待つ RET クリティカルリージョンに入る leave_region: MOVE LOCK,#0 LOCK を 0 にする RET Operating System

4 TSL 命令 LOCK p0 によるクリティカルリージョン処理 p1 によるクリティカルリージョン処理 p0enter 即 return p1wait p0leave の return p1leave プロセスがクリテイカルリージョンに入ろうとする前に ente_region( ロックが解除状態になるまで, この中でビジーウエイトする ) を呼び出し ロックを獲得して戻る クリテイカルリージョンから出る際に leave_region() を呼び出して lock に 0 を書き込む クリテイカルリージョン問題を解決するためには この約束を守って正しいタイミングで enter_region() と leave_region() の手続きを呼ばなければならない プロセスがこの約束を守らないと相互排除にはならない Operating System 生産者 消費者問題 ( 有限バッファ問題 ) ビジーウェイト (CPU を消費する ) を用いない方法 問題 : 生産者は共有バッファに新たな物を格納 消費者はそれを取り出し消費する 生産者 消費者を調整する機構が必要 バッファが満杯になったら生産者はどうするか? バッファが空になったら消費者はどうするか? 共有バッファ個数 N Producer( 生産者 ) Consumer( 消費者 ) Operating System 問題点 これまでの方法はスピンロックを使用しており CPU 資源を無駄に使う可能性がある また 考えていた 2 つのプロセスは対等であったのでうまく行ったが プロセスに優先順位がある場合はうまく行かない可能性がある ( 優先度逆転問題 ) プロセス A B があり B の優先順位が高いとする プロセス A がロックを獲得しクリティカルリージョンの処理を始める 優先順位が高いプロセス B が来たので プロセススイッチする プロセス B がロックを獲得しようとする ところがロックを A が獲得したままなので永久に待つ事になる Operating System 生産者 消費者問題の解 Sleep と Wakeup システムコールを使用 バッファが空になったら消費者は sleep 生産者がバッファに入れたら消費者は wakeup バッファが満杯になったら生産者は sleep 消費者が 1 つ以上消費したら生産者は wakeup #define N 100 /* バッファの個数 */ int count=0; /* バッファが埋まっている個数 */ void producer(void) { item = produce_item(); /* 生産 */ if(count == N) sleep(); insert_item(item); /* バッファに追加 */ count = count+1; If(count == 1) wakeup(consumer); /* 空?*/ void consumer(void) { if(count == 0) sleep(); item = remove_item(); /* バッファから削除 */ count = count-1; if(count == N-1) wakeup(producer); /* 満杯?*/ consume_item(item); /* 消費 */ Operating System

5 問題は? 致命的な競合状態が起こり得る count 変数へのアクセスが制限されない場合 ウエイクアップが失われる バッファ空 消費者 count 0 認識 スケジューラが生産者にスイッチ 項目を一つ格納 count++ 生産者は消費者を wakeup 消費者はまだ sleep していない wakeup が失われる 消費者は sleep する 生産者はバッファを満杯にし こちらも sleep( 両者永遠に sleep のまま ) 一つの解はウエイクアップ待ちビットの導入 ( まだ )sleep していないプロセスへの wakeup を紛失しない 3 プロセスなど もっと複雑な場合は複雑化する Operating System セマフォ (2) セマフォに対する 2 つの操作 : Down セマフォの値によって以下の動作をする 1 以上 : セマフォから 1 を減じる 0: そのままスリープに入る 値をチェックし 値を減じる / スリープすると言う一連の動作は単一の動作で アトミックアクション (Atomic Action) と呼ばれる ( その間に割込み ディスパッチが起こらない ) Up セマフォに 1 加える Operating System セマフォ (1) セマフォは非負の整数値を持つ スリープからウエイクアップすべき個数をカウントする 0: ウエイクアップすべきプロセスなし 0: ウエイクアップすべきプロセスの数 Operating System Down & Up 操作 Down(S): if (S==0) sleep(); else S = S-1; Up(S): S = S+1; S が 1 以上の時 down 操作によってスリープしているプロセスがある場合 そのプロセルを一つ起こす Example (s=1 initially) Down(s) <critical section> Up(s) S の初期値を 1 とする down() と up() はアトミックアクションである 同時に down() が呼ばれた場合も S は負数にはならない Operating System

6 S Down&Up 操作 p0 によるクリティカルリージョン処理 p1 によるクリティカルリージョン処理 p0down p1down p0up p1up p1sleep p1down の return Operating System セマフォでの生産者 消費者問題の解 (2) void producer(void) { void consumer(void) { item = produce_item();// 生産 down(&empty); down(&mutex); //CR に入る insert_item(item); // 追加 up(&mutex); //CR から出る up(&full); down(&full); down(&mutex); //CR に入る item = remove_item(); // 取出 up(&mutex); //CR から出る up(&empty); consume_item(item);// 消費 注 :CR= クリティカルリージョン Operating System セマフォでの生産者 消費者問題の解 (1) 3 つのセマフォを使用 mutex: 生産者と消費者が同時にバッファにアクセス出来ないよう制御する = 相互排除用 (1 に初期化 ) empty: バッファの空きスロット数 = 同期用 (N に初期化 ) full: バッファの使用スロット数 = 同期用 (0 に初期化 ) /* バッファのスロット数 */ #define N 100 /*a special kind of int*/ typedef unsigned int semaphore; /* クリティカルリージョンアクセス */ semaphore mutex = 1; /* バッファの空きスロット数 */ semaphore empty = N; /* バッファの使用スロット数 */ semaphore full = 0; Operating System Binary Semaphores 値は 0( アンロック ) か 1( ロック ) のみ down() 値が 1 になるのを待つ 1 になったら 0 にセット up() は値を 1 にセット ( 待っている物があれば ) 起こす mutex セマフォの単純形 ( 計数しない ) Operating System

7 2.3.6mutex(1) mutex は相互排除に使用される (1bit 又は整数 ) ロック (0 以外 ): クリティカルリージョン使用不可 アンロック状態 (0): クリティカルリージョン使用可 クリティカルリージョンに 入る際に mutex_lock を行う 出た時に mutex_unlock を行う mutex_lock: TSL REG,MUTEX MUTEX の値を REG に読出しその後 1 代入 CMP REG,#0 MUTEX の値は 1 だったか? JZE ok 0 ならロックされていないので戻る CALL thread_yield ロックされている場合は他のスレッド実行 JMP mutex_lock 再度実行 ok: RET mutex_unlock: MOVE MUTEX,0 MUTEX に 0 を入れアンロック状態に RET Operating System メッセージ通信 A high-level primitive for IPC 2 つのシステムコールで実現 : send and receive Send(destination, &message) Receive(source, &message) Can either block or return immediately Operating System mutex(2) スレッドの場合同一メモリアドレス空間だが 異なるプロセスは異なるアドレス空間で実行されている どのようにして セマフォやバッファなどのような 共有変数 をプロセス間で共有出来るのだろう? 2 つの方法 1. 共有変数をカーネル内に持たせ システムコールによってアクセスさせる 2. プロセスのアドレスの一部を他プロセスに共有させる手段を持たせる (Unix や Windows などの現代 OS では大体この機能を提供している ) Operating System メッセージ通信を用いた生産者 消費者問題 #define N 100 /* スロット数 */ void producer(void) { message m; /* メッセージバッファ */ void consumer(void) { message m; /* 最初に N 個の空きスロットを送る */ for(i=0; i<n; i++) send(producer, &m); item = produce_item(); /* 空きスロットの到着待ち */ receive(consumer, &m); /* 送信するメッセージ作成 */ build_messasge(&m, item); send(consumer, &m); /* 項目が入ったメッセージ獲得 */ receive(producer, &m); item = extract_item(&m); /* 空きスロット送信 */ send(producer, &m); consume_item(item); Operating System