エンベデッドシステムスペシャリスト 2013年 午前2 問08

周期タスクの期限内実行可能性【午前2解説】

正解の理由

解法ステップ

1. 各タスクの周期を求めます。
   条件が $D=T$ なので、各タスクの周期は選択肢にあるデッドライン $D$ と同じです。
2. 総CPU使用率を計算します。
   周期タスクの総CPU使用率は、次の式で求められます。
   $$U=\sum _i\frac{C_i}{T_i}$$
   総使用率が1を超える場合、必要な実行時間がCPUの処理能力を超えるため、スケジュールできません。
3. 使用率が1以下の候補は、優先順位も考慮して確認します。
   イは使用率がちょうど1です。Xを優先して実行するスケジュールを作ると、すべてのデッドラインに間に合うことを確認できます。

選択肢別の誤答解説

• ア：総CPU使用率は $\frac{1}{2}+\frac{2}{3}=\frac{7}{6}$ です。1を超えるため、長期的に必要な処理を完了できません。
• イ：総CPU使用率は $\frac{1}{2}+\frac{2}{4}=1$ です。Xを優先するスケジュールで、期限を守れることを確認できます。
• ウ：総CPU使用率は $\frac{2}{3}+\frac{2}{3}=\frac{4}{3}$ です。1を超えるため、スケジュールできません。
• エ：総CPU使用率は $\frac{2}{4}+\frac{3}{4}=\frac{5}{4}$ です。1を超えるため、スケジュールできません。

よくある誤解

• 各タスクが単独で期限に間に合えば、全体でもスケジュール可能だと思う
  各タスクの $C\le D$ は、単独で実行した場合の条件です。複数タスクが同じCPUを使う場合は、合計の処理量も考える必要があります。
• 総CPU使用率が1以下なら、必ずスケジュール可能だと思う
  使用率が1を超える場合は不可能ですが、1以下であることだけでは一般に十分とは限りません。優先順位やデッドラインも確認します。この問題では、イについて実際の実行順を確認しています。
• デッドラインと実行完了時刻は、必ずデッドラインより前でなければならないと思う
  デッドラインの時刻ちょうどに実行を完了しても、期限を守ったことになります。

補足コラム

FAQ