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

問題文

五つのタスク A〜Eの優先度と、各タスクを単独で実行した場合のCPUと入出力装置(I/O)の動作順序と処理時間は、表のとおりである。優先度 “高”のタスク Aと B〜Eのどのタスクを組み合わせれば、組み合わせたタスクが同時に実行を開始してから、両方のタスクの実行が終了するまでの間のCPUの遊休時間をゼロにできるか。ここで、IO は競合せず、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待ち、タスクスケジューリング