セマフォ（プログラミング）

コンピュータ サイエンスにおいて、セマフォとは、複数のスレッドによる共通リソースへのアクセスを制御し、マルチタスク オペレーティングシステムなどの並行システムでクリティカル セクションの問題を回避するために使用される変数または抽象データ型です。セマフォは、同期プリミティブの一種です。単純なセマフォは、プログラマが定義した条件に応じて変更される (たとえば、増分または減分、または切り替えられる) 単純な変数です。

実際のシステムで使用されるセマフォを考える場合、特定のリソースのユニットがいくつ使用可能かを記録し、ユニットが取得されたり解放されたりしたときにその記録を安全に調整する (つまり、競合状態を回避する) 操作と組み合わせ、必要に応じてリソースのユニットが使用可能になるまで待機する操作と考えると便利です。

セマフォは競合状態を防ぐのに役立ちますが、競合状態が存在しないことが保証されるわけではありません。任意のリソース カウントを許可するセマフォはカウンティング セマフォと呼ばれ、値 0 と 1 (またはロック/ロック解除、使用不可/使用可能) に制限されるセマフォはバイナリ セマフォと呼ばれ、ロックを実装するために使用されます。

セマフォの概念は、オランダの コンピュータ科学者 エドガー・ダイクストラが1962年か1963年に発明したもので、^{[1]ダイクストラと彼のチームが}エレクトロロジカX8用のオペレーティングシステムを開発していたときに考案されました。そのシステムは最終的にTHEマルチプログラミングシステムとして知られるようになりました。

物理的な図書館に、一度に 1 人の学生が使用できる 10 の同じ自習室があるとします。学生はフロント デスクに部屋をリクエストする必要があります。空いている部屋がない場合、学生は誰かが部屋を譲るまでデスクで待機します。学生は部屋の使用を終えたら、デスクに戻って部屋が空いていることを示す必要があります。

最も単純な実装では、フロント デスクの係員は空いている部屋の数しか知りません。この場合、すべての学生が登録期間中は部屋を使用し、使用後は部屋を返却する必要があります。学生が部屋をリクエストすると、係員はこの数を減らします。学生が部屋を解放すると、係員はこの数を増やします。部屋は必要な期間だけ使用できるため、事前に部屋を予約することはできません。

このシナリオでは、フロントデスクのカウントホルダーはカウントセマフォを表し、部屋はリソース、学生はプロセス/スレッドを表します。このシナリオのセマフォの値は最初は 10 で、すべての部屋が空いています。学生が部屋を要求すると、アクセスが許可され、セマフォの値は 9 に変更されます。次の学生が来ると、値は 8 に下がり、その次は 7 になります。誰かが部屋を要求し、セマフォの現在の値が 0 の場合、^[2]部屋が解放されるまで (カウントが 0 から増加するまで) 待機する必要があります。部屋の 1 つが解放されたが、待機している学生が複数いる場合は、任意の方法 ( FIFOやランダムに選択するなど) を使用して、部屋を使用する学生を選択できます。そしてもちろん、学生は実際に部屋を出た後でのみ、店員に部屋を解放したことを知らせる必要があります。

リソースプールへのアクセスを制御するために使用する場合、セマフォは空いているリソースの数のみを追跡します。どのリソースが空いているかは追跡しません。特定の空いているリソースを選択するには、他のメカニズム (おそらくより多くのセマフォを必要とする) が必要になる場合があります。

このパラダイムは、セマフォのカウントがさまざまなアクションの便利なトリガーとして機能するため、特に強力です。上記の司書は、生徒がいなくなったときに自習室の照明を消したり、ほとんどの部屋が使用中のときに部屋が非常に混雑していることを示す標識を設置したりすることができます。

プロトコルが成功するには、アプリケーションがプロトコルに正しく従う必要があります。 1 つのプロセスでも誤った動作をすると、公平性と安全性が損なわれる可能性があります (つまり、プログラムの動作が遅くなったり、不規則になったり、ハングしたり、クラッシュしたりする可能性があります)。 これには次のものが含まれます。

• リソースを要求して解放し忘れる;
• 要求されていないリソースを解放する。
• 必要のないリソースを長期間保持すること。
• 事前に要求せずに（または解放した後に）リソースを使用すること。

すべてのプロセスがこれらのルールに従っている場合でも、異なるセマフォによって管理される異なるリソースがある場合や、食事中の哲学者問題で示されるように、プロセスが一度に複数のリソースを使用する必要がある場合には、マルチリソース デッドロックが発生する可能性があります。

