Microsoft PowerPoint - OS06.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - OS06.pptx"

えみかみいしづ
5 years ago
Views:

1 この資料は情報工学レクチャーシリーズ松尾啓志著 ( 森北出版株式会社 ) を用いて授業を行うために名古屋工業大学松尾啓志津邑公暁が作成しました並行プロセスモニタパワーポイント 2007 で最終版として保存しているため変更はできませんが授業でお使いなる場合は松尾 (matsuo@nitech.ac.jp) まで連絡いただければ編集可能なバージョンをお渡しする事も可能です排他制御の枠組み復習セマフォ復習プロセス協調問題 Producer-Consumer プロセス間通信, 計算機間通信 P 命令リソース獲得要求, 失敗時には待ち状態に移行 V 命令リソース解放, 待ちプロセスを実行可能状態にリソースを獲得できなかったプロセスは待ち状態にビジーウェイトが発生しない Reader-Writer データベースアクセス制御 Dining Philosophers 複数リソースを要求する場合デッドロックの考慮が重要

2 セマフォの問題点 6.1 セマフォの問題点ユーザ依存 P 命令発行せずにクリティカルセクションにアクセス可能他のプロセスからリソースの状況が判断不可能に V 命令 P 命令でリソースへのアクセス権を獲得し, アクセス終了後に V 命令を実行しないことも可能他のプロセスは永遠にリソースへのアクセス不可能全てユーザ ( プログラマ ) の良識責任に任せられているモニタモニタモニタセマフォより洗練された排他制御の仕組みオブジェクト指向の枠組みモニタの詳細... の前に最近では Java の同期機構として採用されている

