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

問題文

リアルタイムOSで用いられる、タスクがデッドラインを必ず守るデッドラインスケジューリングでは、周期タスクを図のように次の四つのパラメタ

r, C, D, T

（

0 < r + C \leq D \leq T

）の組みで表現することができる。

二つのタスクX、Yを

r = 0

、

D = T

という条件下で生成した場合、スケジュールが可能となる

C, D

の組合せはどれか。ここで、タスクはX、Yの順に起動され、優先度はXの方が高い。また、スケジューリングはプリエンプティブ方式であり、OSのオーバヘッドは考慮しない。

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

選択肢

ア：

イ：（正解）

ウ：

エ：

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

周期タスクの実行可能性判定【午前2解説】

正解の理由

各タスクは周期ごとに実行され、条件

r = 0

、

D = T

なので、タスクは周期の開始時に起動し、次の周期の開始までに実行を終えればよいです。

1プロセッサで実行する周期タスクの総実行時間が、単位時間当たりにどれだけ必要かを表す利用率は、次の式で求められます。

U = i \sum \frac{C _{i}}{T _{i}}

利用率が1を超えると、必要な実行時間がプロセッサの処理能力を上回るため、スケジュールできません。選択肢を確認すると、イの利用率は

\frac{1}{2} + \frac{2}{4} = 1

です。利用率だけでは実際に期限を守れるかまでは確定できませんが、イは次のようにスケジュールできます。

時刻0〜1：優先度の高いタスクXを実行
時刻1〜2：タスクYを実行
時刻2〜3：次に起動したタスクXを実行
時刻3〜4：実行するタスクなし

タスクXは周期2、タスクYは周期4で起動します。このスケジュールでは、XもYも各デッドラインまでに処理を完了できます。時刻4から同じスケジュールを繰り返せるため、イがスケジュール可能です。

解法ステップ

$D = T$ なので、各タスクの周期 $T$ を選択肢の期限 $D$ から読み取ります。
各タスクの利用率 $C / T$ を求め、合計します。
合計が1を超える選択肢は、処理能力が足りないため除外します。
利用率が1以下の選択肢について、優先度と実行順序を確認し、各タスクがデッドラインまでに完了するかを確かめます。

選択肢別の誤答解説

選択肢	利用率の計算	判定
ア	$\frac{1}{2} + \frac{2}{3} = \frac{7}{6} > 1$	必要な処理時間がプロセッサの処理能力を超えるため、スケジュールできません。
イ	$\frac{1}{2} + \frac{2}{4} = 1$	周期ごとの実行順序を確認すると、各デッドラインまでに処理を完了できます。
ウ	$\frac{2}{3} + \frac{2}{3} = \frac{4}{3} > 1$	必要な処理時間がプロセッサの処理能力を超えるため、スケジュールできません。
エ	$\frac{2}{4} + \frac{3}{4} = \frac{5}{4} > 1$	必要な処理時間がプロセッサの処理能力を超えるため、スケジュールできません。

よくある誤解

利用率が1以下なら必ず実行可能だと思う
利用率が1以下であることは、実行可能性を判断するための目安です。一般には、それだけで期限を守れるとは限らないため、実行順序も確認します。
期限 $D$ と周期 $T$ を別々に扱い忘れる
この問題では $D = T$ という条件があるため、選択肢の $D$ を周期 $T$ として利用率を計算できます。
優先度の高いタスクが常に先に完了すると考える
優先度の高いタスクは、起動後に実行中のタスクへ割り込めます。各タスクの実行時間と起動時刻を踏まえて、時系列で確認することが大切です。

補足コラム

この問題ではOSのオーバヘッドを考慮しないため、利用率の合計が1でも、プロセッサを空き時間なく使い続けるスケジュールが成立する場合があります。実際のシステムでは、タスク切替などのオーバヘッドも処理時間に加わるため、利用率に余裕を持たせる必要があります。

FAQ

Q. 利用率の合計が1を超えたら、なぜ実行できないのですか？
A. 長い時間で見ると、必要な処理時間がプロセッサの処理可能時間より多くなるためです。期限を守れないタスクが必ず生じます。

Q. 利用率の合計が1なら、必ず実行可能ですか？
A. 必ずとは限りません。タスクの起動時刻や優先度によっては期限を守れないことがあります。この問題では、実行順序を確認して期限内に完了することを確かめています。

関連キーワード: リアルタイムOS、周期タスク、デッドライン、タスク優先度、利用率、プリエンプティブスケジューリング

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！