セマフォ（）とは、計算機科学において、並列プログラミング環境での複数の実行単位（主にプロセス）が共有する資源にアクセスするのを制御する際の単純だが便利な抽象化を提供する変数または抽象データ型である。ある資源が何個使用可能かを示す記録と考えればわかりやすく、それにその資源を使用する際や解放する際にその記録を「安全に」（すなわち競合状態となることなく）書き換え、必要に応じて資源が使用可能になるまで待つ操作が結びついている。セマフォは競合状態を防ぐ便利なツールである。しかしセマフォを使うことでプログラムにおける競合状態がなくなると保証するものではない。任意個の資源を扱うセマフォをカウンティングセマフォ、値が0と1に制限されている（ロック/アンロック、使用可能/使用不可の意味がある）セマフォをバイナリセマフォと呼ぶ。後者はミューテックスと同等の機能を持つ。セマフォの概念はオランダ人計算機科学者エドガー・ダイクストラが考案した。今では様々なオペレーティングシステムで採用されている。「」の本来の語義は「視覚による通信・信号」全般を指し、腕木通信や、それから派生した鉄道の腕木信号（や自動車の方向指示器）、手旗信号などが含まれる。日本語でのセマフォは本用途（コンピュータ、プログラミング関連）に限られる。ある図書室に学習用の個室が10部屋あり、それぞれの学習室は一度に1人の学生が使用するとする。争奪戦が始まらないよう、学生はフロントデスクで学習室の使用を申し込むことになっている。学習室を使用し終えたら、学生はフロントに立ち寄ってその学習室が空いたことを知らせなければならない。全ての学習室が埋まっている場合、学生はフロントで部屋が空くのを待つ。フロントの図書係はどの学習室が空いているかは把握しておらず、単に空いている部屋数のみを知っている。学生が申し込んできたとき、図書係はその数から1を引く。学生が学習室の利用を終えたとき、図書係はその数に1を加える。学習室の使用許可が与えられたとき、その部屋は必要なだけ使い続けることができ、したがって事前に学習室を予約することはできない。このシナリオでは、フロントデスクがセマフォ、学習室が資源、学生が実行単位に相当する。また、セマフォの初期値は10になっている。学生が学習室の使用を申し込んで許可されたとき、セマフォ値から1が引かれて9になる。次の学生のときには8、さらに次は7となる。1を引くとセマフォ値が負になるという状態で学生が申し込んだ場合、その学生は待たされる。複数人の学生が待っているとき、彼らは待ち行列を形成するか、いずれかの学生が学習室の使用を終えてフロントにやってきたときにラウンドロビン・スケジューリング方式で空いた部屋を割り当てる（このあたりはセマフォの実装に依存する）。複数の資源に対して使用する場合、セマフォは個々の資源の使用/解放状態を把握せず、単に個数のみを保持する。特定の資源を指定したい場合は、他の機構が必要とされる（複数のセマフォの組合せでも可能）。実行単位群はそのプロトコルに従うという点で信頼されている。1つの実行単位が間違った動作をすれば、公平性と安全性は損なわれ、性能低下、不正動作、フリーズ、クラッシュなどが発生しうる。例えば、次のような動作が間違った動作である。全実行単位がその規則に従ったとしても、資源が複数種類あって、それぞれにセマフォが設定されている場合、実行単位が複数の資源を同時に使用するなら新たな問題が発生しうる。例えば、食事する哲学者の問題がそのような状況を示している。セマフォ変数の重要な属性として、その値の変更には特定の関数群を使わなければならないという点が挙げられる。ここではそれら関数を wait() と signal() とする。カウンティングセマフォでの2つの操作は、歴史的には V（または signal()）と P（または wait()）と記述される。V操作はセマフォSをインクリメントし、P操作はデクリメントする。それら操作の意味論は後述する。角括弧で囲まれた部分は不可分操作であることを意味し、その部分の途中経過は他の実行単位からは見えない。セマフォSの値は、その時点で使用可能な資源の個数である。P操作は資源を獲得しようとするもので、セマフォで守られている資源が使用可能になるまでビジーウェイトまたはで待つことになる。V操作はその逆であり、使用していた資源を解放する。wait() と signal() を簡単に説明すると次のようになる。多くのOSは効率的なセマフォのプリミティブを提供しており、セマフォをインクリメントした際には1つだけ待ち状態の実行単位をアンブロックする。すなわち、複数の実行単位を同時にアンブロックした際の無用なセマフォ値のチェック処理を防いでいる。カウンティングセマフォの概念は、一度に複数個の資源を獲得・解放できるように拡張でき、UNIXでの実装もそのようになっている。その場合のVおよびP操作は次のように修正される。リソーススタベーションを防ぐため、セマフォには実行単位のキュー（通常はFIFO）が1つ付属している。セマフォ値がゼロのときにP操作をすると、その実行単位はセマフォ付属のキューに追加される。別の実行単位がV操作でセマフォ値をインクリメントしたとき、キュー上に実行単位があれば、そのうちの1つをキューから外して実行再開させる。実行単位に優先度が設定されている場合、キュー上で優先度順に実行単位を並べるなどして、最も優先度の高い実行単位が最初に実行再開できるようにする。実装においてインクリメント/デクリメントや比較の不可分性が保証されていない場合、インクリメントやデクリメントが行われなかったり、セマフォ値が不正になる危険性が生じる。不可分性を達成するには、（読み取って、変更を加えて、書き込むという処理サイクル）を不可分に実行できる機械語命令を使用する。そのような機械語命令がない場合、デッカーのアルゴリズムなどのソフトウェアによる排他制御を使用する。シングルプロセッサのシステムでの不可分操作は、プリエンプションを一時的に禁止したり、割り込みをマスクしたりすることでも実現できる。マルチプロセッサシステムではそれだけでは不十分で、同じセマフォを共有する2つのプログラムが別々のプロセッサ上で同時に動作している場合に対処できない。そのためテスト・アンド・セット命令などを使用してセマフォ変数へのアクセスをロックする必要がある。では、1つの実行単位（生産者）がデータを生成し、もう1つの実行単位（消費者）がそれらを受け取って使用する。データの受け渡しは最大サイズNのキューで行い、次のような条件に従う。生産者/消費者問題をセマフォで解決する場合、キューの状態を2つのセマフォで表す。codice_3 はキュー上の空いているスロット数を保持し、codice_4 はキュー上の要素数を保持する。完全性を維持するには、codice_3 を実際の空きスロット数より小さくなるようにし、codice_4 を実際のキュー上の要素数より小さくなるようにする（どちらも実際の数を越えてはならない）。空きスロットと要素は、空の箱と満たされた箱という2種類の資源を表しており、セマフォ codice_3 と codice_4 はそれら資源についての制御を管理する。バイナリセマフォ codice_9 は、例えば2つの生産者が同時にデータをキューに格納しようとするなどといった不正な状態が発生しないことを保証するためにある。このバイナリセマフォはミューテックスで代替することもできる。codice_3 の初期値は N、codice_4 の初期値は0、codice_9 の初期値は1である。生産者は次のような処理を繰り返す。消費者は次のような処理を繰り返す。具体的には次のような動作をする。codice_3 はキュー上の実際の空きスロット数より小さくなる可能性がある。例えば、複数の生産者がデクリメントを行っても、codice_9 によってキューへのデータ投入は逐次化されるためである。したがって常に codice_19 であり、等号が成り立つのは生産者も消費者も全くクリティカルセクションに入っていない場合だけである。元もとの名前であるPとVは、オランダ語の単語の頭文字に由来している。Vは "verhogen"（増加する）を意味する。Pについては、"proberen"（テストする）、"passeer"（通過）、"probeer"（試みる）、"pakken"（つかむ）などいくつかの説明がある。セマフォの本来の意味である腕木通信から、Vを "verhoog"（腕木を上げる、通行禁止）、Pを "passeren"（腕木を下げる、通行許可）とする説もある。ただしダイクストラ自身はPを "probeer te verlagen"（減らすことを試みる）を略したかばん語 "prolaag" の頭文字だとしている。この混乱のもとは、オランダ語で "increase" と "decrease" に相当する語がどちらも "V" で始まるためで、かといってオランダ語の単語をそのまま使ってもオランダ語を知らない人はかえって混乱するとダイクストラが考えたためである。ALGOL 68 やLinuxカーネル、いくつかの英語の教科書では、PとVはそれぞれ "down" と "up" とされている。ソフトウェア工学では一般に wait と signal、acquire と release（Javaのライブラリで使用）、pend と post などと呼ばれることが多い。教科書によっては元もとのオランダ語の頭文字に一致するよう procure と vacate としているものもある。ミューテックスは基本的にバイナリセマフォと等価であり、時には基本実装が同一ということもある。ただし、ミューテックスは2つの実行単位が同時に共用資源にアクセスするのを防止する構成物を表し、バイナリセマフォは単一の資源へのアクセスを制限する構成物を表す。多くの場合、ミューテックスには「所有者」の概念がある。すなわちミューテックスをロックした実行単位だけがそれをアンロックすることができる。対照的にセマフォにはそのような制限がなく、上述の生産者/消費者問題の例でもそれを利用している。したがって基本的には、ミューテックスは実行単位などの実行実体と結びついており、セマフォは資源と結びついている。

出典:wikipedia