カウンティング セマフォには 2 つの操作があり、歴史的には P と V で表されます (別名については § 操作名を参照)。操作 V はセマフォSを増分し、操作 P はセマフォ S を減分します。

セマフォSの値は、現在利用可能なリソースのユニット数です。P 操作は、セマフォによって保護されているリソースが利用可能になるまで時間を浪費するかスリープ状態になります。利用可能になった時点で、リソースは直ちに要求されます。V 操作はその逆で、プロセスがリソースの使用を終了した後、そのリソースを再び利用可能にします。セマフォSの重要な特性の 1 つは、V 操作と P 操作を使用しない限り、その値を変更できないことです。

待機(P) とシグナル(V) の操作を理解する簡単な方法は次のとおりです。

• wait : セマフォ変数の値を 1 減らします。セマフォ変数の新しい値が負の場合、waitを実行しているプロセスはブロックされます (つまり、セマフォのキューに追加されます)。それ以外の場合、プロセスはリソースの単位を使用して実行を継続します。
• signal : セマフォ変数の値を 1 増加します。増加後、増加前の値が負の場合 (リソースを待機しているプロセスがあることを意味します)、ブロックされたプロセスをセマフォの待機キューから準備完了キューに転送します。

多くのオペレーティング システムでは、セマフォが増加すると待機中のプロセスのブロックを解除する効率的なセマフォ プリミティブが提供されています。つまり、プロセスはセマフォの値を不必要にチェックして時間を無駄にしません。

カウント セマフォの概念は、セマフォから複数の「ユニット」を要求または返す機能によって拡張できます。これは、Unixで実装された手法です。変更された V および P 操作は次のとおりです。角括弧を使用してアトミック操作(つまり、他のプロセスに分割できない操作) を示します。

関数V(セマフォ S、整数 I):
    [S ← S + I]

関数P(セマフォ S, 整数 I):
    繰り返し: 
        [ S ≥ Iの場合:
        S ← S − I
        壊す]

ただし、このセクションの残りの部分では、特に指定がない限り、単項 V および P 操作を使用するセマフォについて説明します。

飢餓状態を回避するために、セマフォにはプロセスのキューが関連付けられています(通常はFIFOセマンティクスを使用)。プロセスが値 0 のセマフォに対して P 操作を実行すると、そのプロセスはセマフォのキューに追加され、その実行は一時停止されます。別のプロセスが V 操作を実行してセマフォを増分し、キューにプロセスがある場合は、そのうちの 1 つがキューから削除され、実行が再開されます。プロセスの優先度が異なる場合、キューはそれに応じて順序付けされ、最も優先度の高いプロセスが最初にキューから取り出されます。

実装によって増分、減分、および比較操作のアトミック性が保証されていない場合、増分または減分が忘れられたり、セマフォの値が負になったりするリスクがあります。アトミック性は、1 回の操作でセマフォの読み取り、変更、および書き込みができるマシン命令を使用することで実現できます。このようなハードウェア命令がない場合、ソフトウェア相互排他アルゴリズムを使用してアトミック操作を合成できます。ユニプロセッサシステムでは、一時的にプリエンプションを中断するか、ハードウェア割り込みを無効にすることでアトミック操作を確保できます。この方法は、セマフォを共有する 2 つのプログラムが同時に異なるプロセッサで実行される可能性があるマルチプロセッサ システムでは機能しません。マルチプロセッサ システムでこの問題を解決するには、ロック変数を使用してセマフォへのアクセスを制御します。ロック変数は、test-and-set-lockコマンドを使用して操作します。

変数Aとブール変数Sを考えてみましょう。AはSが true とマークされている場合にのみアクセスされます。したがって、S はAのセマフォです。

駅 ( A ) のすぐ前に信号機 ( S ) があると想像してください。この場合、信号が緑であれば駅に入ることができます。信号が黄色や赤 (またはその他の色) であれば、駅に入ることはできません。

10 人のユーザー (S=10) しかサポートできないシステムについて考えてみましょう。ユーザーがログインするたびに、P が呼び出され、セマフォSが 1 減ります。ユーザーがログアウトするたびに、V が呼び出され、Sが 1 増えます。これは、ログイン スロットが空いたことを示します。S が 0 の場合、ログインを希望するユーザーは、Sが増加するまで待機する必要があります。ログイン要求は、スロットが解放されるまで FIFO キューにエンキューされます。相互排他制御によって、要求が順番にエンキューされます。S が増加するたびに(ログイン スロットが使用可能)、ログイン要求がキューから取り出され、要求を所有するユーザーはログインできます。S がすでに 0 より大きい場合、ログイン要求は直ちにキューから取り出されます。

