この記事はコンピュータプログラミング用語について説明しています。その他の用法については、「セマフォ（曖昧さ回避）」を参照してください。

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

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

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

セマフォの概念は、オランダの コンピュータ科学者 エドガー・ダイクストラによって1962年か1963年に発明されました^{[ 1 ]。}当時、ダイクストラと彼のチームはElectrologica X8用のオペレーティングシステムを開発していました。このシステムは後に「THE マルチプログラミングシステム」として知られるようになりました。

図書館の例え

[編集]

ある図書館に、同じ自習室が10室あり、一度に1人の学生が利用しているとします。学生は受付で部屋をリクエストする必要があります。空いている部屋がない場合、学生は誰かが部屋を空けるまで受付で待機します。部屋の使用を終えた学生は、受付に戻り、空いている部屋であることを伝えなければなりません。

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

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

重要な観察

[編集]

リソースプールへのアクセス制御に使用する場合、セマフォは空きリソースの数のみを追跡します。どのリソースが空きであるかは追跡しません。特定の空きリソースを選択するには、別のメカニズム（場合によっては複数のセマフォを必要とする）が必要になる場合があります。

このパラダイムは、セマフォのカウントが様々な行動のトリガーとして役立つため、特に強力です。例えば、司書は生徒がいなくなったら自習室の照明を消したり、ほとんどの部屋が満員なのに「大変混雑しています」という看板を掲げたりするかもしれません。

プロトコルの成功には、アプリケーションがプロトコルに正しく従うことが不可欠です。たとえ1つのプロセスでも誤った動作をすると、公平性と安全性が損なわれる可能性が高くなります（実際には、プログラムの動作が遅くなったり、不安定になったり、ハングしたり、クラッシュしたりする可能性があります）。これには以下が含まれます。

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

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

セマンティクスと実装

[編集]

計数セマフォには2つの操作があり、歴史的にはPとVで表されます（別名については§ 操作名を参照）。操作VはセマフォSをインクリメントし、操作PはセマフォSをデクリメントします。

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

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

• wait : セマフォ変数の値を1減算します。セマフォ変数の新しい値が負の場合、waitを実行しているプロセスはブロックされます（つまり、セマフォのキューに追加されます）。それ以外の場合、プロセスはリソースを1単位使用して実行を継続します。
• 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つがキューから削除され、実行が再開されます。プロセスに異なる優先度がある場合、キューは優先度に応じて順序付けされ、最も優先度の高いプロセスが最初にキューから取り出されます。

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

例

[編集]

些細な例

[編集]

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

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

ログインキュー

[編集]

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

生産者・消費者問題

[編集]

生産者・消費者問題では、一方のプロセス（生産者）がデータ項目を生成し、もう一方のプロセス（消費者）がそれを受信して​​使用します。これらのプロセスは、最大サイズ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. 単一のコンシューマがクリティカルセクションに入ります。がfullCount0なので、コンシューマはブロックされます。
2. 複数のプロデューサーがプロデューサークリティカルセクションに入ります。エントリー制約のため、クリティカルセクションに入ることができるプロデューサーはN個までです。emptyCount
3. プロデューサーは、1 人ずつキューにアクセスしuseQueue、アイテムをキューに置きます。
4. 最初のプロデューサーがクリティカル セクションを終了すると、fullCountが増分され、1 つのコンシューマーがクリティカル セクションに入ることができるようになります。

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

バトンパスのパターン

[編集]

グレゴリー・R・アンドリュースが提唱した「バトンパス」パターン^{[ 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. 偶発的な解放: 解放するタスクがミューテックスの所有者でない場合は、ミューテックスの解放時にエラーが発生します。

参照

[編集]

• モニター（同期）
• ロック（コンピュータサイエンス）
• 非同期/待機
• 同期（コンピュータサイエンス）
• フラグ（プログラミング）
• スピンロック
• 読者と書き手の問題
• 食事哲学者問題
• 寝ている理髪師の問題
• 喫煙者の問題
• 偽のウェイクアップ
• クリティカルセクション
• 競合状態

参考文献

[編集]

1. Dijkstra、Edsger W. 一連の手順に関する詳細 (EWD-35) (PDF)。 EW ディクストラ アーカイブ。テキサス大学オースティン校アメリカ史センター。（転写）（日付不明、1962年または1963年）
2. セマフォの小さな本アレン・B・ダウニー
3. Andrews, Gregory R. (1999). 『マルチスレッド、並列、分散プログラミングの基礎』 . Addison-Wesley.
4. Carver, Richard H.; Thai, Kuo-Chung (2005). 『モダン・マルチスレッディング：マルチスレッドJavaおよびC++/Pthreads/Win32プログラムの実装、テスト、デバッグ』 Wiley.
5. Maurer, Christian (2021). Goによる非逐次分散プログラミング. Springer.
6. シルバーシャッツ、アブラハム、ガルビン、ピーター・ベア、ガニエ、グレッグ（2008年）、オペレーティングシステムコンセプト（第8版）、ジョン・ワイリー・アンド・サンズ社、p.234、ISBN 978-0-470-12872-5
7. Dijkstra, Edsger W. EWD-74 (PDF) . EW Dijkstraアーカイブ.テキサス大学オースティン校アメリカ史センター. （転写）
8. Dijkstra, Edsger W. MULTIPROGAMMERING EN DE X8 (EWD-51) (PDF) . EW Dijkstraアーカイブ.テキサス大学オースティン校アメリカ歴史センター. （転写）（オランダ語）
9. ダイクストラ自身の翻訳では「try- and- decrease」となっているが、このフレーズは口語的な「try-and...」を知らない人にとっては混乱を招くかもしれない。
10. (PATCH 1/19) MUTEX: シンプルなミューテックス実装の導入Linuxカーネルメーリングリスト、2005年12月19日
11. LinuxカーネルハッキングHOWTO Archived 2010-05-28 at the Wayback Machine LinuxGrill.com
12. Mullender, Sape; Cox, Russ (2008). Plan 9におけるセマフォ(PDF) . 第3回Plan 9国際ワークショップ.
13. java.util.concurrent.Semaphore
14. "exec.library/Procure" . amigadev.elowar.com . 2016年9月19日閲覧。
15. "exec.library/Vacate" . amigadev.elowar.com . 2016年9月19日閲覧。

外部リンク

[編集]

紹介

[編集]

• Hilsheimer, Volker (2004). 「Read/Write Mutex の実装」（Web ページ）. Qt Quarterly , Issue 11 - Q3 2004
• ゼレンスキー、ジュリー；パランテ、ニック。「スレッドとセマフォの例」 （PDF）。配布資料。CS107プログラミングパラダイム。2008年春（23）。スタンフォード・エンジニアリング・エブリウェア（SEE）。

参考文献

[編集]

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