基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

OSにおけるプロセスのスケジューリングに関する次の記述を読んで，設問1～3に答えよ。

　OSの役割の一つとして，プロセスにCPUを割り当てることがある。そして，プロセスにCPUを割り当てる順序(以下，実行順序という)を決定する方式には，次のようなものがある。ここで，プロセスが実行されるコンピュータのCPUは 一つであり，CPUは同時に一つのプロセスしか実行できない。

• 到着順方式
  　プロセスを到着順に待ち行列の末尾に登録する。実行中のプロセスが終了すると 待ち行列の先頭からプロセスを一つ取り出してCPUを割り当て，実行を開始する。到着順方式を図1に示す。待ち行列に登録されているプロセスの状態を実行可能状態，実行中のプロセスの状態を実行状態と呼ぶ。
  
• ラウンドロビン方式
  　プロセスを到着順に待ち行列の末尾に登録する。実行中のプロセスが終了すると，待ち行列の先頭からプロセスを一つ取り出してCPUを割り当て，実行を開始する。また，プロセスの実行中に一定時間(以下，タイムクウォンタムという)が経過したら，実行を中断して，待ち行列の末尾に再登録する。そして，待ち行列の先頭から プロセスを一つ取り出してCPUを割り当て，実行を開始する。ラウンドロビン方式を図2に示す。
  

プロセスXを到着順方式で実行した場合のプロセスの状態の遷移について考える。プロセスの状態の遷移を図3に示す。図3において，(a)～(d)の矢印は 状態の遷移を示す。プロセスXの処理順序が図4に示す①～⑤の場合，図3に示す(a)～(d)の各遷移の発生する回数の組合せとして正しい答えを，解答群の中から選べ。
　なお，プロセスの実行中にデータの入出力が発生した場合，その実行を中断して待ち状態となり，データの入出力が完了したら実行可能状態となる。ここで，待ち状態のプロセスにはCPUを割り当てないものとする。

ラウンドロビン方式についての，次の記述中の　に入れる正しい答えを，解答群の中から選べ。

　四つのプロセスA～Dがあり，各プロセスの到着時刻と処理時間を表1に示す。表1において，到着時刻とは，プロセスAが到着して最初に待ち行列に登録された時刻からプロセスB～Dが到着して最初に待ち行列に登録されるまでの経過時間である。処理時間とは，各プロセスの処理が完了するために必要なCPUの割当時間である。　タイムクウォンタムが20ミリ秒の場合，プロセスDが最初に実行状態になったときには，待ち行列の先頭から　の順にプロセスが登録されている。ここで，プロセスAが最初に待ち行列に登録されたとき，実行可能状態，実行状態及び待ち状態にあるプロセスはないものとし，プロセスA～Dは，実行中にタイムクウォンタムの経過以外で中断することはないものとする。
　なお，プロセスの登録と取出し，及び中断の処理に掛かる時間は考えないものとする。

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

　プロセスの実行順序を決定する別の方式に残余処理時間順方式がある。残余処理時間順方式は，一定の時間ごとに実行状態と実行可能状態にあるプロセスの残余処理時間を比較し，その時間が最も短いプロセスにCPUを割り当てる方式である。ここで，残余処理時間とは，プロセスの残りの処理が完了するまでに必要なCPUの割当時間である。
　表1に示すプロセスA～Dを，残余処理時間順方式で実行した場合のターンアラウンドタイムについて考える。ターンアラウンドタイムとは，プロセスが最初に待ち行列に登録されてから処理が完了するまでの時間である。
　プロセスAが登録されてから10ミリ秒ごとに残余処理時間を比較しながら実行したとき，プロセスA，B，Cのターンアラウンドタイムはそれぞれaミリ秒，bミリ秒，cミリ秒である。図5には，プロセスAが登録されてから90ミリ秒までのプロセスの状態の遷移を記入してある。ここで，プロセスAが最初に待ち行列に登録されたとき，実行可能状態実行状態及び待ち状態にあるプロセスはないものとし，プロセスA～Dは，実行中に残余処理時間の比較結果以外で中断することはないものとする。また，プロセスが到着して待ち行列に登録された時点で，残余処理時間の比較対象となっているものとする。
　なお，プロセスの登録，取出しと中断の処理，及び残余処理時間の比較処理に掛かる時間は考えないものとする。