平成23年特別試験午後問題 問2

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

問2 ソフトウェア

CPUの割当て方式に関する次の記述を読んで,設問1,2に答えよ。

 オペレーティングシステムの役割のーつとして,プロセスにCPUを割り当てることがある。そして,プロセスの実行順序を決定する方式には,次のようなものがある。
  • 到着順方式
     到着順にプロセスを待ち行列の末尾に登録する。実行中のプロセスが終了すると,待ち行列の先頭からプロセスを一つ取り出して実行を開始する。
     到着順方式を図1に示す。待ち行列に登録されているプロセスの状態を実行可能状態,実行中のプロセスの状態を実行状態と呼ぶ。
    pm02_1.gif
  • ラウンドロビン方式
     到着順にプロセスを待ち行列の末尾に登録する。実行中のプロセスが終了すると,待ち行列の先頭からプロセスを一つ取り出して実行を開始する。また,実行中のプロセスが一定時間(以下,タイムクウォンタムという)を経過したら,実行を中断して,待ち行列の末尾に再登録し,待ち行列の先頭からプロセスを一つ取り出して実行を開始する。
     ラウンドロビン方式を図2に示す。
    pm02_2.gif
 これらの方式の効率を示す指標としてターンアラウンドタイムがある。ここで,ターンアラウンドタイムとは,プロセスが待ち行列に到着してから実行が終了するまでの時間であり,プロセスの実行順序に影響される。
 なお,このコンピュータシステムのCPUは一つであり,CPUは同時に一つのプロセスしか実行できない。

設問1

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

 四つのプロセスA~Dがあり,各プロセスの到着時刻と処理時間を表1に示す。表1において,到着時刻とは,プロセスAが待ち行列に到着した時刻を0としたときの各プロセスが到着する時刻であり,処理時間とは,各プロセスの処理が完了するために必要なCPUの処理時間である。
pm02_3.gif
 このとき,到着順方式におけるターンアラウンドタイムの平均はaミリ秒である。そして,タイムクウォンタムが20ミリ秒のとき,ラウンドロビン方式におけるターンアラウンドタイムの平均はbミリ秒である。ここで,プロセスAが到着したとき,実行可能状態及び実行状態のプロセスはないものとする。
 なお,プロセスの登録と取出し,及び中断の処理でのオーバーヘッドは考えない。また,CPUを割り当てられたプロセスは,タイムクウォンタム以外で中断することはない。
a,b に関する解答群
  • 80.0
  • 102.5
  • 182.5
  • 192.5
  • 242.5
解答選択欄
  • a:
  • b:
  • a=
  • b=

解説

aについて〕
CPUで実行されるプロセスと待ち行列の状態を時系列に表すと以下のようになります。
pm02_6.gif
それぞれのターンアラウンドタイムは「処理完了時刻-到着時刻」で計算できるので、

[プロセスA] 180-0=180(ミリ秒)
[プロセスB] 260-10=250(ミリ秒)
[プロセスC] 300-30=270(ミリ秒)
[プロセスD] 320-50=270(ミリ秒)

となります。したがって4つのプロセスの平均値は、

 (180+250+270+270)÷4=242.5(ミリ秒)

a=オ:242.5

bについて〕
上記と同様にCPUで実行されるプロセスと待ち行列の状態を時系列に表すと以下のようになります。(CPUが実行するタスクはタイムクォンタムの20ミリ秒ごとに切り替わっていきます)
pm02_7.gif
図を参考にするとラウンドロビン方式におけるターンアラウンドタイムは、

[プロセスA] 320-0=320(ミリ秒)
[プロセスB] 220-10=210(ミリ秒)
[プロセスC] 160-30=130(ミリ秒)
[プロセスD] 120-50=70(ミリ秒)

となります。したがって4つのプロセスの平均値は、

 (320+210+130+70)÷4=182.5(ミリ秒)

b=ウ:182.5

設問2

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

 プロセスの実行順序を決める別の方式に優先度順方式がある。優先度順方式の例を図3に示す。プロセスにはあらかじめ優先度が付けてあり,待ち行列は優先度ごとに用意してある。ここで,優先度は1~10の10種類で,値の大きい方が優先度は高い。
pm02_4.gif
 この方式では,次のとおりにプロセスの実行を制御する。
  1. プロセスを優先度に対応した待ち行列の末尾に登録する。
  2. プロセスが登録されている優先度の最も高い待ち行列の先頭からプロセスを一つ取り出して実行を開始する。
  3. 実行中のプロセスの優先度が2以上のとき,実行時間が20ミリ秒経過するごとに優先度を一つ下げる。優先度を下げた結果,実行中のプロセスの優先度が実行可能状態にある優先度の最も高いプロセスよりも低くなった場合,実行中のプロセスを中断して,①に戻る。
  4. 実行中のプロセスが終了した場合,②に戻る。
  5.  優先度順方式において,あるプロセスが終了した時点で表2に示す三つのプロセスだけが優先度に対応した待ち行列に登録されていたとする。このとき,三つのプロセスが終了する順番はcである。そして,プロセスBの実行が終了したときのプロセスBの優先度はdである。ここで,三つのプロセスが終了するまで新たに到着するプロセスはないものとする。
     なお,プロセスの登録と取出し,及び中断の処理でのオーバーヘッドは考えない。また,CPUを割り当てられたプロセスは,タイムクウォンタム以外で中断することはない。
    pm02_5.gif
c に関する解答群
  • A,B,C
  • A,C,B
  • B,A,C
  • B,C,A
  • C,A,B
  • C,B,A
d に関する解答群
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
解答選択欄
  • c:
  • d:
  • c=
  • d=

解説

cdについて〕
CPUで実行されるプロセスと優先度ごとの待ち行列の状態の遷移を図で表すと以下のようになります。
pm02_8.gif
図よりプロセスの終了する順番は B→A→C、プロセスBの実行が完了したときの優先度は 5 が適切です。

c=ウ:B,A,C
 d=オ:5

Pagetop