生産者 - 消費者問題では、1 つのプロセス (生産者) がデータ項目を生成し、別のプロセス (消費者) がそれを受信して​​使用します。これらは最大サイズNのキューを使用して通信し、次の条件に従います。

• キューが空の場合、コンシューマーはプロデューサーが何かを生成するまで待機する必要があります。
• キューがいっぱいの場合、プロデューサーはコンシューマーが何かを消費するまで待機する必要があります。

生産者-消費者問題に対するセマフォによる解決法では、キューの状態を 2 つのセマフォで追跡します。emptyCountはキュー内の空き領域の数、 はfullCountキュー内の要素の数です。整合性を維持するために、 はemptyCountキュー内の実際の空き領域の数よりも小さくなることがありますfullCount(ただし、大きくなることはありません)。また、 はキュー内の実際の項目数よりも小さくなることがあります (ただし、大きくなることはありません)。空き領域と項目は、空のボックスといっぱいのボックスという 2 種類のリソースを表し、セマフォemptyCountと はfullCountこれらのリソースを制御します。

バイナリ セマフォは、useQueueキュー自体の状態の整合性が損なわれないことを保証します。たとえば、2 つのプロデューサーが同時に空のキューにアイテムを追加しようとして、キューの内部状態が破壊されるようなことはありません。バイナリ セマフォの代わりに、 ミューテックスを使用することもできます。

はemptyCount最初はN、fullCountは最初は 0、 はuseQueue最初は 1 です。

プロデューサーは次のことを繰り返し行います。

生産する：
    P(空カウント)
    P(キューの使用)
    アイテムをキューに入れる(アイテム)
    V(キューの使用)
    V(フルカウント)

消費者は次のことを繰り返し行う

消費する：
    P(フルカウント)
    P(キューの使用)
    アイテム ← getItemFromQueue()
    V(キューの使用)
    V(空カウント)

以下に具体的な例を示します。

1. 単一のコンシューマーがクリティカル セクションに入ります。fullCountは 0 なので、コンシューマーはブロックします。
2. 複数のプロデューサーがプロデューサー クリティカル セクションに入ります。エントリの制約により、クリティカル セクションに入ることができるプロデューサーはN個までです。emptyCount
3. プロデューサーは、1 人ずつキューにアクセスしuseQueue、キューにアイテムを置きます。
4. 最初のプロデューサーがクリティカル セクションを終了すると、fullCountが増分され、1 つのコンシューマーがクリティカル セクションに入ることができるようになります。

emptyCountは、キュー内の実際の空きスペースの数よりもはるかに少ない場合があることに注意してください。たとえば、多くのプロデューサーがキューの数を減らしたが、useQueue空きスペースを埋める前に順番を待っている場合などです。 は常に成立し、プロデューサーまたはコンシューマーがクリティカル セクションを実行していない場合にのみ等しくなります。 emptyCount + fullCount ≤ N

Gregory R. Andrews が提案した「バトンを渡す」パターン^{[3] [4] [5]}は、複数のプロセスが同じリソースを複雑なアクセス条件 (特定の優先基準を満たす、またはリソース不足を回避するなど) で競合する、多くの複雑な並行プログラミング問題を解決する汎用スキームです。共有リソースが与えられた場合、このパターンでは、関係する各プロセス (またはプロセス クラス) にプライベートな「priv」セマフォ (0 に初期化) と、相互排他用の「mutex」セマフォ (1 に初期化) が 1 つ必要です。各プロセスの疑似コードは次のとおりです。

void process ( int proc_id , int res_id ) { resource_acquire ( proc_id , res_id ); <リソースres_idを使用する> ; resource_release ( proc_id , res_id ); }    

	 
	
	   
	
	 

リソースの取得および解放プリミティブの疑似コードは次のとおりです。

