基本情報技術者 2011年 春期 午後 問02
CPUの割当て方式に関する次の記述を読んで、設問1，2に答えよ。
オペレーティングシステムの役割の一つとして、プロセスにCPUを割り当てることがある。そして、プロセスの実行順序を決定する方式には、次のようなものがある。
(1) 到着順方式
到着順にプロセスを待ち行列の末尾に登録する。実行中のプロセスが終了すると、待ち行列の先頭からプロセスを一つ取り出して実行を開始する。
到着順方式を図1に示す。待ち行列に登録されているプロセスの状態を実行可能状態、実行中のプロセスの状態を実行状態と呼ぶ。
(2) ラウンドロビン方式
到着順にプロセスを待ち行列の末尾に登録する。実行中のプロセスが終了すると、待ち行列の先頭からプロセスを一つ取り出して実行を開始する。また、実行中のプロセスが一定時間（以下、タイムクウォンタムという）を経過したら、実行を中断して、待ち行列の末尾に再登録し、待ち行列の先頭からプロセスを一つ取り出して実行を開始する。
ラウンドロビン方式を図2に示す。
これらの方式の効率を示す指標としてターンアラウンドタイムがある。ここで、ターンアラウンドタイムとは、プロセスが待ち行列に到着してから実行が終了するまでの時間であり、プロセスの実行順序に影響される。
なお、このコンピュータシステムのCPUは一つであり、CPUは同時に一つのプロセスしか実行できない。
設問1：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
四つのプロセスA〜Dがあり、各プロセスの到着時刻と処理時間を表1に示す。表1において、到着時刻とは、プロセスAが待ち行列に到着した時刻を0としたときの各プロセスが到着する時刻であり、処理時間とは、各プロセスの処理が完了するために必要なCPUの処理時間である。
このとき、到着順方式におけるターンアラウンドタイムの平均はaミリ秒である。そして、タイムクウォンタムが20ミリ秒のとき、ラウンドロビン方式におけるターンアラウンドタイムの平均はbミリ秒である。ここで、プロセスAが到着したとき、実行可能状態及び実行状態のプロセスはないものとする。
なお、プロセスの登録と取出し、及び中断の処理でのオーバヘッドは考えない。また、CPUを割り当てられたプロセスは、タイムクウォンタム以外で中断することはない。
解答群
ア：80.0
イ：102.5
ウ：182.5
エ：192.5
オ：242.5
模範解答
a：オ、b：ウ
解説
解答の導き方
この問題では、プロセスが到着してから処理を終えるまでの時間を求めます。CPU（Central Processing Unit：コンピュータの処理を行う装置）は一つなので、同時に実行できるプロセスは一つだけです。
ターンアラウンドタイムは、「到着してから実行が終了するまでの時間」です。CPUを使っていた時間だけでなく、待ち行列で待っていた時間も含みます。
到着順方式
本文には、プロセスを到着順に待ち行列へ登録し、実行中のプロセスが終了すると先頭から取り出すとあります。この方式では、先に到着したプロセスが先に処理されます。
プロセスAは時刻0に実行を始め、処理時間は180ミリ秒です。Aの実行中にB、C、Dが到着するため、Aの後は到着順にB、C、Dを実行します。
各プロセスのターンアラウンドタイムは、終了時刻から到着時刻を引いて求めます。
平均は、4プロセスのターンアラウンドタイムの合計を4で割ります。
したがって、到着順方式の平均は242.5ミリ秒で、解答群ではオです。
ラウンドロビン方式
ラウンドロビン方式では、実行中のプロセスがタイムクウォンタム（1回に続けて実行できる時間）を経過しても処理が終わっていなければ、待ち行列の末尾に戻ります。ここではタイムクウォンタムが20ミリ秒なので、20ミリ秒ごとに待ち行列の先頭のプロセスへ実行を交代します。
例えば、時刻20では、時刻10に到着したBが待ち行列にいます。Aは20ミリ秒実行しても処理が終わっていないため、末尾に戻ります。そのため、次に実行するのはBです。
このルールで実行順を追うと、次のようになります。終了したプロセスは待ち行列に戻らず、処理が残っているプロセスだけが末尾に戻ります。
時刻220にBが終わると、ほかのプロセスはすでに終了しています。そのため、Aは待ち行列に戻るたびに再び先頭となり、処理を続けます。
各プロセスの終了時刻は、Aが320、Bが220、Cが160、Dが120です。到着時刻を引いて、ターンアラウンドタイムを求めます。
平均は次のとおりです。
したがって、ラウンドロビン方式の平均は182.5ミリ秒で、解答群ではウです。
誤りやすいポイント
-
処理時間だけをターンアラウンドタイムと考えること
ターンアラウンドタイムには、待ち時間も含まれます。例えば、Bは処理時間が80ミリ秒ですが、到着した時刻10から終了時刻220までの210ミリ秒がターンアラウンドタイムです。 -
ラウンドロビン方式で、タイムクウォンタムごとに必ず別のプロセスへ交代すると考えること
実行できるプロセスがほかにいなければ、処理が残っているプロセスが再び実行されます。時刻220以降はAだけが残っているため、Aが続けて実行されます。 -
20ミリ秒実行したプロセスは、必ず処理が終わると考えること
タイムクウォンタムは1回の実行時間の上限です。処理が残っていれば待ち行列に戻り、順番が来たときに続きから実行されます。CやBは複数回に分けて処理されています。 -
到着時刻をターンアラウンドタイムに加えること
ターンアラウンドタイムは「終了時刻 − 到着時刻」です。到着時刻はすでに差し引かれるため、加算しません。
FAQ
Q: ターンアラウンドタイムには、待ち行列で待った時間も含まれますか？
A: はい。到着してから処理が終わるまでの時間なので、待ち行列で待った時間と、CPUで処理した時間の両方が含まれます。
A: はい。到着してから処理が終わるまでの時間なので、待ち行列で待った時間と、CPUで処理した時間の両方が含まれます。
Q: プロセスがタイムクウォンタムより早く処理を終えた場合はどうなりますか？
A: そのプロセスは待ち行列に戻りません。実行が終わった時点で、待ち行列の先頭にいる次のプロセスを実行します。
A: そのプロセスは待ち行列に戻りません。実行が終わった時点で、待ち行列の先頭にいる次のプロセスを実行します。
Q: ラウンドロビン方式で、処理の途中から再開できるのはなぜですか？
A: タイムクウォンタムの終了時に中断しても、処理が終わっていなければ、残りの処理を待ち行列に戻して後から続けるためです。
A: タイムクウォンタムの終了時に中断しても、処理が終わっていなければ、残りの処理を待ち行列に戻して後から続けるためです。
関連キーワード: CPUスケジューリング、到着順方式、ラウンドロビン方式、タイムクウォンタム、ターンアラウンドタイム
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
プロセスの実行順序を決める別の方式に優先度順方式がある。優先度順方式の例を図3に示す。プロセスにはあらかじめ優先度が付けてあり、待ち行列は優先度ごとに用意してある。ここで、優先度は1〜10の10種類で、値の大きい方が優先度は高い。
この方式では、次のとおりにプロセスの実行を制御する。
① プロセスを優先度に対応した待ち行列の末尾に登録する。
② プロセスが登録されている優先度の最も高い待ち行列の先頭からプロセスを一つ取り出して実行を開始する。
③ 実行中のプロセスの優先度が2以上のとき、実行時間が20ミリ秒経過するごとに優先度を一つ下げる。優先度を下げた結果、実行中のプロセスの優先度が実行可能状態にある優先度の最も高いプロセスよりも低くなった場合、実行中のプロセスを中断して、①に戻る。
④ 実行中のプロセスが終了した場合、②に戻る。
優先度順方式において、あるプロセスが終了した時点で表2に示す三つのプロセスだけが優先度に対応した待ち行列に登録されていたとする。このとき、三つのプロセスが終了する順番はcである。そして、プロセスBの実行が終了したときのプロセスBの優先度はdである。ここで、三つのプロセスが終了するまで新たに到着するプロセスはないものとする。
なお、プロセスの登録と取出し、及び中断の処理でのオーバヘッドは考えない。また、CPUを割り当てられたプロセスは、タイムクウォンタム以外で中断することはない。
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：オ
解説
解答の導き方
プロセス（実行中の仕事の単位）にCPU（Central Processing Unit：命令を実行する装置）を割り当てる順番を考えます。優先度順方式では、値が大きいプロセスほど優先されます。また、実行中のプロセスは、20ミリ秒ごとに優先度が一つ下がります。
表2の初期状態では、Bの優先度が8、Aが6、Cが5です。したがって、最初に実行されるのはBです。
優先度が下がったとき、待っているプロセスの優先度よりも低くなると、実行中のプロセスは中断されます。優先度が同じになっただけでは中断されない点に注意してください。
ここで、同じ優先度の待ち行列では末尾に登録されます。AはCより先に優先度4の待ち行列に登録されているので、優先度5のBが終了した後は、優先度4のAがCより先に実行されます。
Bは最初に60ミリ秒実行され、残り10ミリ秒を実行して終了します。残りの実行時間は20ミリ秒未満なので、その間に優先度はさらに下がりません。したがって、Bの終了時の優先度は5です。
その後、Aは残り20ミリ秒を実行して終了し、最後にCが残り80ミリ秒を実行して終了します。よって、終了順はB、A、Cです。
誤りやすいポイント
- Bの優先度が6になった時点では、Aの優先度も6です。問題文では「実行可能状態にある優先度の最も高いプロセスよりも低くなった場合」に中断するとあるため、同じ優先度では中断されません。
- 実行中のプロセスだけが、実行時間に応じて優先度を下げます。待っている間に優先度が下がるわけではありません。
- 同じ優先度になったときは、待ち行列への登録順が重要です。AはCより先に優先度4の待ち行列に入るため、Aが先に実行されます。
- Bは合計70ミリ秒実行しますが、最初の60ミリ秒で優先度が5まで下がります。残り10ミリ秒では、さらに20ミリ秒経過しないため優先度は下がりません。
FAQ
Q: 優先度が同じなら、実行中のプロセスは中断されますか？
A: いいえ。中断されるのは、実行中のプロセスの優先度が、待っているプロセスの最も高い優先度より低くなった場合です。同じ優先度なら実行を続けます。
A: いいえ。中断されるのは、実行中のプロセスの優先度が、待っているプロセスの最も高い優先度より低くなった場合です。同じ優先度なら実行を続けます。
Q: Bはなぜ優先度5の待ち行列に登録されますか？
A: Bは最初に60ミリ秒実行され、その間に優先度が8から5まで下がります。中断された時点の優先度で、残りの実行を待ちます。
A: Bは最初に60ミリ秒実行され、その間に優先度が8から5まで下がります。中断された時点の優先度で、残りの実行を待ちます。
Q: AはCより先に実行されるのですか？
A: はい。どちらも優先度4ですが、Aが先に優先度4の待ち行列に登録されます。登録順に先頭から取り出すため、Aが先です。
A: はい。どちらも優先度4ですが、Aが先に優先度4の待ち行列に登録されます。登録順に先頭から取り出すため、Aが先です。
関連キーワード: CPUスケジューリング、優先度順方式、待ち行列、実行可能状態、プリエンプション
