エンベデッドシステムスペシャリスト 2018年午前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解説】

正解の理由

各タスクの実行時間を周期で割ると、CPUの使用率が求められます。2つのタスクの使用率の合計が1を超える場合、長期的に必要な処理時間がCPUの処理能力を上回るため、スケジュールできません。

各選択肢を計算すると、次のとおりです。

選択肢	タスクXの使用率	タスクYの使用率	合計
ア	$1/2$	$2/3$	$7/6$
イ	$1/2$	$2/4$	$1$
ウ	$2/3$	$2/3$	$4/3$
エ	$2/4$	$3/4$	$5/4$

合計が1を超えるア、ウ、エはスケジュールできません。

一方、イは使用率の合計が1です。ただし、使用率が1以下であることだけでは、常にスケジュール可能とは限りません。そこで実際の実行順を確認します。

タスクXの周期と実行時間はそれぞれ2、1、タスクYはそれぞれ4、2です。タスクXの優先度が高いため、時間の流れは次のようになります。

時刻0〜1：タスクXを実行
時刻1〜2：タスクYを実行
時刻2〜3：次のタスクXを実行
時刻3〜4：タスクYを実行

タスクXは時刻2、4にそれぞれの期限までに処理を終えます。タスクYも時刻4までに処理を終え、期限を守ります。この4時間のスケジュールが繰り返されるため、イはスケジュール可能です。

解法ステップ

各タスクの使用率を「実行時間 $C$ ÷ 周期 $T$ 」で求めます。
2つの使用率を合計します。
合計が1を超える選択肢を除外します。
合計が1以下の選択肢は、優先度に従った実行順を確認します。
イは実行順を確認しても、すべてのタスクが期限内に完了します。

選択肢別の誤答解説

ア：使用率の合計は $1/2 + 2/3 = 7/6$ です。CPUの処理能力を超えるため、スケジュールできません。
イ：使用率の合計は $1/2 + 2/4 = 1$ です。実行順を確認すると、タスクX、Yの両方が期限までに処理を終えます。
ウ：使用率の合計は $2/3 + 2/3 = 4/3$ です。必要な処理時間がCPUの処理能力を超えます。
エ：使用率の合計は $2/4 + 3/4 = 5/4$ です。必要な処理時間がCPUの処理能力を超えます。

よくある誤解

使用率の合計が1以下なら必ずスケジュール可能だと思う
使用率の合計が1以下であることは、スケジュール可能性の確認に役立ちますが、それだけで十分とは限りません。期限や優先度も確認します。
期限時刻ちょうどの完了は期限遅れだと思う
処理が期限時刻までに完了すれば、期限を守っています。イではタスクYが時刻4に完了し、期限を守ります。
タスクYの実行中にタスクXが起動しても、Yはそのまま実行されると思う
この問題はプリエンプティブ方式です。優先度の高いタスクXが起動すると、タスクYの実行を中断してXを先に実行します。

補足コラム

今回のようにCPU使用率の合計が1の場合、CPUに空き時間がなくても、処理順が適切なら期限を守れます。イでは、タスクXが周期2で起動するため、タスクYはXの実行を挟みながら処理されます。

また、デッドラインスケジューリングでは、周期

T

はタスクの起動間隔、実行時間

C

は処理に必要な時間、期限

D

は起動から処理を終えるべき時刻を表します。この問題では

D = T

なので、各タスクの期限は次の起動時刻と一致します。

FAQ

Q. CPU使用率の合計が1を超えたら、必ずスケジュールできませんか？
A. はい。長期的に必要な処理時間がCPUの処理能力を上回るため、すべての期限を守ることはできません。

Q. CPU使用率の合計が1なら、必ず期限を守れますか？
A. いいえ。使用率だけでは判断できない場合があります。タスクの優先度や実際の実行順も確認してください。

Q. 時刻4ちょうどに完了するタスクYは、期限を守っていますか？
A. はい。期限時刻までに完了しているため、期限を守っています。

関連キーワード: 周期タスク、デッドライン、CPU使用率、プリエンプティブ方式、優先度スケジューリング

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

\ せっかくなら /

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

クイズ画面へ遷移する→

すぐに利用可能！