Microsoft PowerPoint - OS04.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - OS04.pptx"

しゅんすけさどひら
5 years ago
Views:

1 この資料は情報工学レクチャーシリーズオペレーティングシステム松尾啓志著 ( 森北出版株式会社 ) を用いて授業を行うために名古屋工業大学松尾啓志津邑公暁が作成しましたオペレーティングシステム #4 並行プロセス : 排他制御基礎パワーポイント 2007 で最終版として保存しているため変更はできませんが授業でお使いなる場合は松尾 (matsuo@nitech.ac.jp) まで連絡いただければ編集可能なバージョンをお渡しする事も可能ですプロセスの同時実行複数プロセスが同時に動作する際にプロセスの競合, 協調, 干渉プロセス協調仕事の分担や通信など, 複数プロセスが助け合うプロセス競合複数プロセスで有限リソースを取り合う調停し, 各プロセスに適切にリソース割当プロセス干渉他プロセスの影響で異常が発生すること原因はプログラムのバグ

2 プロセス協調プロセス協調例 ) プロセス間通信何も通信のための仕組みがない場合... 送信側と受信側でタイミングを合わせる必要受信側は, 常にメッセージが来ないかをチェックしていなければならない通信バッファ問題読み出す前に上書き... とりこぼしバッファ格納する前に再読込... だぶって受け取りバッファバッファフラグによる管理プロセス競合受信すべきメッセージがバッファ内に存在するか否かをフラグで判断バッファフラグが立っている間, 送信側は新たに送信を行わない上書き回避フラグが降りている間, 受信側は新たに順を行わない再受信回避例 ) 磁気テープの利用プログラム例 LOAD NUM, R DEC R, 1 STORE NUM, R : : テープ使用 : LOAD NUM, R INC R, 1 STORE NUM, R テープを確保テープを解放 NUM: 空きテープ数

3 プログラムの意味テープの確保変数 NUM の値をレジスタにロードレジスタから 1 減算レジスタの値を変数 NUM にストア ( 格納 ) テープの解放変数 NUM の値をレジスタにロードレジスタから 1 減算レジスタの値を変数 NUM にストア LOAD NUM, R DEC R, 1 STORE NUM, R : : : LOAD NUM, R INC R, 1 STORE NUM, R プロセスAとプロセスBがテープにアクセスプロセスBが確保中プロセスAによる確保とプロセスBによる解放が発生結果, テープの空き数は変化しないはず空きテープケース1 ケース2 DEC R, 1 R=0 STORE NUM, R R=0 NUM DEC R, 1 R=0 NUM LOAD NUM, R R=0 INC R, 1 R=2 INC R, 1 R=1 STORE NUM, R R=0 STORE NUM, R R=1 STORE NUM, R R=2 テープの空きは 1 で OK テープの空きは 1 しかないはず ( 実際より多いと勘違い )

4 ケース3 DEC R, 1 R=0 STORE NUM, R R=0 INC R, 1 R=2 STORE NUM, R R=2 NUM テープの空きは 1 あるはず ( 実際より少ないと勘違い ) 原因変数 NUM から値を読んで, 変数 NUM に値を書くまでの間に, 他のプロセスが変数 NUM を読んでしまう対処法他のプロセスからみて, 変数 NUM は変化していない実際は変化させるための手続きが始まっている LOADからSTOREまでの一連の処理を不可分にクリティカルセクション : このような分割してはいけない一連の処理排他制御 (mutual exclusion): クリティカルセクションなどを他のプロセスと排他的に実行するための制御プロセスがクリティカルセクションを他のプロセスと排他的に実行できるように排他制御 4.2 排他制御重要な性質即時性デッドロック防止公平性

