REAL-TIME SYSTEMS TECHNOLOGY

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

2020年10月30日

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/Vyper,Java,Ruby,Go,Rust,D,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開
  • 2020年1月~現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務.2022年6月~現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO.
  • 最近は自然言語処理AIイーサリアムに関する有益な情報発信に従事.
    • (AI全般を含む)自然言語処理AIの論文の日本語訳や,AIチャットボット(ChatGPT,Auto-GPT,Gemini(旧Bard)など)の記事を50本以上執筆.アメリカのサンフランシスコ(広義のシリコンバレー)の会社でプロンプトエンジニア・マネージャー・Quality Assurance(QA)の業務委託の経験あり.
    • (スマートコントラクトのプログラミングを含む)イーサリアムや仮想通貨全般の記事を200本以上執筆.イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり.

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

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

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

リアルタイムシステムで使われているリアルタイム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でスケジューリングされることを想定します.

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言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

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

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