セマフォ
セマフォ（テンプレート:Lang-en-short）とは、計算機科学において、並列プログラミング環境での複数のプロセスが共有する資源にアクセスするのを制御する際の単純だが便利な抽象化を提供する変数または抽象データ型である。
ある資源が何個使用可能かを示す記録と考えればわかりやすく、それにその資源を使用する際や解放する際にその記録を「安全に」（すなわち競合状態となることなく）書き換え、必要に応じて資源が使用可能になるまで待つ操作が結びついている。セマフォは競合状態を防ぐ便利なツールである。しかしセマフォを使うことでプログラムにおける競合状態がなくなると保証するものではない。任意個の資源を扱うセマフォをカウンティングセマフォ、値が0と1に制限されている（ロック/アンロック、使用可能/使用不可の意味がある）セマフォをバイナリセマフォと呼ぶ。後者はミューテックスと同等の機能を持つ。
セマフォの概念はオランダ人計算機科学者エドガー・ダイクストラが考案した[1]。今では様々なオペレーティングシステムで採用されている。
「semaphore」の本来の語義は「視覚による通信・信号」全般を指し、腕木通信や、それから派生した鉄道の腕木信号（や自動車の方向指示器）、手旗信号などが含まれる。日本語でのセマフォは本用途（コンピュータ、プログラミング関連）に限られる。
目次
図書室のたとえ
ある図書室に学習用の個室が10部屋あり、それぞれの学習室は一度に1人の学生が使用するとする。争奪戦が始まらないよう、学生はフロントデスクで学習室の使用を申し込むことになっている。学習室を使用し終えたら、学生はフロントに立ち寄ってその学習室が空いたことを知らせなければならない。全ての学習室が埋まっている場合、学生はフロントで部屋が空くのを待つ。
フロントの図書係はどの学習室が空いているかは把握しておらず、単に空いている部屋数のみを知っている。学生が申し込んできたとき、図書係はその数から1を引く。学生が学習室の利用を終えたとき、図書係はその数に1を加える。学習室の使用許可が与えられたとき、その部屋は必要なだけ使い続けることができ、したがって事前に学習室を予約することはできない。
このシナリオでは、フロントデスクがセマフォ、学習室が資源、学生がプロセスに相当する。また、セマフォの初期値は10になっている。学生が学習室の使用を申し込んで許可されたとき、セマフォ値から1が引かれて9になる。次の学生のときには8、さらに次は7となる。1を引くとセマフォ値が負になるという状態で学生が申し込んだ場合、その学生は待たされる[2]。複数人の学生が待っているとき、彼らは待ち行列を形成するか、いずれかの学生が学習室の使用を終えてフロントにやってきたときにラウンドロビン・スケジューリング方式で空いた部屋を割り当てる（このあたりはセマフォの実装に依存する）。
重要な観点
複数の資源に対して使用する場合、セマフォは個々の資源の使用/解放状態を把握せず、単に個数のみを保持する。特定の資源を指定したい場合は、他の機構が必要とされる（複数のセマフォの組合せでも可能）。
プロセス群はそのプロトコルに従うという点で信頼されている。1つのプロセスが間違った動作をすれば、公平性と安全性は損なわれ、性能低下、不正動作、フリーズ、クラッシュなどが発生しうる。例えば、次のような動作が間違った動作である。
- 資源を要求しておいて、使用後に解放し忘れる。
- 要求したことのない資源を解放する。
- 使っていない資源を長期に渡って獲得したままにする。
- 要求せずに資源を使用する。あるいは解放済みの資源を使用する。
全プロセスがその規則に従ったとしても、資源が複数種類あって、それぞれにセマフォが設定されている場合、プロセスが複数の資源を同時に使用するなら新たな問題が発生しうる。例えば、食事する哲学者の問題がそのような状況を示している。
意味論と実装
セマフォ変数の重要な属性として、その値の変更には特定の関数群を使わなければならないという点が挙げられる。ここではそれら関数を wait() と signal() とする。
カウンティングセマフォでの2つの操作は、歴史的には V（または signal()）と P（または wait()）と記述される。V操作はセマフォSをインクリメントし、P操作はデクリメントする。それら操作の意味論は後述する。角括弧で囲まれた部分は不可分操作であることを意味し、その部分の途中経過は他のプロセスからは見えない。
セマフォSの値は、その時点で使用可能な資源の個数である。P操作は資源を獲得しようとするもので、セマフォで守られている資源が使用可能になるまでビジーウェイトまたはテンプレート:仮リンクで待つことになる。V操作はその逆であり、使用していた資源を解放する。
wait() と signal() を簡単に説明すると次のようになる。
-
wait(): セマフォの値を1だけデクリメントする。その結果、値が負になるなら wait() を実行しているプロセスはブロックされる。つまり、セマフォのキューに追加される。 -
signal(): セマフォの値を1だけインクリメントする。その後、インクリメント前の値が負だったら（つまり資源待ち状態のプロセスがあるなら）、セマフォの待ちキュー上にあるブロックされたプロセスをレディ（実行可能）キューに移す。
多くのOSは効率的なセマフォのプリミティブを提供しており、セマフォをインクリメントした際には1つだけ待ち状態のプロセスをアンブロックする。すなわち、複数のプロセスを同時にアンブロックした際の無用なセマフォ値のチェック処理を防いでいる。
カウンティングセマフォの概念は、一度に複数個の資源を獲得・解放できるように拡張でき、UNIXでの実装もそのようになっている。その場合のVおよびP操作は次のように修正される。
function V(semaphore S, integer I):
[S ← S + I]
function P(semaphore S, integer I):
repeat:
[if S >= I:
S ← S - I
break]
リソーススタベーションを防ぐため、セマフォにはプロセスのキュー（通常はFIFO）が1つ付属している。セマフォ値がゼロのときにP操作をすると、そのプロセスはセマフォ付属のキューに追加される。別のプロセスがV操作でセマフォ値をインクリメントしたとき、キュー上にプロセスがあれば、そのうちの1つをキューから外して実行再開させる。プロセスに優先度が設定されている場合、キュー上で優先度順にプロセスを並べるなどして、最も優先度の高いプロセスが最初に実行再開できるようにする。
実装においてインクリメント/デクリメントや比較の不可分性が保証されていない場合、インクリメントやデクリメントが行われなかったり、セマフォ値が不正になる危険性が生じる。不可分性を達成するには、テンプレート:仮リンク（読み取って、変更を加えて、書き込むという処理サイクル）を不可分に実行できる機械語命令を使用する。そのような機械語命令がない場合、デッカーのアルゴリズムなどのソフトウェアによる排他制御を使用する。シングルプロセッサのシステムでの不可分操作は、プリエンプションを一時的に禁止したり、割り込みをマスクしたりすることでも実現できる。マルチプロセッサシステムではそれだけでは不十分で、同じセマフォを共有する2つのプログラムが別々のプロセッサ上で同時に動作している場合に対処できない。そのためテスト・アンド・セット命令などを使用してセマフォ変数へのアクセスをロックする必要がある。
例: 生産者/消費者問題
テンプレート:仮リンクでは、1つのプロセス（生産者）がデータを生成し、もう1つのプロセス（消費者）がそれらを受け取って使用する。データの受け渡しは最大サイズNのキューで行い、次のような条件に従う。
- キューが空の場合、消費者は生産者がデータを生成するのを待たなければならない。
- キューが満杯の場合、生産者は消費者がデータを消費するのを待たなければならない。
生産者/消費者問題をセマフォで解決する場合、キューの状態を2つのセマフォで表す。emptyCount はキュー上の空いているスロット数を保持し、fullCount はキュー上の要素数を保持する。完全性を維持するには、emptyCount を実際の空きスロット数より小さくなるようにし、fullCount を実際のキュー上の要素数より小さくなるようにする（どちらも実際の数を越えてはならない）。空きスロットと要素は、空の箱と満たされた箱という2種類の資源を表しており、セマフォ emptyCount と fullCount はそれら資源についての制御を管理する。
バイナリセマフォ useQueue は、例えば2つの生産者が同時にデータをキューに格納しようとするなどといった不正な状態が発生しないことを保証するためにある。このバイナリセマフォはミューテックスで代替することもできる。
emptyCount の初期値は N、fullCount の初期値は0、useQueue の初期値は1である。生産者は次のような処理を繰り返す。
produce:
P(emptyCount)
P(useQueue)
putItemIntoQueue(item)
V(useQueue)
V(fullCount)
消費者は次のような処理を繰り返す。
consume:
P(fullCount)
P(useQueue)
item ← getItemFromQueue()
V(useQueue)
V(emptyCount)
具体的には次のような動作をする。
- 1つの消費者がクリティカルセクションに入る。
fullCountは0なので、消費者はブロックする。 - いくつかの生産者が生産者側のクリティカルセクションに入る。
emptyCountで制限されるのでN以上の生産者はクリティカルセクションに入れない。 - 生産者は
useQueueにより一度に1つずつキューにアクセスし、データをキューに入れていく。 - 最初の生産者がクリティカルセクションを抜けるとき、
fullCountがインクリメントされるので、ブロックしていた消費者がクリティカルセクション内の処理に進むことができる。
emptyCount はキュー上の実際の空きスロット数より小さくなる可能性がある。例えば、複数の生産者がデクリメントを行っても、useQueue によってキューへのデータ投入は逐次化されるためである。したがって常に emptyCount + fullCount ≤ N であり、等号が成り立つのは生産者も消費者も全くクリティカルセクションに入っていない場合だけである。
関数名の語源
元もとの名前であるPとVは、オランダ語の単語の頭文字に由来している。Vは verhogen（増加する）を意味する。Pについては、proberen（テストする）[3]、passeer（通過）、probeer（試みる）、pakken（つかむ）などいくつかの説明がある。セマフォの本来の意味である腕木通信から、Vを verhoog（腕木を上げる、通行禁止）、Pを passeren（腕木を下げる、通行許可）とする説もある。ただしダイクストラ自身はPを probeer te verlagen（減らすことを試みる）を略したかばん語 prolaag の頭文字だとしている[4][5][6][7]。この混乱のもとは、オランダ語で increase と decrease に相当する語がどちらも V で始まるためで、かといってオランダ語の単語をそのまま使ってもオランダ語を知らない人はかえって混乱するとダイクストラが考えたためである。
ALGOL 68 やLinuxカーネル[8]、いくつかの英語の教科書では、PとVはそれぞれ down と up とされている。ソフトウェア工学では一般に wait と signal、acquire と release（Javaのライブラリで使用[9]）、pend と post などと呼ばれることが多い。教科書によっては元もとのオランダ語の頭文字に一致するよう procure と vacate としているものもある。
セマフォとミューテックス
ミューテックスは基本的にバイナリセマフォと等価であり、時には基本実装が同一ということもある。ただし、ミューテックスは2つのプロセスが同時に共用資源にアクセスするのを防止する構成物を表し、バイナリセマフォは単一の資源へのアクセスを制限する構成物を表す。
多くの場合、ミューテックスには「所有者」の概念がある。すなわちミューテックスをロックしたプロセスだけがそれをアンロックすることができる。対照的にセマフォにはそのような制限がなく、上述の生産者/消費者問題の例でもそれを利用している。
したがって基本的には、ミューテックスはプロセスなどの実行実体と結びついており、セマフォは資源と結びついている。
環境毎の使用方法
- Windows
- WindowsのWin32 APIでは、
CreateSemaphore関数とReleaseSemaphore関数を使う。 - .NET Framework
- .NET Framework 2.0以降では、
System.Threading.Semaphoreクラスを使う。バージョン1.1以前では自作するかWin32 APIを呼び出す必要がある。 - Java
- Javaでは、
java.util.concurrent.Semaphoreクラスを使う。Java 5 以降で使用可能である。 - Perl
- Perlでは、
Thread::Semaphoreモジュールや、新しくはCoro::Semaphoreモジュールなどを使う。 - Python
- Pythonでは、
threadingモジュール中にSemaphoreクラスが用意されている。
脚注
参考文献
関連項目
外部リンク
- Dijkstra, Edsger W. Over Seinpalen (EWD-74). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription), 最初のセマフォに関する文書（オランダ語）
- semaphore.h programming interface - The Open Group Base Specifications Issue 6, IEEE Std 1003.1
- The Little Book of Semaphores Allen B. Downey
- A pragmatic, historically oriented survey on the universality of synchronization primitives, Jouni Leppäjärvi
