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

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

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$ 収束する前に$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年度秋期 午前 問題に戻る