基本情報技術者 2018年 秋期 午後 問02
プロセスのスケジューリングに関する次の記述を読んで、設問1，2に答えよ。
OSの機能の一つに、プロセスのCPUへの割当てがある。プロセスをCPUに割り当てる順序（以下、実行順序という）を決定する方式として、本問で示すラウンドロビン方式と優先度順方式を考える。プロセスが実行されるコンピュータのCPUは一つであり、CPUは一度に一つのプロセスしか実行できないものとする。
ラウンドロビン方式では、キューを用いて、複数のプロセスを一定時間（以下、タイムクウォンタムという）を限度にCPUに割り当てて実行する。ラウンドロビン方式でプロセスの実行順序を決定する例を、図1に示す。
(1) プロセスを生成順にキューの末尾に登録する。
(2) プロセスの実行の中断などによって、実行中のプロセスがない場合、キューの先頭からプロセスを一つ取り出してCPUに割り当て、実行を開始する。
(3) プロセスの実行が終了すると、そのプロセスを消滅させる。
(4) プロセスの実行中にタイムクウォンタムが経過したら、実行を中断して、キューの末尾に登録する。
(5) 実行中のプロセスが入出力を開始したら、実行を中断する。
(6) プロセスの入出力が完了したら、キューの末尾に登録する。
キューに登録されているプロセスの状態を“実行可能”、実行中のプロセスの状態を“実行”、入出力の完了を待っているプロセスの状態を“待ち”と呼ぶ。ここで、実行の中断はタイムクウォンタムの経過と入出力の開始だけで行い、“待ち”への遷移は入出力の開始だけで行うものとする。また、OSによるオーバヘッドはないものとする。
設問1：
問題文を見る 図2に示す処理順序をもつプロセスXを、図1に示すラウンドロビン方式で実行する場合を考える。プロセスXの処理時間及び待ち時間を表1に示す。
表1において、処理時間とは、処理1、処理2及び処理3のそれぞれが実行を開始してから終了するまでに必要なCPUの使用時間である。待ち時間とは、入出力待ち1及び入出力待ち2のそれぞれが入出力を開始してから完了するまでに要する時間であり、その間CPUを使用しない。
タイムクウォンタムが20ミリ秒のとき、プロセスXが生成されてから消滅するまでに、図3に示す①〜④の遷移が起こる回数の組合せとして正しい答えを、解答群の中から選べ。
解答群
模範解答
オ
解説
解答の導き方
求めるのは、図3の①〜④の状態遷移が何回起こるかです。CPU（Central Processing Unit：プログラムの命令を実行する装置）を使う時間と、入出力のために待つ時間を分けて数えます。
ラウンドロビン方式は、プロセス（実行中のプログラム）に順番にCPUを割り当てる方式です。問題文には「タイムクウォンタムが経過したら、実行を中断して、キューの末尾に登録する」とあります。つまり、プロセスはCPUを使い始めてから最大20ミリ秒でいったん実行可能状態に戻ります。
まず、処理ごとにCPUの使用時間を20ミリ秒ずつに分けます。
①は、実行可能状態のプロセスがCPUを使い始めるときの遷移です。したがって、CPUを使う区切りの数だけ起こります。処理1では2回、処理2では3回、処理3では1回なので、①は合計6回です。
④は、タイムクウォンタムが経過して、まだ処理が残っているときに起こる遷移です。処理1は20ミリ秒経過後も10ミリ秒残るため1回、処理2は20ミリ秒経過後に処理が残る場面が2回あるため2回起こります。処理3は10ミリ秒で終了し、20ミリ秒に達しないため起こりません。よって、④は合計3回です。
次に、入出力の待ちによる遷移を数えます。処理1と処理2の後に、それぞれ入出力待ちがあります。入出力を開始すると実行状態から待ち状態へ移るので、②は2回です。入出力が完了すると待ち状態から実行可能状態へ移るので、③も2回です。入出力待ちの間はCPUを使わないため、その時間はタイムクウォンタムの回数には加えません。
以上から、回数の組合せは①が6回、②が2回、③が2回、④が3回です。この組合せに当たるのは、解答群のオです。
誤りやすいポイント
- ①を処理の種類の数だけ数えないようにします。処理1や処理2はタイムクウォンタムで分割されるため、CPUを使い始める回数を数えます。
- ④は、タイムクウォンタムが経過するたびに必ず起こるわけではありません。処理が終わる前にタイムクウォンタムが経過した場合に起こります。
- 入出力待ちの時間はCPUを使いません。入出力待ちの30ミリ秒を、タイムクウォンタムの経過として数えないようにします。
- 入出力の開始と完了は別々の遷移です。入出力待ち1回につき、②と③がそれぞれ1回起こります。
FAQ
Q: プロセスが一つしかなくても、①が6回になるのはなぜですか？
A: ①は、別のプロセスに切り替わる回数ではなく、プロセスが実行可能状態から実行状態になる回数です。タイムクウォンタムで処理が分割されるたびに、いったん実行可能状態に戻り、その後CPUを使い始めるため、複数回起こります。
A: ①は、別のプロセスに切り替わる回数ではなく、プロセスが実行可能状態から実行状態になる回数です。タイムクウォンタムで処理が分割されるたびに、いったん実行可能状態に戻り、その後CPUを使い始めるため、複数回起こります。
Q: 処理が10ミリ秒で終わる場合も、④は起こりますか？
A: 起こりません。④はタイムクウォンタムが経過したときの遷移です。処理が20ミリ秒より前に終われば、タイムクウォンタムは経過していないためです。
A: 起こりません。④はタイムクウォンタムが経過したときの遷移です。処理が20ミリ秒より前に終われば、タイムクウォンタムは経過していないためです。
Q: 入出力待ちの30ミリ秒は、CPUを使う時間に含めますか？
A: 含めません。問題文では、入出力待ちの間はCPUを使用しないとされています。入出力待ちの時間は、②と③の遷移を数えるときに関係します。
A: 含めません。問題文では、入出力待ちの間はCPUを使用しないとされています。入出力待ちの時間は、②と③の遷移を数えるときに関係します。
関連キーワード: プロセス、ラウンドロビン方式、タイムクウォンタム、状態遷移、CPUスケジューリング
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
優先度順方式では、ラウンドロビン方式と同様にキューを用いて、複数のプロセスをタイムクウォンタムを限度にCPUに割り当てて実行する。この方式では、プロセスには優先度が与えられ、優先度ごとに決められたキューに登録される。優先度順方式でプロセスの実行順序を決定する例を、図4に示す。ここで、優先度は1〜5の5段階であり、値の大きい方が優先度は高い。プロセスをキューから取り出すときは、プロセスが登録されているキューの中で、優先度の最も高いキューの先頭からプロセスを取り出す。
この方式では、プロセスの優先度を次のように与える。
(1) プロセスが生成された場合、そのプロセスに優先度3を与える。
(2) プロセスの実行中にタイムクウォンタムが経過して、実行を中断した場合、そのプロセスの現在の優先度に応じて、次のとおり優先度を与える。
・優先度が1のとき、優先度1を与える。
・優先度が2〜5のとき、1段階下げた優先度を与える。
(3) プロセスの入出力が完了した場合、そのプロセスに優先度5を与える。
表1に示すプロセスXを、図4に示す優先度順方式で実行する場合を考える。タイムクウォンタムが20ミリ秒のとき、プロセスXが生成されてから消滅するまでの優先度の推移は、aとなる。
図4に示す優先度順方式において、“実行”、“実行可能”及び“待ち”のプロセスが一つもないとき、表2に示す三つのプロセスA, B, Cが順次生成される場合を考える。
(1) 生成時刻は、プロセスAが生成された時刻からの経過時間である。
(2) 三つのプロセスA, B, Cが全て消滅するまで、他のプロセスが新たに生成されることはなく、OSによるオーバヘッドもない。
(3) 入出力装置は同時に動作が可能であり、同じ時間帯に複数のプロセスが“待ち”になっても、待ち時間は表2に示すとおりで変わらない。複数のプロセスの入出力が同時に完了した場合、入出力を開始してから完了するまでの時間が最も長かったプロセスを先にキューに登録する。
タイムクウォンタムが20ミリ秒のとき、プロセスBの処理1が実行を開始する時刻は、プロセスAの生成時刻からbミリ秒後であり、プロセスAの処理1が終了する時刻は、プロセスAの生成時刻からcミリ秒後である。
aに関する解答群
ア：3→2→5→4→3→2
イ：3→2→5→4→3→5
ウ：3→3→5→3→1
エ：3→4→5→4→3→5
b, cに関する解答群
ア：10
イ：20
ウ：30
エ：40
オ：50
カ：60
キ：70
ク：80
ケ：90
模範解答
a：イ、b：イ、c：キ
解説
解答の導き方
OS（Operating System：コンピュータの動作を管理する基本ソフト）は、プロセス（実行を管理するプログラムの単位）にCPU（Central Processing Unit：命令を実行する装置）を割り当てます。キューは順番待ちの列、タイムクウォンタムはプロセスが1回にCPUを使える上限時間です。
この問題では、タイムクウォンタムが経過するとプロセスはいったん実行を中断し、入出力が完了すると再びキューに登録されます。優先度順方式では、数値が大きいほど優先度が高く、優先度が同じならキューに先に登録されたプロセスから実行します。
1. プロセスXの優先度の推移を求めます
表1では、プロセスXのCPUを使う処理時間が「30ミリ秒、50ミリ秒、10ミリ秒」、入出力にかかる待ち時間が「30ミリ秒、30ミリ秒」です。タイムクウォンタムは20ミリ秒です。
タイムクウォンタムが経過したときは、優先度が2〜5なら1段階下がり、1ならそのままです。入出力が完了したときは、優先度が5になります。処理時間とタイムクウォンタムを対応させると、次のようになります。
優先度の変化を順に並べると、処理1の実行開始時の「3」、最初のタイムクウォンタム経過後の「2」、入出力待ち1の完了後の「5」、処理2でのタイムクウォンタム経過後の「4」「3」、入出力待ち2の完了後の「5」です。
したがって、優先度の推移は「3→2→5→4→3→5」で、aの解答群のイに当たります。
2. プロセスBの処理1が始まる時刻を求めます
プロセスAは時刻0に生成され、優先度3で処理1を開始します。時刻10にプロセスBが生成されますが、問題文には、ほかのプロセスが生成されたときに実行中のプロセスを中断するとは書かれていません。そのため、Aは時刻20まで実行を続けます。
時刻20にAのタイムクウォンタムが経過し、Aの優先度は3から2に下がります。Aがキューに戻ると、優先度3のBが優先度2のAより先に実行されます。よって、Bの処理1が始まるのは時刻20です。bは20ミリ秒です。
3. プロセスAの処理1が終わる時刻を求めます
したがって、Aの処理1が終了するのは、Aの生成時刻から70ミリ秒後です。cは70ミリ秒です。
誤りやすいポイント
- タイムクウォンタムは「必ずその時間だけ実行する時間」ではなく、CPUを使える上限です。たとえば処理時間が30ミリ秒でタイムクウォンタムが20ミリ秒なら、20ミリ秒と残り10ミリ秒に分けて考えます。
- タイムクウォンタムが経過すると、処理が終わっていなくても優先度が下がります。プロセスXの処理2は50ミリ秒なので、20ミリ秒ごとに2回、優先度が下がります。
- 入出力待ちの間、プロセスはCPUを使いません。入出力が完了したときに優先度5でキューに戻ります。
- 同じ優先度のプロセスが複数ある場合、キューに登録された順番で実行します。プロセスAとBはどちらも優先度2になった時点があり、そのときは先に登録されたAが先に実行されます。
FAQ
Q: 時刻10にプロセスBが生成されたとき、Aの実行が中断されないのはなぜですか？
A: 問題文では、実行を中断する条件としてタイムクウォンタムの経過と入出力の開始を示しています。プロセスの生成は中断条件ではないため、Aはタイムクウォンタムが経過する時刻20まで実行を続けます。
A: 問題文では、実行を中断する条件としてタイムクウォンタムの経過と入出力の開始を示しています。プロセスの生成は中断条件ではないため、Aはタイムクウォンタムが経過する時刻20まで実行を続けます。
Q: 入出力待ちの時間も、タイムクウォンタムに含まれますか？
A: 含まれません。タイムクウォンタムはCPUを使える時間の上限です。入出力待ちの間はCPUを使わないので、その待ち時間はCPU処理時間とは別に扱います。
A: 含まれません。タイムクウォンタムはCPUを使える時間の上限です。入出力待ちの間はCPUを使わないので、その待ち時間はCPU処理時間とは別に扱います。
Q: 優先度が同じプロセスは、どちらから実行されますか？
A: キューに先に登録されたプロセスから実行されます。このため、プロセスAとBが同じ優先度2になったときは、先にキューへ戻っていたAが先です。
A: キューに先に登録されたプロセスから実行されます。このため、プロセスAとBが同じ優先度2になったときは、先にキューへ戻っていたAが先です。
関連キーワード: プロセススケジューリング、優先度順方式、ラウンドロビン方式、タイムクウォンタム、キュー
