岩波講座 ソフトウエア科学6「オペレーティングシステム」#7

セマフォ

前節の排他制御の方式は、現実のシステムには適用しにくい。また適用するにしてもビジーウェイティングを使っているので、ごく短いクリティカルセクションへの利用に限定されるべきである。

より一般的な排他制御として、セマフォを導入する。

セマフォはプロセス間通信の伝達に使われる整数型の変数である。

セマフォは、0と1以外の値も取ることができ、より多くの情報を伝達できる。

セマフォは一般に、イベント変数と呼ばれるプロセス間の共通変数の一種である。

セマフォの変数へのアクセスも排他制御が必要である。

プロセス間で伝達されるイベントには以下が含まれる。
(1) プロセスがクリティカルセクションに入った。
(2) プロセスがクリティカルセクションから出た。
(3) 新しいプロセスが始まった。
(4) 入出力操作が始まった。
(5) 入出力操作が完了した。
(6) メッセージを受け取った。
(7) リソースを受け取った。
(8) リソースを開放した。

イベント変数は、
(1) イベントの履歴を記録するデータ構造(整数型の変数)。
(2) イベント変数の待ち条件が満たされるのを待っているプロセスの待ち行列。
からなる。

セマフォにはP命令(wait命令)とV命令(signal命令)が定義される。

P命令は、引数SについてS≧1が満たされるまでプロセスを一時停止させるのが役割である。もし、S≧が満たされていればSを1減らしてプロセスは継続する。

V命令は、引数Sのセマフォの待ち行列で待っているプロセスの中から1つが選ばれ、実行可能状態に移行させる。ディスパッチャーは実行可能プロセスから1つを選び実行する。もし、Sのセマフォの待ち行列が空であった場合には、Sは1増加させられVを実行したプロセスは続行される。

P命令とV命令は、セマフォを提唱したダイクストラの母語であるオランダ後のPasseren(パスを許す)とVerhoog(起こす)に由来する。

P命令とV命令はそれぞれ分割不可能でなくてはならない。つまり、ひとときにはある1つのセマフォに対して、1つのPまたはVしか実行できない。

P、V、ディスパッチャーは、いずれも共通データである待ち行列を操作するので、排他制御を必要とする。