意味論と実装

ウィキペディア小見出し辞書

意味論と実装

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/15 04:56 UTC 版)

「セマフォ」の記事における「意味論と実装」の解説

セマフォ変数の重要な属性として、その値の変更には特定の関数群を使わなければならないという点が挙げられる。ここではそれらの関数を 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つのプログラムが別々のプロセッサ上で同時に動作している場合に対処できない。そのためテスト・アンド・セット命令などを使用してセマフォ変数へのアクセスをロックする必要がある。