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