平成24年秋期試験午後問題　問1

午前試験免除制度対応！基本情報技術者試験のeラーニング【独習ゼミ】

問1　ソフトウェア

プロセスの排他制御に関する次の記述を読んで，設問1～3に答えよ。

　複数のプロセスが，共有するデータ(以下，共有データという)を書き換える処理を，並行して実行する場合がある。このようにプロセス間でデータを共有する方法の一つとして，プロセス間で共有するメモリ(以下，共有メモリという)に共有データを格納する方法がある。ここでは，CPUが一つで共有メモリをもつコンピュータ X 上で，二つのプロセスp1，p2が 共有メモリを使用して並行に処理を実行する場合を考える。

　プロセスp1，p2が共有データ y に対して計算処理をする場合を，図1に示す。ここで，各プロセスの計算処理は，次のとおりである。

〔計算処理〕
  1. 共有データ y の値を読み込む。
  2. 読み込んだ値を用いて計算する。
  3. 計算結果を y に書き込む。
pm01_1.png
広告

設問1

図1に示すプロセスp1，p2が共有データ y に対して次の処理を 実行する場合を考える。
  • プロセスp1：yの値を2だけ増加させる。
  • プロセスp2：yの値を1だけ減少させる。
　プロセスの実行前の共有データ y の値が5であり，y に対する排他制御をしないとき，プロセスp1，p2が並行に1回だけ処理を実行した直後において，y が取り得ない値を，解答群の中から選べ。
解答群
  • 4
  • 5
  • 6
  • 7
解答選択欄
  • 　
  • 　イ

解説

[結果が 4 になるケース]
以下のように、プロセスp1の更新をプロセスp2の結果で上書きする順番で処理が行われたときにこの値になります。
  1. プロセスp1が y を読込み(p1:y＝5)
  2. プロセスp1が y を＋2する(p1:y＝7)
  3. プロセスp2が y を読込み(p2:y＝5)
  4. プロセスp2が y を－1する(p2:y＝4)
  5. プロセスp1が共有データに書込み(共有データ:y＝7)
  6. プロセスp2が共有データに書込み(共有データ:y＝4)
[結果が 5 になるケース]
ありません。

[結果が 6 になるケース]
以下のように、プロセスp1とプロセスp2の処理が(排他制御をしたように)順次行われたときにこの値になります。
  1. プロセスp1が y を読込み(p1:y＝5)
  2. プロセスp1が y を＋2する(p1:y＝7)
  3. プロセスp1が共有データに書込み(共有データ:y＝7)
  4. プロセスp2が y を読込み(p2:y＝7)
  5. プロセスp2が y を－1する(p2:y＝6)
  6. プロセスp2が共有データに書込み(共有データ:y＝6)
[結果が 7 になるケース]
以下のように、プロセスp2の更新をプロセスp1の結果で上書きする順番で処理が行われたときにこの値になります。
  1. プロセスp1が y を読込み(p1:y＝5)
  2. プロセスp1が y を＋2する(p1:y＝7)
  3. プロセスp2が y を読込み(p2:y＝5)
  4. プロセスp2が y を－1する(p2:y＝4)
  5. プロセスp2が共有データに書込み(共有データ:y＝4)
  6. プロセスp1が共有データに書込み(共有データ:y＝7)
∴イ：5
広告

設問2

次の記述中の　に入れる正しい答えを，解答群の中から選べ。

　プロセスの排他制御の仕組みとして，共有データがいずれかのプロセスに確保されている状態(以下，確保状態という)又はどのプロセスにも確保されていない状態(以下，解放状態という)のいずれかの状態をもつ同期変数を使用する方法を考える。図1のプロセスp1，p2の計算処理で使用する共有データ y に対して同期変数 s を用いて排他制御する場合を，図2に示す。
pm01_2.png
　図2において，同期変数の状態を変更する関数lとuがあり，同期変数を引数で指定する。各プロセスは，共有データを排他制御して計算処理をする場合，関数lの呼出し，計算処理，関数uの呼出しの順番で処理を実行する。このとき，共有データ yを排他制御するために，関数lとuの引数として同期変数 s を指定する。
　関数lの操作内容はa処理であり，関数uの操作内容はb処理である。ここで，"同期変数の状態を調べて，変更する処理"は中断のない処理として実行されるものとする。ただし，プロセスが待ちの状態になったら，CPUは別のプロセスに割り付けられるものとする。
a，b に関する解答群
  • s の状態が解放状態ならば確保状態にし，確保状態ならば解放状態になるまで待ってから確保状態にする
  • s の状態が解放状態ならば確保状態にし，確保状態ならば何もしない
  • s の状態が解放状態ならば確保状態になるまで待ち，確保状態ならば解放状態になるまで待つ
  • s の状態が解放状態ならば確保状態になるまで待ち，確保状態ならば何もしない
  • s の状態が確保状態ならば解放状態にし，解放状態ならば何もしない
  • s の状態が確保状態ならば解放状態になるまで待ち，解放状態ならば何もしない
解答選択欄
  • a:
  • b:
  • a=ア
  • b=オ

解説

〔aについて〕
関数lは共有データの更新を伴う計算処理の前に呼ばれるので、行うべきは資源の確保(占有／ロック)処理になります。

解答群中「確保状態にする」処理は「ア」と「イ」です。この2つの処理は「ア」が確保状態になるまで待つのに対し、「イ」では既に確保状態であれば何もしないという点が異なります。「イ」の方式では場合によっては資源をロックしないまま計算処理が行われてしまうので、排他制御になりません。

したがって関数lの適切な処理方式は「ア」です。

∴a＝ア

〔bについて〕
関数uは共有データの更新後に呼ばれるので、行うべきは資源の解放処理になります。

計算処理中は共有データを自プロセスが独占的に確保しているため、使用し終わったら資源を解放しなくてはなりません。解答群中「解放状態にする」処理は「オ」のみなので、これが正解となります。
「カ」にも「解放状態になるまで待ち…」という記述がありますが、ロックをかけているのは自プロセスなので自身が明示的に解放しない限り自然と解放状態になることはありません。

したがって関数uの適切な処理は「オ」です。

∴b＝オ
広告

設問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の解放
解答選択欄
  • 　
  • 　ウ

解説

デッドロックとは、共有資源を使用する2つ以上のプロセスが、互いに相手プロセスの必要とする資源を排他的に使用していて、互いのプロセスが相手の使用している資源の解放を待っている状態です。
デッドロックが発生するとプロセスは永遠に待ち状態になってしまうためプロセスの続行ができなくなってしまいます。

デッドロックの発生は、2つのプロセスで互いに使用する資源の占有順序が反対であるときに起こる可能性があります。プロセスp1は「y1→y2」の順で資源を占有するので、これとは逆の「y2→y1」の順である「ウ」「エ」が対象となりますが、「エ」は2つの資源を同時に占有することがないのでデッドロックが起こることはありません。
したがって「ウ」が正解です。

具体的には2つのプロセスが次のように資源を占有した場合にデッドロックが発生します。
  1. プロセスp1が共有データy1を確保
  2. プロセスp2が共有データy2を確保
  3. プロセスp1は共有データy2の確保を要求するが、プロセスp2によって占有済みなので確保できない
  4. プロセスp2は共有データy1の確保を要求するが、プロセスp1によって占有済みなので確保できない
  5. 2つのプロセス間がデッドロックとなる
∴ウ：y2の確保，y1の確保，y1の解放，y2の解放
広告
広告

次の問題

▲
Pagetop