セマフォ

語源の腕木式信号機

セマフォ（英: semaphore）とは、計算機科学において、並行プログラミング環境での複数の実行単位（主にプロセス）が共有する資源にアクセスするのを制御する際の、単純だが便利な抽象化を提供する変数または抽象データ型である。

概要

セマフォは、ある資源が何個使用可能かを示す記録と考えればわかりやすく、それにその資源を使用する際や解放する際にその記録を「安全に」（すなわち競合状態となることなく）書き換え、必要に応じて資源が使用可能になるまで待つ操作が結びついている。セマフォは競合状態を防ぐ便利なツールであるが、セマフォを使うことでプログラムにおける競合状態がなくなると保証するものではない。任意個の資源を扱うセマフォをカウンティングセマフォ、値が0と1に制限されている（ロック/アンロック、使用可能/使用不可の意味がある）セマフォをバイナリセマフォと呼ぶ。後者はミューテックスと同等の機能を持つ。

セマフォの概念はオランダ人計算機科学者エドガー・ダイクストラが考案した。今ではさまざまなオペレーティングシステムで採用されている。

「en:semaphore」の本来の語義は「視覚による通信・信号」全般を指し、腕木通信や、それから派生した鉄道の腕木信号（や自動車の方向指示器）、手旗信号などが含まれる。

図書室のたとえ

ある図書室に学習室が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() を簡単に説明すると次のようになる。

• 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. 1つの消費者がクリティカルセクションに入る。fullCount は0なので、消費者はブロックする。
2. いくつかの生産者が生産者側のクリティカルセクションに入る。emptyCount で制限されるのでN以上の生産者はクリティカルセクションに入れない。
3. 生産者は useQueue により一度に1つずつキューにアクセスし、データをキューに入れていく。
4. 最初の生産者がクリティカルセクションを抜けるとき、fullCount がインクリメントされるので、ブロックしていた消費者がクリティカルセクション内の処理に進むことができる。

emptyCount はキュー上の実際の空きスロット数より小さくなる可能性がある。例えば、複数の生産者がデクリメントを行っても、useQueue によってキューへのデータ投入は逐次化されるためである。したがって常に emptyCount + fullCount ≤ N であり、等号が成り立つのは生産者も消費者も全くクリティカルセクションに入っていない場合だけである。

関数名の語源

歴史的に用いられてきた名前である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、pend と post などと呼ばれることが多い。教科書によっては元もとのオランダ語の頭文字に一致するよう procure と vacate としているものもある。

セマフォとミューテックス

ミューテックスは基本的にバイナリセマフォと等価であり、時には基本実装が同一ということもある。ただし、ミューテックスは2つの実行単位が同時に共用資源にアクセスするのを防止する構成物を表し、バイナリセマフォは単一の資源へのアクセスを制限する構成物を表す。

多くの場合、ミューテックスには「所有者」の概念がある。すなわちミューテックスをロックした実行単位だけがそれをアンロックすることができる。対照的にセマフォにはそのような制限がなく、上述の生産者/消費者問題の例でもそれを利用している。

したがって基本的には、ミューテックスは実行単位などの実行実体と結びついており、セマフォは資源と結びついている。

環境ごとの使用方法

POSIX

POSIX準拠の環境では、semaphore.hに宣言された型と関数を使用できる。sem_init()で無名のセマフォを生成するか、sem_open()で名前付きセマフォを生成またはオープンできる。sem_init()の引数psharedに非ゼロの値を指定することで、プロセス間で共有されるセマフォを生成することもできる。sem_wait()でセマフォの値を減らし（ロック）、sem_post()でセマフォの値を増やす（ロック解除）。sem_destroy()で無名のセマフォを破棄する。sem_close()で名前付きセマフォをクローズする。

Windows

WindowsのWin32 APIでは、CreateSemaphore()関数でセマフォを生成またはオープンできる。WaitForSingleObject()関数でセマフォを待機する（カウント減少）。ReleaseSemaphore()関数でセマフォを解放する（カウント増加）。CloseHandle()関数でセマフォのハンドルをクローズする（オブジェクト破棄）。OpenSemaphore()関数で既存の名前付きセマフォをオープンできる。スレッド間同期だけでなく、プロセス間同期に使用することもできる。

MFCにはC++のコンストラクタ/デストラクタによるRAII機構を利用した、Win32同期オブジェクトのラッパークラスCSemaphoreが用意されている（実際にはCSingleLockと組み合わせて使用することが多い）。

.NET

.NET Framework 2.0以降では、System.Threading.Semaphore クラスを使う。バージョン1.1以前では自作するかWin32 APIを呼び出す必要がある。ローカルセマフォはスレッド間同期にのみ使用できるが、名前付きシステムセマフォはプロセス間同期に使用することもできる。Semaphoreクラスは.NET Coreおよび.NET 5以降でも利用可能だが、Windows以外のプラットフォームではスレッド間同期にのみ使用でき、プロセス間同期には使用できない。

.NET Framework 4.0以降では、同一プロセス内のスレッド間同期であれば、軽量化されたSystem.Threading.SemaphoreSlim クラスを利用できる。

Java

Javaでは、java.util.concurrent.Semaphore クラスを使う。Java 5 以降で使用可能である。

Perl

Perlでは、Thread::Semaphore モジュールや、新しくはCoro::Semaphore モジュールなどを使う。

Python

Pythonでは、threadingモジュール中に Semaphoreクラスが用意されている。

Swift

Swiftでは、Grand Central Dispatchの機能として Dispatch フレームワーク中に DispatchSemaphore クラスが用意されている。

参考文献

• Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operating System Concepts (8th ed.), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5 

関連項目

• 排他制御
• マルチスレッド
• デッドロック
• スレッド
• クリティカルセクション
• ミューテックス
• 食事する哲学者の問題
• 居眠り床屋問題
• モニタ (同期)

外部リンク

• 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