優先度付きスケジューリングで処理順はどう決まるか
基本情報技術者試験 平成30年度春期 午前 問16 ／ ソフトウェア › オペレーティングシステム
過去問にチャレンジ
三つのタスクA～Cの優先度と、各タスクを単独で実行した場合のCPUと入出力（I/O）装置の動作順序と処理時間は、表のとおりである。A～Cが同時に実行可能状態になって3ミリ秒経過後から7ミリ秒間のスケジューリングの状況を表したものはどれか。ここで、I/Oは競合せず、OSのオーバヘッドは考慮しないものとする。また、表中の（ ）内の数字は処理時間を表すものとし、解答群の中の“待ち”は、タスクが実行可能状態にあり、CPUの割当てで待ちであることを示す。
- ア
- イ
- ウ
- エ
会話形式の解説
講師まず、I/O中のタスクはCPUを使わないことと、I/Oが終わった時点で優先度を比べ直すことに注目します。
受験者優先度が最も高いAが、最初から続けてCPUを使うと考えてしまいました。
講師Aは開始から2ミリ秒で最初のCPU処理を終え、時刻2から4までI/Oを行います。したがって、時刻3から4のCPUはBが使います。
受験者では、時刻3から5までAがCPUを使う図は、I/O中の区間を取り違えているのですね。
講師そのとおりです。時刻4にAのI/Oが終わると、実行可能になったAの優先度をBと比べ直します。Aのほうが高いので、BのCPU処理を中断してAに割り当てます。
受験者Bは時刻2から4までに2ミリ秒使ったので、CPU処理はあと1ミリ秒残りますね。
講師はい。Aは時刻4から6まで最後のCPU処理を行って完了します。その後、Bが時刻6から7まで残りの1ミリ秒を処理し、I/Oに入ります。
受験者時刻4から6にCがCPUを使う図も、戻ってきたAの優先度を見落としていますね。
講師はい。Aを時刻4から7までCPU待ちにしてBやCへ割り当てる図も、同じ理由で誤りです。
受験者BがI/Oに入る時刻7からは、CがCPUを使えますか。
講師Cが時刻7から9までCPUを使い、時刻9からI/Oに入ります。Aが3から4にI/O、4から6にCPU、Bが6から7にCPU、Cが7から9にCPUとなるウの図が一致します。
受験者I/O中とCPU待ちを分けて見て、I/O終了時に優先度を比べ直し、中断したCPU処理は残り時間から再開すればよいのですね。
まとめ
正解はウです。Aは時刻3から4までI/O中で、終了後は優先度に従って時刻4から6までCPUを使います。中断されたBは時刻6から7まで残り1ミリ秒のCPU処理を行い、続いてCが時刻7から9までCPUを使います。I/O中とCPU待ちを区別し、I/Oが終わるたびに優先度を比べ直すことが判断の鍵です。
解答・解説
正解はウです
この問題のテーマ
優先度に従ってCPUを割り当て、I/O中のタスクとCPUの割当てを待つタスクを区別できるかを問う問題です。
解き方の考え方
開始から2ミリ秒は優先度が最も高いAがCPUを使い、その後2ミリ秒間のI/Oに入ります。その間にBがCPUを使い始めますが、時刻4にAのI/Oが終わるので、優先度を比べ直します。CPU処理の残り時間を引き継ぎながら、時刻10まで追います。
選択肢ごとの解説
- ×アアは時刻3～5にAがCPUを使う図です。しかし時刻3～4のAは、先に始めたI/Oの途中です。この区間のCPUはBに割り当てられます。
- ×イイは時刻3～4にAがCPUを使い、時刻4～6にCがCPUを使う図です。時刻3～4のAはI/O中であり、時刻4にI/Oを終えた後は、Cより優先度の高いAがCPUを使います。
- ○ウAは時刻3～4にI/Oを続け、4～6に最後のCPU処理2ミリ秒を行って完了します。Bは時刻4に中断され、6～7に残り1ミリ秒のCPU処理を終えてI/Oに入ります。続いてCが7～9にCPUを使い、9からI/Oに入るため、図の各区間と一致します。
- ×エエはI/Oを終えたAを時刻4～7にCPU待ちとし、その間にBとCへCPUを割り当てる図です。時刻4にはAが実行可能状態に戻り、両者より優先度が高いため、AがCPUを取得します。
POINT
- I/O中のタスクはCPUを使わないので、ほかの実行可能なタスクへCPUを割り当てます。
- I/Oが終わった時点で優先度を比べ直します。
- CPU処理を中断されたタスクは、残りの処理時間から再開します。