AP過去問令和5年度秋期午前問17

問17(問題文)

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

回答・解説

【解き方】

タスクBが処理を完了できるかどうかは、応答時間解析(response time analysis)で判断します。

応答時間の式（初期値はタスクBの実行時間から開始）：

$\require{enclose} \begin{eqnarray} R = C_B + \sum_{i \in hp(B)} \left\lceil \frac{R}{T_i} \right\rceil \cdot C_i \end{eqnarray}$

$C_B$ ：タスクBの最大実行時間

$T_i$ ：タスクAの周期

$C_i$ ：タスクAの最大実行時間

$\left\lceil \frac{R}{T_i} \right\rceil$ は天井関数と呼ばれ、シーリング Ti ぶんの Rのように読みます。これは0.8や0.2のような少数を切り上げ、1とする演算です。タスクBより優先度が高いもの(higher priority B)について総和をとることを意味します。この問題ではタスクBに対してはタスクAの1つしかないので総和をとる必要はありません。

ア：

タスクA： $C_i=2$ 、 $T_i=4$

タスクB： $C_B=3$ 、 $T_B=8$

初期値： $R$ には仮に $C_B$ を入れ、算出された値を次の $R$ とします。収束するか、 $T_B$ を超えるまで計算します。超えるとタスクが滞りますので、駄目です。 $T_B$ の周期を超えると、次々とBのタスクがやってきて、消化できずに処理が滞ります。

$R=3+\left\lceil \frac{3}{4} \right\rceil \cdot 2=3+1\cdot2=5$

次：

$R=3+\left\lceil \frac{5}{4} \right\rceil \cdot 2=3+2\cdot2=7$

次：

$R=3+\left\lceil \frac{7}{4} \right\rceil \cdot 2=3+2\cdot2=7$ (収束)

$→ R=7 \leqq T_B=8$ 　→ OK、もう答えは定まったのでこれ以上計算する必要はないですね。

でも、念のため、練習を兼ねて、他の選択肢についても計算をしてみましょう。

イ：

タスクA： $C_i=3$ 、 $T_i=6$

タスクB： $C_B=4$ 、 $T_B=9$

初期：

$R=4+\left\lceil \frac{4}{6} \right\rceil \cdot 3=4+1\cdot3=7$

次：

$R=4+\left\lceil \frac{7}{6} \right\rceil \cdot 3=4+2\cdot3=10$

次：

$R=4+\left\lceil \frac{10}{6} \right\rceil \cdot 3=4+2\cdot3=10$ (収束)

$→ R=10 \gt T_B=9$ 　 $R=10$ が $T_B=9$ → より大きいので処理が滞る。

ウ：

タスクA： $C_i=3$ 、 $T_i=5$

タスクB： $C_B=5$ 、 $T_B=13$

初期：

$R=5+\left\lceil \frac{5}{5} \right\rceil \cdot 3=5+1\cdot3=8$

次：

$R=5+\left\lceil \frac{8}{5} \right\rceil \cdot 3=5+2\cdot3=11$

次：

$R=5+\left\lceil \frac{11}{5} \right\rceil \cdot 3=5+3\cdot3=14$

$→ R=14 \gt T_B=13$ 収束する前に $R=14$ が $T_B=13$ → より大きくなった。これも処理が滞る。

エ：

タスクA： $C_i=4$ 、 $T_i=6$

タスクB： $C_B=5$ 、 $T_B=15$

初期：

$R=5+\left\lceil \frac{5}{6} \right\rceil \cdot 4=5+1\cdot4=9$

次：

$R=5+\left\lceil \frac{9}{6} \right\rceil \cdot 4=5+2\cdot4=13$

次：

$R=5+\left\lceil \frac{13}{6} \right\rceil \cdot 4=5+3\cdot4=17$

$→ R=17 \gt T_B=15$ 収束する前に $R=17$ が $T_B=15$ → より大きくなった。これも処理が滞る。

　したがって

ア

　が答えです。

　もっと地道な導出方法もあります。方眼紙みたいな奴にウメウメしていく手法です。

　方眼紙に最大処理時間2なら2マス。周期4なら2マスあげて描く

■■□□■■□□■■□□■■□□■■□□■■□□■■□□■■□□

こんな感じ。

　タスクBは最大処理時間2なら3マス。周期8なら処理時間を差し引いた5マスあげて描く

☒☒☒□□□□□☒☒☒□□□□□☒☒☒□□□□□☒☒☒□□□□□こんな感じ。

これを真ん中の方眼紙に埋めていく。

■■□□■■□□■■□□■■□□■■□□■■□□■■□□■■□□

■■☒☒☒■■□■■☒☒☒■■□■■☒☒☒■■□■■☒☒☒■■□

☒☒☒□□□□□☒☒☒□□□□□☒☒☒□□□□□☒☒☒□□□□□

こんな感じ。処理が滞らないか確かめるタイムライン図を作る。うまくいくので、アが正解で終わり。他のもやっていいけど疲れるので、棄権します。みなさんはやってみて下さい。つまり、なんだかキツネにつままれたような計算式を使わない方法はある。

AP過去問令和5年度秋期午前問16前の問題へ

AP過去問令和5年度秋期午前問18次の問題へ

AP過去問令和5年度秋期午前問題に戻る