Online Adaptive Fault Tolerant based Feedback Control Scheduling Algorithm for Multiprocessor Embedded Systems

技術要約：マルチプロセッサ組込みシステムのためのオンライン適応型フォールトトレラント・フィードバック制御スケジューリング・アルゴリズム

問題提起
本論文は、開放的かつ予測不可能な環境下で動作するマルチプロセッサ組込みシステムの、制御とスケジューリングの協調設計（co-design）に内在する課題に対処している。レートモノトニック（RM）や最早デッドライン優先（EDF）といった従来のスケジューリング・アルゴリズムは、タスクのマッピングと最悪実行時間（WCET）が事前定義されているオープンループの仮定に依存している。しかし、現実世界のシナリオでは、環境の不確実性により、セーフティクリティカル（SC）タスクおよび非SCタスクの両方の実行時間が変動するため、デッドラインミスやリソースの過不足が生じる可能性がある。既存のフィードバック制御スケジューリング・アルゴリズム（FCSA）は、動的な負荷変動に対して最適な解を提供できないことが多く、現在のフォールトトレランス（FT）設計は、システム故障を考慮しない固定的なマッピングを前提としており、関心事が分離されていることが多い。著者らは、マルチプロセッサシステムにおいて、QoS（サービス品質）とデッドライン遵守を保証するために、オンライン適応、フォールトトレランス、およびフィードバック制御を統合した統一的なアプローチに関する文献上の空白を特定している。

手法
提案される手法は、分散共有ハードウェアプラットフォーム向けに設計された「オンライン適応型フォールトトレラント・フィードバック制御スケジューリング・アルゴリズム」を導入する。システムアーキテクチャはマルチプロセッサノードで構成され、各ノードにはSCタスク専用のコアと非SCタスク専用のコアの計2つのコアが含まれる。スケジューリング・アルゴリズムは、固定優先度プリエンプションを用いたリアルタイムオペレーティングシステム（RTOS）上で動作する。

手法の核となるのは、以下のコンポーネントからなるクローズドループ制御システムである。

1. システムモデル： マルチプロセッサシステムを、非線形な多入力多出力（MIMO）システムとしてモデル化する。制御入力はタスク周期（サンプリングレート）であり、出力変数は測定されたCPU利用率である。
2. コントローラ設計： 著者らは、以下の2つの主要要素からなる「オンライン適応型コントローラ」を採用している。
   • 逐次最小二乗法（RLS）モデル推定器： このコンポーネントは、指数忘却係数を用いて、システムのモデルパラメータをオンラインで識別する。これにより、変化する実行時間の偏差や実行時の状況の変化に適応してモデル係数を更新する。
   • 線形二次形式（LQ）最適コントローラ： このコントローラは、制御入力の大きな変化にペナルティを課しながら、参照コマンド（目標とするCPU利用率）を追従するように二次コスト関数を最小化する。コスト関数は、追従精度と制御調整の大きさのバランスをとる。
3. フォールトトレランスの統合： 設計には、過渡的または恒久的な故障が発生した場合でもSCタスクがデッドラインを満たすことを保証するためのフォールトトレランス・メカニズム（背景で言及されているアクティブ複製、再実行、またはチェックポインティングの概念など）が組み込まれている。コントローラは、故障が存在する場合でも、CPU利用率をスケジューラブルな境界内に維持することを目指す。

主な貢献

• 新規な統合： 本論文は、オンライン適応、フォールトトレランス、およびフィードバック制御スケジューリングを、特にマルチプロセッサ組込みシステム向けに統合した手法を提示しており、この文脈においてこれら3つの要素を同時に扱う最初の研究であると主張している。
• 適応メカニメント： 静的または非適応型のFCSA設計とは異なり、提案されたアルゴリズムはRLSベースの推定器を利用してシステムモデルを動的に更新するため、実際のタスク実行時間の事前知識なしに、動的な負荷変動や実行時間の変動に対処できる。
• ロバストな制御戦略： LQコントローラの使用により、システムを所望の利用率設定点に保持することで、過負荷を回避し、デッドラインミスの比率を最小限に抑え、CPU性能とリソース利用率を最適化することができる。

実験結果
著者らは、CPU利用率の制御に焦点を当てた3つの実験を通じて、手法の検証を行った。

1. 低利用シナリオ： 実際の実行時間が推定値の30%である状態（過小利用）から開始し、コントローラはタスクレートを増加させ、両プロセッサのCPU利用率を目標値である0.8123へと収束させた。
2. 過負荷シナリオ： 実際の実行時間が推定値の7倍に設定された状態（深刻な過負荷）において、コントローラはタスクレートを減少させた。モデル推定の不正確さによる初期の振動にもかかわらず、システムは速やかに0.8123の設定点へと収束した。
3. 動的負荷に対するロバスト性： システムに対し、特定のインターバル（300、400、800サンプルステップ目）で動的なワークロードの変化を与えた。オンライン適応型コントローラは、最小限の振動で利用率を設定点に維持し、急激な負荷変動に対するロバスト性を実証した。

結果は、タスクがデッドラインを満たしている限り、実際の実行時間が推定値よりも大幅に高い（最大7倍）場合でも、システムが安定していることを示している。ただし、実行時間がこの閾値を超えると、システムは不安定になり、振動とデッドラインミスが発生すると著者らは指摘している。

意義と主張
本論文は、提案された手法が、CPU性能とリソース利用率の観点からQoSを提供することにより、マルチプロセッサ組込みシステムにおける制御とスケジューリングの協調設計において優れたアプローチを提供すると主張している。その意義は、従来のオープンループまたは非適応型のフィードバック手法では達成が困難な、故障や動的な負荷変化が存在する状況下においても、システムの安定性を維持し、SCタスクのデッドラインを遵守できる能力にある。

著者らは、提案されたシステムは改善された安定性とリソース使用率を示しているものの、このようなフィードバック・スケジューリング・ベースの制御システムの実際の実装は「ほぼ完全に未解決の問題」として残っていると結論づけている。彼らは、今後の研究として、システム全体の性能をさらに向上させるために、より高度なCPU利用率モデルやハイブリッド・オンラインコントローラの開発に焦点を当てるべきであると示唆している。本論文は、すべてのリアルタイム・スケジューリング問題を解決すると主張しているのではなく、適応型かつフォールトトレラントなアプローチが、現代の組込み環境の不確実性に対処するための重要な一歩であることを位置づけている。