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

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

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

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

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

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

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

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

Improved Priority Exchange （IPE）Server

Earliest Deadline Late（EDL） Serverは最適ですが，非常にオーバヘッドが大きいので，実用的ではありません．

しかし，主要なアイデアは，最適に近い振る舞いをする手法を開発することに役立ちます．

アイドル時間の算出には非常に長い処理時間が必要ですが，優先度交換の機構を利用することで回避することができます．

実際，この機構により，システムは周期タスクに先立ってアイドル時間の追跡を容易にし，正しい優先度レベルでアイドル時間を回収することができます．

周期タスクを先んじて実行する時，EDL Serverのアイドル時間はオフラインにあらかじめ算出され，非周期サーバは非周期タスクのスケジュールにそのアイドル時間を利用することができます．

後者の場合，あらかじめ算出したアイドル時間は実行する周期タスクの優先度レベルで非周期サーバの容量として保存することができます．

上記のアイデアは，Improved Priority Exchange（IPE）Serverと呼ばれる手法に利用されます．

具体的には，Dynamic Priority Exchange（DPE）ServerをEDLスケジューラのアイドル時間を利用するように修正します．

この手法は2つの主要な利点があります．

• 非周期サーバにはるかに効率的な補給ポリシーを達成すること
• 非周期サーバは周期的ではなく，システムの最高優先度でいつも実行できること

IPE Serverは以下の方法で定義されます．

• IPE Serverは非周期サーバの容量を持ち，初期値は0に設定します．
• 各々の時刻\(t = e_i + kH\)（\(0 \leq i \leq p\)かつ\(k \geq 0\)）において，\(\Delta_i\)ユニット時間の補給は非周期サーバの容量向けにスケジュールされます．
  すなわち，時刻\(t=e_0\)で非周期サーバは\(\Delta_0\)ユニット時間を受け取ります．（2つの配列\(\cal{E}\)と\(\cal{D}\)は前回定義しました．）
• 他の絶対デッドラインに関わらず，非周期サーバの優先度は，システムの最高優先度になります．
• IPE Serverの全ての他のルール（非周期タスクと周期タスクのジョブの実行，優先度交換，非周期サーバの容量の消費）はDPE Serverと同じになります．

上図に，前回の2番目と同様のタスクセットをIPE Serverでスケジュールする例を示します．

非周期サーバの容量の補給は，前回の1番目の図で示した関数\(\omega_{\tau}^{EDL}\)により設定されることに注意して下さい．

非周期タスクが時刻\(t=8\)に到着した時，非周期サーバは1ユニット時間を非周期タスクにすぐに割り当てます．

しかし，前の絶対デッドラインを交換することが原因で，他の2ユニット時間が絶対デッドライン12に対応する優先度レベルで利用可能になり，最初の1ユニット時間の後にすぐに割り当てられ，合計3ユニット時間を連続して実行します．

非周期サーバがさらに1ユニット時間を受信する時刻\(t=12\)では，最後の1ユニット時間が後に割り当てられます．

この状況では，応答時間の最適性は維持します．

後ほど説明する通り，最適なEDL ServerがIPE Serverより若干良くなることは非常にまれです．

すなわち，IPE Serverはほぼ最適な振る舞いをします．

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

IPE Serverのスケジュール可能性解析をするためには，DPE Server向けに行ったようなスケジュール間の変換を定義することが役に立ちます．

具体的には，IPE Serverにより生成されたスケジュール\(\sigma\)において，スケジュール\(\sigma'\)を以下のように構築します．

• 絶対デッドラインの交換（すなわち，対応する非周期サーバの容量の増加）の間における各々の周期タスクのジョブの実行は，非周期サーバの容量が減るまで延期します．
• 全ての他の周期タスクのジョブの実行は\(\sigma'\)として残ります．

このケースでは，非周期サーバは他のタスクに代替できません．

\(\sigma'\)は明確に定義され，不変です．すなわち，\(\sigma'\)は\(\sigma\)に依存せず，周期タスクセットにのみ依存します．

さらには，\(\sigma'\)は周期タスクセットに適用したEDLにより生成されるスケジュールになります．

※今回の図と前回の1番目の図を比較してみて下さい．

IPE Serverのスケジュール可能性解析の最適性は以下の定理に記載します．

定理24.1：CPU利用率\(U_p\)を持つ\(n\)個の周期タスクと対応するIPE Serverのセット（非周期サーバのパラメータは周期タスクセットに依存）において，全体のタスクセットは以下の条件を満たす場合においてのみスケジュール可能になる．

$$U_p \leq 1$$

（非周期サーバは自動的にバンド幅\(1-U_p\)を非周期タスクに割り当てます．）

証明：まず，「条件を満たす場合（if）」を証明します．

この条件は，EDFにおける周期タスクセットのスケジュール可能性解析の十分条件になります（※EDLはEDFの特定の実装）．

IPE Serverにより生成される各々のスケジュールにおいて，周期タスクのジョブの終了時刻は対応する\(\sigma'\)（EDLにおける周期タスクセットのスケジュール）のジョブの終了時刻を超えることはありません．

すなわち，周期タスクのジョブはデッドラインミスをしません．

次に，「この場合においてのみ（only if）」を証明します．

この条件は周期タスクセットのみの必要条件なので，自明です．□

IPE Serverの備考

利用されない周期タスクの実行時間の回収は，DPE Serverと同様の方法で行うことができます．

周期タスクが終了した時，空き時間は対応する非周期サーバの容量に追加されます．

この振る舞いは，DPE Serverと同様なので，システムのスケジュール可能性に影響しません．

IPE Serverを実装するためには，システムが実行する前に，2つの配列\(\cal{E}\)と\(\cal{D}\)を事前に算出しなければなりません．

IPE Serverにおける非周期サーバの容量の補給は，周期的ではないですが複雑度は変更しないので，DPE Serverと比較可能です．

IPE ServerとDPE Serverの大きな違いは，メモリ要求です．

実際，もし周期タスクの周期がハーモニックの関係（タスクの周期間の関係が整数倍）でない場合，非常に大きなハイパーピリオド\(H= \mathrm{lcm}(T_1, ..., T_n)\)になります．

なので，2つの配列\(\cal{E}\)と\(\cal{D}\)を格納するための巨大なメモリ空間が要求されます．

まとめ

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

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

• IPE Serverの特徴
• IPE Serverのスケジュール可能性解析
• IPE Serverの備考

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

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

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

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

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