応用情報技術者 2023年秋期午前2 問17

問題文

プリエンプティブな優先度ベースのスケジューリングで実行する二つの周期タスクA及びBがある。タスクBが周期内に処理を完了できるタスクA及びBの最大実行時間及び周期の組合せはどれか。ここで、タスク Aの方がタスクBより優先度が高く、かつ、タスク AとBの共有資源はなく、タスク切替え時間は考慮しないものとする。また、時間及び周期の単位はミリ秒とする。

選択肢

ア：（正解）

イ：

ウ：

エ：

プリエンプティブな優先度ベースのスケジューリング問題【午前2 解説】

要点まとめ

結論：選択肢アの組合せがタスクBを周期内に完了可能な最大実行時間と周期の組合せです。
根拠：優先度が高いタスクAの実行時間が短く、タスクBの利用率が周期内に収まるため、スケジューリング可能です。
差がつくポイント：利用率の計算とプリエンプティブ優先度スケジューリングの理解、特にタスクAの優先度が高いことによる影響を正しく評価できるかが鍵です。

正解の理由

プリエンプティブな優先度ベーススケジューリングでは、優先度の高いタスクAが優先的にCPUを使用します。
タスクBが周期内に完了するためには、CPU利用率の合計が1以下である必要があります。
選択肢アでは、タスクAの利用率

2/4 = 0.5

、タスクBの利用率

3/8 = 0.375

で合計

0.875

となり、1を超えません。
したがって、タスクBは周期内に処理を完了できます。

よくある誤解

タスクの利用率合計が1を超えてもスケジューリング可能と誤解しがちです。
優先度の高いタスクが長時間CPUを占有する場合、低優先度タスクが遅延することを見落としやすいです。

解法ステップ

各タスクのCPU利用率を計算する（実行時間 ÷ 周期）。
利用率の合計が1以下か確認する。
優先度の高いタスクがCPUを占有することを考慮し、低優先度タスクの完了可能性を評価する。
選択肢ごとに上記を繰り返し、条件を満たす組合せを選ぶ。

選択肢別の誤答解説

イ：利用率は $3/6 = 0.5$ と $4/9 \approx 0.444$ で合計約0.944。利用率は1以下だが、タスクBの実行時間が長く、優先度の高いタスクAの影響でBが遅延する可能性がある。
ウ：利用率は $3/5 = 0.6$ と $5/13 \approx 0.385$ で合計約0.985。利用率は1以下だが、タスクAの周期が短くCPU占有が多いためBの完了が危うい。
エ：利用率は $4/6 \approx 0.667$ と $5/15 = 0.333$ で合計約1.0。理論上は可能だが、タスクAの実行時間が長く、Bの完了保証が難しい。

補足コラム

プリエンプティブ優先度スケジューリングは、リアルタイムシステムでよく使われる方式です。
利用率の合計が1以下であっても、優先度の高いタスクの実行時間が長いと低優先度タスクが遅延するため、レスポンス時間分析も重要です。
また、共有資源がある場合は優先度逆転問題が発生するため、優先度継承プロトコルなどの対策が必要です。