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

問題文

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

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

選択肢

ア：（正解）

イ：

ウ：

エ：

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

応答時間解析【午前2解説】

正解の理由

タスクBが周期内（＝デッドライン＝周期）に完了するかは、単にCPU利用率の合計が1以下かでは判断できません。固定優先度プリエンプティブでは高優先度タスクAによる離散的な干渉回数を切り上げで評価する応答時間解析（RTA）が必要です。選択肢アでは、応答時間反復計算

R_{B}^{(k + 1)} = C_{B} + ⌈ R_{B}^{(k)} / T_{A} ⌉ \cdot C_{A}

を繰り返すと収束値が

R_{B} = 7 ms

となり、タスクBの周期

8 ms

を超えないため、Bは周期内に完了します。したがって選択肢アが成立します。

解法ステップ

各選択肢についてパラメータを定義する（ $C_{A}, T_{A}, C_{B}, T_{B}$ ）。
初期値 $R_{B}^{(0)} = C_{B}$ として反復を開始する。
更新式を用いて $R_{B}^{(k + 1)} = C_{B} + 高優先度 i \sum ⌈ \frac{R _{B}^{(k)}}{T _{i}} ⌉ C_{i} .$ （本問題は高優先度はAのみなので項は1つ）
収束（ $R_{B}^{(k + 1)} = R_{B}^{(k)}$ ）するか、あるいは途中で $R_{B}^{(k)} > T_{B}$ となれば不成立と判定する。
収束値が $T_{B}$ 以下ならタスクBは周期内に完了すると判断する。

計算手順の実例（選択肢ア）：

$C_{A} = 2, T_{A} = 4, C_{B} = 3, T_{B} = 8$
$R^{(0)} = 3$
$R^{(1)} = 3 + ⌈ 3/4 ⌉ \cdot 2 = 3 + 1 \cdot 2 = 5$
$R^{(2)} = 3 + ⌈ 5/4 ⌉ \cdot 2 = 3 + 2 \cdot 2 = 7$
$R^{(3)} = 3 + ⌈ 7/4 ⌉ \cdot 2 = 3 + 2 \cdot 2 = 7$ （収束）
収束値 $7 \leq 8$ → 可 schedulable

選択肢別の誤答解説

ア（正当化）
- 利用率合計は $2/4 + 3/8 = 0.875$ で1未満だが、正しい判定はRTAで行った結果 $R_{B} = 7 \leq 8$ のため可です。ここでのポイントは「必要条件（利用率合計≦1）」を満たすだけでなく、応答時間が周期内に収束することを確かめた点です。
イ
- パラメータ： $C_{A} = 3, T_{A} = 6, C_{B} = 4, T_{B} = 9$ 。
- 反復： $R^{(0)} = 4$ → $R^{(1)} = 7$ → $R^{(2)} = 10$ → 収束 $10 > 9$ 。よってBは期限内に終わらない。利用率合計は約0.944で1以下だが、切り上げ干渉で期限超過する典型例です。
ウ
- パラメータ： $C_{A} = 3, T_{A} = 5, C_{B} = 5, T_{B} = 13$ 。
- 反復： $5 \to 8 \to 11 \to 14$ （収束14）で $14 > 13$ のため不可。利用率合計は約0.985で1未満でも失敗します。
エ
- パラメータ： $C_{A} = 4, T_{A} = 6, C_{B} = 5, T_{B} = 15$ 。
- 反復： $5 \to 9 \to 13 \to 17$ （収束17）で $17 > 15$ のため不可。利用率合計は1.0ちょうどでもRTAで不可となることに注意。

よくある誤解

利用率合計 ≦ 1 が十分条件だと誤解する
- 利用率合計が1以下は必要条件に過ぎません。高優先度タスクの発生が周期境界で重なると、切り上げにより瞬間的な干渉が増え、応答時間が期限を超えます。必ずRTAでチェックしてください。
干渉回数を小数で扱う（切り上げを忘れる）
- 干渉回数は実際の発生回数なので $⌈ R / T ⌉$ の切り上げを使う必要があります。小数のまま積算すると過小評価になります。
反復の初期化や終了判定を適切に行わない
- 初期は $R^{(0)} = C_{B}$ 、収束判定は繰返しで等しくなるか、途中で $R > T_{B}$ が出たら即座に不可と判断します。

補足コラム

ブロッキング（共有資源がある場合）：もし高優先度/低優先度間で共有資源が存在するなら、プロトコル（例えば優先度継承法や優先度上限プロトコル）による最大ブロッキング時間 $B_{j}$ を応答時間式に加えます。 $R_{j} = C_{j} + B_{j} + i \in h p (j) \sum ⌈ \frac{R _{j}}{T _{i}} ⌉ C_{i} .$
タスクが複数の高優先度タスクを持つ場合：干渉項はそれらすべての和になります（本問は高優先度がAのみのため1項）。
簡易判定：利用率チェックは速いスクリーニングになりますが、本問のように厳密判定が必要な場合は必ずRTAを実施してください。

FAQ

Q. 反復が収束しない場合はどう判断するべきですか？
A. 反復中に

R^{(k)} > T_{B}

が出たら即時「不可」と判定できます。通常は有限ステップで収束または期限超過が判明します。

Q. デッドラインが周期より短い場合は？
A. 解析式は同様ですが、比較対象はデッドライン

D_{B}

です。収束値が

D_{B}

以下かを確認します。

Q. 実務で手で計算するのが大変な場合は？
A. 小さな数のタスクなら手計算で十分ですが、複数タスクの系ではツールやスクリプト（簡単なRTAループ）を使うと安全です。以下は単純な実装例です：

import math

def rta(Ca, Ta, Cb, Tb):
    R = Cb
    while True:
        R_next = Cb + math.ceil(R / Ta) * Ca
        if R_next == R:
            return R_next
        if R_next > Tb:
            return None  # 未達成
        R = R_next

print(rta(2,4,3,8))  # 選択肢ア -> 7