基本情報技術者 2012年 秋期 午後 問01
プロセスの排他制御に関する次の記述を読んで、設問1〜3に答えよ。
複数のプロセスが、共有するデータ（以下、共有データという）を書き換える処理を、並行して実行する場合がある。このようにプロセス間でデータを共有する方法の一つとして、プロセス間で共有するメモリ（以下、共有メモリという）に共有データを格納する方法がある。ここでは、CPUが一つで共有メモリをもつコンピュータX上で、二つのプロセスp1, p2が共有メモリを使用して並行に処理を実行する場合を考える。
プロセスp1, p2が共有データyに対して計算処理をする場合を、図1に示す。ここで、各プロセスの計算処理は、次のとおりである。
〔計算処理〕
① 共有データyの値を読み込む。
② 読み込んだ値を用いて計算する。
③ 計算結果をyに書き込む。
設問1：
問題文を見る 図1に示すプロセスp1, p2が共有データyに対して次の処理を実行する場合を考える。
プロセスp1：yの値を2だけ増加させる。
プロセスp2：yの値を1だけ減少させる。
プロセスの実行前の共有データyの値が5であり、yに対する排他制御をしないとき、プロセスp1, p2が並行に1回だけ処理を実行した直後において、yが取り得ない値を、解答群の中から選べ。
解答群
ア：4
イ：5
ウ：6
エ：7
模範解答
イ
解説
解答の導き方
この問題では、処理後の共有データ がどの値になり得るかを考えます。選択肢のうち「取り得ない値」を見つけるには、まず各プロセスがどんな順番で読み込みや書込みをするかを確認します。
-
各プロセスの処理は、読み込み・計算・書込みの3段階です。問題文には、計算処理として「共有データyの値を読み込む」「読み込んだ値を用いて計算する」「計算結果をyに書き込む」とあります。つまり、読み込んだ時点の値をもとに計算し、その結果を後から書き込みます。プロセスp1は、読み込んだ値に を足します。プロセスp2は、読み込んだ値から を引きます。
-
一方のプロセスが先に最後まで処理すれば、最終的に になります。p1が先に処理する場合は、 は から になり、その後p2が を読み込んで を書き込みます。p2が先に処理する場合は、 は から になり、その後p1が を読み込んで を書き込みます。したがって、順番に処理した場合の最終値は、どちらの順でも です。
-
排他制御をしないと、2つのプロセスが同じ値を読み込むことがあります。排他制御とは、複数のプロセスが同時に共有データを書き換えないように、処理する順番を制御することです。この問題では排他制御をしないため、p1とp2がどちらも、書込み前の を読み込む場合があります。その場合、p1は を計算し、p2は を計算します。その後、どちらが最後に書き込むかで最終値が変わります。
-
最終値が になる場合はありません。ここまでで、最終値として考えられるのは 、、 です。選択肢のうち、この中に含まれないのは です。したがって、 は取り得ない値です。
誤りやすいポイント
-
処理の順番を考えずに、 だけで判断すること
この計算で分かるのは、2つの処理が順番に反映される場合の値です。排他制御がないと、両方が同じ古い値を読み込み、後の書込みで先の結果を上書きすることがあります。 -
CPUが一つなら、処理が必ず一つずつ最後まで実行されると思うこと
CPUが一つでも、読み込み・計算・書込みの途中で別のプロセスに切り替わることがあります。処理全体が一まとまりで実行されるとは限りません。 -
読み込んだ値と書き込む値を混同すること
各プロセスは、共有データの現在の値を読み込んでから計算します。後から別のプロセスが書き込んでも、先に読み込んだプロセスの計算結果は自動では変わりません。
FAQ
Q: 2つのプロセスが同じ を読み込むと、なぜ が残らないのですか？
A: どちらのプロセスも、計算結果を共有データに書き込むためです。p1は 、p2は を書き込みます。最後に書き込まれる値はそのどちらかなので、 は残りません。
A: どちらのプロセスも、計算結果を共有データに書き込むためです。p1は 、p2は を書き込みます。最後に書き込まれる値はそのどちらかなので、 は残りません。
Q: 排他制御をすると、どうして結果が安定するのですか？
A: 一度に一つのプロセスだけが共有データを読み込んでから書き込むようにできるためです。もう一方は、その処理が終わって更新された値を読み込めます。
A: 一度に一つのプロセスだけが共有データを読み込んでから書き込むようにできるためです。もう一方は、その処理が終わって更新された値を読み込めます。
Q: 2つの処理を順番に実行すると、順番によって答えは変わりますか？
A: この問題では変わりません。p1の後にp2を実行しても、p2の後にp1を実行しても、最終値は です。
A: この問題では変わりません。p1の後にp2を実行しても、p2の後にp1を実行しても、最終値は です。
関連キーワード: 共有メモリ、共有データ、排他制御、並行処理、競合状態
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
プロセスの排他制御の仕組みとして、共有データがいずれかのプロセスに確保されている状態（以下、確保状態という）又はどのプロセスにも確保されていない状態（以下、解放状態という）のいずれかの状態をもつ同期変数を使用する方法を考える。図1のプロセスp1, p2の計算処理で使用する共有データyに対して同期変数sを用いて排他制御する場合を、図2に示す。
図2において、同期変数の状態を変更する関数ℓとuがあり、同期変数を引数で指定する。各プロセスは、共有データを排他制御して計算処理をする場合、関数ℓの呼出し、計算処理、関数uの呼出しの順番で処理を実行する。このとき、共有データyを排他制御するために、関数ℓとuの引数として同期変数sを指定する。
関数ℓの操作内容はa処理であり、関数uの操作内容はb処理である。ここで、“同期変数の状態を調べて、変更する処理”は中断のない処理として実行されるものとする。ただし、プロセスが待ちの状態になったら、CPUは別のプロセスに割り付けられるものとする。
解答群
ア：sの状態が解放状態ならば確保状態にし、確保状態ならば解放状態になるまで待ってから確保状態にする
イ：sの状態が解放状態ならば確保状態にし、確保状態ならば何もしない
ウ：sの状態が解放状態ならば確保状態になるまで待ち、確保状態ならば解放状態になるまで待つ
エ：sの状態が解放状態ならば確保状態になるまで待ち、確保状態ならば何もしない
オ：sの状態が確保状態ならば解放状態にし、解放状態ならば何もしない
カ：sの状態が確保状態ならば解放状態になるまで待ち、解放状態ならば何もしない
模範解答
a：ア、b：オ
解説
解答の導き方
この問題では、共有データ を使う計算処理が、プロセスp1とプロセスp2で同時に進まないようにする方法を考えます。
共有データを読み込み、計算し、書き込む処理の途中で別のプロセスも同じデータを書き換えると、計算結果が上書きされることがあります。そのため、計算処理の前に「使ってよい状態か」を確認し、使い終わった後に「使い終わった」と知らせます。
-
関数ℓは、共有データを使い始めるときの処理です。
同期変数 は、共有データを使える「解放状態」と、どれかのプロセスが使っている「確保状態」のどちらかを示します。関数ℓを呼び出したとき、 が解放状態なら、確保状態に変更してから計算処理に進みます。すでに確保状態なら、別のプロセスが計算処理をしています。そのプロセスが使い終わり、 が解放状態になるまで待ちます。そして、解放状態になったら確保状態に変更してから計算処理を始めます。この動きに当てはまるのは ア です。 -
関数uは、共有データを使い終わったときの処理です。
計算処理が終わったら、 が確保状態であることを確認し、解放状態に戻します。すでに解放状態なら、変更する必要はありません。この動きに当てはまるのは オ です。 -
状態を調べて変更する処理が中断されないことも重要です。
問題文では、この処理は「中断のない処理」とされています。つまり、解放状態かどうかの確認と、確保状態への変更の間に、別のプロセスが割り込むことはありません。これにより、p1とp2が同時に「解放状態だ」と判断して、二つとも計算処理を始める事態を防げます。
このように、関数ℓで使う権利を確保し、関数uで解放することで、共有データ を一度に一つのプロセスだけが使えます。
誤りやすいポイント
- 関数ℓと関数uの役割を逆にしないようにします。関数ℓは計算処理の前に確保する処理、関数uは計算処理の後に解放する処理です。
- が確保状態のとき、関数ℓはそのまま計算処理に進むのではなく、解放状態になるまで待つ必要があります。待たずに進むと、複数のプロセスが同じ共有データを同時に使うおそれがあります。
- 関数uは、 が解放状態のときに確保状態へ変更する処理ではありません。使い終わったことを示すため、確保状態を解放状態に戻します。
- CPUが一つでも、プロセスの処理は交互に進むことがあります。そのため、CPUが一つであるだけでは、共有データへの同時アクセスを防げません。
FAQ
Q: 関数ℓで待っている間、CPUはどうなりますか？
A: 問題文では、プロセスが待ち状態になると、CPUは別のプロセスに割り付けられるとされています。待っているプロセスがCPUを使い続けるわけではありません。
A: 問題文では、プロセスが待ち状態になると、CPUは別のプロセスに割り付けられるとされています。待っているプロセスがCPUを使い続けるわけではありません。
Q: なぜ「状態を調べて、変更する処理」を中断できないようにするのですか？
A: 確認と変更の間に別のプロセスが動くと、両方のプロセスが「解放状態だ」と判断する可能性があります。確認から変更までを一続きにすることで、その重複を防ぎます。
A: 確認と変更の間に別のプロセスが動くと、両方のプロセスが「解放状態だ」と判断する可能性があります。確認から変更までを一続きにすることで、その重複を防ぎます。
Q: 計算処理が終わった後に、関数uを呼び出すのはなぜですか？
A: 関数uを呼び出して を解放状態に戻さないと、別のプロセスが待ち続けることになります。解放することで、次のプロセスが共有データを使えるようになります。
A: 関数uを呼び出して を解放状態に戻さないと、別のプロセスが待ち続けることになります。解放することで、次のプロセスが共有データを使えるようになります。
関連キーワード: 排他制御、共有メモリ、同期変数、クリティカルセクション、不可分操作
設問3：
問題文を見る プロセスp1, p2が使用する共有データが二つあり、共有データy1に対して同期変数s1を用いて排他制御し、共有データy2に対して同期変数s2を用いて排他制御する場合を考える。
プロセスp1が、y1の確保、y2の確保、y2の解放、y1の解放の順序で同期変数を操作するとき、プロセスp2がy1, y2の確保と解放を行う順序によってはデッドロックが発生する可能性がある。デッドロックが発生する可能性のあるプロセスp2の操作の順序を、解答群の中から選べ。
解答群
ア：y1の確保、y1の解放、y2の確保、y2の解放
イ：y1の確保、y2の確保、y2の解放、y1の解放
ウ：y2の確保、y1の確保、y1の解放、y2の解放
エ：y2の確保、y2の解放、y1の確保、y1の解放
模範解答
ウ
解説
解答の導き方
この問題では、プロセスp1とプロセスp2が共有データを使うとき、どの順序で利用権を確保し、解放するかを考えます。
排他制御とは、同じ共有データを複数のプロセスが同時に使わないようにする制御です。問題では、共有データy1を使うために同期変数s1を、共有データy2を使うために同期変数s2を使います。あるプロセスが共有データの利用権を確保している間、もう一方のプロセスは、その利用権が解放されるまで待ちます。
本文によると、プロセスp1は「y1の確保、y2の確保、y2の解放、y1の解放」の順に操作します。つまり、p1はy1を確保したままy2の確保を試みます。y2を別のプロセスが確保していれば、p1はそこで待つことになります。
デッドロックは、複数のプロセスが互いの確保した利用権を待ち続け、どちらも先へ進めなくなる状態です。p1がy1を確保したままy2を待つ状況を作るには、p2がy2を確保したままy1を待つ順序になっている必要があります。
選択肢ウでは、p2は「y2の確保」の後に「y1の確保」を試みます。次のような実行順序が可能です。
- p1がy1を確保します。
- p2がy2を確保します。
- p1がy2を確保しようとしますが、p2が確保しているため待ちます。
- p2がy1を確保しようとしますが、p1が確保しているため待ちます。
p1はy2を確保できないので、y2を解放する段階に進めません。p2もy1を確保できないので、y1を解放する段階に進めません。このように互いに相手の解放を待ち続けるため、選択肢ウの順序でデッドロックが発生する可能性があります。
ほかの選択肢では、p2は、もう一方の共有データの利用権を待つ前に、すでに確保している利用権を解放するか、p1と同じ順で確保します。そのため、p1とp2が互いの利用権を保持したまま待つ状態にはなりません。
誤りやすいポイント
- 確保の順序だけでなく、解放のタイミングも確認します。利用権を確保したまま別の利用権を待つかどうかが、デッドロックの判断に関わります。
- 「別々の共有データを使う」ことだけでは、デッドロックになるとは限りません。p1がy1を、p2がy2を確保したまま、互いに相手が確保している共有データを待つ状況が必要です。
- 「CPUが一つ」でも、デッドロックは起こり得ます。プロセスは交互に実行されることがあり、待っている間も、確保した利用権を保持しているためです。
FAQ
Q: なぜ、利用権を確保した順序が重要なのですか？
A: 互いに異なる利用権を一つずつ確保し、そのまま相手の利用権を待つ状況ができるからです。この問題では、p1がy1を持ってy2を待ち、p2がy2を持ってy1を待つと、どちらも解放まで進めません。
A: 互いに異なる利用権を一つずつ確保し、そのまま相手の利用権を待つ状況ができるからです。この問題では、p1がy1を持ってy2を待ち、p2がy2を持ってy1を待つと、どちらも解放まで進めません。
Q: デッドロックは必ず発生しますか？
A: 必ずではありません。問題では「発生する可能性」が問われています。p1とp2がそれぞれy1とy2を確保する順序で実行された場合に、デッドロックが起こります。
A: 必ずではありません。問題では「発生する可能性」が問われています。p1とp2がそれぞれy1とy2を確保する順序で実行された場合に、デッドロックが起こります。
Q: 利用権を解放すると、待っているプロセスはどうなりますか？
A: 解放された利用権を確保できれば、待っていたプロセスは処理を再開できます。デッドロックでは、互いに必要な利用権が解放されないため、処理を再開できません。
A: 解放された利用権を確保できれば、待っていたプロセスは処理を再開できます。デッドロックでは、互いに必要な利用権が解放されないため、処理を再開できません。
関連キーワード: 排他制御、同期変数、共有メモリ、デッドロック、資源獲得順序
