酒居敬一(sakai.keiichi@kochi-tech.ac.jp) オペレーティングシステムJ/K 2004年10月7日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/OS2004/

Presentation on theme: "酒居敬一(sakai.keiichi@kochi-tech.ac.jp) オペレーティングシステムJ/K 2004年10月7日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/OS2004/"— Presentation transcript:

1 酒居敬一(sakai.keiichi@kochi-tech.ac.jp)
オペレーティングシステムJ/K 2004年10月7日

2 予定（２００４年１０月４日版） 第1回講義 10月 4日２時限目 第2回講義 １０月 ７日２時限目 第１回演習 １０月１４日２時限目
第1回講義 10月　4日２時限目 第2回講義 １０月　７日２時限目 　 第１回演習 １０月１４日２時限目 第3回講義 １０月１８日２時限目 第４回講義 １０月１８日５時限目 　 第２回演習 １０月２１日２時限目 第５回講義 １０月２５日２時限目 第６回講義 １０月２８日２時限目 第７回講義 １１月　１日２時限目 　 中間試験 １１月　１日５時限目 第８回講義 １１月　４日２時限目 第９回講義 １１月　８日２時限目 　 第３回演習 １１月１１日２時限目 第１０回講義 １１月１５日２時限目 第１１回講義 １１月１５日５時限目 　 第４回演習 １１月１８日２時限目 第１２回講義 １１月２２日２時限目 第１３回講義 １１月２５日２時限目 第１４回講義 １１月２９日２時限目 クオータ末試験　１１月２９日５時限目 ※これらは予定なので、変更の可能性があります。

3 ハードウェアの管理 Uni-Processor Multi-Processor 管理する主体(=プロセッサ)がひとつ 管理する主体が複数ある
つまり、プロセスの実行管理だけを考えればよい Multi-Processor 管理する主体が複数ある どのプロセッサが何を管理するか、という管理も必要！ 計算機の実装方式が複数ある OS内部の管理表は唯一でなければならないが、 複数プロセッサ間で管理のための方法が単一ではない！ （→　教科書46ページの図）

4 並行プロセスと並行プログラミング プロセスの概念 並行プロセス間で生じる問題 その解決方法（並行プログラミング機構） デッドロック 相互排除
デッドロックの検出と回避 プロセスにまつわる実装の話　→　もっと後の回

5 プロセスの概念 プロセッサを抽象化したもの 固有の記憶空間が与えられる 実行のひとつの単位 プログラム、データ、レジスタの中身… を含む
プログラム、データ、レジスタの中身…　を含む 固有の記憶空間が与えられる 記憶空間などを共有しているもの→スレッド スレッドとプロセスを明確に区別しない→タスク 実行のひとつの単位 プロセスは（理想的には）複数が同時に走行 （現実にはプロセッサはプログラムを処理するために使われる資源で、複数のプロセスで共有）→次回

6 このような逐次的資源が共有されるとき、Atomicに操作できるような機構が必要となる。
並行プロセス間で生じる問題 逐次的資源 たとえば、Read-modify-write のような、 　一連の操作をAtomicに行う必要のある資源。 このような逐次的資源が共有されるとき、Atomicに操作できるような機構が必要となる。 もし、そういう機構がなければプログラムが意図したとおりに動かない。

7 処理の粒度 マルチジョブ マルチタスク マルチCPU レコードの排他的利用 トランザクションを不可分な処理単位とする
メモリ上の共有領域の排他的利用 共有領域を使用するプログラムを排他的に実行 マルチCPU メモリ上の変数の排他的利用 プロセッサのバスサイクルを連続する

8 c1やc2は、自プロセスが 他プロセスに、臨界領域に入ること を知らせるための変数。 先に臨界領域に入ることを宣言した
プロセスが実際に臨界領域に入る。 両方が臨界領域に入ろうとしたとき、 turn変数により一方が譲る。 臨界領域に入っているとき、 c1かc2の一方だけがtrueである。 [大久保英嗣, オペレーティングシステムの基礎]

