REAL-TIME SYSTEMS TECHNOLOGY

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

2021年1月3日

本記事の信頼性

  • リアルタイムシステムの研究歴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社で自分に合うスクールを見つけましょう.後悔はさせません!

動的優先度の非周期サーバのまとめ

実験的なシミュレーションの結果,性能面では,Improved Priority Exchange(IPE) Server,Earliest Deadline Late(EDL) Server,Improving TBS(TB*)が非周期応答性の低減に最も優れた結果を示していることが確認されています.

しかし,最適ではあるが,全体的に複雑なため,EDLは実用化には程遠いです.

一方,IPEとTB*は,計算オーバーヘッドを大幅に削減しながら,同等の性能を達成しています.

さらに,EDLとIPEの両方とも,タスクの周期がハーモニックの関係(タスクの長い周期が短い周期の整数倍)でない場合には,かなりのメモリ空間を必要とすることがあります.

Total Bandwidth Server(TBS)も良好な性能を示し,ほぼ最適なIPEに匹敵することもあります.

実装の複雑さが最も単純なものの一つであることから,TBSは実用的なシステムの良い候補になります.

また,TBSのデッドライン割り当てルールをチューニングすることで,最適なTB*の振る舞いまで非周期タスクの応答性を向上できます.

IPEやEDLと比較して,TB*は大きなメモリ容量を必要とせず,最適なデッドラインを\(\mathcal{O}(Nn)\)の計算量で計算できます.

ここで,\(N\)は各タスクの(TBSルール割り当てられる)最初のデッドラインを短縮するための最大ステップ数,\(n\)はタスク数です.

EDLサーバに関しては,最悪の場合\(N\)が大きくなる可能性があるため,疑似多項式的な計算量があります.

TBSとTB*の大きな問題点は,非周期タスクの実行を制御するために非周期サーバのバジェットを利用せず,各々のジョブの到着時に指定された最悪実行時間の知識に依存していることです.

このような知識が利用できなかったり,信頼できなかったり,(実行時間の変動が大きいために)悲観的になりすぎたりすると,ハードタスクはソフトタスクで発生する一時的なオーバーランから保護されず,デッドラインまでに実行が終了しなくなる可能性があります.

Constant Bandwidth Server(CBS)は,TBSと同等の性能を持ち,タスクのバンド幅の要件を設計時に指定された\(U_s\)の値に制限することで,テンポラルアイソレーション(時間的な分離)を提供するため,このような状況で効率的に利用できます.

下表は,動的優先度の非周期サーバの回で紹介した手法の性能,計算量,メモリ要件,実装の複雑さの観点からの定性的な評価を示しています.

動的優先度の非周期サーバ性能計算量メモリ要件実装の複雑さ
バックグラウンドスケジューリング
Dynamic Priority Exchange Server
Dynamic Slack Stealer
Total Bandwidth Server
Earliest Deadline Late Server
Improved Priority Exchange Server
Improving TBS
Constant Bandwidth Server

次回は,資源アクセスプロトコルを紹介します.

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

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

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

友だち追加

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

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

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