基本情報のセマフォを解説！P操作・V操作と待機の例題

基本情報のセマフォは、複数の処理が共有する資源を安全に使うための仕組みです。P操作で利用の許可を求め、使い終わったらV操作で返します。空きがなければ、その処理は待機します。

初期値1の例では、先に入った処理が資源を使っている間、後から来た処理は待ちます。試験問題では、セマフォの値だけでなく、誰が資源を持ち、誰が待っているかを一行ずつ追うと判断できます。この記事では、値と処理の状態を分けて記録する方法を例題で説明します。

この記事のポイント

共有データの更新が競合する理由
P操作で取得しV操作で解放する流れ
待機と再開を含むセマフォ値の追い方
複数資源を扱う際のデッドロックの見分け方

無料

基本情報技術者試験過去問アプリ

本番形式で繰り返し解ける。スキマ時間に1問から

2,000問以上収録

無料で過去問を解く

基本情報のセマフォの仕組みと操作

共有資源を順番に使う理由

複数の処理が同じデータや装置を利用する場合、それぞれの処理はいつでも連続して最後まで進むとは限りません。実行の途中で別の処理に切り替わると、古い値を使った更新が後から上書きされることがあります。こうした不整合を避けるため、同時に触れてはいけない処理の範囲を決め、その範囲に一度に入れる処理を制限します。この範囲をクリティカルセクション、または危険区間と呼びます。

例えば共有カウンタが100のとき、処理Aと処理Bがそれぞれ1を加算するとします。Aが100を読み、書き戻す前にBも100を読み取ると、両方とも101を書き戻してしまう順序が生じます。実際には2回の加算を行ったのに最終値は101です。この「更新の消失」は、読み取り、計算、書き込みという一連の作業を、互いに割り込ませたことによって生じます。

この例では、カウンタの読み取りから書き戻しまでを同じ保護対象に含める必要があります。書き込みの瞬間だけを保護しても、両者が先に同じ古い値を読み取れば、結果は正しくなりません。セマフォは、このような区間へ入る前後に操作を置き、共有資源の利用順を調整する方法の一つです。

値とP操作・V操作の関係

ここでは、セマフォの値を「今すぐ取得できる許可の数」として扱います。初期値が1なら許可は1個です。処理AがP操作を行って取得すると値は1から0になります。このとき別の処理BがP操作を要求しても、空きがないためBは待ちます。Aが使い終えてV操作を行うと、待っている処理が利用できるようになります。

P操作は資源を使う前の取得要求、V操作は使い終えた後の解放に対応します。Pを実行したから必ず即座に先へ進めるわけではありません。取得に成功した場合にだけ危険区間へ入り、取得できない場合は待つことがポイントです。V操作も、待機中の処理を起こす動作を伴う場合があり、「値を足すだけ」と単純化すると待ち状態の読み違いにつながります。

試験ではセマフォの表現方法が問題文で定義されることがあります。この記事の表は、値を0以上の利用可能数として扱い、待っている処理があれば解放された許可をその処理に引き渡す前提です。待ち人数を負の値で表現する方式もあります。どちらを採るかで表中の数値は変わるので、出題されたP操作・V操作の定義を最優先してください。

操作を分割できない理由

「値が1以上なら1を引く」という操作は、確認と更新を別々の無保護な処理として行ってよいわけではありません。値が1のときAが空きを確認し、その直後にBも同じ1を確認できると、両方が許可を取ったつもりになり、保護対象へ同時に入れてしまいます。これでは排他制御のために作った仕組み自体が競合します。

そのため、セマフォのP操作とV操作は、それぞれ他の操作に途中を割り込まれない原子的な操作として提供されます。問題を解くときは、Pの「確認」と「取得」の間に、別のPが入るような順序を勝手に作らないでください。原子性は操作そのものの性質であって、PからVまでの処理全体がCPUを独占するという意味ではありません。

実際のAPIには待機を伴う操作のほか、取得できなければすぐ戻る操作などもあります。試験問題で求められるのは、特定の製品の関数名を覚えることよりも、指定された操作が成功・待機のどちらになるかです。仕組みの詳細はOracleのセマフォの説明でも確認できます。

二値と計数の使い分け

初期値1の二値セマフォは、1つの共有資源を同時に1処理だけが利用する場面の理解に向いています。一方、同種の資源が複数ある場合は、使用可能な数を初期値にする計数セマフォを考えられます。例えば接続枠が3つあるとき、初期値を3とし、取得のたびに1減らして、返却時に1戻すという考え方です。

