AP過去問 令和5年度秋期 午前 問17
AP過去問 令和5年度秋期 午前 問16前の問題へ
AP過去問 令和5年度秋期 午前 問18次の問題へ
問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 \) 収束する前にspan style="font-size: 0.9rem;">\( 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 \) 収束する前にspan style="font-size: 0.9rem;">\( R=17 \)が\( T_B=15 \)→ より大きくなった。これも処理が滞る。
したがって
ア
が答えです。
もっと地道な導出方法もあります。方眼紙みたいな奴にウメウメしていく手法です。
方眼紙に最大処理時間2なら2マス。周期4なら2マスあげて描く
■■□□■■□□■■□□■■□□■■□□■■□□■■□□■■□□
こんな感じ。
タスクBは最大処理時間2なら3マス。周期8なら処理時間を差し引いた5マスあげて描く
☒☒☒□□□□□☒☒☒□□□□□☒☒☒□□□□□☒☒☒□□□□□こんな感じ。
これを真ん中の方眼紙に埋めていく。
■■□□■■□□■■□□■■□□■■□□■■□□■■□□■■□□
■■☒☒☒■■□■■☒☒☒■■□■■☒☒☒■■□■■☒☒☒■■□
☒☒☒□□□□□☒☒☒□□□□□☒☒☒□□□□□☒☒☒□□□□□
こんな感じ。処理が滞らないか確かめるタイムライン図を作る。うまくいくので、アが正解で終わり。他のもやっていいけど疲れるので、棄権します。みなさんはやってみて下さい。つまり、なんだかキツネにつままれたような計算式を使わない方法はある。
AP過去問 令和5年度秋期 午前 問16前の問題へ
AP過去問 令和5年度秋期 午前 問18次の問題へ