基本情報技術者過去問題 平成29年秋期 午後問2

⇄問題文と設問を画面2分割で開く⇱問題PDF

問2 ソフトウェア

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

 単一のCPUと,プロセス間で共有するデータ(以下,共有データという)を格納するためのメモリ(以下,共有メモリという)をもつコンピュータXにおいて,並行に実行される複数のプロセスが,共有データを更新する場合を考える。
 二つのプロセスp1,p2が共有データyを更新する際には,図1に示す更新処理1,更新処理2を,それぞれ①〜③の順番に行う。

設問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

解答選択欄

  •  

解答

  •  

解説

普通に考えれば初期値yが100であり、更新処理1が+30、更新処理2が−50ですから、結果は80になると期待します。しかし、同じデータに対して同時並行的に更新処理を行うと、読書きのタイミングによっては更新消失が生じる可能性があります。

[結果が50になるケース]
以下のように、プロセスp1の更新をプロセスp2の結果で上書きする順番で処理が行われた場合、結果は50になります。
  • プロセスp1が y を読込み(p1:y=100)
  • プロセスp1が y を+30する(p1:y=130)
  • プロセスp2が y を読込み(p2:y=100)
  • プロセスp2が y を−50する(p2:y=50)
  • プロセスp1が共有データyに書込み(共有データ:y=130)
  • プロセスp2が共有データyに書込み(共有データ:y=50)
[結果が80になるケース]
以下のように、プロセスp1とプロセスp2の処理が直列的に(排他制御が行われたように)実行された場合、結果は80になります。
  • プロセスp1が y を読込み(p1:y=100)
  • プロセスp1が y を+30する(p1:y=130)
  • プロセスp1が共有データyに書込み(共有データ:y=130)
  • プロセスp2が y を読込み(p2:y=130)
  • プロセスp2が y を−50する(p2:y=80)
  • プロセスp2が共有データyに書込み(共有データ:y=80)
[結果が100になるケース]
ありません

[結果が130になるケース]
結果が50になるケースとは逆に、プロセスp2の更新をプロセスp1の結果で上書きする順番で処理が行われた場合、結果は130になります。
  • プロセスp1が y を読込み(p1:y=100)
  • プロセスp1が y を+30する(p1:y=130)
  • プロセスp2が y を読込み(p2:y=100)
  • プロセスp2が y を−50する(p2:y=50)
  • プロセスp2が共有データyに書込み(共有データ:y=50)
  • プロセスp1が共有データyに書込み(共有データ:y=130)
∴ウ:100

設問2

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

 共有データに対して排他制御を行う仕組みとして,セマフォ変数を利用する方法を考える。セマフォ変数は,対応する共有データが,解放されている状態を示す1,又はいずれかのプロセスに確保されている状態を示す0の値をもつ。セマフォ変数の値は,P操作とV操作で変更する。共有データyに対応するセマフォ変数Sを利用したプロセスp3,p4が共有データyを更新する際の動作を,図2に示す。
pm02_2.gif/image-size:377×227
 図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:

解答

  • a=
  • b=

解説

問題文では、セマフォ変数が"1"であれば共有データは解放されており、"0"であればいずれかのプロセスに確保されていると説明されています。

aについて〕
P操作は、更新処理の開始前に呼ばれるので、行うべきは資源の確保(占有/ロック)処理になります。つまりP操作は、共有データyが解放されていれば確保し、使用中であれば解放されるのを待ってから確保する処理です。

資源の確保はセマフォ変数を1から0に変更することで行います。セマフォ変数の状態(解放=1、使用中=0)を用いてP操作を言い表すと、

「共有データに対応するセマフォ変数が1(解放)であれば0(使用中)に変更し、0(使用中)であれば1になる(解放される)のを待った後、0(使用中)に変更する」

となります。したがって「ウ」の操作が適切です。

a=ウ:セマフォ変数Sの値が1であれば0に変更し,終了する。0であれば1になるまで,待った後,0に変更して終了する
  • 0から1への変更は資源の解放を意味するため不適切です。
  • 0から1への変更は資源の解放を意味するため不適切です。
  • 正しい。
  • 0の時に何もせずに終了してしまうと、資源の確保を行わないまま更新処理が実行されます。この場合、同時更新による更新消失を起こす可能性があるので不適切です。

bについて〕
V操作は、更新処理の終了後に呼ばれるので、行うべきは確保した資源の解放(アンロック)処理になります。使用中の共有データに対応するセマフォ変数は、資源の確保時に0に変更されているので、V操作ではセマフォ変数を1に変更して解放状態にします。

b=エ:セマフォ変数の値を1にして終了する
  • V操作の実行時点で資源を確保しているのは、P操作を行った自プロセスです。資源の確保中は、他のプロセスによりその資源が確保されることはないので、他のプロセスの操作によりセマフォ変数が1になることはありません。
  • P操作によりセマフォ変数は0に変更されています。V操作はP操作の後に呼ばれるのでセマフォ変数が0になっていることはありません。
  • 0にする操作は資源の確保を意味するため不適切です。0にして終了すると他のプロセスがその資源を使用できなくなってしまいます。
  • 正しい。

設問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の解放

解答選択欄

  •  

解答

  •  

解説

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

デッドロックの発生する可能性があるのは、2つのプロセスで互いに使用する資源の占有順序が「逆順」のときです。これを踏まえると、プロセスp5の資源占有順序「y1→y2」とは逆の占有順序「y2→y1」になっている「エ」と「オ」に対象を絞れます。さらに、"y2の確保と"y1の確保"の間に"y2の解放"を挟んでいる「オ」は、2つの資源を同時に占有する状態にはならないため、プロセスp5とのデッドロックにはなり得ません。

したがって「エ」が正解です。

以下はプロセスp6が「エ」の順序で資源を確保した場合に、プロセスp5との間でデッドロックに陥る例です。
  • プロセスp5が共有データy1を確保
  • プロセスp6が共有データy2を確保
  • プロセスp5は共有データy2の確保を要求するが、プロセスp6が使用中なので、プロセスp5は共有データy2の解放待ちとなる
  • プロセスp6は共有データy1の確保を要求するが、プロセスp5が使用中なので、プロセスp6は共有データy1の解放待ちとなる
  • 2つのプロセスはデッドロックとなる

∴エ:y2の確保,y1の確保,y1の解放,y2の解放

平成29年秋期 午後問題一覧

問1 問2 問3 問4 問5 問6 問7 問8 問9 問10 問11 問12 問13 採点講評
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop