コンテンツにスキップ
メインメニュー
メインメニュー
サイドバーに移動
非表示
案内
メインページ
最近の更新
おまかせ表示
MediaWiki についてのヘルプ
特別ページ
Wikippe
検索
検索
表示
ログイン
個人用ツール
ログイン
セマフォのソースを表示
ページ
議論
日本語
閲覧
ソースを閲覧
履歴を表示
ツール
ツール
サイドバーに移動
非表示
操作
閲覧
ソースを閲覧
履歴を表示
全般
リンク元
関連ページの更新状況
ページ情報
表示
サイドバーに移動
非表示
←
セマフォ
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
要求した操作を行うことは許可されていません。
このページのソースの閲覧やコピーができます。
'''セマフォ'''({{lang-en-short|semaphore}})とは、[[計算機科学]]において、[[並列計算|並列プログラミング]]環境での複数の[[プロセス]]が共有する資源にアクセスするのを制御する際の単純だが便利な抽象化を提供する[[変数 (プログラミング)|変数]]または[[抽象データ型]]である。 ある資源が何個使用可能かを示す記録と考えればわかりやすく、それにその資源を使用する際や解放する際にその記録を「安全に」(すなわち[[競合状態]]となることなく)書き換え、必要に応じて資源が使用可能になるまで待つ操作が結びついている。セマフォは競合状態を防ぐ便利なツールである。しかしセマフォを使うことでプログラムにおける競合状態がなくなると保証するものではない。任意個の資源を扱うセマフォを'''カウンティングセマフォ'''、値が0と1に制限されている(ロック/アンロック、使用可能/使用不可の意味がある)セマフォを'''バイナリセマフォ'''と呼ぶ。後者は[[ミューテックス]]と同等の機能を持つ。 セマフォの概念はオランダ人[[計算機科学]]者[[エドガー・ダイクストラ]]が考案した<ref>[[エドガー・ダイクストラ|Dijkstra, Edsger W.]] ''Cooperating sequential processes (EWD-123)''. E.W. Dijkstra Archive. Center for American History, [[テキサス大学オースティン校|University of Texas at Austin]]. ([http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD123.PDF original]; [http://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html transcription]) (September 1965)</ref>。今では様々な[[オペレーティングシステム]]で採用されている。 「{{lang|en|semaphore}}」の本来の語義は「視覚による通信・信号」全般を指し、[[腕木通信]]や、それから派生した[[鉄道]]の[[鉄道信号機|腕木信号]](や[[自動車]]の[[方向指示器]])、[[手旗信号]]などが含まれる。日本語でのセマフォは本用途([[コンピュータ]]、[[プログラミング (コンピュータ)|プログラミング]]関連)に限られる。 [[画像:Udegishiki Tokushima.jpg|thumb|150px|right|語源の腕木式信号機]] == 図書室のたとえ == ある図書室に学習用の個室が10部屋あり、それぞれの学習室は一度に1人の学生が使用するとする。争奪戦が始まらないよう、学生はフロントデスクで学習室の使用を申し込むことになっている。学習室を使用し終えたら、学生はフロントに立ち寄ってその学習室が空いたことを知らせなければならない。全ての学習室が埋まっている場合、学生はフロントで部屋が空くのを待つ。 フロントの図書係はどの学習室が空いているかは把握しておらず、単に空いている部屋数のみを知っている。学生が申し込んできたとき、図書係はその数から1を引く。学生が学習室の利用を終えたとき、図書係はその数に1を加える。学習室の使用許可が与えられたとき、その部屋は必要なだけ使い続けることができ、したがって事前に学習室を予約することはできない。 このシナリオでは、フロントデスクがセマフォ、学習室が資源、学生がプロセスに相当する。また、セマフォの初期値は10になっている。学生が学習室の使用を申し込んで許可されたとき、セマフォ値から1が引かれて9になる。次の学生のときには8、さらに次は7となる。1を引くとセマフォ値が負になるという状態で学生が申し込んだ場合、その学生は待たされる<ref>[http://greenteapress.com/semaphores/ ''The Little Book of Semaphores''] Allen B. Downey</ref>。複数人の学生が待っているとき、彼らは[[キュー (コンピュータ)|待ち行列]]を形成するか、いずれかの学生が学習室の使用を終えてフロントにやってきたときに[[ラウンドロビン・スケジューリング]]方式で空いた部屋を割り当てる(このあたりはセマフォの実装に依存する)。 === 重要な観点 === 複数の資源に対して使用する場合、セマフォは個々の資源の使用/解放状態を把握せず、単に個数のみを保持する。特定の資源を指定したい場合は、他の機構が必要とされる(複数のセマフォの組合せでも可能)。 プロセス群はそのプロトコルに従うという点で信頼されている。1つのプロセスが間違った動作をすれば、公平性と安全性は損なわれ、性能低下、不正動作、[[フリーズ]]、[[クラッシュ (コンピュータ)|クラッシュ]]などが発生しうる。例えば、次のような動作が間違った動作である。 * 資源を要求しておいて、使用後に解放し忘れる。 * 要求したことのない資源を解放する。 * 使っていない資源を長期に渡って獲得したままにする。 * 要求せずに資源を使用する。あるいは解放済みの資源を使用する。 全プロセスがその規則に従ったとしても、資源が複数種類あって、それぞれにセマフォが設定されている場合、プロセスが複数の資源を同時に使用するなら新たな問題が発生しうる。例えば、[[食事する哲学者の問題]]がそのような状況を示している。 == 意味論と実装 == セマフォ変数の重要な属性として、その値の変更には特定の関数群を使わなければならないという点が挙げられる。ここではそれら関数を wait() と signal() とする。 カウンティングセマフォでの2つの操作は、歴史的には '''V'''(または signal())と '''P'''(または wait())と記述される。'''V'''操作はセマフォ'''S'''を[[インクリメント]]し、'''P'''操作は[[デクリメント]]する。それら操作の意味論は後述する。角括弧で囲まれた部分は[[不可分操作]]であることを意味し、その部分の途中経過は他のプロセスからは見えない。 セマフォ'''S'''の値は、その時点で使用可能な資源の個数である。'''P'''操作は資源を獲得しようとするもので、セマフォで守られている資源が使用可能になるまで[[ビジーウェイト]]または{{仮リンク|スリープ (オペレーティングシステム)|en|sleep (operating system)|label=スリープ}}で待つことになる。'''V'''操作はその逆であり、使用していた資源を解放する。 wait() と signal() を簡単に説明すると次のようになる。 * <code>wait()</code>: セマフォの値を1だけデクリメントする。その結果、値が負になるなら wait() を実行しているプロセスはブロックされる。つまり、セマフォのキューに追加される。 * <code>signal()</code>: セマフォの値を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つをキューから外して実行再開させる。プロセスに優先度が設定されている場合、キュー上で優先度順にプロセスを並べるなどして、最も優先度の高いプロセスが最初に実行再開できるようにする。 実装においてインクリメント/デクリメントや比較の[[不可分操作|不可分性]]が保証されていない場合、インクリメントやデクリメントが行われなかったり、セマフォ値が不正になる危険性が生じる。不可分性を達成するには、{{仮リンク|リード・モディファイ・ライト|en|read-modify-write}}(読み取って、変更を加えて、書き込むという処理サイクル)を不可分に実行できる機械語命令を使用する。そのような機械語命令がない場合、[[デッカーのアルゴリズム]]などのソフトウェアによる[[排他制御]]を使用する。シングルプロセッサのシステムでの不可分操作は、[[プリエンプション]]を一時的に禁止したり、[[割り込み (コンピュータ)|割り込み]]をマスクしたりすることでも実現できる。[[マルチプロセッサ]]システムではそれだけでは不十分で、同じセマフォを共有する2つのプログラムが別々のプロセッサ上で同時に動作している場合に対処できない。そのため[[テスト・アンド・セット]]命令などを使用してセマフォ変数へのアクセスを[[ロック (情報工学)|ロック]]する必要がある。 == 例: 生産者/消費者問題 == {{仮リンク|生産者/消費者問題|en|Producer-consumer problem}}では、1つのプロセス(生産者)がデータを生成し、もう1つのプロセス(消費者)がそれらを受け取って使用する。データの受け渡しは最大サイズNのキューで行い、次のような条件に従う。 * キューが空の場合、消費者は生産者がデータを生成するのを待たなければならない。 * キューが満杯の場合、生産者は消費者がデータを消費するのを待たなければならない。 生産者/消費者問題をセマフォで解決する場合、キューの状態を2つのセマフォで表す。<code>emptyCount</code> はキュー上の空いているスロット数を保持し、<code>fullCount</code> はキュー上の要素数を保持する。完全性を維持するには、<code>emptyCount</code> を実際の空きスロット数より小さくなるようにし、<code>fullCount</code> を実際のキュー上の要素数より小さくなるようにする(どちらも実際の数を越えてはならない)。空きスロットと要素は、空の箱と満たされた箱という2種類の資源を表しており、セマフォ <code>emptyCount</code> と <code>fullCount</code> はそれら資源についての制御を管理する。 バイナリセマフォ <code>useQueue</code> は、例えば2つの生産者が同時にデータをキューに格納しようとするなどといった不正な状態が発生しないことを保証するためにある。このバイナリセマフォは[[ミューテックス]]で代替することもできる。 <code>emptyCount</code> の初期値は N、<code>fullCount</code> の初期値は0、<code>useQueue</code> の初期値は1である。生産者は次のような処理を繰り返す。 '''produce:''' P(emptyCount) P(useQueue) putItemIntoQueue(item) V(useQueue) V(fullCount) 消費者は次のような処理を繰り返す。 '''consume:''' P(fullCount) P(useQueue) item ← getItemFromQueue() V(useQueue) V(emptyCount) 具体的には次のような動作をする。 # 1つの消費者が[[クリティカルセクション]]に入る。<code>fullCount</code> は0なので、消費者はブロックする。 # いくつかの生産者が生産者側のクリティカルセクションに入る。<code>emptyCount</code> で制限されるのでN以上の生産者はクリティカルセクションに入れない。 # 生産者は <code>useQueue</code> により一度に1つずつキューにアクセスし、データをキューに入れていく。 # 最初の生産者がクリティカルセクションを抜けるとき、<code>fullCount</code> がインクリメントされるので、ブロックしていた消費者がクリティカルセクション内の処理に進むことができる。 <code>emptyCount</code> はキュー上の実際の空きスロット数より小さくなる可能性がある。例えば、複数の生産者がデクリメントを行っても、<code>useQueue</code> によってキューへのデータ投入は逐次化されるためである。したがって常に <code>emptyCount + fullCount ≤ N </code> であり、等号が成り立つのは生産者も消費者も全くクリティカルセクションに入っていない場合だけである。 == 関数名の語源 == 元もとの名前である'''P'''と'''V'''は、[[オランダ語]]の単語の頭文字に由来している。'''V'''は ''verhogen''(増加する)を意味する。'''P'''については、''proberen''(テストする)<ref>{{Harvnb|Silberschatz|Galvin|Gagne|2008|p=234}}</ref>、''passeer''(通過)、''probeer''(試みる)、''pakken''(つかむ)などいくつかの説明がある。セマフォの本来の意味である[[腕木通信]]から、'''V'''を ''verhoog''(腕木を上げる、通行禁止)、'''P'''を ''passeren''(腕木を下げる、通行許可)とする説もある。ただしダイクストラ自身は'''P'''を ''probeer te verlagen''(減らすことを試みる)を略した[[かばん語]] ''prolaag'' の頭文字だとしている<ref>[[エドガー・ダイクストラ|Dijkstra, Edsger W.]] ''Over Seinpalen (EWD-74)''. E.W. Dijkstra Archive. Center for American History, [[テキサス大学オースティン校|University of Texas at Austin]]. ([http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD74.PDF original]; [http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD74.html transcription])</ref><ref>[[エドガー・ダイクストラ|Dijkstra, Edsger W.]] ''MULTIPROGAMMERING EN DE X8 (EWD-51)''. E.W. Dijkstra Archive. Center for American History, [[テキサス大学オースティン校|University of Texas at Austin]]. ([http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD51.PDF original]; [http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD51.html transcription]) ([[オランダ語]])</ref><ref name="try-and">ダイクストラ自身は英語訳に際して "try-''and''-decrease" としているが、[http://www.wsu.edu/~brians/errors/try.html 口語体の "try-and..."] と紛らわしい。</ref><ref>[http://lkml.org/lkml/2005/12/19/34 (PATCH 1/19) MUTEX: Introduce simple mutex implementation] Linux Kernel Mailing List, 19 December 2005</ref>。この混乱のもとは、オランダ語で ''increase'' と ''decrease'' に相当する語がどちらも ''V'' で始まるためで、かといってオランダ語の単語をそのまま使ってもオランダ語を知らない人はかえって混乱するとダイクストラが考えたためである。 [[ALGOL|ALGOL 68]] や[[Linuxカーネル]]<ref>[http://www.linuxgrill.com/anonymous/fire/netfilter/kernel-hacking-HOWTO-5.html#ss5.3 Linus Kernel hacking HOWTO] LinuxGrill.com</ref>、いくつかの英語の教科書では、'''P'''と'''V'''はそれぞれ ''down'' と ''up'' とされている。[[ソフトウェア工学]]では一般に '''wait''' と '''signal'''、'''acquire''' と '''release'''([[Java]]のライブラリで使用<ref>{{Javadoc:SE|package=java.util.concurrent|java/util/concurrent|Semaphore}}</ref>)、'''pend''' と '''post''' などと呼ばれることが多い。教科書によっては元もとのオランダ語の頭文字に一致するよう '''procure''' と '''vacate''' としているものもある。 == セマフォとミューテックス == [[ミューテックス]]は基本的にバイナリセマフォと等価であり、時には基本実装が同一ということもある。ただし、ミューテックスは2つのプロセスが同時に共用資源にアクセスするのを防止する構成物を表し、バイナリセマフォは単一の資源へのアクセスを制限する構成物を表す。 多くの場合、ミューテックスには「所有者」の概念がある。すなわちミューテックスをロックしたプロセスだけがそれをアンロックすることができる。対照的にセマフォにはそのような制限がなく、上述の生産者/消費者問題の例でもそれを利用している。 したがって基本的には、ミューテックスはプロセスなどの実行実体と結びついており、セマフォは資源と結びついている。 == 環境毎の使用方法 == ; Windows : [[Microsoft Windows|Windows]]の[[Windows API|Win32 API]]では、<code>CreateSemaphore</code> 関数と <code>ReleaseSemaphore</code> 関数を使う。 ; .NET Framework : [[.NET Framework]] 2.0以降では、<code>System.Threading.Semaphore</code> クラスを使う。バージョン1.1以前では自作するかWin32 APIを呼び出す必要がある。 ; Java : [[Java]]では、<code>java.util.concurrent.Semaphore</code> クラスを使う。Java 5 以降で使用可能である。 ; Perl : [[Perl]]では、<code>Thread::Semaphore</code> モジュールや、新しくは<code>Coro::Semaphore</code> モジュールなどを使う。 ; Python : [[Python]]では、<code>threading</code>モジュール中に <code>Semaphore</code>クラスが用意されている。 == 脚注 == {{Reflist|2}} == 参考文献 == * {{Citation| last = Silberschatz | first = Abraham | last2 = Galvin | first2 = Peter Baer | last3 = Gagne | first3 = Greg | title = Operating System Concepts | publisher = John Wiley & Sons. Inc | year = 2008 | edition = 8th | isbn = 978-0-470-12872-5 | ref=harv}} == 関連項目 == * [[排他制御]] * [[マルチスレッド]] * [[スレッド (コンピュータ)|スレッド]] * [[クリティカルセクション]] * [[ミューテックス]] * [[食事する哲学者の問題]] * [[居眠り床屋問題]] * [[モニタ (同期)]] == 外部リンク == * [[エドガー・ダイクストラ|Dijkstra, Edsger W.]] ''Over Seinpalen (EWD-74)''. E.W. Dijkstra Archive. Center for American History, [[テキサス大学オースティン校|University of Texas at Austin]]. ([http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD74.PDF original]; [http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD74.html transcription]), 最初のセマフォに関する文書(オランダ語) * [http://www.opengroup.org/onlinepubs/009695399/basedefs/semaphore.h.html semaphore.h] programming interface - The Open Group Base Specifications Issue 6, IEEE Std 1003.1 * [http://greenteapress.com/semaphores/ ''The Little Book of Semaphores''] Allen B. Downey * [http://www.enseignement.polytechnique.fr/informatique/INF431/X09-2010-2011/AmphiTHC/SynchronizationPrimitives.pdf ''A pragmatic, historically oriented survey on the universality of synchronization primitives''], Jouni Leppäjärvi {{DEFAULTSORT:せまふお}} [[Category:排他制御]]
このページで使用されているテンプレート:
テンプレート:Citation
(
ソースを閲覧
)
テンプレート:Harvnb
(
ソースを閲覧
)
テンプレート:Javadoc:SE
(
ソースを閲覧
)
テンプレート:Lang
(
ソースを閲覧
)
テンプレート:Lang-en-short
(
ソースを閲覧
)
テンプレート:Reflist
(
ソースを閲覧
)
テンプレート:仮リンク
(
ソースを閲覧
)
セマフォ
に戻る。
検索
検索
セマフォのソースを表示
話題を追加