【第18回】元東大教員から学ぶリアルタイムシステム「固定優先度の非周期サーバのまとめ」

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

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

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

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

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

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

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

最適な固定優先度の非周期サーバは存在しない

前回のSlack Stealingは，全ての利用可能なスラックをできるだけ多く確保して，そのスラックを非周期タスクの実行に使います．

この理由により，Slack Stealingは最適な手法となります．

すなわち，各々の非周期タスクの応答時間を最短化することが可能になります．

残念ながら，Slack Stealingは非周期タスクの応答時間を最短化することに関して最適ではありません．

スラックが現在の時刻で利用可能になる場合，Slack Stealingはしばらくたってから非周期タスクをスケジュールする必要があるからです．

※定理17.1は，2つ以上の非周期タスクが同時にActiveにならない場合のみ成立します．

Tia，Liu，Shankerらは，もし周期タスクが固定優先度でスケジュールされる場合，各々の非周期タスクの応答時間を最小化し，周期タスクのスケジュール可能性を保証するスケジューリングが存在しないことを証明しました．

定理18.1：固定優先度の優先度順にソートされたあらゆる周期タスクセットと非周期タスクのキューイングポリシーによりソートされた非周期タスクにおいて，あらゆるソフト非周期タスクの応答時間を最短化するスケジューリングは存在しない．

証明：3つの周期タスクの最悪実行時間\(C_1=C_2=C_3=1\)，周期\(T_1=3\)，\(T_2=4\)，\(T_3=6\)を持ち，RMでスケジューリングされることを想定します．

上図の上部に非周期タスクを実行しない場合の周期タスクのスケジュールを示します．

時刻\(t=2\)に最悪実行時間\(C_{a_1}=1\)を持つ非周期タスク\(J_1\)が到着することを考慮します．

この場合，以下の2つの選択があります．

1. 時刻\(t=2\)で\(J_1\)をスケジュールしない．
   このケースでは，\(J_1\)の応答時間は1より大きくなり，最短値ではなくなります．
2. 時刻\(t=2\)で\(J_1\)をスケジュールする．
   このケースでは，時刻\(t=3\)に最悪実行時間\(C_{a_2}=1\)を持つ他の非周期タスク\(J_2\)を想定します．
   区間\([3, 6)\)では利用可能なスラックがないので，\(J_2\)は時刻\(t=6\)で開始し，時刻\(t=7\)で終了します（上図の中央部）．

しかし，ケース2の\(J_2\)の応答時間は最短値ではありません．

実際，もし\(J_1\)が時刻\(t=3\)でスケジュールされた場合，時刻\(t=4\)で他のスラックが利用可能になり，時刻\(t=5\)で\(J_2\)が終了していました（上図の下部）．

上図の例では，同時に\(J_1\)と\(J_2\)の応答時間を最短化するスケジューリングは不可能であることを示します．

もし\(J_1\)がすぐにスケジュールされる場合，\(J_2\)が最短にはなりません．

他方，もし\(J_2\)の応答時間を最短化するために\(J_1\)が遅延した場合，\(J_1\)の応答時間が長くなります．

したがって，非周期タスクの応答時間を最短化するためのスケジューリングは存在しません．□

この例は非周期タスクがあらかじめ到着することを知っているかどうかに関係なく適用できるので，定理18.1は以下の両方の場合に適用できることに注意して下さい．

• 千里眼：あらかじめ非周期タスクが到着する時刻や最悪実行時間がわかっている場合（証明はないがほぼ自明）
• オンラインスケジューリング：実行時に動的にスケジューリング場合（証明は定理18.2）

平均応答時間を最短化するための重要な結果を証明することに，この例を使うことができます．

定理18.2：固定優先度の優先度順にソートされたあらゆる周期タスクセットと非周期タスクのキューイングポリシーによりソートされた非周期タスクにおいて，あらゆるソフト非周期タスクの応答時間を最短化するオンラインスケジューリングは存在しない．

証明：上図の例から，もし各々のハイパーピリオドで\(J_1\)のみがある場合，できるだけ早く\(J_1\)をスケジューリングすることは平均応答時間を最短化することは簡単にわかります．

他方，もし各々のハイパーピリオドで\(J_1\)と\(J_2\)がある場合，できるだけ早く各々の非周期タスクをスケジューリングすることは平均応答時間を最短化するとは限りません．

これは，非周期タスクの到着をあらかじめ知らない場合，オンラインスケジューリングは非周期タスクをいつスケジューリングすればよいのかわからないことを意味します．□

固定優先度の非周期サーバのまとめ

今回は，固定優先度の非周期サーバのまとめを紹介しました．

下表にこれまでに紹介した固定優先度の非周期サーバを比較します．

固定優先度の非周期サーバ	性能	計算量	メモリ量	実装の難易度
バックグラウンドスケジューリング	△	◎	◎	◎
Polling Server	△	◎	◎	◎
Deferrable Server	○	◎	◎	◎
Priority Exchange	○	○	○	○
Sporadic Server	○	○	○	○
Slack Stealing	◎	△	△	△

次回からは動的優先度の非周期サーバを紹介します．

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

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

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

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

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