ぱらぱらめくる『相互排除問題』
相互排除問題――「際どい資源」をいかにプログラムで利用するか
- 作者: 土居範久
- 出版社/メーカー: 岩波書店
- 発売日: 2011/04/23
- メディア: 単行本
- クリック: 9回
- この商品を含むブログ (1件) を見る
- 1 プロセスと同期
- プロセス
- 逐次プロセス
- 並列プロセス
- スレッド
- マルチスレッド
- オーバーヘッド
- プロセスの生成とプロセススイッチが増やす時間と資源の消費
- 同期
- 共有資源をもつ、並行プロセスの間に取るもの
- 排除と協調
- 排除の中の相互排除(１プロセスのみが共有資源を使用できる)
- 協調するために情報通信が必要で、それが信号
- 際どい部分 critical section 際どい資源 critical resource
- 共有される資源であって、相互排除的に使われるものが際どい資源
- 各プロセスが使用する際どい資源が際どい部分
- 際どい資源・際どい部分の使用を可能にするために、「出入り」を制御する
- プレリュード prelude とポストルード postlude(際どい部分に入る決断、待ちプロセスに明け渡す決断)
- 並行プロセスの状態
- デッドロック(想定外の待ち状態)
- 飢餓状態((特定のプロセスだけが)永遠に待たされる状態)
- プロセス
- 2 共有記憶を用いた相互排除
- 2.1 ソフトウェアによる解法
- 相互排除問題の解の条件
- 主記憶は際どい資源
- CPU間の相対速度は不明
- 際どい部分同士に優先順位がない
- 際どい部分の外でのプロセス停止は可(際どい部分は明け渡しが必要だから、プロセスが勝手に止まってもらっては困る)
- あるプロセスの際どい部分への出入りを際どい部分の外の別プロセスが制御しない
- ２プロセスのプレリュードの譲り合いは有限回
- 設計において出てくること
- 自分の状態と相手の状態
- 整構造化表現で比較
- 相互排除問題の解の条件
- 2.2 ハードウェアによる解法
- 単一プロセサの場合
- 割り込み禁止
- 複数プロセサの場合
- 単一の記憶位置へのアクセスの排他性管理
- 単一プロセサの場合
- 2.3 同期問題
- 2.4 同期基本命令
- CPUの状態を表す「状態語、コンテキスト」
- プロセス制御ブロック(PCB)
- プロセスの識別子
- 状態語
- プロセスの実行状態
- 優先度
- 割り当てた資源およびその使用状況
- リスト・列につなぐためのポインタ
- 実行状態
- 実行
- 実行待ち
- 待機
- 制御情報
- 基本命令・同期基本命令
- セマフォアという構造体とP命令とV命令
- 2.1 ソフトウェアによる解法
- 3 相互排除のための言語機構
- 相互排除を実現するためには、それを実現するための概念対応記述が必要
- 並行文
- 条件付き際どい区域
- モニタ
- 順路式
- 強制論理
- 待合せ
- 4 分散環境における相互排除
- 分散環境では、プロセスが持つ情報は「局所情報」のみなので、相互に「陽」に情報を通信することが必要。したがって、分散環境における相互排除では、プロセス間のメッセージ通信に基づいたアルゴリズムが登場する
- 状態変数を用いた解法
- メッセージ通信に基づいた解法