ここで数えているのは「残っている許可」であり、処理の総数ではありません。3つの枠のうち2つが取得済みで待ちがなければ値は1です。3処理が取得済みなら値は0となり、4番目の取得要求は待ちます。初期値3のセマフォが直接保証するのは最大3処理の同時利用であり、共有データの更新を1処理だけに制限することではありません。1つのデータの更新を排他的に守る場合は、その目的に合う別の保護を考えます。

二値セマフォとミューテックスは、どちらも一度に1つの処理を通す用途で使われますが、同じ名称として扱うと所有者や解放の規則を誤解します。ミューテックスには取得した処理が解放する所有権のルールを持つ実装が一般的です。試験では両者をひとまとめにせず、問題文に示された機能や制約に従って判断してください。

基本情報のセマフォを例題で追う方法

値と各処理の状態を表にする

次の例では、共有資源が1つ、セマフォSの初期値が1です。AとBはどちらも同じSを使います。AがPを行い、その後BがPを行い、続いてAがVを行う順で考えます。待ちがある場合は、Vによって解放された許可が待機中のBに渡るものとします。

開始時：Sは1。AもBも資源を持っていない
AがPを実行：Aが許可を取得し、Sは0になる
BがPを実行：空きがないためBは待機し、Sは0のまま
AがVを実行：Aは資源を返し、待機中のBに許可が引き渡される
Bが利用を終えてVを実行：待機者がいなければSは1に戻る

4行目で「Vなら必ず値が1になり、その状態が続く」と決めつけないでください。この例ではBが待っているため、解放された許可はBへ引き渡されます。Bが取得した後を記録すればSは0です。実装によっては解放と再取得を細かい別の状態として記録するので、途中の数値まで問われた場合は問題が示す規則を使います。

手書きで解く場合は、操作の列に加えて「Sの値」「Aの状態」「Bの状態」を横に並べます。状態には未取得、使用中、待機、終了などを記入します。値が同じ0でも、Aが持っているのかBが持っているのかは異なります。所有者を書き忘れると、次にVできる処理を間違えやすくなります。

更新結果を順序別に計算する

次に、共有値が10で、Aは3を加算し、Bは2を乗算する例を考えます。両者が読み取りから書き戻しまでを同じ二値セマフォで保護するなら、Aが先の場合は10＋3＝13、その後Bが13×2＝26です。Bが先の場合は10×2＝20、その後Aが20＋3＝23になります。保護されていても実行順が決まっていなければ、結果が常に一つとは限りません。

ここで得られるのは23または26です。どちらも各処理が直前の最新値を読み、最後まで更新した結果です。「セマフォで保護したから順番に関係なく同じ値になる」と考えるのは誤りです。実行順で結果が変わる計算であれば、順番を指定する追加の条件がなければ、順序ごとに計算します。

一方、保護がなければ、両者が10を先に読み、Aが13を書き、Bが古い10を使って20を書き戻す、といった順序も考えられます。この場合の最終値は20です。問題によっては各処理の中の手順や一時変数の扱いが異なるため、可能な結果を列挙する前に、各処理の命令順序が守られているかを確認します。

複数の資源と待ちを見分ける

共有資源が二つ以上ある場合、資源ごとに別のセマフォを置いても、使う順序によってはデッドロックが起こり得ます。資源XとYがそれぞれ1つあり、両方を使う処理AとBを考えます。AがXを取得してからYを要求し、BがYを取得してからXを要求する場合です。

Aが先にX、Bが先にYを取得した後、AはBの持つYを待ち、BはAの持つXを待ちます。双方とも、相手が解放するまで自分の処理を進められないなら、互いに待ち続けます。セマフォの値が0であることだけではデッドロックとは限りません。誰が何を保持し、何を待ち、その保持者が先へ進めるかを確認します。

対策の考え方の一つは、複数資源を取得するときの順序をそろえることです。AもBも必ずXを取ってからYを取るなら、片方がXを保持している間、もう片方はXで待つため、この二つの資源について取得順の逆転による循環待ちは避けられます。ただし、プログラム全体に別の資源や待ち条件があれば、順序を一部そろえただけで全デッドロックがなくなるとは言えません。

データベースの共有ロックと占有ロック、トランザクションの性質も一緒に整理したい場合は、基本情報のトランザクション処理とデッドロックを参照してください。こちらの記事はデータベース操作の保護が中心で、セマフォの操作列を追う本記事とは確認する対象が異なります。

問題文で確認する条件

