【第20回】元東大教員から学ぶリアルタイムシステム「Dynamic Priority Exchange Server」

こういった私から学べます．

前回を読んでいない方はこちらからどうぞ．

リアルタイムシステムの記事一覧はこちらからどうぞ．

リアルタイムシステムで使われているリアルタイムOSは，主にC言語で書かれています．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！

Dynamic Priority Exchange (DPE) Server

Dynamic Priority Exchange （DPE）はSpuriとButtazzoらにより提案された非周期サーバで，Priority Exchange（PE）を拡張して動的優先度スケジューリング（EDF）に適用可能にしたものです．

DPEの主なアイデアは，非周期タスクが実行可能状態でない場合，非周期サーバをその実行時間と低優先度タスク（EDFでは遅い絶対デッドライン）の実行時間を交換させることです．

この方法では，非周期サーバの実行時間は周期タスクと交換されますが，（もしアイドル時間がない場合は）無駄にはなりません．

非周期サーバの実行時間はたとえ低優先度でも簡単に保存できます．

非周期タスクがシステムに到着した時，非周期タスクの実行時間は後で回収することができます．

DPEは，以下を定義します．

• DPEは周期\(T_s\)と容量\(C_s\)を持つ．
• 各々の周期の最初に，非周期サーバの容量は\(C_S^d\)（\(d\)は現在の非周期サーバの周期の絶対デッドライン）に設定される．
• \(i\)番目の周期タスクのジョブの各々の絶対デッドライン\(d\)は，非周期サーバの容量\(C_{S_i}^d\)（初期値は0）を持つ．
• 非周期サーバの容量（0より大きい）は，全ての周期タスクのジョブのように，非周期サーバの絶対デッドラインとEDFにより優先度を受け取る（タイブレーク方式は，非周期タスクを優先する）．
• システムの最高優先度のものが非周期サーバの容量\(C\)を持つ場合，以下が発生する．
  • もしシステムに非周期タスクがある場合，非周期タスクが終了するか非周期サーバの容量がなくなるまで実行される（各々の非周期タスクは最悪実行時間と同じ容量を消費する）．
  • もし非周期タスクがない場合，最も早い絶対デッドラインの周期タスクが実行される．最悪実行時間の長さと同じ非周期サーバの容量は，タスクの絶対デッドラインの非周期サーバの容量\(C_{S_i}^d\)に追加され，\(C\)から減る（すなわち，最高優先度の容量と周期タスクの絶対デッドライン（つまりEDFにおける優先度）が交換される）．
  • もし非周期タスクも周期タスクも実行可能状態でない場合，アイドル時間になり，容量\(C\)はなくなるまで消費される．

上図にDPEのスケジュール例を示します．

システムには，2つの周期タスク\(\tau_1\)と\(\tau_2\)，周期\(T_1=8\)，\(T_2=12\)，最悪実行時間\(C_1=2\)，\(C_2=3\)，非周期サーバDPEの周期\(T_s=6\)，容量\(C_s=3\)があります．

• 時刻0：（絶対デッドライン6を持つ）非周期サーバの容量が\(C_s=C_S^6=3\)に設定されるので，（絶対デッドライン8を持つ）非周期サーバの容量\(C_{S_1}^8\)と（絶対デッドライン12を持つ）非周期サーバの容量\(C_{S_2}^{12}\)は0に設定されます．
  非周期タスクがないので，2つの周期タスク\(\tau_1\)と\(\tau_2\)の最初のジョブが実行され，\(C_s\)は最初の3ユニット時間を消費します．
  同じ区間で，2ユニット時間を\(C_{S_1}^8\)に蓄積され，1ユニット時間を\(C_{S_2}^{12}\)に蓄積されます．
• 時刻3：\(C_{S_1}^8\)はシステムの最高優先度になります．
  非周期タスクが実行可能状態でないので，\(\tau_2\)は実行を継続し，\(C_{S_1}^8\)の2ユニット時間を消費し，\(C_{S_2}^{12}\)に蓄積されます．
  次の3ユニット時間分，CPU時間はアイドルで，\(C_{S_2}^{12}\)は完全に消費されます．
• 時刻6：非周期サーバの容量がシステムの最高優先度の時（非周期サーバの容量のタイブレーク方式はFIFO），非周期サーバの容量\(C_s=C_S^{12}\)は3に設定され，時刻\(t=8\)まで保持されることに注意して下さい．
• 時刻8：\(C_S^{12}\)の2ユニット時間が\(C_{S_1}^{16}\)と交換され，非周期サーバの3ユニット時間がCPUがアイドルになるまで消費されます．
• 時刻14：7ユニット時間を持つ非周期タスク\(J_1\)がシステムに到着します．
  \(C_S^{18}=2\)なので，\(J_1\)の最初の2ユニット時間が絶対デッドライン18で実行されます．
• 時刻16：次の2ユニット時間は，\(C_{S_2}^{24}\)を利用して，絶対デッドライン24で実行されます．
• 時刻18：最終的に，残りの3ユニット時間は絶対デッドライン24で実行されます．
  この理由は，時刻18で非周期サーバの容量\(C_S^{24}\)が3に設定されるからです．

