REAL-TIME SYSTEMS TECHNOLOGY

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

2020年10月2日

本記事の信頼性

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

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

これまでに紹介したスケジューリングは,周期タスクセットのみでした.

多くのリアルタイムアプリケーションでは,周期タスクだけでなく非周期タスク(Aperiodic Task)を扱います.

周期タスクと非周期タスクの重要度の指標は異なる場合があります.

周期タスクは時間駆動で,一定の間隔毎にハードリアルタイム性を保証しつつ重要な制御動作をする必要があります.

これに対して,非周期タスクは通常はイベント起動で動作し,特定のアプリケーション毎に以下の3種類の性質を持ちます.

  • ハードリアルタイム性の保証
  • ソフトリアルタイム性の保証
  • 保証不要(ノンリアルタイム性)

周期タスクと非周期タスクを持つハイブリッドなタスクセットの場合,カーネルのメインの目的は以下の2つになります.

  • 最悪の条件において全てのハードリアルタイムタスクのスケジュール可能性を保証
  • ソフトリアルタイムタスクやノンリアルタイムタスクの応答時間を短縮

時間制約を持つイベント駆動の非周期タスクは,実行環境において適切な想定をすることでオフラインで(受け入れ前に)保証することができます.

すなわち,各々の重要なイベント(非周期タスクの到着)の最大到着率を想定することです.

重要なイベントに関連する非周期タスクは,連続したジョブ間の最短到着間隔(非周期タスクの負荷の上限)を持つことを意味します.

最短到着間隔を持つ(周期以上の間隔で到着する)非周期タスクのことを散発的タスク(Sporadic Task)と呼びます.

また,散発的タスクは,最大到着率を想定して最大負荷の状況(最悪の条件)でリアルタイム性を保証します.

イベントの最大到着率の上限を事前に解析することができない場合,関連する非周期タスクはオフラインで(実行前に)リアルタイム性を保証することができません.

ただし,オンライン(実行時)の各々のジョブのリアルタイム性を保証できる可能性はあります.

オンラインで各々のジョブのリアルタイム性を保証する必要がある非周期タスクのことをファーム(firm)と呼びます.

ファーム非周期タスクが到着した時,カーネルはそのファーム非周期タスクがデッドラインまでに終了できるかどうかを検証する受け入れテストを実行します.

この受け入れテストが失敗した場合,そのファーム非周期タスクは受け入れを拒否されます.

すなわち,そのファーム非周期タスクは実行できません.

これからは,ハードリアルタイムの性質を持つ(ハード:Hard)周期タスクとソフトリアルタイムの性質を持つ(ソフト:Soft)非周期タスクを持つハイブリッドなタスクセットを扱うスケジューリングを紹介します.

これらのスケジューリングは,以下を想定します.

  • 周期タスクは固定優先度スケジューリングのRMでスケジュールされます.
  • 全ての周期タスクは,時刻\(t=0\)で同期して起動します.相対デッドラインは周期と同じになります.
  • 非周期タスクの到着時刻は不明です.
  • 明示的に指定しない場合,散発的タスクの最短到着間隔は,相対デッドラインと同じになります.
  • 全てのタスクは完全にプリエンプティブです.

動的優先度の非周期サーバは,固定優先度の非周期サーバの後に紹介します.

バックグラウンドスケジューリング

周期タスクが実行するリアルタイムシステムで非周期タスクを扱う最も簡単な方法は,非周期タスクをバックグラウンドで(実行可能状態の周期タスクのジョブがない時に)スケジュールすることです.

この方法の大きな問題は,周期タスクのCPU利用率が高い場合,非周期タスクの応答時間がとても長くなってしまうことです.

この理由により,バックグラウンドスケジューリングは,非周期タスクが厳しい時間制約を持たず,周期タスクのCPU利用率が高くない場合に適用できます.

Example of Background Scheduling of Aperiodic Tasks under RM

上図に2つの周期タスクがRMでスケジュールし,2つの非周期タスクがバックグラウンドで実行する例を示します.

周期タスクセットの合計CPU利用率は\(U=2/6+4/10=0.733\)で,RMにおける2タスクのスケジュール可能上限\(U_{lub} \simeq 0.828\)以下です.

なので,この周期タスクセットはRMでスケジュール可能です.

バックグラウンドスケジューリングは周期タスクの実行に影響しないため,このスケジュール可能性判定テストは,非周期タスクの存在により変わらないことに注意して下さい.

Scheduling Queues Requred for Background Scheduling

バックグラウンドスケジューリングの利点は単純なことです.

上図に示すように,2つのキューがスケジューリングを実装するために必要になります.

  • 高優先度キュー:周期タスクをRMでスケジューリング
  • 低優先度キュー:非周期タスクをFirst Come First Served(FCFS)でスケジューリング

これらの2つのキューの戦略は独立しています.

低優先度キューにある非周期タスクは,高優先度キューに周期タスクがない場合のみ実行します.

新しい周期タスクのジョブがリリースした時,非周期タスクはすぐにプリエンプションされて周期タスクのジョブを実行します.

まとめ

今回は,固定優先度の非周期サーバを紹介しました.

具体的には,以下の内容を解説しました.

  • 周期タスクと非周期タスクの両方を持つハイブリッドなタスクセットとその想定モデル
  • 周期タスクは固定優先度スケジューリングRMでスケジュール
  • 非周期タスクのスケジューリングの方法としてバックグラウンドスケジューリング(FCFSで非周期タスクを実行)

今後は,様々な固定優先度の非周期サーバを紹介していきます.

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

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

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

友だち追加

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

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

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