void resource_acquire ( int proc_id , int res_id ) { P ( mutex ); if ( < res_idにアクセスするための条件がproc_idに対して検証されていない> ) { < proc_idがres_idに対して中断されていることを示す> ; V ( mutex ); P ( priv [ proc_id ] ); < proc_idがres_idに対して中断されていないことを示す> ; } < proc_id がリソースにアクセスしていることを示す> ; pass_the_baton (); // 以下を参照}    

	
	
	         
	
		      
		
		
		        
	
	
	      
	
	 

void resource_release ( int proc_id , int res_id ) { P ( mutex ); < proc_id がリソースres_idにアクセスしていないことを示す> ; pass_the_baton ( ); // 以下を参照}    

	
	
	         
	
	 

両方のプリミティブは、疑似コードが次のとおりである「pass_the_baton」メソッドを使用します。

void pass_the_baton ( int res_id ) { if < res_idにアクセスするための条件が少なくとも1 つの中断されたプロセスに対してtrueである場合> { int p = <ウェイクするプロセスを選択する> ; V ( priv [ p ]); } else { V ( mutex ); } }  

	             
	
		       
		
	
	
	
		
	

備考

このパターンは、「バトンを渡す」と呼ばれます。これは、リソースを解放するプロセスと、新たに再アクティブ化されたプロセスは、最大で 1 つの中断されたプロセスをアクティブ化する、つまり「バトンを渡す」ためです。ミューテックスは、プロセスが自身を中断しようとするとき (resource_acquire)、または pass_the_baton が別の中断されたプロセスを再アクティブ化できない場合にのみ解放されます。

正統な名前である V と P はオランダ語の頭文字に由来する。V は一般的にverhogen (「増加」) と説明される。P については、proberen (「テストする」または「試す」)、^[6] passeren (「通過する」)、pakken (「掴む」) など、いくつかの説明が提示されている。ダイクストラのこの主題に関する最初の論文^[1]では、 Pの意味としてpassering (「通過する」) 、 V の意味としてvrijgave (「解放する」) が挙げられている。また、この用語は鉄道信号で使用されている用語から取られていることにも言及している。ダイクストラはその後、P をprolaag ^[7]の略語として意図したと記している。probeer te verlagen の略語で、文字通り「減らそうとする」、または他のケースで使用されている用語と平行して「減らそうとする」。^{[8] [9] [10]}

ALGOL 68、Linuxカーネル^[11]、および一部の英語の教科書では、V操作とP操作はそれぞれupとdown と呼ばれています。ソフトウェアエンジニアリングの実務では、これらはsignalとwait ^[12] 、releaseとacquire ^[12] (標準Javaライブラリ)、^[13]、postとpendと呼ばれることがよくあります。一部のテキストでは、元のオランダ語の頭文字に合わせてvacateとprocure と呼んでいます。 ^{[14] [15]}

ミューテックスは、バイナリ セマフォと同じ基本実装を使用するロック メカニズムです。ただし、使用方法は異なります。バイナリ セマフォは口語的にミューテックスと呼ばれることもありますが、真のミューテックスは、ミューテックスをロックしたタスクのみがロックを解除できるという点で、より具体的な使用例と定義を持っています。この制約は、セマフォの使用に関する潜在的な問題に対処することを目的としています。

1. 優先度の反転: ミューテックスが誰がロックしたかを認識しており、誰がロックを解除すべきかがわかっている場合、優先度の高いタスクがミューテックスで待機を開始するたびに、そのタスクの優先度を上げることができます。
2. タスクの早期終了: ミューテックスは削除安全性も提供し、ミューテックスを保持しているタスクが誤って削除されることはありません。^{[引用が必要]}
3. 終了デッドロック: ミューテックスを保持しているタスクが何らかの理由で終了した場合、OS はミューテックスを解放し、この状態の待機中のタスクにシグナルを送信できます。
4. 再帰デッドロック: タスクは、再入可能ミューテックスを同じ回数だけロック解除するため、それを複数回ロックできます。
5. 偶発的な解放: 解放するタスクがミューテックスの所有者でない場合は、ミューテックスの解放時にエラーが発生します。

• 非同期/待機
• フラグ（プログラミング）
• 同期（コンピュータサイエンス）
• 喫煙者の問題
• 食事哲学者問題
• 読者と書き手の問題
• 寝ている理容師の問題
• モニター
• 偽のウェイクアップ

• Hilsheimer, Volker (2004)。「読み取り/書き込みミューテックスの実装」(Web ページ)。Qt Quarterly、第 11 号 - 2004 年第 3 四半期
• Zelenski, Julie; Parlante, Nick. 「スレッドとセマフォの例」(PDF)。配布資料。CS107 プログラミング パラダイム。2008 年春 (23)。Stanford Engineering Everwhere (SEE)。

• Dijkstra, Edsger W.協調する連続プロセス (EWD-123) (PDF) 。EW Dijkstra アーカイブ。テキサス大学オースティン校アメリカ歴史センター。（転写）（1965年9月）
• 「semaphore.h - セマフォ (REALTIME)」。Open Group 基本仕様第 6 版 IEEE Std 1003.1、2004 年版。Open Group。2004 年。
• ダウニー、アレン B. (2016) [2005]。『セマフォの小さな本』（第 2 版）。グリーン ティー プレス。
• Leppäjärvi, Jouni (2008 年 5 月 11 日)。「同期プリミティブの普遍性に関する実用的かつ歴史的指向の調査」(PDF)。オウル大学、フィンランド。