基本情報技術者 2017年 秋期 午後 問02
プロセスの排他制御に関する次の記述を読んで、設問1～3に答えよ。
単一のCPUと、プロセス間で共有するデータ（以下、共有データという）を格納するためのメモリ（以下、共有メモリという）をもつコンピュータXにおいて、並行に実行される複数のプロセスが、共有データを更新する場合を考える。
二つのプロセスp1, p2が共有データyを更新する際には、図1に示す更新処理1、更新処理2を、それぞれ①～③の順番に行う。
↩設問1
↩設問1設問1：
問題文を見る 図1に示すプロセスp1の更新処理1とプロセスp2の更新処理2が、次のとおりに共有データyを更新する場合を考える。
【更新処理1】：共有データyの値を30増加させる。
【更新処理2】：共有データyの値を50減少させる。
二つのプロセスp1, p2の実行前の共有データyの値が100であり、共有データyに対して排他制御を行わずに、プロセスp1が更新処理1を、プロセスp2が更新処理2を並行して各1回だけ行った。結果として、共有データyが取り得ない値を、解答群の中から選べ。
解答群
ア：50
イ：80
ウ：100
エ：130
模範解答
ウ
解説
解答の導き方
プロセス（実行中のプログラム）p1は共有データyを30増やし、プロセスp2は50減らします。排他制御（複数のプロセスが共有データを同時に更新しないよう、順番に実行させる制御）をしない場合、二つのプロセスは処理の途中で交互に実行されることがあります。
問題文では、各プロセスが更新処理を「①～③の順番」に行うとあります。これは、各プロセスの中で①、②、③の順に進むという意味です。二つのプロセスの処理全体が、必ず一つずつ連続して実行されるわけではありません。CPU（Central Processing Unit：プログラムの命令を実行する装置）が一つでも、処理の途中で別のプロセスに切り替わることがあります。
まず、次のような順番で処理が進む場合を考えます。
p2が書き込んだ50は、その後p1が130を書き込むことで上書きされます。どちらのプロセスも更新処理を実行していますが、共有データyの最終的な値は130になります。
逆に、p2が50を書き込んだ後にp1が共有データyを読み取ると、p1はを計算します。p1がその80を書き込めば、最終的な値は80です。また、p1が130を書き込んだ後にp2が読み取って更新すれば、となり、最終的な値はやはり80です。
50も取り得ます。p2とp1がどちらも共有データyの値が100のときに読み取り、その後p1が130を書き込み、最後にp2が50を書き込めば、最終的な値は50です。p2の書込みが、p1の書込みを上書きするためです。
したがって、最後に書き込まれる値は50、80、130のいずれかです。100にするには、p1が70を読み取って30を加えるか、p2が150を読み取って50を減らす必要があります。しかし、この更新処理で共有データyに書き込まれる値は50、80、130のいずれかなので、70や150を読み取ることはありません。
このように、共有データを更新する順番の組合せによって結果が変わる問題を競合状態といいます。取り得ない値は100なので、選択肢ではウです。
誤りやすいポイント
- 「30増やす処理」と「50減らす処理」を単純に足し引きして、最終的な値は必ず80だと考えてしまうことがあります。二つの処理が同じ値を読み取った後に書き込むと、後の書込みが先の書込みを上書きすることがあります。
- ①の読込みから③の書出しまでを、分割できない一つの処理だと思い込まないようにします。二つのプロセスは、①～③の間で交互に実行される場合があります。
- CPUが一つなら処理が交互に進むことはない、とは限りません。CPUが一つでも、プロセスの切替えによって処理の途中で実行順が変わります。
FAQ
Q: 二つの処理を順番に行った場合、共有データyはいくつになりますか？
A: どちらを先にしても80です。p1を先にするとの後にとなり、p2を先にするとの後にとなります。
A: どちらを先にしても80です。p1を先にするとの後にとなり、p2を先にするとの後にとなります。
Q: 図2のセマフォ変数Sは、何のために使われますか？
A: セマフォは、複数のプロセスが共有データにアクセスする順番を調整する仕組みです。図2では、P操作とV操作を使って更新処理の実行を制御し、二つのプロセスが同時に更新処理を行わないようにします。
A: セマフォは、複数のプロセスが共有データにアクセスする順番を調整する仕組みです。図2では、P操作とV操作を使って更新処理の実行を制御し、二つのプロセスが同時に更新処理を行わないようにします。
関連キーワード: 共有データ、排他制御、競合状態、セマフォ
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
共有データに対して排他制御を行う仕組みとして、セマフォ変数を利用する方法を考える。セマフォ変数は、対応する共有データが、解放されている状態を示す1、又はいずれかのプロセスに確保されている状態を示す0の値をもつ。セマフォ変数の値は、P操作とV操作で変更する。共有データyに対応するセマフォ変数Sを利用したプロセスp3、p4が共有データyを更新する際の動作を、図2に示す。
図2において、共有データyに対して排他制御をした上で、更新処理を行うために、プロセスp3は、P操作、更新処理1、V操作の順に処理を行い、プロセスp4は、P操作、更新処理2、V操作の順に処理を行う。P操作は、a。V操作は、b。ここで、P操作とV操作は、それぞれ実行中の中断はないものとする。ただし、プロセスが待ち状態になれば、CPUは別のプロセスを実行させるものとする。
aに関する解答群
ア：セマフォ変数Sの値が0であれば1に変更し、終了する。1であれば0になるまで待った後、1に変更して終了する
イ：セマフォ変数Sの値が0であれば1に変更し、終了する。1であれば何もせずに終了する
ウ：セマフォ変数Sの値が1であれば0に変更し、終了する。0であれば1になるまで待った後、0に変更して終了する
エ：セマフォ変数Sの値が1であれば0に変更し、終了する。0であれば何もせずに終了する
bに関する解答群
ア：セマフォ変数Sの値が0であれば1になるまで待った後、終了する
イ：セマフォ変数Sの値が1であれば0になるまで待った後、終了する
ウ：セマフォ変数Sの値を0にして終了する
エ：セマフォ変数Sの値を1にして終了する
模範解答
a：ウ、b：エ
解説
解答の導き方
この設問では、共有データを同時に更新しないための「排他制御」と、そのために使う「セマフォ変数」の動作を考えます。排他制御とは、複数のプロセス（実行中のプログラム）が共有データを同時に使わないようにする仕組みです。セマフォ変数は、共有データを使えるかどうかを示す値です。
本文では、セマフォ変数の値は、共有データが解放されているときは「1」、いずれかのプロセスに確保されているときは「0」とされています。つまり、共有データを使い始めるときに「1」から「0」にし、使い終わったときに「1」に戻せば、ほかのプロセスが同時に使うのを防げます。
-
aはP操作の役割です。
更新処理を始める前に、共有データを確保します。セマフォ変数Sが「1」なら、共有データは空いているので、Sを「0」にして更新処理を始めます。すでにSが「0」なら、別のプロセスが使っているため、Sが「1」になるまで待ちます。その後、Sを「0」にして更新処理を始めます。
この動作に当てはまるのは ウ です。 -
bはV操作の役割です。
更新処理が終わったら、共有データを解放します。解放されたことを示すには、Sを「1」にします。したがって、当てはまるのは エ です。
たとえば、共有データが解放された状態から始めると、処理は次のようになります。
本文には、P操作とV操作は「実行中の中断はない」とあります。このため、Sの確認と変更が途中で別のプロセスに割り込まれることはありません。これにより、p3とp4が同時に共有データを使い始めるのを防げます。
誤りやすいポイント
- Sの値の意味を逆にしないようにします。「1」は使用中ではなく、共有データが解放されている状態です。「0」は、いずれかのプロセスが確保している状態です。
- P操作は、共有データを使い始める前に行います。空いていればSを「0」にし、使用中なら空くまで待ちます。
- V操作は、共有データを使い終わった後に行います。Sを「1」にして、共有データを解放します。
- Sが「0」のとき、P操作はそのまま終了するのではありません。別のプロセスが使用中なので、Sが「1」になるまで待ちます。
FAQ
Q: P操作でSを「0」にするのはなぜですか？
A: 「0」は、共有データが確保されている状態を示すからです。Sを「0」にしておけば、後から来たプロセスは使用中だと分かり、更新処理の開始を待てます。
A: 「0」は、共有データが確保されている状態を示すからです。Sを「0」にしておけば、後から来たプロセスは使用中だと分かり、更新処理の開始を待てます。
Q: p4が待ち状態になったら、CPUは何をしますか？
A: 本文では、プロセスが待ち状態になれば、CPUは別のプロセスを実行するとされています。そのため、p4が待っている間にp3が更新処理を進められます。
A: 本文では、プロセスが待ち状態になれば、CPUは別のプロセスを実行するとされています。そのため、p4が待っている間にp3が更新処理を進められます。
Q: P操作とV操作の実行中に中断されないことは、なぜ重要ですか？
A: Sの値を確認して変更する途中に別のプロセスが割り込むと、複数のプロセスが同時に「空いている」と判断する可能性があるためです。確認と変更を一まとまりで行うことで、共有データを確実に一つのプロセスだけが使えるようにします。
A: Sの値を確認して変更する途中に別のプロセスが割り込むと、複数のプロセスが同時に「空いている」と判断する可能性があるためです。確認と変更を一まとまりで行うことで、共有データを確実に一つのプロセスだけが使えるようにします。
関連キーワード: セマフォ、排他制御、P操作、V操作、共有メモリ
設問3：
問題文を見る プロセスp5、p6が更新する二つの共有データy1、y2があり、それぞれに異なるセマフォ変数を対応させて、個別に確保と解放ができるようにした場合を考える。共有データy1に対してセマフォ変数S1を、共有データy2に対してセマフォ変数S2を用いて排他制御を行う。プロセスp5が、次の順序で共有データy1、y2に対する確保と解放を行うとき、プロセスp6が、共有データy1、y2に対する確保と解放を行う順序によってはデッドロックが発生する可能性がある。デッドロックが発生する可能性がある、プロセスp6の共有データy1、y2に対する確保と解放の順序を、解答群の中から選べ。
［プロセスp5の共有データに対する確保と解放の順序］
y1の確保、y2の確保、y2の解放、y1の解放
解答群
ア：y1の確保、y1の解放、y2の確保、y2の解放
イ：y1の確保、y2の確保、y1の解放、y2の解放
ウ：y1の確保、y2の確保、y2の解放、y1の解放
エ：y2の確保、y1の確保、y1の解放、y2の解放
オ：y2の確保、y2の解放、y1の確保、y1の解放
模範解答
エ
解説
解答の導き方
この問題では、プロセスp5とプロセスp6が、共有データy1、y2を使うときの確保と解放の順番を考えます。排他制御（同じデータを複数のプロセスが同時に使わないようにする仕組み）では、共有データごとにセマフォ（共有資源を使う順番を調整する仕組み）を使います。
図2のP操作はセマフォの確保、V操作は解放に対応します。あるプロセスが確保済みのセマフォを別のプロセスが確保しようとすると、先に使っているプロセスが解放するまで待ちます。
まず、問題文にあるプロセスp5の順番を確認します。
- y1を確保する
- y2を確保する
- y2を解放する
- y1を解放する
プロセスp5は、y1を確保したままy2も確保します。つまり、処理の途中でy1とy2の両方を確保している状態になります。
デッドロック（複数のプロセスが互いに相手の確保した資源を待ち、処理を進められなくなる状態）が起こるには、次のような状況が必要です。
- p5がy1を確保し、y2を待つ
- p6がy2を確保し、y1を待つ
こうなると、p5はp6がy2を解放するのを待ち、p6はp5がy1を解放するのを待ちます。しかし、どちらも待ち状態なので、解放まで進めません。
選択肢を順番に確認します。
したがって、デッドロックが発生する可能性があるのは、p5とは逆にy2、y1の順で確保するエです。
誤りやすいポイント
- 「確保する順番」だけでなく、解放する前に次のデータを確保するかも確認します。アとオは、次のデータを確保する前に先のデータを解放しています。
- p5とp6が別々の共有データを確保しているだけでは、デッドロックとは限りません。互いに相手が確保したデータを待つ状態になることがポイントです。
- y1とy2の確保順序が同じか逆かを見落とさないようにします。確保順序が逆だと、デッドロックが起きる可能性があります。
FAQ
Q: デッドロックは、選択肢エなら必ず発生しますか？
A: 必ずではありません。p5がy1を確保し、p6がy2を確保するなど、処理が特定のタイミングで重なった場合に発生する可能性があります。
A: 必ずではありません。p5がy1を確保し、p6がy2を確保するなど、処理が特定のタイミングで重なった場合に発生する可能性があります。
Q: p5とp6の確保順序が同じなら、なぜデッドロックになりにくいのですか？
A: 両方がy1から確保するため、一方がy1を確保すると、もう一方はy1の確保を待ちます。待っている側はy2を先に確保していないので、互いに相手の確保したデータを待つ形になりません。
A: 両方がy1から確保するため、一方がy1を確保すると、もう一方はy1の確保を待ちます。待っている側はy2を先に確保していないので、互いに相手の確保したデータを待つ形になりません。
Q: 一度に一つのデータしか確保しない場合、なぜこの問題のデッドロックを避けられるのですか？
A: 相手が確保したデータを待つ状態になっても、自分が別のデータを確保したまま待つことがありません。そのため、互いに資源を持ち合って待ち続ける状況を作れません。
A: 相手が確保したデータを待つ状態になっても、自分が別のデータを確保したまま待つことがありません。そのため、互いに資源を持ち合って待ち続ける状況を作れません。
関連キーワード: 排他制御、セマフォ、デッドロック、相互排除、資源割当て