計算に入る前に、まず初期値が許可の数なのか、資源の状態を表す二値なのかを確認します。次に、値が0のときのP操作が待機なのか、値を負にして待ち人数を表すのかを読みます。さらに、V操作が待機者を起こすときの値の扱い、待機者の選択順、途中で別の処理に切り替わる位置を確認します。これらが省略されている場合に、特定の実装方式を勝手に補って数値を断定しないことが大切です。

続いて、PとVで挟まれた区間がどこかを追います。共有値の読み取りがPより前にあるなら、計算に必要な値が古いまま残り、書き込みだけを保護しても更新消失を防げない場合があります。逆に、関係のない長い処理まで危険区間に入れると、正しさを保ててもほかの処理の待ちが増えます。問題文が正確性を問うのか、待機時間や並行性も問うのかを見分けましょう。

基本情報の過去問では、旧形式で共有データの更新とP操作・V操作の読み取りを扱った例があります。IPAの平成29年度秋期午後問題は当時の形式の問題です。現在の試験形式そのものを示す資料ではない点を踏まえ、共有データの更新順と排他制御の考え方を練習する素材として利用してください。

計数セマフォの演習

ここで、利用可能な接続枠が2つある場合の追跡にも取り組みましょう。Sの初期値を2とし、A、B、Cがこの順でPを要求します。各処理は取得した枠を一つ使い、利用後にVで返します。空きがないときは待ち、返された枠は待機者に引き渡す前提です。AとBが先に取得した時点でSは0です。CがPを要求するとCは待ち、Sは0のままです。

続いてBが枠を返すと、Cが待っていたため、その枠はCへ渡ります。AとCが枠を使っているので、利用可能数Sは引き続き0です。その後Aが返し、ほかに待機者がいなければSは1になります。最後にCも返すとSは2に戻ります。最初の資源数が2だからといって、待機がある途中で直ちに値を2へ戻すのではなく、各処理が返却するたびに状態を更新します。

この演習では、Bが返した直後に利用するのはCですが、Cが実際にいつCPU上で実行されるかはスケジューリングにも依存します。「待機が解除された」と「その瞬間に処理を完了した」は別です。問題で順序が指定されていないとき、複数の待機者のうち誰が先に進むかをFIFOだと決めつけないようにしましょう。資源数の追跡と、CPU実行の順序の追跡は関連しますが、同じ表の同じ列ではありません。

許可を取得した処理が返却を忘れると、その枠はほかの処理が利用できない状態のままになることがあります。例外処理や途中終了があるプログラムでは、どの経路で解放するかまで設計する必要があります。ただし、試験で途中終了の動作が書かれていなければ、自動的に返却されるとも、必ず永久に失われるとも補わず、設問で与えられた条件に従ってください。

確認問題として、初期値2のSにAとBが続けてPを行い、両者が取得した後にAがVを行った場面を考えます。待機者がいなければ、Aの返却後のSは1で、Bはまだ資源を保持しています。Sが1になったからといって、Bも返却したことにはなりません。次にCがPを成功させればSは0となり、BとCがそれぞれ一つの枠を使用している状態です。各時点で「利用中の枠」と「残りの枠」を合計し、初期値と照合すると、返却や取得の記録漏れに気付きやすくなります。この確認は、許可の重複発行や余分なV操作がないという例題の前提の下で使います。

通知としての使い方に注意

セマフォは共有資源への入場制限だけでなく、ある処理の完了を別の処理に知らせる同期にも使えます。例えば初期値0のセマフォに対し、処理Bが先にPを要求すれば、まだ許可がないので待機します。処理Aが準備を終えてVを実行すると、Bが進めるようになるという考え方です。ここではVが知らせる役、Pが待つ役を持ちます。

この通知の例では、B自身が過去にPで資源を取得してからVする形ではありません。したがって「PとVは必ず同じ処理が交互に実行する」と暗記すると、同期用途を正しく判断できません。資源の貸出数を管理する例と、処理間で完了を通知する例では目的が違います。どちらの用法かを問題文から確認し、同じ単語を見ただけで操作の意味を固定しないことが重要です。

一方で、通知だけを受けたことと、共有データへのアクセスが安全に保護されることも同じではありません。どのデータが、どの操作の前に完成し、どの処理が更新するのかを確認し、必要な排他制御が別途設定されているかを読み取ります。セマフォが登場したという理由だけで、すべての競合や順序の問題が解決すると考えないようにしましょう。

練習するときは、まず各操作の前後における値と待機状態を記録し、次に危険区間に同時に入れる処理数を確認してください。値の計算が正しくても共有データに触れる範囲が保護されていなければ、期待した結果にならない場合があります。