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

オペレーティングシステムJ/K
2004年10月7日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/OS2004/
予定(2004年10月4日版)
1. 第1回講義
10月 4日2時限目
2. 第2回講義
10月 7日2時限目
3.
第1回演習
4. 第3回講義
10月18日2時限目
5. 第4回講義
10月18日5時限目
6.
第2回演習
7. 第5回講義
10月25日2時限目
8. 第6回講義
10月28日2時限目
9. 第7回講義
11月 1日2時限目
10.
中間試験
11.第8回講義
11月 4日2時限目
12.第9回講義
11月 8日2時限目
13.
第3回演習
14.第10回講義 11月15日2時限目
15.第11回講義 11月15日5時限目
16.
第4回演習
17.第12回講義 11月22日2時限目
18.第13回講義 11月25日2時限目
19.第14回講義 11月29日2時限目
20.クオータ末試験 11月29日5時限目
※これらは予定なので、変更の可能性があります。
10月14日2時限目
10月21日2時限目
11月 1日5時限目
11月11日2時限目
11月18日2時限目
ハードウェアの管理
• Uni-Processor
– 管理する主体(=プロセッサ)がひとつ
• つまり、プロセスの実行管理だけを考えればよい
• Multi-Processor
– 管理する主体が複数ある
• どのプロセッサが何を管理するか、という管理も必要!
– 計算機の実装方式が複数ある
• OS内部の管理表は唯一でなければならないが、
• 複数プロセッサ間で管理のための方法が単一ではない!
(→ 教科書46ページの図)
並行プロセスと並行プログラミング
• プロセスの概念
• 並行プロセス間で生じる問題
– その解決方法(並行プログラミング機構)
• 相互排除
– デッドロック
• デッドロックの検出と回避
• プロセスにまつわる実装の話 → もっと後の回
プロセスの概念
• プロセッサを抽象化したもの
– プログラム、データ、レジスタの中身… を含む
• 固有の記憶空間が与えられる
– 記憶空間などを共有しているもの→スレッド
– スレッドとプロセスを明確に区別しない→タスク
• 実行のひとつの単位
• プロセスは(理想的には)複数が同時に走行
• (現実にはプロセッサはプログラムを処理するため
に使われる資源で、複数のプロセスで共有)→次回
並行プロセス間で生じる問題
逐次的資源
たとえば、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(不可分かつ連続)して処理
• バイナリセマフォ、2値セマフォ、を実現する。
変形セマフォ
• セマフォ変数
– 正の値は利用可能な資源の数
– 負の値は現在待ちに入っているプロセスの数
• P操作
– セマフォの値をatomicに1減らしテストする
• テスト結果が負になったときは、待ち状態に入る
• V操作
– セマフォの値をatomicにテストし1増やす
• テスト結果が負のときは、待ち状態にあるプロセスを
ひとつ動作可能状態にする
相互排除とデッドロック
• 競合を避けるため相互排除機構を持っている。
– これが時に問題を起こす。
2つのスレッドが資源Aと資源Bを同時にとりたいとき
資源が2つそろうまでは返さないぞ、というアルゴリズムだと…
スレッド1
スレッド2
資源Aを獲得
資源Bを獲得したい!
資源Bを獲得
資源Aを獲得したい!
デッドロックの発生条件と防止
 逐次的資源に関する相互排除条件
 待ち条件
 資源要求は同時に行う
 横取り不可条件
 資源を同時に確保できない場合、解放し再度要求
 循環待ち条件
 資源を順序だてて取得する
2つのプロセスが資源R1と資源R2を同時にとりたいとき
Deadlock!
資源が2つそろうまでは返さないぞ、というアルゴリズムだと…
プロセスP1
資源R1を獲得
資源R2を獲得したい!
プロセスP2
資源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