REAL-TIME SYSTEMS TECHNOLOGY

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

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社で自分に合うスクールを見つけましょう.後悔はさせません!

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

今回からは,動的優先度割り当てによるハード周期タスクとソフト非周期タスクのスケジューリングを説明します.

具体的には,異なる非周期サーバを紹介し,その目的はハード周期タスクのスケジュール可能性を低下しない範囲内で非周期タスクの応答時間を短くすることです.

周期タスクはEarliest Deadline First(EDF)によりスケジュールされます.

固定優先度割り当てに関して,動的スケジューリングは高いスケジュール可能上限を持ちます.

この高いスケジュール可能上限は,CPUを効率的に利用し,非周期サーバのCPU利用率を大きくし,非周期タスクの応答性を向上します.

例えば,同じCPU利用率\(U_1=U_2=0.3\)を持つ2つの周期タスクセットを考慮すると周期タスクの合計CPU利用率は\(U_p=0.6\)になります.

もし優先度が周期タスクにRMで割り当てられ,非周期タスクがSporadic Server(SS)で実行される場合,非周期サーバの最大CPU利用率は式\((16.1)\)により\(U_{SS}^{max}=(2-P)/P\)になり,
\(P=(U_1+1)(U_2+1)=1.69\)になります.

したがって,\(U_{SS}^{max} \simeq 0.183\)になります.

他方,もし周期タスクがEDFでスケジューリングされる場合,CPU利用率は1.0になるので,非周期サーバの最大CPU利用率は\(U_s=1-U_p=0.4\)まで増えます.

わかりやすくするために,全ての動的優先度の非周期サーバの性質は以下の5つの想定に基づきます.

  • 全ての周期タスク\(\tau_i : i=1, ..., n\)はハードデッドラインを持ち,スケジュール可能性はオフラインで(実行前に)保証されている.
  • 全ての非周期タスク\(J_i : i=1, ..., ,\)はデッドラインを持たないが,周期タスクのスケジュール可能性を低下させない範囲内で,できるだけ早くスケジュールされる.
  • 各々の周期タスク\(\tau_i\)は周期\(T_i\),最悪実行時間\(C_i\),相対デッドライン\(D_i\)(周期と同じ)を持つ.
  • 全ての周期タスクは時刻\(t=0\)で同時にリリースされる.
  • 各々の非周期タスクは最悪実行時間は既知だが,到着時刻は未知とする.

上記の想定のいくつかは,任意の位相や周期と相対デッドラインが異なる場合の周期タスクを扱うことに,簡単に制限を緩める(拡張する)ことができます.

まとめ

今回は,動的優先度の非周期サーバについて紹介しました.

動的優先度の非周期サーバでは,周期タスクはEDFでスケジュールされること,その性質は5つの想定に基づいていることがわかりました.

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

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

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

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

友だち追加

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

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

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