5 排他制御の性質クリティカルセクション即時性クリティカルセクションの実行に競合するプロセスがほかにない場合, プロセスはクリティカルセクションの実行を即座に許可されるデッドロック防止競合するプロセスがある場合でも, 許可されるまで永久に待たされてはいけない公平性どのプロセスも, 他のプロセスがクリティカルセクションを実行することを妨げられないエントリーシーケンスクリティカルセクションに入る権利を獲得する処理イグジットシーケンスクリティカルセクションから出るための処理例 ) フラグによる制御例 ) フラグによる制御例 ) フラグによる制御新幹線のトイレと同じうまくいかない場合空いた! 空いてる... クリティカルセクション ( トイレ ) に入ろうとするプロセス ( 乗客 ) は, フラグ ( インジケータ ) を確認し, 入れるかどうかを決定入ると同時にフラグを下げる ( インジケータが点く ) 空いてる空いてるフラグを見て確認入るという2つの処理は不可分空いてない... 一見うまくいくこの方式では排他制御を実現できない

6 2 プロセスの排他制御を行うことを可能とする 4.3 Interest プロセス A,B がクリティカルセクションに興味があるか否かを示す Priority プロセス A,B がクリティカルセクションに同時に興味を持った場合, どちらを優先するかを決定する Interest Interest[A] = TRUE; while( Interest[B] ){ if( Priority == B ){ Interest[A] = FALSE; while( Priority == B ){; Interest[A] = TRUE; Interest[B] = TRUE; while( Interest[A] ){ if( Priority == A ){ Interest[B] = FALSE; while( Priority == A ){; Interest[B] = TRUE; 空いてる競合者なし状まずクリティカルセクションに入る前に, クリティカルセクションに入りたい旨を宣言競合者がいなければ入れる Priority = B; Interest[A] = FALSE; Priority = A; Interest[B] = FALSE;

7 さっき私だったのでどうぞ競合者あり Priority 競合者がいた場合 Priority が示す優先度でどちらが入るか決定自分に優先度が回ってくるまで Interest 状態を解除状 Interest[A] = TRUE; Interest[B] 権 = TRUE; while( Interest[B] ){ while( Interest[A] ){ if( Priority == B ){ if( 状 Priority 権 == A ){ Interest[A] = FALSE; 優先権を得たら Interest[B] = FALSE; while( Priority == B ){; 再びInterest while( 状態オン Priority == A ){; Interest[A] = TRUE; Interest[B] = TRUE; 状空いてる空いてる Priority = B; Interest[A] = FALSE; 終わったら優先権を相手に渡して Interest 状態オフ Priority = A; Interest[B] = FALSE; ポイント入る前に手を挙げる優先権により競合を解決問題点ユーザプログラムに依存ちゃんとプロセスが約束を守ってくれないと破綻ビジーウェイト (busy wait) 一方がクリティカルセクションを実行中, 待っている方は優先権をひたすらチェックし続ける CPUリソースの無駄 4.4 割り込み制御による排他制御

8 ユニプロセッサの場合割り込みのみがプロセス中断を発生させるエントリーシーケンスで割り込み禁止命令を実行しておけばよい同様にイグジットシーケンスで割り込み禁止を解除ただし... 割り込み禁止時間の増加はシステムの性能に影響 4.5 ハードウェアによる排他制御ハードウェアによる排他制御 TEST AND SET による排他制御対話処理の重要性から排他制御の必要性が認識 Flag X = 1; テストアンドセット命令ハードウェア自体に, 排他制御のための仕組みを v = test_and_set(x) v = x と x = 0 を同時に実行する命令競合者フラグのチェックとセットを同時に行える Int v; Repeat v = test_and_set(x); Until v == 1; クリティカルセクション X = 1; Int u; Repeat u = test_and_set(x); Until u == 1; クリティカルセクション X = 1;

9 今日のまとめプロセス競合クリティカルセクション : リソース競合が発生する可能性のある部分排他制御 (MUTEX): クリティカルセクションに同時に複数プロセスが入らないようにする制御ソフトウェアによる排他制御の基本手法ビジーウェイトという問題点プロセス協調

Microsoft PowerPoint - OS07.pptx

Microsoft PowerPoint - OS07.pptx この資料は情報工学レクチャーシリーズ松尾啓志著 ( 森北出版株式会社 ) を用いて授業を行うために名古屋工業大学松尾啓志津邑公暁が作成しました主記憶管理主記憶管理基礎パワーポイント 27 で最終版として保存しているため変更はできませんが授業でお使いなる場合は松尾 (matsuo@nitech.ac.jp) まで連絡いただければ編集可能なバージョンをお渡しする事も可能です復習 OS