基本情報技術者 2014年 秋期 午後 問03
OSにおけるプロセスのスケジューリングに関する次の記述を読んで、設問1～3に答えよ。
OSの役割の一つとして、プロセスにCPUを割り当てることがある。そして、プロセスにCPUを割り当てる順序（以下、実行順序という）を決定する方式には、次のようなものがある。ここで、プロセスが実行されるコンピュータのCPUは一つであり、CPUは同時に一つのプロセスしか実行できない。
(1) 到着順方式
プロセスを到着順に待ち行列の末尾に登録する。実行中のプロセスが終了すると、待ち行列の先頭からプロセスを一つ取り出してCPUを割り当て、実行を開始する。到着順方式を図1に示す。待ち行列に登録されているプロセスの状態を実行可能状態、実行中のプロセスの状態を実行状態と呼ぶ。
(2) ラウンドロビン方式
プロセスを到着順に待ち行列の末尾に登録する。実行中のプロセスが終了すると、待ち行列の先頭からプロセスを一つ取り出してCPUを割り当て、実行を開始する。また、プロセスの実行中に一定時間（以下、タイムクウォンタムという）が経過したら、実行を中断して、待ち行列の末尾に再登録する。そして、待ち行列の先頭からプロセスを一つ取り出してCPUを割り当て、実行を開始する。ラウンドロビン方式を図2に示す。
設問1：
問題文を見る プロセスXを到着順方式で実行した場合のプロセスの状態の遷移について考える。プロセスの状態の遷移を図3に示す。図3において、(a)〜(d)の矢印は状態の遷移を示す。プロセスXの処理順序が図4に示す①〜⑤の場合、図3に示す(a)〜(d)の各遷移の発生する回数の組合せとして正しい答えを、解答群の中から選べ。
なお、プロセスの実行中にデータの入出力が発生した場合、その実行を中断して待ち状態となり、データの入出力が完了したら実行可能状態となる。ここで、待ち状態のプロセスにはCPUを割り当てないものとする。
解答群
模範解答
ウ
解説
解答の導き方
図3の(a)〜(d)は、プロセスの状態が変わる向きを表しています。まず、実行可能状態は「CPUを使う順番を待っている状態」、実行状態は「CPUを使っている状態」、待ち状態は「データの入出力が終わるのを待っている状態」です。
図3では、実行可能状態から実行状態への遷移が(a)、実行状態から実行可能状態への遷移が(b)、実行状態から待ち状態への遷移が(c)、待ち状態から実行可能状態への遷移が(d)です。
図4の処理順序を、CPUを使う処理とデータの入出力に分けて追います。問題文には、入出力が発生すると「実行を中断して待ち状態となり」、入出力が完了すると「実行可能状態となる」とあります。このため、入出力のたびに(c)と(d)が1回ずつ発生します。
①、③、⑤の3回、プロセスXは実行状態になります。したがって、(a)は3回です。
入出力は②と④の2回です。それぞれで実行状態から待ち状態になるので、(c)は2回です。また、入出力が完了するたびに待ち状態から実行可能状態になるので、(d)も2回です。
(b)は、実行状態から実行可能状態に戻る遷移です。到着順方式では、実行中のプロセスがタイムクウォンタムの経過などで中断されることはありません。入出力を始めるときは実行可能状態ではなく待ち状態になるため、(b)は0回です。
よって、回数は(a)が3回、(b)が0回、(c)が2回、(d)が2回となり、解答群ではウに当たります。なお、⑤の処理が終わった後の終了は、図3では破線の矢印で表されており、(a)〜(d)の回数には含めません。
誤りやすいポイント
- 入出力の開始時は、実行状態から実行可能状態ではなく、待ち状態へ移ります。したがって、ここで数えるのは(b)ではなく(c)です。
- 入出力の完了時に、待ち状態から実行可能状態へ移ります。入出力の完了だけで実行状態になるわけではないため、CPUを使い始めるときに(a)を数えます。
- プロセスが一つでも、CPUを使う処理が3つあれば、実行可能状態から実行状態への遷移は3回発生します。
- 最後の処理が終わった後の終了は、図3の(a)〜(d)には含まれません。
FAQ
Q: 入出力中のプロセスが、すぐにCPUを使わないのはなぜですか？
A: 問題文では、入出力中は待ち状態になり、CPUを割り当てないとされています。入出力が終わって実行可能状態になった後、CPUを使う順番が来ると実行状態になります。
A: 問題文では、入出力中は待ち状態になり、CPUを割り当てないとされています。入出力が終わって実行可能状態になった後、CPUを使う順番が来ると実行状態になります。
Q: (b)はどのようなときに発生しますか？
A: 実行中のプロセスが中断され、CPUを使う順番待ちに戻るときに発生します。例えば、ラウンドロビン方式ではタイムクウォンタムが経過すると、実行中のプロセスを中断して待ち行列の末尾に戻します。この問題の到着順方式では、そのような中断はありません。
A: 実行中のプロセスが中断され、CPUを使う順番待ちに戻るときに発生します。例えば、ラウンドロビン方式ではタイムクウォンタムが経過すると、実行中のプロセスを中断して待ち行列の末尾に戻します。この問題の到着順方式では、そのような中断はありません。
Q: プロセスの到着時に(a)を数えますか？
A: 到着しただけでは、まだ実行状態ではありません。まず実行可能状態になり、CPUを割り当てられて実行状態になったときに(a)を数えます。
A: 到着しただけでは、まだ実行状態ではありません。まず実行可能状態になり、CPUを割り当てられて実行状態になったときに(a)を数えます。
関連キーワード: プロセス状態、到着順方式、ラウンドロビン方式、CPUスケジューリング、入出力待ち
設問2：
問題文を見る ラウンドロビン方式についての、次の記述中のに入れる正しい答えを、解答群の中から選べ。
四つのプロセスA〜Dがあり、各プロセスの到着時刻と処理時間を表1に示す。表1において、到着時刻とは、プロセスAが到着して最初に待ち行列に登録された時刻からプロセスB〜Dが到着して最初に待ち行列に登録されるまでの経過時間である。処理時間とは、各プロセスの処理が完了するために必要なCPUの割当時間である。
タイムクウォンタムが20ミリ秒の場合、プロセスDが最初に実行状態になったときには、待ち行列の先頭からの順にプロセスが登録されている。ここで、プロセスAが最初に待ち行列に登録されたとき、実行可能状態、実行状態及び待ち状態にあるプロセスはないものとし、プロセスA〜Dは、実行中にタイムクウォンタムの経過以外で中断することはないものとする。
なお、プロセスの登録と取出し、及び中断の処理に掛かる時間は考えないものとする。
解答群
ア：A, B, C
イ：A, C, B
ウ：B, A, C
エ：B, C, A
オ：C, A, B
カ：C, B, A
模範解答
イ
解説
解答の導き方
ラウンドロビン方式では、実行中のプロセスがタイムクウォンタム（1回のCPU割当て時間の上限）を使い切ると、待ち行列の末尾に戻ります。CPU（Central Processing Unit：プログラムの命令を処理する装置）は一つなので、実行できるプロセスは同時に一つだけです。
この問題では、タイムクウォンタムは20ミリ秒です。各プロセスの処理時間はAが120ミリ秒、Bが90ミリ秒、Cが60ミリ秒、Dが30ミリ秒です。Dが初めて実行されるまで、実行中のプロセスは20ミリ秒ごとに待ち行列へ戻ります。到着したプロセスは、その時点の待ち行列の末尾に加わります。
待ち行列の並びを、先頭から順に追います。
ここで、待ち行列には実行中のDは含まれません。Dを先頭から取り出した後の並びは、A、C、Bです。したがって、該当する順序は A, C, B です。
誤りやすいポイント
-
到着したプロセスが、実行中のプロセスをすぐに交代させると思うこと
B、C、Dが到着しても、その時点では実行中のプロセスは実行を続けます。到着したプロセスは待ち行列の末尾に加わります。 -
タイムクウォンタム終了後のプロセスを、待ち行列の先頭に戻すこと
本文には、タイムクウォンタムが経過したプロセスを「待ち行列の末尾に再登録する」とあります。すでに待っているプロセスより後ろに並びます。 -
実行中のプロセスを待ち行列に含めること
100ミリ秒の時点では、Dは取り出されて実行中です。そのため、待ち行列に残るのはA、C、Bです。
FAQ
Q: Bは10ミリ秒に到着したのに、すぐ実行されないのはなぜですか？
A: その時点ではAが実行中だからです。Bは待ち行列に加わり、Aのタイムクウォンタムが終わった後に実行されます。
A: その時点ではAが実行中だからです。Bは待ち行列に加わり、Aのタイムクウォンタムが終わった後に実行されます。
Q: Dが初めて実行されるのは、到着した50ミリ秒ですか？
A: いいえ。50ミリ秒に待ち行列へ加わりますが、その時点ではAが実行中です。その後、待ち行列の先頭に来た100ミリ秒に初めて実行されます。
A: いいえ。50ミリ秒に待ち行列へ加わりますが、その時点ではAが実行中です。その後、待ち行列の先頭に来た100ミリ秒に初めて実行されます。
Q: 待ち行列にいるプロセスは「待ち状態」ですか？
A: この問題の待ち行列にいるプロセスは、CPUが割り当てられるのを待つ「実行可能状態」です。データ入力など、CPU以外の処理を待つ「待ち状態」とは区別します。
A: この問題の待ち行列にいるプロセスは、CPUが割り当てられるのを待つ「実行可能状態」です。データ入力など、CPU以外の処理を待つ「待ち状態」とは区別します。
関連キーワード: プロセス、CPU、ラウンドロビン方式、タイムクウォンタム、待ち行列
設問3：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
プロセスの実行順序を決定する別の方式に残余処理時間順方式がある。残余処理時間順方式は、一定の時間ごとに実行状態と実行可能状態にあるプロセスの残余処理時間を比較し、その時間が最も短いプロセスにCPUを割り当てる方式である。ここで、残余処理時間とは、プロセスの残りの処理が完了するまでに必要なCPUの割当時間である。
表1に示すプロセスA〜Dを、残余処理時間順方式で実行した場合のターンアラウンドタイムについて考える。ターンアラウンドタイムとは、プロセスが最初に待ち行列に登録されてから処理が完了するまでの時間である。
プロセスAが登録されてから10ミリ秒ごとに残余処理時間を比較しながら実行したとき、プロセスA、B、Cのターンアラウンドタイムはそれぞれaミリ秒、bミリ秒、cミリ秒である。図5には、プロセスAが登録されてから90ミリ秒までのプロセスの状態の遷移を記入してある。ここで、プロセスAが最初に待ち行列に登録されたとき、実行可能状態、実行状態及び待ち状態にあるプロセスはないものとし、プロセスA〜Dは、実行中に残余処理時間の比較結果以外で中断することはないものとする。また、プロセスが到着して待ち行列に登録された時点で、残余処理時間の比較対象となっているものとする。
なお、プロセスの登録、取出しと中断の処理、及び残余処理時間の比較処理に掛かる時間は考えないものとする。
a〜cに関する解答群
ア：60
イ：80
ウ：90
エ：100
オ：120
カ：180
キ：300
模範解答
a：キ、b：カ、c：ウ
解説
解答の導き方
この問題では、残余処理時間順方式でプロセスを実行したとき、各プロセスのターンアラウンドタイムを求めます。
OS（Operating System：コンピュータの基本動作を管理するソフトウェア）は、プロセス（実行中のプログラムを管理する単位）にCPU（Central Processing Unit：プログラムの命令を処理する装置）を割り当てます。残余処理時間順方式では、一定時間ごとに「あとどれだけCPUを使えば処理が終わるか」を比べ、残りが最も短いプロセスを実行します。
ターンアラウンドタイムは、プロセスが最初に登録されてから処理が完了するまでの経過時間です。CPUを使っている時間だけでなく、実行可能状態で待っている時間も含みます。
表1の処理時間と登録時刻、および図5の状態を使って、実行順序を追います。時間はすべてミリ秒です。
表の各時刻では、その時点で登録済みのプロセスを比べています。たとえば時刻10では、Aの残りは110ミリ秒ですが、登録されたばかりのBは90ミリ秒です。そのため、残りが短いBが実行されます。問題文にあるとおり、到着して登録されたプロセスも、その時点で比較の対象になります。
図5では、Aは0〜10ミリ秒、Bは10〜30ミリ秒、Cは30〜50ミリ秒、Dは50〜80ミリ秒に実行されています。時刻80では、Dが完了しており、残りが最も短いCが実行されます。Cはその後も残り時間が最も短いため、時刻120に処理を終えます。図5の表示は90ミリ秒までですが、90ミリ秒以降も同じ方式で比較を続けます。
完了時刻から登録時刻を引くと、ターンアラウンドタイムになります。
- A：完了時刻300 − 登録時刻0 ＝ 300ミリ秒
- B：完了時刻190 − 登録時刻10 ＝ 180ミリ秒
- C：完了時刻120 − 登録時刻30 ＝ 90ミリ秒
誤りやすいポイント
- CPUを使った時間だけで計算する
ターンアラウンドタイムには、実行可能状態で待っている時間も含まれます。 - 実行を開始した時刻から数える
数え始めるのは、最初に待ち行列へ登録された時刻です。Bは実行を開始する時刻ではなく、登録された時刻10から数えます。 - 図5が90ミリ秒までなので、そこで計算を止める
図5は90ミリ秒までの状態を示しています。処理が完了するまで、その後の比較と実行も続けて考えます。 - 新しく登録されたプロセスを、次の比較まで無視する
問題文では、登録された時点で残余処理時間の比較対象になるとされています。
FAQ
Q: ターンアラウンドタイムと、プロセスの処理時間は何が違いますか？
A: 処理時間は、プロセスがCPUを使う時間です。ターンアラウンドタイムは、登録から完了までの経過時間なので、CPUを待つ時間も含みます。
A: 処理時間は、プロセスがCPUを使う時間です。ターンアラウンドタイムは、登録から完了までの経過時間なので、CPUを待つ時間も含みます。
Q: 時刻90以降もCが実行されるのはなぜですか？
A: 時刻90では、Cの残りは30ミリ秒です。Aの残り110ミリ秒、Bの残り70ミリ秒より短いため、Cが選ばれます。その後もCが最も短い状態が続き、時刻120に完了します。
A: 時刻90では、Cの残りは30ミリ秒です。Aの残り110ミリ秒、Bの残り70ミリ秒より短いため、Cが選ばれます。その後もCが最も短い状態が続き、時刻120に完了します。
Q: あるプロセスが比較のたびに最短なら、毎回別のプロセスへ切り替わりますか？
A: いいえ。比較した結果、同じプロセスが引き続き最短なら、そのプロセスを続けて実行します。
A: いいえ。比較した結果、同じプロセスが引き続き最短なら、そのプロセスを続けて実行します。
関連キーワード: プロセス、プロセススケジューリング、残余処理時間順方式、実行可能状態、ターンアラウンドタイム