DPEのスケジュール可能性解析

DPEと一緒にスケジュールされる周期タスクセットのスケジュール可能性を解析します．

直感的に，非周期サーバは他の周期タスクのように振る舞います．

非周期サーバと周期タスクの違いは，非周期サーバは自分の実行時間を低優先度タスクの実行時間と交換できることです．

ある程度の時間量を交換した時，1つ以上の低優先度タスクは高優先度レベルで実行し，これらの低優先度時間は非周期タスク向けに保存します．

また，この実行時間の交換は，スケジュール可能性に影響しません．

周期タスクはLiuとLaylandのスケジュール可能上限を利用して，リアルタイム性を保証できます．

$$U_p + U_s \leq 1$$

ここで，\(U_p\)は周期タスクの合計CPU利用率，\(U_s\)はDPEのCPU利用率を示します．

この結果を証明するために，DPEで生成されたスケジュール\(\sigma\)と以下の方法で生成されたスケジュール\(\sigma'\)を考慮します．

• DPEと周期タスク\(\tau_s\)（周期\(T_s\)，最悪実行時間\(C_s\)）を交換し，非周期サーバの容量が\(\sigma\)に消費される時はいつでも，\(\tau_s\)は\(\sigma'\)で実行します．
• 絶対デッドラインの交換する間の周期タスクのジョブの実行は，非周期サーバが減るまで延期します．
• 全ての他の周期タスクのジョブは\(\sigma\)で実行します．

DPEの定義から多くとも1つの非周期サーバの容量はいつでも\(\sigma\)で減り，\(\sigma'\)は明確に定義されています．

また，DPEにより生成される各々のスケジュール可能なスケジュールにおいて，全ての非周期サーバの容量はそれぞれの絶対デッドラインでなくなることを観察して下さい．

上図に最初の図のスケジュール\(\sigma\)から得られたスケジュール\(\sigma'\)を示します．

非周期サーバの容量を増やすことに関連する全ての周期タスクの実行は，同じ非周期サーバの容量が減る区間に関連して移動していることに注意して下さい．

また，スケジュール\(\sigma'\)は非周期タスクに依存せず，非周期サーバの特徴と周期タスクセットに依存することに注意して下さい．

この調査に基づいて，以下の定理を証明します．

定理20.1：合計CPU利用率\(U_p\)の周期タスクセットとCPU利用率\(U_s\)のDPEがある場合，全体のタスクセットは以下の条件を満たす場合においてのみEDFでスケジュール可能になる．

$$U_p + U_s \leq 1$$

証明：各々のスケジュール\(\sigma\)で，周期タスクのジョブの終了時刻はスケジュール\(\sigma'\)で関連するジョブの終了時刻以下になります．

したがって，もし\(\sigma'\)がスケジュール可能な場合，\(\sigma\)もスケジュール可能です．

すなわち，周期タスクセットはDPEでスケジュール可能になります．

逆に，十分な非周期タスクがある場合，\(\sigma'\)はDPEにより生成されたスケジュールになることを観察して下さい．

もし\(\sigma\)がスケジュール可能な場合，\(\sigma'\)もスケジュール可能になります．

したがって，この定理は証明されました．□

DPEによる空き時間の回収

ハードリアルタイムシステムにおいて，重要なタスクの十分テストは，最悪ケースのスケジュール可能性解析で行います．

すなわち，全てのタスクのジョブの最悪実行時間を想定しています．

しかし，最大負荷にならない時，実際実行時間は最悪実行時間より短くなりますが，空き時間を効果的に回収する方法は必ずしも明らかではありません．

DPEを利用することで，周期タスクより利用されなかった空き時間を非周期タスクの実行のために簡単に回収することができます．

周期タスクが終了する時はいつでも，その空き時間を関連する非周期サーバの容量に追加することで十分になります．

上図にこの機構の回収例を示します．

非周期サーバの容量のプロットからわかるように，最初の2つの周期タスクのジョブの終了時刻で，関連する非周期サーバの容量（\(C_{S_1}^8\)と\(C_{S_2}^{12}\)）は，保存された空き時間分を増加します．

この回収機構により，最初の非周期タスクは必要な7ユニット時間分をすぐに実行でき，時刻\(t=11\)で終了します．

回収機構が動作しない場合は，最初の非周期タスクは時刻\(t=12\)で終了するはずでした．

非周期サーバの容量として周期タスクセットの空き時間を回収することは，システムのスケジュール可能性に影響しません．

実際，あらゆる空き時間は優先度レベルの絶対デッドラインに関連して，タスクセットがリアルタイム性を保証できることがわかった時に，すでに割り当てられるからです．

したがって，空き時間は同じ絶対デッドラインが必要な場合，安全に利用することができます．

まとめ

今回は，Dynamic Priority Exchange （DPE）Serverについて紹介しました．

具体的には，以下の内容を解説しました．

• DPEの特徴
• DPEのスケジュール可能性解析
• DPEによる空き時間の回収

リアルタイムシステムで使われているリアルタイムOSは，主にC言語で書かれています．

私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！

次回はこちらからどうぞ．