エンベデッドシステムスペシャリスト 2010年午前2 問23

問題文

プリエンプティブな優先度ベーススケジューリングで動作する三つの周期タスクA、B、Cがある。タスクCが実行可能になってから完了するまでの時間は最大何ミリ秒か。

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

選択肢

ア：300

イ：550

ウ：600（正解）

エ：700

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

周期タスクの応答時間【午前2解説】

正解の理由

タスクCは優先度が最も低いため、実行中にタスクAまたはBが実行可能になると、それらに処理を割り込まれます。したがって、Cの完了までの時間は、C自身の実行時間に加えて、AとBによる割込み時間を考慮して求めます。

Cが実行可能になった時点でA、Bも実行可能になるケースを考えます。これは、高優先度タスクから受ける影響が大きくなるケースです。

タスクCの実行時間：300ミリ秒
タスクA：開始時と400ミリ秒後の計2回実行されるため、 $50 \times 2 = 100$ ミリ秒
タスクB：開始時の1回実行されるため、200ミリ秒

よって、完了までの時間は次のとおりです。

300 + 100 + 200 = 600 ミリ秒

したがって、正しい選択肢はウです。

解法ステップ

タスクCより優先度が高いタスクを確認します。
タスクAとタスクBが、Cに割り込めるタスクです。
Cの実行時間を基準に、AとBの実行による影響を加えます。
まずCの実行時間300ミリ秒に、AとBがそれぞれ1回実行される時間を加えると、550ミリ秒です。
その間に高優先度タスクが再び実行可能になるかを確認します。
Aの周期は400ミリ秒なので、開始時に加えて400ミリ秒後にも実行されます。Bの周期は650ミリ秒なので、600ミリ秒以内には2回目の実行はありません。
Aの2回目の実行時間50ミリ秒を加えます。
$550 + 50 = 600$ ミリ秒となります。

選択肢別の誤答解説

ア：300ミリ秒
タスクC自身の最大実行時間だけを答えています。高優先度のタスクA、Bによる割込みを考慮していません。
イ：550ミリ秒
AとBがそれぞれ1回ずつ実行される影響は加えていますが、Cの処理中に周期400ミリ秒のAが再び実行可能になることを見落としています。
ウ：600ミリ秒
Cの実行時間に、Aが2回、Bが1回実行される時間を加えています。
エ：700ミリ秒
Bが2回実行されるとして計算した場合などに得られる値ですが、Bの周期は650ミリ秒です。Cの応答時間が600ミリ秒以内なら、Bの2回目の実行は発生しません。

よくある誤解

Cの実行時間が、そのまま完了までの時間になると思う
プリエンプティブな優先度ベーススケジューリングでは、高優先度タスクに割り込まれた時間も完了までの時間に含まれます。
高優先度タスクは、それぞれ1回だけ実行されると思う
Cの処理が長ければ、周期の短いタスクは処理中に再び実行可能になることがあります。この問題ではAが2回実行されます。
周期が短い順に、単純にすべての実行時間を加える
応答時間内に何回実行されるかを、周期と経過時間から判断する必要があります。

補足コラム

このような問題では、応答時間を次の式で段階的に求める方法もあります。

R_{C} = C_{C} + ⌈ \frac{R _{C}}{T _{A}} ⌉ C_{A} + ⌈ \frac{R _{C}}{T _{B}} ⌉ C_{B}

ここで、

C

は最大実行時間、

T

は周期、

R_{C}

はタスクCの応答時間です。右辺の値を繰り返し計算し、値が変わらなくなったところが応答時間です。

初期値： $R_{C} = 300$
次の値： $300 + 1 \times 50 + 1 \times 200 = 550$
次の値： $300 + 2 \times 50 + 1 \times 200 = 600$
再計算しても600となるため、応答時間は600ミリ秒です。

FAQ

なぜAは2回実行されるのですか？
Aの周期は400ミリ秒です。Cの応答時間が600ミリ秒なので、Cが実行可能になった時点の実行に加え、400ミリ秒後の実行も応答時間内に発生します。

なぜBは1回だけなのですか？
Bの周期は650ミリ秒です。応答時間600ミリ秒の範囲内では、開始時の実行後に次の周期を迎えないためです。

割込みが起きると、タスクCの実行時間自体も増えますか？
C自身の実行時間は300ミリ秒のままです。ただし、割込み中はCが進まないため、実行可能になってから完了するまでの時間が長くなります。

関連キーワード: プリエンプティブ方式、優先度ベーススケジューリング、周期タスク、応答時間、最大実行時間

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

エンベデッドシステムスペシャリストを
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！