平成30年秋期試験午後問題 問2
問2 ソフトウェア
プロセスのスケジューリングに関する次の記述を読んで，設問1，2に答えよ。
OSの機能の一つに，プロセスのCPUへの割当てがある。プロセスをCPUに割り当てる順序(以下，実行順序という)を決定する方式として，本問で示すラウンドロビン方式と優先度順方式を考える。プロセスが実行されるコンピュータのCPUは一つであり，CPUは一度に一つのプロセスしか実行できないものとする。
ラウンドロビン方式では，キューを用いて，複数のプロセスを一定時間(以下，タイムクウォンタムという)を限度にCPUに割り当てて実行する。ラウンドロビン方式でプロセスの実行順序を決定する例を，図1に示す。
キューに登録されているプロセスの状態を"実行可能"，実行中のプロセスの状態を"実行"，入出力の完了を待っているプロセスの状態を"待ち"と呼ぶ。ここで，実行の中断はタイムクウォンタムの経過と入出力の開始だけで行い，"待ち"への遷移は入出力の開始だけで行うものとする。また，OSによるオーバーヘッドはないものとする。
OSの機能の一つに，プロセスのCPUへの割当てがある。プロセスをCPUに割り当てる順序(以下，実行順序という)を決定する方式として，本問で示すラウンドロビン方式と優先度順方式を考える。プロセスが実行されるコンピュータのCPUは一つであり，CPUは一度に一つのプロセスしか実行できないものとする。
ラウンドロビン方式では，キューを用いて，複数のプロセスを一定時間(以下，タイムクウォンタムという)を限度にCPUに割り当てて実行する。ラウンドロビン方式でプロセスの実行順序を決定する例を，図1に示す。
- プロセスを生成順にキューの末尾に登録する。
- プロセスの実行の中断などによって，実行中のプロセスがない場合，キューの先頭からプロセスを一つ取り出してCPUに割り当て，実行を開始する。
- プロセスの実行が終了すると，そのプロセスを消滅させる。
- プロセスの実行中にタイムクウォンタムが経過したら，実行を中断して，キューの末尾に登録する。
- 実行中のプロセスが入出力を開始したら，実行を中断する。
- プロセスの入出力が完了したら，キューの末尾に登録する。
キューに登録されているプロセスの状態を"実行可能"，実行中のプロセスの状態を"実行"，入出力の完了を待っているプロセスの状態を"待ち"と呼ぶ。ここで，実行の中断はタイムクウォンタムの経過と入出力の開始だけで行い，"待ち"への遷移は入出力の開始だけで行うものとする。また，OSによるオーバーヘッドはないものとする。
広告
設問1
図2に示す処理順序をもつプロセスXを，図1に示すラウンドロビン方式で実行する場合を考える。プロセスXの処理時間及び待ち時間を表1に示す。
表1において，処理時間とは，処理1，処理2及び処理3のそれぞれが実行を開始してから終了するまでに必要なCPUの使用時間である。待ち時間とは，入出力待ち1及び入出力待ち2のそれぞれが入出力を開始してから完了するまでに要する時間であり，その間CPUを使用しない。
タイムクウォンタムが20ミリ秒のとき，プロセスXが生成されてから消滅するまでに，図3に示す①～④の遷移が起こる回数の組合せとして正しい答えを，解答群の中から選べ。
表1において，処理時間とは，処理1，処理2及び処理3のそれぞれが実行を開始してから終了するまでに必要なCPUの使用時間である。待ち時間とは，入出力待ち1及び入出力待ち2のそれぞれが入出力を開始してから完了するまでに要する時間であり，その間CPUを使用しない。
タイムクウォンタムが20ミリ秒のとき，プロセスXが生成されてから消滅するまでに，図3に示す①～④の遷移が起こる回数の組合せとして正しい答えを，解答群の中から選べ。
解答群
解答選択欄
- オ
解説
プロセスXの生成から消滅までを追って、各回数を数えます。- プロセスが生成され、実行可能状態になる。
- 実行可能状態から実行状態になる（処理1の開始）。…①
- 20ミリ秒のタイムクウォンタムが経過し、実行可能状態に戻る。…④
- 実行可能状態から実行状態になる。…①
- 10ミリ秒が経過し処理1が完了する。プロセスは入出力待ち1のため待ち状態に遷移する。…②
- 入出力待ち1が終わり、実行可能状態に遷移する。…③
- 実行可能状態から実行状態になる（処理2の開始）。…①
- 20ミリ秒のタイムクウォンタムが経過し、実行可能状態に戻る。…④
- 実行可能状態から実行状態になる。…①
- 20ミリ秒のタイムクウォンタムが経過し、実行可能状態に戻る。…④
- 実行可能状態から実行状態になる。…①
- 10ミリ秒が経過し処理2が完了する。プロセスは入出力待ち2のため待ち状態に遷移する。…②
- 入出力待ち2が終わり、実行可能状態に遷移する。…③
- 実行可能状態から実行状態になる（処理3の開始）。…①
- 10ミリ秒が経過し処理3が完了する。全処理が完了したためプロセスは消滅する。
広告
設問2
次の記述中の に入れる正しい答えを，解答群の中から選べ。
優先度順方式では，ラウンドロビン方式と同様にキューを用いて，複数のプロセスをタイムクウォンタムを限度にCPUに割り当てて実行する。この方式では，プロセスには優先度が与えられ，優先度ごとに決められたキューに登録される。優先度順方式でプロセスの実行順序を決定する例を，図4に示す。ここで，優先度は1～5の5段階であり，値の大きい方が優先度は高い。プロセスをキューから取り出すときは，プロセスが登録されているキューの中で，優先度の最も高いキューの先頭からプロセスを取り出す。
この方式では，プロセスの優先度を次のように与える。
図4に示す優先度順方式において，"実行"，"実行可能"及び"待ち"のプロセスが一つもないとき，表2に示す三つのプロセスA，B，Cが順次生成される場合を考える。
タイムクウォンタムが20ミリ秒のとき，プロセスBの処理1が実行を開始する時刻は，プロセスAの生成時刻からbミリ秒後であり，プロセスAの処理1が終了する時刻は，プロセスAの生成時刻からcミリ秒後である。
優先度順方式では，ラウンドロビン方式と同様にキューを用いて，複数のプロセスをタイムクウォンタムを限度にCPUに割り当てて実行する。この方式では，プロセスには優先度が与えられ，優先度ごとに決められたキューに登録される。優先度順方式でプロセスの実行順序を決定する例を，図4に示す。ここで，優先度は1～5の5段階であり，値の大きい方が優先度は高い。プロセスをキューから取り出すときは，プロセスが登録されているキューの中で，優先度の最も高いキューの先頭からプロセスを取り出す。
- プロセスが生成された場合，そのプロセスに優先度3を与える。
- プロセスの実行中にタイムクウォンタムが経過して，実行を中断した場合，そのプロセスの現在の優先度に応じて，次のとおり優先度を与える。
- 優先度が1のとき，優先度1を与える。
- 優先度が2～5のとき，1段階下げた優先度を与える。
- プロセスの入出力が完了した場合，そのプロセスに優先度5を与える。
図4に示す優先度順方式において，"実行"，"実行可能"及び"待ち"のプロセスが一つもないとき，表2に示す三つのプロセスA，B，Cが順次生成される場合を考える。
- 生成時刻は，プロセスAが生成された時刻からの経過時間である。
- 三つのプロセスA，B，Cが全て消滅するまで，他のプロセスが新たに生成されることはなく，OSによるオーバーヘッドもない。
- 入出力装置は同時に動作が可能であり，同じ時間帯に複数のプロセスが"待ち"になっても，待ち時間は表2に示すとおりで変わらない。複数のプロセスの入出力が同時に完了した場合，入出力を開始してから完了するまでの時間が最も長かったプロセスを先にキューに登録する。
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:
- a=イ
- b=イ
- c=キ
解説
〔aについて〕優先度の変化に注意しながら、プロセスXの遷移を追っていきます。
- 生成されたプロセスは[優先度3]のキューに入る。
- キューから取り出され実行状態に移る（処理1の開始）。
- 20ミリ秒のタイムクウォンタムが経過したため、現状より1段階低い[優先度2]のキューに入る。
- キューから取り出され実行状態に移る。
- 10ミリ秒が経過し処理1が完了する。プロセスは入出力待ち1のため待ち状態に遷移する。
- 入出力待ち1が終了する。入出力完了後なので[優先度5]のキューに入る。
- キューから取り出され実行状態に移る（処理2の開始）。
- 20ミリ秒のタイムクウォンタムが経過したため、現状より1段階低い[優先度4]のキューに入る。
- キューから取り出され実行状態に移る。
- 20ミリ秒のタイムクウォンタムが経過したため、現状より1段階低い[優先度3]のキューに入る。
- キューから取り出され実行状態に移る。
- 10ミリ秒が経過し処理2が完了する。プロセスは入出力待ち2のため待ち状態に遷移する。
- 入出力待ち2が終了する。入出力完了後なので[優先度5]のキューに入る。
- キューから取り出され実行状態に移る。
- 10ミリ秒が経過し処理3が完了する。全処理が完了したためプロセスは消滅する。
∴a＝イ：3→2→5→4→3→5
〔b，cについて〕
プロセスAの処理1が終わるまでの推移を追っていきます。
- 0ミリ秒
- プロセスAが生成され、優先度3のキューに入る。プロセスAは即座に実行状態になる（A-処理1の開始）。
- 10ミリ秒後
- プロセスBが生成され、優先度3のキューに入る。
- 20ミリ秒後
- 20ミリ秒のタイムクウォンタムが経過し、プロセスAは優先度2のキューに入る。優先度3のキューからプロセスBが取り出され実行状態になる（B-処理1の開始）。
- 30ミリ秒後
- プロセスCが生成され、優先度3のキューに入る。
- 40ミリ秒後
- 20ミリ秒のタイムクウォンタムが経過し、プロセスBは優先度2のキューに入る。優先度3のキューからプロセスCが取り出され実行状態になる（C-処理1の開始）。
- 60ミリ秒後
- 20ミリ秒のタイムクウォンタムが経過し、プロセスCは優先度2のキューに入る。優先度2のキューからプロセスAが取り出され実行状態になる（A-処理1の再開）
- 70ミリ秒後
- 10ミリ秒が経過しプロセスAの処理1が完了する（A-処理1の終了）。
- （以下省略）
∴b＝20
c＝70
広告
広告