応用情報技術者 2010年秋期午前2 問18

問題文

五つのタスクA〜Eの優先度と、各タスクを単独で実行した場合のCPUと入出力装置(I/O)の動作順序と処理時間は、表のとおりである。優先度 “高”のタスクAとB〜Eのどのタスクを組み合わせれば、組み合わせたタスクが同時に実行を開始してから、両方のタスクの実行が終了するまでの間のCPUの遊休時間をゼロにできるか。ここで、I/Oは競合せず、OSのオーバヘッドは無視できるものとする。また、表の( )内の数字は処理時間を表すものとする。

🖊️ 解答を隠して解いてみる

選択肢

ア：

イ：

ウ：（正解）

エ：

🔒 解説は解答すると表示されます

CPU遊休ゼロ組合せ【午前2解説】

正解の理由

高優先度のタスクAと低優先度のタスクD（選択肢ウ）を同時に開始すると、優先度によりAは常に実行可能時にCPUを占有します。AがI/Oで待ちになる各期間に、DのCPU実行区間がちょうど入り込み、Aの実行期間とDの実行期間が断続的に入れ替わるため、開始から両者の終了までCPUが連続稼働して空き時間が発生しません。両タスクのCPU総和が

8 + 10 = 18 ms

で、実際のスケジュールの末尾も18msとなることから（下記タイムライン参照）、CPU遊休時間はゼロになります。

解法ステップ

優先度が高いタスクAは実行可能なら常にCPUを取得（プリエンプティブ想定）。
両タスクを同時開始（時刻0）として、時系列で「どのタスクがCPUを使うか」をシミュレーションする。
各I/O終了時刻に低優先度タスクの状態がどうなるかを確認し、CPUに隙間（両者ともI/O中や未到着でCPUが空く瞬間）ができないかを調べる。
CPUが連続して埋まるかを確認（総CPU時間と最終完了時刻が一致すれば遊休ゼロ）。

具体的なタイムライン（A高優先、D低優先、同時開始）：

0–3 ms: AがCPU(3)
3–6 ms: DがCPU(3)（AはI/O(3)）
6–9 ms: AがCPU(3)（Dは6–8 msにI/O(2) を終え、8 msにReady。8–9 msはReady状態で待機）
9–12 ms: DがCPU(3)（AはI/O(3) で9–12 ms）
12–14 ms: AがCPU(2)（Dは12–13 msにI/O(1)、13 msにReadyして待機）
14–18 ms: DがCPU(4)

この通りCPUは0–18 msの全区間で何らかのタスクが実行しており、遊休時間は発生しません。

選択肢別の誤答解説

ア（B）：
- Bの第1 CPUは2 msと短く、その直後のI/Oが長い（5 ms）ため、Aの第1 I/O（3 ms）終了時にBは既にI/O中（5 msの途中）でCPUが空く区間が発生します。具体的にはBのI/Oが5–10 msに跨るとき、Aの6 ms時点でBはまだI/O中のため5–6 msの間にCPUが空きます。
イ（C）：
- Cの第1 CPUはAの第1 I/Oに合わせて入り切るが、その後のI/O/CPU配列で11–12 msの間に両方がI/O/待ちになり、11–12 msにCPUの空きが発生します（Cが11 msに第2 I/Oに入り、Aは9–12 msにI/O）。
エ（E）：
- Eの第1 I/Oが長め（4 ms）で、EのI/O終了がAのI/Oとずれるため9–10 msの間にCPUが空きます（Aが9–12 msにI/O中で、Eが6–10 msにI/O）。よって遊休ゼロになりません。

各誤答は「AのI/Oと相手タスクのI/O／CPUの配置が重ならず、両者ともにCPUを必要としない瞬間が生じる」ことで失敗します。

よくある誤解

Aが常に優先されるため「低優先度は全く実行されない」と考える誤り：低優先度でも高優先タスクがI/Oで待ちになる瞬間に必ず実行機会が生じる点を見落としやすいです。
I/O完了＝CPU直使用と短絡的に扱う誤り：複数のイベントが同時刻に発生する場合（I/O完了とCPU終了が同じ時刻など）は、優先度や遷移順により「誰が先にCPUを取るか」を正確に扱う必要があります。今回のように同時到着で高優先度が先に取ります。
時刻区間の端点扱い（開区間・閉区間）でのオフバイワン：同じ時刻に区切られるイベントは「終端が次の動作の開始になってCPUが連続するか」を正確に判断すること。

補足コラム

簡易チェック法として「総CPU時間 = 実行開始から最終終了時刻」であればCPUは連続稼働（遊休ゼロ）になり得ます。今回の組合せではA: 3+3+2 = 8 ms、D: 3+3+4 = 10 ms、合計18 ms。シミュレーションの最終完了時刻も18 msで一致するため、遊休ゼロであることが迅速に確認できます。ただしこの条件は必要条件であり十分条件となるためには、I/Oの時間配置が干渉しないこと（高優先度タスクのI/O期間に低優先度が必ずCPUを持てる等）を確認する必要があります。

FAQ

Q. タイムスライスやコンテキスト切り替えがあると結果は変わるか？
A. 本問題はオーバーヘッド無視、優先度プリエンプションの単純モデルを想定しているため、短いタイムスライスや文脈切り替えがあっても総じて高優先度優先の挙動になります。実時間の切替オーバーヘッドが無視できない場合、細かい境界で微小な差が出る可能性がありますが、本種の設問では無視して良いです。

Q. I/Oが競合する（同一デバイスを共有する）場合は？
A. I/Oが競合するとI/O開始時刻や完了時刻がずれるため今回のような綺麗な埋め合わせが崩れ、遊休時間が発生する可能性があります。設問条件にある通り競合しない前提が重要です。

関連キーワード: プリエンプティブスケジューリング、ガントチャート、CPU利用率、I/O待ち、タスクスケジューリング