優先度方式のタスクスケジューリングでCPUの遊休時間を求める
基本情報技術者試験 平成30年度秋期 午前 問16 ／ ソフトウェア › オペレーティングシステム
過去問にチャレンジ
三つのタスクの優先度と、各タスクを単独で実行した場合のCPUと入出力(I/O)装置の動作順序と処理時間は、表のとおりである。優先度方式のタスクスケジューリングを行うOSの下で、三つのタスクが同時に実行可能状態になってから、全てのタスクの実行が終了するまでのCPUの遊休時間は何ミリ秒か。ここで、CPUは1個であり、1CPUは1コアで構成され、I/Oは競合せず、OSのオーバヘッドは考慮しないものとする。また、表中の( )内の数字は処理時間を示すものとする。
- ア
2
- イ
3
- ウ
4
- エ
5
会話形式の解説
講師この問題は、三つのタスクがCPUとI/Oを交互に使うようすをタイムチャート、つまり時間の流れに沿った図に描けるかどうかが要点です。CPUが空いたときにどのタスクを動かすかと、I/Oが他のタスクのCPU処理と並行して進む点に注目してください。
受験者表を見ると、どのタスクもCPU、I/O、CPUの順に動いています。I/O中はCPUを使わないので、その間は別のタスクがCPUを使えるということでしょうか。
講師そのとおりです。もう一つ、問題文に「I/Oは競合しない」とあります。これは何を意味すると思いますか。
受験者複数のタスクが同時にI/Oをしても、順番待ちにならないということだと思います。
講師はい。各タスクのI/Oは始めた時点からそのまま進みます。では時刻0では、三つとも実行可能状態です。最初にCPUを使うのはどれでしょう。
受験者優先度が高いタスクです。CPU処理が3ミリ秒なので、0〜3ミリ秒は高のタスクが使います。
講師高はそのあと3〜8ミリ秒がI/Oです。3ミリ秒の時点で残っている実行可能なタスクは中と低なので、中が3〜5ミリ秒、続いて低が5〜6ミリ秒にCPUを使います。中のI/Oは5〜11、低のI/Oは6〜11ミリ秒になります。
受験者すると6ミリ秒の時点で、三つともI/O中です。高のI/Oが終わる8ミリ秒まではCPUを使えるタスクがないので、6〜8ミリ秒の2ミリ秒が遊休になります。
講師よく追えています。8ミリ秒に高が戻ってきて、8〜10ミリ秒に後半のCPU処理をして終了します。その後はどうなりますか。
受験者中と低はどちらも11ミリ秒までI/O中なので、10〜11ミリ秒もCPUが空きます。11〜13ミリ秒に中、13〜14ミリ秒に低が動いて終わりです。遊休は2＋1で3ミリ秒ですね。
講師正解です。2ミリ秒という選択肢は、6〜8ミリ秒の区間だけを数えた値です。高が終わった後の10〜11ミリ秒の空きを見落とすと、この数になります。
受験者4ミリ秒や5ミリ秒は、どう考えると出てくるのでしょうか。I/O時間をそのまま遊休と考えたのかなと思いました。
講師あるタスクがI/O中でも、実行可能な別のタスクがあればCPUはそちらを処理するので、I/O時間がそのまま遊休になるわけではありません。チャート上の遊休区間は6〜8と10〜11の二つだけで、4ミリ秒にも5ミリ秒にもなる組合せはありません。
受験者遊休時間は、全部のタスクがI/O中か終了済みで、動かせるタスクがない区間だけを足せばよいということですね。
講師そうです。検算もできます。全体の終了時刻14ミリ秒から、CPU処理時間の合計3＋2＋2＋2＋1＋1＝11ミリ秒を引くと3ミリ秒で、答えと一致します。チャートを描くときは1ミリ秒刻みで、各タスクのI/Oが戻る時刻を書き込みながら進めると取り違えにくくなります。
まとめ
この問題は、優先度方式のタスクスケジューリングで、CPUが何もしていない遊休時間を求めるものです。CPUが空いたときは、実行可能なタスクのうち優先度が最も高いものを動かします。I/Oは競合しないので、各タスクのI/Oは他のタスクのCPU処理と並行して進みます。タイムチャートを描くと、遊休区間は6〜8ミリ秒と10〜11ミリ秒の二つで、合計は3ミリ秒です。終了時刻14ミリ秒からCPU処理時間の合計11ミリ秒を引いても3ミリ秒になり、検算できます。
解答・解説
正解はイです
この問題のテーマ
優先度方式のスケジューリングで、CPU処理とI/O処理が重なり合う様子をタイムチャートに描き、CPUが何も実行していない時間を求める問題です。
解き方の考え方
CPUが空いたときは、実行可能なタスクのうち優先度の最も高いものに割り当てます。I/Oは競合しないので、各タスクのI/Oは開始と同時に並行して進められます。時刻0から、各タスクがいつCPUを使い、いつI/Oを終えて実行可能に戻るかを順に追います。実行可能なタスクが一つもない区間がCPUの遊休時間です。
選択肢ごとの解説
- ×ア 22ミリ秒は、6〜8ミリ秒の遊休区間だけの長さです。タイムチャートでは高のCPU処理が10ミリ秒に終わった後にも、中と低がI/O中でCPUが空く区間があります。その1ミリ秒を加えると合計は2ミリ秒になりません。
- ○イ 30〜3ミリ秒は高、3〜5は中、5〜6は低がCPUを使い、各タスクのI/Oは高が3〜8、中が5〜11、低が6〜11です。6〜8は3タスクともI/O中でCPUが空き、8〜10に高の後半処理が入ります。10〜11も中・低がI/O中で空き、11〜13に中、13〜14に低が実行されます。遊休は2＋1＝3ミリ秒です。
- ×ウ 4遊休区間は6〜8と10〜11の二つだけで、合計は3ミリ秒です。4ミリ秒になる区間の組合せはタイムチャート上にありません。
- ×エ 5あるタスクがI/O処理をしている間も、実行可能な別のタスクがあればCPUはそちらを処理します。このためI/O時間がそのまま遊休になるわけではなく、実際に空いているのは3ミリ秒です。
POINT
- 優先度方式では、CPUが空いた時点で実行可能なタスクのうち最も優先度の高いものが実行されます。
- I/Oが競合しない条件では、各タスクのI/Oは他のタスクのCPU処理と並行して進みます。
- CPUの遊休時間は、全タスクがI/O中または終了済みで、実行可能なタスクがない区間の合計です。
- 検算として、全体の終了時刻14から CPU処理時間の合計11（3+2+2+2+1+1）を引くと、遊休時間3と一致します。