REAL-TIME SYSTEMS TECHNOLOGY

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

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

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

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

第17回リアルタイムシステム
【第17回】元東大教員から学ぶリアルタイムシステム「Slack Stealing」

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. リアルタイムシステムの記事一覧はこちらからどうぞ. 目次1 Slack Stealing2 Slack Stealingのスケジュ ...

続きを見る

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

リアルタイムシステム
元東大教員から学ぶリアルタイムシステム

こういった私から学べます. リアルタイムシステムとは,決められた時間(デッドライン)までに処理を完了しなければならない性質をもつシステムのことです. リアルタイムシステムは,ロボット,自動車や航空機な ...

続きを見る

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

前回の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でスケジューリングされることを想定します.

No Algorithm can Minimize Response Time of Every Aperiodic Request a
No Algorithm can Minimize Response Time of Every Aperiodic Request b
No Algorithm can Minimize Response Time of Every Aperiodic Request c

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

時刻\(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言語エンジニアになりたいあなたにおすすめのオンラインプログラミングスクール3社で自分に合うスクールを見つけましょう.

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

第19回リアルタイムシステム
【第19回】元東大教員から学ぶリアルタイムシステム「動的優先度の非周期サーバ」

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. リアルタイムシステムの記事一覧はこちらからどうぞ. 目次1 動的優先度の非周期サーバ2 まとめ 動的優先度の非周期サーバ 今回から ...

続きを見る

-REAL-TIME SYSTEMS, TECHNOLOGY
-, , , , , , , , , , , , , , , , , , , , , , , , , , , ,

© 2021 元東大教員/アメリカのスタートアップCTO