オペレーティングシステムJ/K (並行プロセスと並行プログラミング)

Presentation on theme: "オペレーティングシステムJ/K (並行プロセスと並行プログラミング)"— Presentation transcript:

1 オペレーティングシステムJ/K (並行プロセスと並行プログラミング)
2005年10月6日

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17 例：相互排除 /usr/src/linux/drivers/char/lp.c Atomic処理 スピンロック
カーネルロック(全域的ロック) mutexやセマフォ(局所的ロック)

18 例：相互排除の実装 Atomic処理 スピンロック カーネルロック(全域的ロック) mutexやセマフォ(局所的ロック)
/usr/src/linux/include/asm/atomic.h スピンロック /usr/src/linux/include/asm/lock.h カーネルロック(全域的ロック) /usr/src/linux/include/asm/smplock.h mutexやセマフォ(局所的ロック) /usr/src/linux/include/asm/semaphore.h