第９回プロセスの協調と排他制御並行プロセスと資源の競合  競合問題  セマフォ  −  不可分命令の実装 −  PV命令 Test & Set プロセス間通信並行プロセス並行実行(concurrent processing)されているプロセスの集合を並行プロセスを呼ぶ  並行プロセスの実行には様々な問題がある  − − − − 資源の競合クリティカルセクション競合問題(Racing Conditions) プロセス間通信資源の競合     ブロッキング : 他のプロセスが使用している共有資源が解放されるのを待機している状態ライブロック：共有資源を複数プロセスが譲り合う無限待機状態デッドロック：資源の依存関係がプロセス間で環状につながれている状態で、各プロセスが他のプロセスの占有している資源の解放を待っている無限待機状態飢餓状態：永久にブロッキングされている状態資源の待ち行列  OSの扱うスケジューリングは、プロセススケジューリング（CPUの割り当て）の他に、入出力装置の割り当ても含まれる入出力待ち行列入出力装置入出力装置 CPU 入出力装置 CPU待ち行列入出力装置資源競合の解決  防止策 − −  資源を獲得できたら実行複数の資源を獲得することを禁止解決策 − − ロールバック(rollback) ... いったん確保した資源を元に戻すプロセスの強制終了プロセス間の同期 (Process Synchronization) • 並行プロセスのプリミティブセット – parabegin ... paraend parabegin s1 // s2 // --- // Sn paraend • 以下の状態では、様々な値をとる可能性がある(プロセス間にデータ依存） parabegin a = b + c // c = i + j // j = a + b paraend 競合問題(Racing Conditions)  一般に、並行プロセスでは、２つのプロセス間のread setとwrite setが空集合でない場合、競合状態(Racing Conditions)を持つことになる Read Set Write Set Critical Section(きわどい領域）    Racing Conditionsを回避するため、ただ１つのプロセスのみが実行可能なプログラム区間この区間によって、read setとwrite setの重なりを無くすこの区間を実現するためには 1. 2. 3. 相互排除(mutual exclusion) 前進(progress) 有限待機(bounded waiting) 相互排除（mutual exclusion) ビジーウェイト ... lock – unlock  Test & Set 命令  セマフォ  Spin Lock (lock – unlock) lock L: if x then goto L else w <- true fi; unlock w <- false; • 共有変数によって、Critical Section （CS）の使用を示し、共有変数が真である場合は使用中で、偽である場合は空いている • lock 命令は、共有変数が偽であれば、真にして自分がCSに入るが、偽である場合は、真にセットされるまでビジーウェイティングする（spin lock) • unlock 命令で、共有変数を偽にセットして、CSを他のプロセスに解放する • ただし、共有変数の値のチェックと値のセットは、不可分命令で実装されてないと２つのプロセスが同時にCSに入れる可能性がある • シングルプロセッサの場合は、lock 操作時に割込み禁止（プロセスに切り替え禁止）にすればよい Test & Set Primitives マルチプロセッサシステムでは、プロセス間の同期をとるためには、同期変数の値のチェックとセットを不可分(atomic)に行わなければならない  このためハードウェア側で、同期変数（共有変数）のチェックと値のセットを一括処理する命令をTest & Set 命令(不可分命令）として用意している  Test & Set 命令は、値をセットし、セットする前の値を同時に読み込む enter_CS: tsl register flag cmp register #0 jnz enter_CS ret leave_CS: mov flag #0 ret  enter_CS(); Critical Section leave_CS(); セマフォ   P命令とV命令の２つの同期基本命令によってクリティカルセクションをはさむ P命令 ... P(s) : P(s): if ( s <= 0 ) 待ち行列にプロセスを登録して休眠状態(sleep)へ; else s = s – 1;  V命令 ... V(s) : V(s): P(s) s = s + 1; 待ち行列から一つプロセス取り出す(wakeup) P命令, V命令は不可分に処理されなければならない  ｓが１のとき、２値セマフォ（binary semaphore)といい、 lock, unlock 命令として適用可能である  資源の解放を待つ間、プロセスは自らCPUを手放して休眠する（サスペンドロック） Critical Section  V(s) プロセス協調における競合問題生産者-消費者問題  Reader-Writer Problem  哲学者の食事問題  相互排除の問題  − − ピーターソンのアルゴリズム Test & Set Primitive プロセス間通信    プロセス同士がデータの受け渡しを行いながら協調処理する割込み、シグナルを使うプリミティブなもの共有メモリ方式 −  複数のプロセスがアクセス可能なshared memory を用意し、この領域を利用してデータの受け渡しを実現するメッセージパッシング方式 − あるプロセスからメッセージの形で他のプロセスへデータの受け渡しを行うメッセージパッシング方式  直接通信方式 ... link は一つのみ − −  間接通信方式 ... link は複数 − チャネル(channe) ポート(port) メールボックス(mailbox) − send(チャネル、message), receive(チャネル、message) − −  send(pid,message) receive(pid,message) 総称してチャネル通信相手 − 1対多通信 ... 受信者多数。プロセスグループ or チャネルで定義マルチキャスト（multicast) − − 多対１通信 ... 送信者多数。送信者を特定しない多対多通信同期式通信と非同期式通信  同期式通信(synchronous communication) − −  メッセージの受け渡しが完了（確認）されるまで待ち続ける blocking 非同期式通信（asynchronous communication) − − − メッセージの受け渡し完了を待たず、メッセージをバッファリングして先に処理を進める non blocking バッファ式通信パイプ(pipe)    バイト単位のデータの読み出し/書き込みをプロセス間通信に拡張したもの一度読み出したデータは再び読み出すことはできない（stream:ストリーム) Unixのパイプでは、入出力とプロセス間通信のインターフェースを統一プロセスA プロセスB パイプ write read ソフトウェア割込み     プロセスにおいて、プロセスの実行とは独立して、個々の命令の実行によって発生する様々な事象をとらえる仕組み。ソフトウェア割込みでは、ハードウェア割込みと同様に個々の事象ごとに処理をするハンドラが定義される。定義された事象がプロセスの実行において発生すると、プロセスを中断して、ハンドラの処理を行い、その後、中断プロセスを再開するかそのままプログラムを終了させるシグナル: Unix やOS/2では、シグナル（signal)として実装されている − SIGINT, SIGHUP,SIGSEGV,SIGKILL など RPC（遠隔手続き呼び出し）  RPC(Remote Procedure Call) クライアント・サーバ型通信で用いられる − クライアントがサーバの手続き（関数）をローカル（自分持ち）の手続き（関数）を呼び出すのと同じように呼び出す − スタブ（stub） −   クライアントスタブ ... １．RPCから要求メッセージの作成と送信２．応答メッセージを受信してRPCに返すサーバスタブ... １. 要求メッセージを受信してサーバプログラムへ (RPC受理）２. RPCの実行結果を応答メッセージにして送信