3 オブジェクト指向 6.2 オブジェクト指向プログラミングとは? オブジェクト指向 ( プログラミング ) オブジェクト ( 物体 ) 同士の相互作用としてシステムの振る舞いをとらえる考え方プログラムの構造を, オブジェクト群の相互作用およびその雛形であるクラスの関係として捉えるオブジェクト指向言語 C++ Java Smalltalk Objective-C Python(?) Ruby(?) オブジェクト指向の概念クラスクラス (class) メソッド (method) インスタンス (instance) クラスあるオブジェクトの特徴や機能を定義するたとえば自動車さまざまな内部状態の集まりで表現できる class 自動車 { 投入燃料量 ; 制動力 ; タイヤ角度 ; ブレーキランプ ;

4 メソッド減速させたいとき投入燃料量 = 0; 制動力 += n; ブレーキランプ = on; if ( スリップ ){... ; 物体に対する深い知識が必要手順が面倒システムとして異常な動作も許してしまう例 ) 減速中でないのにブレーキランプ = on; class 自動車 { 投入燃料量 ; 制動力 ; タイヤ角度 ; ブレーキランプ ; メソッドオブジェクトに対する操作をメソッドとして外に提供操作を系統的にカプセル化外からタッチ可能な範囲を限定メソッドを通じてのみオブジェクトの内部状態を変更可能に誤操作が減る class 自動車 { public 減速 (n){ 投入燃料量 = 0; 制動力 += n; ブレーキランプ = on; if( スリップ ){... private 投入燃料量 ; 制動力 ; タイヤ角度 ; ブレーキランプ ; インスタンスクラスあくまでオブジェクトの定義インスタンスあるクラスの実例であるオブジェクトメソッド呼びは, インスタンス ( 実体 ) に対して行う class 自動車 { public 減速 ( n ){ private 自動車 A 氏の自動車 ; main(){ A 氏の自動車. 減速 (10); 6.3 モニタ

5 セマフォとモニタモニタセマフォモニタカプセル化提唱者 Dijkstra (1965) Hoare (1978) wait / signal / queue 形態手続き ( サブルーチン ) 構造化 ( オブジェクト指向 ) 可読性保守性低高以下, 実例を通じて... 提供形態ライブラリ等言語仕様の一部モニタにおけるカプセル化共有変数へのアクセス共有リソース直接アクセス禁止メソッドを通じてのみアクセス可能不正な直接アクセスはコンパイル時に検出メソッド排他的他のプロセスがメソッド呼び出し中は, 待ち状態へ monitor{ public use_resource1(n){ リソース 1 += n; use_resource2(){ private リソース 1; リソース 2; プロセスAとプロセスBがテープにアクセスプロセスBが確保中プロセスAによる確保とプロセスBによる解放が発生テープの空き数共有変数 A B 空きテープ

6 共有変数へのアクセス復習リーダライタ問題 Shared_I num; ライタによる書き込み中は読み出し不可同時には 1 ライタのみ書き込み可 monitor Shared_I { private int I; public increment( amount ){ I += amount; decrement( amount ){ I -= amount; num.decrement(1); テープ利用 ; num.increment(1); num.decrement(1); テープ利用 ; num.increment(1); 共有変数へのアクセスはメソッドを通じてのみプログラマは排他制御のための記述の必要なし同時に複数リーダが読み出し可 Writer Writer Writer Reader Reader Database Reader リーダライタ問題 ( その1) 条件変数 monitor Reader_Writer_1{ private int Readers = 0; int Writers = 0; boolean busy = FALSE; public start_read(){ while(writers!=0){; Readers += 1; finish_read(){ Readers -= 1; start_write(){ Writers += 1; while( busy Readers!=0 ){; busy = TRUE; finish_write(){ Writers -= 1; busy = FALSE; Reader_Writer_1 lock; lock.start_write(); lock.start_read(); DBに書く ; DBから読む ; lock.finish_write(); lock.finish_read(); 無限ループによる待機中, 他プロセスはモニタにアクセスできない条件変数ある条件が成立するまでプロセススレッドを待機させる仕組み条件変数操作のためのメソッド wait 待ち状態に移行 signal 待ち状態にあるプロセスのうち 1 つを実行可能に queue 待ち状態のプロセスの有無を返す

7 条件変数のイメージ wait 待ち状態に移行 signal 待ち状態にあるプロセスのうち 1 つを実行可能に queue 待ち状態のプロセスの有無を返す class condition{ private 待ち行列 ; public wait(){ プロセスを待ち行列に追加 ; signal(){ 待ち行列からプロセスを選択し, 実行可能に ; queue(){ if( 待ち行列の長さ > 0 ) return TRUE; else return FALSE; monitor Reader_Writer_2{ private int Readers = 0; int Writers = 0; condition OK_read, OK_write; public start_read(){ if( busy OK_write.queue() ) OK_read.wait(); Readers += 1; while( OK_read.queue() ) OK_read.signal(); finish_read(){ Readers -= 1; if( Readers == 0 ) OK_write.signal(); start_write(){ if( Readers!= 0 busy ) OK_write.wait(); busy = TRUE; finish_write(){ busy = FALSE; if( OK_read.queue() ) OK_read.signal(); else OK_write.signal(); class condition{ public wait(){... signal(){... queue(){... モニタとセマフォリソース空き確認と待ちセマフォモニタセマフォモニタ P 命令共有リソースの取得トライ失敗時, 待ち行列へ V 命令共有リソース返却待ちプロセスを 1 つ実行可能状態へ wait 待ち行列へ signal 待ちプロセスを 1 つ実行可能状態へ queue 待ちプロセスの有無 P 命令を実行しないとセマフォの状態が分からないリソースを取ろうとしないと, 空いてるかどうか不明取れなかったら, いきなり待ち行列に待たされるメソッドにより, 共有リソースの状態を排他的に調べられるリソースの空きの確認とリソース待ちが分離条件変数への wait により, 自由度の高い待ちが可能

8 モニタの利点 ( 対セマフォ ) 復習プロデューサコンシューマリソース確認と待ちの分離リングバッファリソースに空きがない場合, 待ちに入るかどうか自由に選べる排他制御すべきリソースの明示 msg msg モニタ内に記述されるため明示的他の一般的な変数と判別しやすい A msg msg B 排他的メソッドを通じた処理により, 保護 msg プログラマに安全で扱いやすい枠組みを提供プロデューサコンシューマ Dining Philosophers monitor Producer_Consumer{ private Messages Buffer[N]; int S, M; condition Full, Empty; int Count; public producer( word ){ if( Count == N ) Full.wait(); Buffer[S] = word; S = (S + 1) mod N; Count += 1; Empty.signal(); consumer( word ){ if( Count == 0 ) Empty.wait(); word = Buffer[M]; M = (M + 1) mod N; Count = Count 1; Full.signal(); A メッセージでいっぱい状態変数 Full で wait 空いたら書いて, ポインタを進める Empty で読み出し待ちしているかもしれないので B enum{ EATING, HUNGRY, THINKING ; monitor Dining_Philosophers{ private state[n]; condition self[n]; test( i ){ if( (state[(i-1) mod N]!= EATING) && (state[i] == HUNGRY) && (state[(i+1) mod N]!= EATING) ){ state[i] = EATING; self[i].signal(); public up( i ){ state[i] = HUNGRY; test( i ); if( state[i]!= EATING ) self[i].wait(); down( i ){ state[i] = THINKING; test( (i-1) mod N ); test( (i+1) mod N ); 食べようとして, 成功すると EATING に食事トライ失敗すると wait で待ち食事終了両隣の人が HUNGRY なら EATING にして signal で起こす

9 モニタの利点と欠点利点カプセル化による, 排他制御の簡単化可読性保守性の高さ非公開リソースへのアクセス,signal()/wait() のセット使用など, コンパイル時にある程度の不具合検出が可能欠点コンパイル時チェックは完全ではないデッドロックの可能性を完全に排除しているわけではないサポートしている言語が少ない Java による採用で, 再び脚光? まとめ ( モニタ ) モニタオブジェクト指向プログラミングを排他制御に適用リソース操作を, オブジェクトのメソッドとして提供メソッドは排他的にのみ実行可能であり, プログラマはリソース排他制御に注意を払う必要がないデッドロックの可能性を, コンパイル時にある程度排除可能まとめ並行プロセス (1/5) 並行プロセス機器上では一般に複数プログラムが並行動作プロセス並列, さらに細かいスレッド並列などこれに対し, システムのリソースは OS により仮想化 ( 無限 ) されているが実際は有限有限リソースの使用権を, プロセス / スレッド間で調停する必要アリつまりリソース使用が競合しうる場所で何らかの対処が必要まとめ並行プロセス (2/5) クリティカルセクションプログラム中で, リソース競合が発生する可能性のある部分排他制御 (MUTEX) クリティカルセクションに, 複数プロセスが同時に入らないようにするための制御さまざまなアプローチ Dekker のアルゴリズムセマフォモニタ

10 まとめ並行プロセス (3/5) まとめ並行プロセス (4/5) Dekker のアルゴリズム Interest 変数により, 各プロセスがクリティカルセクションに興味があるか否かを表現 Priority 変数により, 複数プロセスが同時にクリティカルセクションに興味を持った場合にどちらを優先するかを決定ソフトウェアのみで実現可能ビジーウェイトさっき私だったのでどうぞ競合者あり Interest 状態セマフォ P 命令リソース獲得要求, 失敗時には待ち状態に移行 V 命令リソース解放, 待ちプロセスを実行可能状態にリソース獲得が失敗すると, 待ち行列へ V 命令が起こしてくれるまで待てばよいビジーウェイト不要プログラマ依存デッドロックの可能性 (Dining Philosopher) V! 待ち P! リソースまとめ並行プロセス (5/5) モニタオブジェクト指向プログラミングカプセル化によるリソースの保護メソッド排他実行による排他制御の簡潔化デッドロック可能性のコンパイル時検出 ( 部分的 ) class 自動車 { public 減速 (n){ 投入燃料量 = 0; 制動力 += n; ブレーキランプ = on; if( スリップ ){... private 投入燃料量 ; 制動力 ; タイヤ角度 ; ブレーキランプ ; 並行プロセスの話は今日で終わり次回からは主記憶 ( メモリ ) 管理の話題

Microsoft PowerPoint - OS04.pptx

Microsoft PowerPoint - OS04.pptx この資料は情報工学レクチャーシリーズオペレーティングシステム松尾啓志著 ( 森北出版株式会社 ) を用いて授業を行うために名古屋工業大学松尾啓志津邑公暁が作成しましたオペレーティングシステム #4 並行プロセス : 排他制御基礎パワーポイント 2007 で最終版として保存しているため変更はできませんが授業でお使いなる場合は松尾 (matsuo@nitech.ac.jp) まで連絡いただければ