オペレーティングシステム

オペレーティングシステムJ/K
(並行プロセスと並行プログラミング)
2005年10月6日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/OS/2005/
並行プロセスと並行プログラミング
• プロセスの概念
• 並行プロセス間で生じる問題
– その解決方法（並行プログラミング機構）
• 相互排除
– デッドロック
• デッドロックの検出と回避
• プロセスにまつわる実装の話 → もっと後の回
プロセスの概念(23ページ)
• プロセッサを抽象化したもの
– プログラム、データ、レジスタの中身… を含む
• 固有の記憶空間が与えられる
– 記憶空間などを共有しているもの→スレッド
– スレッドとプロセスを明確に区別しない→タスク
• 実行のひとつの単位
• プロセスは（理想的には）複数が同時に走行
• （現実にはプロセッサはプログラムを処理するため
に使われる資源で、複数のプロセスで共有）→次回
並行プロセス間で生じる問題
逐次的資源
たとえば、Read-modify-write のような、
一連の操作をAtomicに行う必要のある資源。
このような逐次的資源が共有されるとき、
Atomicに操作できるような機構が必要となる。
もし、そういう機構がなければプログラムが意
図したとおりに動かない。
処理の粒度
• マルチジョブ
– レコードの排他的利用
– トランザクションを不可分な処理単位とする
• マルチタスク
– メモリ上の共有領域の排他的利用
– 共有領域を使用するプログラムを排他的に実行
• マルチCPU
– メモリ上の変数の排他的利用
– プロセッサのバスサイクルを連続する
c1やc2は、自プロセスが
他プロセスに、臨界領域に入ること
を知らせるための変数。
先に臨界領域に入ることを宣言した
プロセスが実際に臨界領域に入る。
両方が臨界領域に入ろうとしたとき、
turn変数により一方が譲る。
臨界領域に入っているとき、
c1かc2の一方だけがtrueである。
[大久保英嗣, オペレーティングシステムの基礎]
相互排除
• TAS命令（計算機アーキテクチャの授業で既出）
– もっとも原始的なロックの実装(primitive)。
– 2値セマフォを実現する。
• セマフォ
– P操作（ロック）とV操作（アンロック）により実現。
– 再帰的ロックとも呼ばれる。
• モニタ（Java言語で使われている）
– 共有資源とそれを操作する手続きを一体化。
– セマフォのわかりにくさを、構造化により解消。
– 構造化セマフォと呼ばれることもある。
TAS命令
• メモリ上の変数をテストする処理、メモリ上の
変数に値をセットする処理、これらを順に他
の処理をはさむことなく(=Atomic)行う。
• テストとは、0かそうでないかを調べてフラグ
に結果を反映する処理
• Intel系では lock xchg 命令で代用する。
– バスサイクルをlock（不可分かつ連続）して処理
• バイナリセマフォ、２値セマフォ、を実現する。
変形セマフォ
• セマフォ変数
– 正の値は利用可能な資源の数
– 負の値は現在待ちに入っているプロセスの数
• P操作
– セマフォの値をatomicに１減らしテストする
• テスト結果が負になったときは、待ち状態に入る
• V操作
– セマフォの値をatomicにテストし１増やす
• テスト結果が負のときは、待ち状態にあるプロセスを
ひとつ動作可能状態にする
相互排除とデッドロック
• 競合を避けるため相互排除機構を持っている。
– これが時に問題を起こす。
２つのスレッドが資源Aと資源Bを同時にとりたいとき
資源が２つそろうまでは返さないぞ、というアルゴリズムだと…
スレッド１
スレッド２
資源Aを獲得
資源Bを獲得したい！
資源Bを獲得
資源Aを獲得したい！
デッドロックの発生条件と防止
 逐次的資源に関する相互排除条件
 待ち条件
 資源要求は同時に行う
 横取り不可条件
 資源を同時に確保できない場合、解放し再度要求
 循環待ち条件
 資源を順序だてて取得する
２つのプロセスが資源R1と資源R2を同時にとりたいとき
Deadlock!
資源が２つそろうまでは返さないぞ、というアルゴリズムだと…
プロセスP１
資源R1を獲得
資源R2を獲得したい！
プロセスP２
資源R2を獲得
資源R1を獲得したい！
デッドロックの回避
1. プロセスが実行時に資源を要求する数 > プロセスが必要と宣言した資源の数
こういうプロセスがもし存在すれば、誤りであるのはあきらか
2. プロセスが実行時に資源を要求する数 > 空いている資源の数
こういうプロセスは待つしかない
3. 待っていればいつかは資源がわりあてられるのだろうか？
4. 空き資源があり、それを割り当てることで、プロセスからの要求を満たせるか？
5. 満たせるときだけ: プロセスに印をつける。プロセスに割り当てられた資源を解放。
6. ステップ4へもどり、印をつけていないすべてのプロセスを調べる。
7. すべてのプロセスに印がついてるか？
ついてたら、システムは安全である。
資源割付けグラフ
• 有向グラフとして表現する
• プロセス：四角
• 資源の型：大きな丸
• 資源：
小さな丸
• 獲得：資源からプロセスへ向かう辺がある
• 要求：プロセスから資源の型へ向かう辺がある
• （排他的に割付ける機構→たとえばセマフォ）
P1
R1
P2
R2
P3
P4
資源割付けグラフの例
R3
P5
資源割付けグラフの簡約
• 簡約とは？
– 資源からプロセスへの有向辺をとりのぞく
– プロセスが必要な資源を使用後解放に相当
• 簡約できる場合とは？
– プロセスからの有向辺に対応できる空き資源がある
– プロセスが必要な資源の要求を満たせる場合に相当
• どうしても簡約できない場合は？
– デッドロックが発生ということになり、回復を試みる
– デッドロック状態のプロセスを1つ以上消滅させる
– チェックポイントリスタートにより後退復帰する
要求を満たした
P1
R1
要求を満たした
P2
R2
R3
要求を満たした
要求を満たした
要求を満たした
P3
P4
資源割付けグラフの簡約
P5
例：相互排除
• /usr/src/linux/drivers/char/lp.c
• Atomic処理
• スピンロック
• カーネルロック(全域的ロック)
• mutexやセマフォ(局所的ロック)
例：相互排除の実装
• Atomic処理
– /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

Download Report