9 TAS命令（計算機アーキテクチャの授業で既出）
相互排除 TAS命令（計算機アーキテクチャの授業で既出） もっとも原始的なロックの実装(primitive)。 2値セマフォを実現する。 セマフォ P操作（ロック）とV操作（アンロック）により実現。 再帰的ロックとも呼ばれる。 モニタ（Java言語で使われている） 共有資源とそれを操作する手続きを一体化。 セマフォのわかりにくさを、構造化により解消。 構造化セマフォと呼ばれることもある。

10 TAS命令 メモリ上の変数をテストする処理、メモリ上の変数に値をセットする処理、これらを順に他の処理をはさむことなく(=Atomic)行う。
テストとは、0かそうでないかを調べてフラグに結果を反映する処理 Intel系では lock xchg 命令で代用する。 バスサイクルをlock（不可分かつ連続）して処理 バイナリセマフォ、２値セマフォ、を実現する。

11 変形セマフォ セマフォ変数 P操作 V操作 正の値は利用可能な資源の数 負の値は現在待ちに入っているプロセスの数
セマフォの値をatomicに１減らしテストする テスト結果が負になったときは、待ち状態に入る V操作 セマフォの値をatomicにテストし１増やす テスト結果が負のときは、待ち状態にあるプロセスをひとつ動作可能状態にする

12 競合を避けるため相互排除機構を持っている。
相互排除とデッドロック 競合を避けるため相互排除機構を持っている。 これが時に問題を起こす。 ２つのスレッドが資源Aと資源Bを同時にとりたいとき 　　　　資源が２つそろうまでは返さないぞ、というアルゴリズムだと… スレッド１ 資源Aを獲得 資源Bを獲得したい！ スレッド２ 資源Bを獲得 資源Aを獲得したい！

13 デッドロックの発生条件と防止 ２つのプロセスが資源R1と資源R2を同時にとりたいとき 逐次的資源に関する相互排除条件 待ち条件
資源要求は同時に行う 横取り不可条件 資源を同時に確保できない場合、解放し再度要求 循環待ち条件 資源を順序だてて取得する ２つのプロセスが資源R1と資源R2を同時にとりたいとき 　　資源が２つそろうまでは返さないぞ、というアルゴリズムだと… Deadlock! プロセスP１ プロセスP２ 資源R1を獲得 資源R2を獲得 資源R2を獲得したい！ 資源R1を獲得したい！

14 デッドロックの回避 プロセスが実行時に資源を要求する数 > プロセスが必要と宣言した資源の数
こういうプロセスがもし存在すれば、誤りであるのはあきらか プロセスが実行時に資源を要求する数 > 空いている資源の数 こういうプロセスは待つしかない 待っていればいつかは資源がわりあてられるのだろうか？ 空き資源があり、それを割り当てることで、プロセスからの要求を満たせるか？ 満たせるときだけ: プロセスに印をつける。プロセスに割り当てられた資源を解放。 ステップ4へもどり、印をつけていないすべてのプロセスを調べる。 すべてのプロセスに印がついてるか？ ついてたら、システムは安全である。

15 資源割付けグラフ 有向グラフとして表現する プロセス：　　四角 資源の型：　大きな丸 資源：　　　　小さな丸 獲得：資源からプロセスへ向かう辺がある 要求：プロセスから資源の型へ向かう辺がある （排他的に割付ける機構→たとえばセマフォ）

16 P1 P2 R1 R2 R3 P3 P4 P5 資源割付けグラフの例

17 資源割付けグラフの簡約 簡約とは？ 簡約できる場合とは？ どうしても簡約できない場合は？ 資源からプロセスへの有向辺をとりのぞく
プロセスが必要な資源を使用後解放に相当 簡約できる場合とは？ プロセスからの有向辺に対応できる空き資源がある プロセスが必要な資源の要求を満たせる場合に相当 どうしても簡約できない場合は？ デッドロックが発生ということになり、回復を試みる デッドロック状態のプロセスを1つ以上消滅させる チェックポイントリスタートにより後退復帰する

18 P1 P2 R1 R2 R3 P3 P4 P5 資源割付けグラフの簡約 要求を満たした 要求を満たした 要求を満たした 要求を満たした