リアルタイム性保証技術 ET/IoT2016 IPA SEC先端技術入門ゼミ リアルタイム性保証技術⼊⾨ 〜制限時間内に処理が終了することを保証するには？〜 2016年11⽉17⽇ ⾼⽥ 広章 名古屋⼤学 ⼤学院情報科学研究科 教授 附属組込みシステム研究センター⻑ NPO法⼈ TOPPERSプロジェクト 会⻑ APTJ株式会社 代表取締役会⻑・CTO Email: [email protected] URL: http://www.ertl.jp/~hiro/ Hiroaki Takada 1 リアルタイム性保証技術 1⽇コースのセミナーの⽬次 リアルタイムシステムとリアルタイム性保証 リアルタイムシステムの性能指標と最悪実行時間解析の困難性 リアルタイム処理の性能評価 リアルタイムスケジューリング理論 ▶ Rate Monotonic Analysis ▶ Critical Instant定理，最適な優先度割り付け ▶ プロセッサ使用率によるスケジュール可能性判定 ▶ 優先度逆転とその解決アプローチ，非周期タスクの扱い ▶ 過負荷に対する対策とQoS制御 ▶ リアルタイムスケジューリング理論の適用事例 最悪実行時間解析 アプリケーション統合のためのスケジューリング Hiroaki Takada 2 リアルタイム性保証技術 本⽇のセミナーの⽬次 リアルタイムシステムとリアルタイム性保証 を簡単に 最悪実行時間解析のさわりだけ リアルタイムシステムの性能指標と最悪実行時間解析の困難性 を簡単に リアルタイム処理の性能評価 リアルタイムスケジューリング理論 の前半だけを簡単に ▶ Rate Monotonic Analysis ▶ Critical Instant定理，最適な優先度割り付け ▶ プロセッサ使用率によるスケジュール可能性判定 ▶ 優先度逆転とその解決アプローチ，非周期タスクの扱い ▶ 過負荷に対する対策とQoS制御 ▶ リアルタイムスケジューリング理論の適用事例 アプリケーション統合のためのスケジューリング Hiroaki Takada 3 リアルタイム性保証技術 リアルタイムシステムと リアルタイム性保証 Hiroaki Takada 4 リアルタイム性保証技術 リアルタイムシステムとは? JISによる「実時間処理」の定義 ▶ 計算機外部の処理に関係を持ちながら，かつ外部の処理 によって定められる時間要件にしたがって，計算機の行な うデータ処理 リアルタイムシステム研究者の間で一般的な定義 ▶ 処理結果の正しさが，出力される結果値の正しさに加えて， 結果を出す時刻にも依存するようなシステム ! 単に速い応答を求められるシステムをリアルタイムシステム と呼ぶわけではない 多くの組込みシステムはリアルタイムシステム ▶ 組込みシステムは，機械・機器を制御するシステムであり， 制御対象の時間要件にしたがうことが必要 ▶ 一部の処理のみにリアルタイム性が求められる場合も Hiroaki Takada 5 リアルタイム性保証技術 用語説明：最悪実行時間，最大実行時間 ▶ 多くの場合，着目する時間が最も長くなる状況が最悪であ るため，一般には，最大時間のことを最悪時間という ※ WCET（Worst Case Execution Time）＝最悪実行時間 用語説明：悲観的な解析，安全な解析，タイトな解析 ▶ 解析結果が，真の最悪実行時間以上の値である場合に， 安全な解析と呼ぶ ▶ 解析結果と真の最悪実行時間の差が大きい場合に，悲観 的（pessimistic）な解析という．逆に，差が小さい場合に，タ イト（tight）な解析という ▶ 最悪実行時間解析にとって，安全であることは必須．タイト であることが望ましい ▶ 性能評価やテストは，安全な解析ではない Hiroaki Takada 6 リアルタイム性保証技術 リアルタイム性保証技術とは？ リアルタイム性保証技術の目的 ▶ システムが時間制約を満たすことを保証すること リアルタイム性保証技術の内容 ▶ リアルタイム性解析技術 … 狭い意味ではこちらだけ ▶ システムの時間的な振舞い（特に，最悪実行時間や最 悪応答時間）を解析（ないしは予測）するための技術 ▶ リアルタイムシステム構築技術 ▶ 時間制約を満たすようにシステムを構築するための技 術 ▶ 時間的な振舞いを解析しやすいようにシステムを構築 するための技術 Hiroaki Takada 7 リアルタイム性保証技術 時間制約解析/保証のアプローチ ▶ 徹底的なテストによる解析/保証 ▶ 現実的な方法で広く使われているが，限界がある ▶ テスト漏れを防ぐためには，時間制約を満たすのが難し くなる条件がわかっていること（最低限の予測可能性） が必要 ▶ 動作原理や理論に基づいた解析/保証 ▶ システムの動作原理に基づいて，時間制約が保証でき るかを理論的に解析する ▶ このアプローチが望ましいのは言うまでもないが，適用 できる状況が限定されたり，悲観的な結果になる場合 が多い ! 両者を補完的に使用するのが望ましい Hiroaki Takada 8 リアルタイム性保証技術 リアルタイムシステムの構築⽅法と解析/保証⽅法 RTOS無しでのシステム構築 ▶ 周期的に繰り返し実行する1つのループで，必要な処理を 順に実行する ▶ ループ内の処理が，周期内に完了するかの保証が必要 RTOSを用いたシステム構築 ▶ RTOS（リアルタイムOS）を用いて必要な処理を実行する ▶ 各タスクの最悪実行時間を解析した後，それらを並行実 行した場合のリアルタイム性保証を行う アプリケーション統合 ▶ 複数のアプリケーションを，1つの計算機上に統合する ▶ 個々のアプリケーションでリアルタイム性を保証すれば，統 合後の再保証はしなくて良いのが望ましい Hiroaki Takada 9 リアルタイム性保証技術 リアルタイムOS (RTOS) とは? ▶ 文字通り，リアルタイムシステムの構築に用いるためのOS RTOSの特徴 ▶ 具体的には，次のような特徴を持つOS（これらの特徴をす べて持っているとは限らない） （１） リアルタイムシステム向けの機能を持つ （２） 予測可能性を持つ （３） 時間制約を管理 ← 一部の研究ベースのRTOS （４） 高速に応答（制御対象に対して十分に） RTOSの最重要機能 ▶ マルチタスク機能とタスクスケジューリング機能が，システ ムが時間制約を満たすようにするために最も重要な機能 Hiroaki Takada 10 リアルタイム性保証技術 マルチタスクとスケジューリング タスクとは？ ! ここでの「タスク」は，「スレッド」と同義 ▶ プログラムの並行実行の単位 ▶ 1つのタスク中のプログラムは逐次的に実行される ▶ 異なるタスクのプログラムは並行して実行される ▶ プロセッサを抽象化・多重化したもの プロセッサ マルチタスク機能 抽象化 多重化 タスク … 仮想化されたプロセッサ ▶ 複数のタスクを疑似並列に実行するための機能 ▶ シングルプロセッサシステムでは，実際に同時に実行で きるタスクは1つのみ ▶ 複数のタスクが同時に実行しているかのように見せる Hiroaki Takada 11 リアルタイム性保証技術 用語説明 ▶ ディスパッチ（タスクディスパッチ，タスク切換え） ▶ プロセッサが実行するタスクを切り換えること ▶ ディスパッチを実現するOS内のモジュールがディスパッ チャ ▶ スケジューリング（タスクスケジューリング） ▶ どの時間にどのタスクを実行するかを決定すること ▶ 多くのRTOSにおいては，次に実行するタスクを決定す る処理 ▶ スケジューリングを実現するOS内のモジュールがスケ ジューラ（UNIX/Linuxのスケジューラは，スケジューリン グに加えて，ディスパッチも行う） ▶ スケジューリングアルゴリズム ▶ どのようにして次に実行するタスクを決定するか？ Hiroaki Takada 12 リアルタイム性保証技術 プリエンプティブな優先度ベーススケジューリング ! ほとんどのRTOSで採用されているスケジューリング方式 （RTOSによっては他の方式もサポートしている） ▶ 優先度ベーススケジューリング ▶ 最も優先度の高いタスクが実行される ▶ 優先度の高いタスクが実行できなくなるまで，優先度の 低いタスクは実行されない ▶ 同一優先度タスク間では FCFS（First Come First Served） ▶ プリエンプティブスケジューリング ▶ 優先度の高いタスクが実行可能になると，優先度の低 いタスクが実行途中でも，タスク切換えが起こる ▶ 実行可能になるきっかけは割込み ! 汎用OSのスケジューリングとは大きく異なる Hiroaki Takada 13 リアルタイム性保証技術 マルチタスクの必要性 タスク分割の基本的な考え方 ▶ 独立した処理の流れを独立したタスクに ▶ 複数のサブシステムに対する処理 ▶ 別々の入出力装置/イベントに対する処理 など リアルタイムシステムにおけるタスク分割の意義 ▶ 論理的な処理の順序と時間的な処理の順序を分離 ▶ プログラムは論理的な処理順序で記述 ▶ RTOSは時間的な処理順序に従って実行する ▶ プログラムの保守性・再利用性の向上 ▶ 外部で開発されたソフトウェア部品の導入を容易に Hiroaki Takada 14 リアルタイム性保証技術 論理的な処理順序と時間的な処理順序の分離 例として次の処理を行う場合を考える ▶ モータの制御処理を10ミリ秒周期で行う．1回の処理に最 大5ミリ秒かかる ▶ それと並行して，ビデオカメラで撮影した画像を認識する 処理を行う．1回の処理に最大100ミリ秒かかる RTOS無しで実現するには… ▶ モータの制御処理を，10ミリ秒周期で回るメインループで 実行する ▶ 画像認識プログラムを，5ミリ秒単位の20個の処理に分割 し，メインループの中で1つずつ順に実行する 画像認識プログラムの保守性・再利用性が低下 Hiroaki Takada 15 リアルタイム性保証技術 RTOS（マルチタスク機能）を用いると… ▶ 2つの処理を別々のタスク（モータ制御タスクと画像認識タ スク）で実現 ▶ モータ制御タスクの方に高い優先度を与える ▶ モータ制御タスクは10ミリ秒周期で起動する 起動 終了 起動 終了 実行継続 実行継続 モータ制御 タスク 画像認識 タスク プリエンプト 画像認識プログラムを分割する必要はなく，保守性・再 利用性が向上 Hiroaki Takada 16 リアルタイム性保証技術 論理的な処理順序と時間的な処理順序の分離が本質 ▶ モータ制御処理と画像認識処理は，論理的には独立の処 理 ▶ 時間的には，画像認識処理の途中にモータ制御処理を 割り込ませないと間に合わない ▶ プログラムは論理的な処理順序で（つまり両処理を独立し て）記述し，それを時間的な処理順序で実行するのは RTOSに任せる ▶ 時間制約を持ったプログラムの保守性・再利用性の向上 ▶ 外部で開発されたソフトウェア部品の導入を容易に ! ただし，この例の場合には，RTOSを使わずに，メインルー プと割込み処理で実現する方法もある Hiroaki Takada 17 リアルタイム性保証技術 RTOSを⽤いたシステムの時間制約保証 時間制約保証の流れ ▶ まず，各タスクの最悪実行時間を求める ▶ 最悪実行時間解析 ▶ リアルタイム処理の性能評価 ▶ 次に，マルチタスク環境下において，各タスクが時間制約 を満たすかを，リアルタイムスケジューリング理論により解 析する 最悪実行時間解析の課題 ▶ 最近のプロセッサ技術では，正確な最悪実行時間解析が 難しい．どうしても悲観的な結果になる ▶ 最悪実行時間解析と性能評価を併用することで，各タスク の最悪実行時間を見積もるのが現実的なアプローチ Hiroaki Takada 18 リアルタイム性保証技術 最悪実⾏時間解析 Hiroaki Takada 19 リアルタイム性保証技術 最悪実⾏時間解析 最悪実行時間解析とは？ ▶ （プログラムを単に実行するだけでなく）プログラムのソース コード，オブジェクトコードや，そこから抽出した構造情報 を用いて，プログラムの最悪実行時間（最大実行時間や 最小実行時間）を解析すること 最悪実行時間解析アプローチの分類 ▶ 静的解析 … 狭い意味での最悪実行時間解析 ▶ タイミングスキーマによる解析 ▶ 最適化問題への帰着による解析 ▶ 測定ベース解析 … 性能評価による方法 ▶ ハイブリッド解析 Hiroaki Takada 20 リアルタイム性保証技術 静的解析 ▶ 対象プログラムのソースコードまたはオブジェクトコードを， 実際に実行することなく（静的に）解析し，最悪実行時間を 求める 測定ベース解析 ▶ プログラムの実際に実行し，実行時間を計測することで， 最悪実行時間を求める ハイブリッド解析 ▶ 静的解析と測定ベース解析を組み合わせた手法 1. ソースコードの基本ブロック単位で，実行時間を測定 する（測定ベース解析） 2. ソースコードの構造やパスを解析する（静的解析） 3. 各実行パスの基本ブロックに，1の測定結果を当ては め，最悪実行時間を求める Hiroaki Takada 21 リアルタイム性保証技術 各解析アプローチの利点と欠点 手法 利点 欠点 ・実行時間が最悪となるパスを特 ・解析結果の精度が，アーキテクチャ 定できる のモデルの精度に依存してしまう ・モデルを作成するのが容易ではない 静的解析・実機での動作が不要 ・複雑なプログラムを解析する場合， 多くの注釈情報を与える必要がある ・最悪実行パスに加えて，実行頻 ・測定において，実行時間が最長とな 度や実行時間分布を取得できる るパスを通過させるのが難しく，真の ・実機やシミュレータを用いること 最悪実行時間よりも短い時間しか観 測定ベー で，実際の環境に近い動作環境 察できない場合がある（測定の網羅 ス解析 で測定できる 性の問題） ・ソフトウェアテストと組み合わせ て，WCET解析を実施できる ・静的解析と測定ベース解析の ハイブリッ 利点を両方得られる ド解析 Hiroaki Takada ・測定が必要であるため，精度を高め るためには，高いソースコードカバ レッジが必要（測定ベースアプローチ と同様の課題） 22 リアルタイム性保証技術 最悪実⾏時間解析の困難性 Hiroaki Takada 23 リアルタイム性保証技術 最悪実⾏時間解析の困難性 実行パスの変動 ▶ プログラムの実行時間は，入力データによる実行パスの変 動により変化 ▶ 起こり得ない実行パスがあると，部分的に最長実行時間と なるパスの合計が，全体の最長になるとは限らない 動作の予測が難しいハードウェアの影響 ▶ 近年のプロセッサには，プログラムの動作を予測し，予測 が当たった場合に高速に動作する機構が多数採用 ▶ そのような機構は，平均性能を大きく向上させるが，最悪 実行時間を見積もるためには大きな障害となる ▶ キャッシュ ▶ MMUのTLB（変換キャッシュ） ▶ 分岐予測 ▶投機的実行 Hiroaki Takada 24 リアルタイム性保証技術 キャッシュの影響の考慮 ▶ 命令キャッシュ：プログラムの実行する経路によって， キャッシュのヒット/ミスが変わる → 比較的予測しやすい ▶ データキャッシュ：プログラムのアクセスするメモリ番地に よって，キャッシュのヒット/ミスが変わる → 単純な変数アクセスなら予測しやすいが，配列やポイ ンタアクセスの解析は困難 ! 数多くの研究がされているが，解析を安全に行うと，悲観的 な結果となる場合が多い（条件によってはそれなりに当たる らしい） キャッシュの連想度の問題 ▶ 連想度（アソシアティビティ）不足により，メモリ配置が少し 変わるだけで，最悪実行時間が大きく変わる可能性 Hiroaki Takada 25 リアルタイム性保証技術 例）キャッシュの連想度不足による性能低下 ▶ ダイレクトマップ（1ウェイセットアソシエイティブ）方式の命 令キャッシュを考える 関数A() { for (……) { 関数B(); } } 関数B() { ……… } ソースコード Hiroaki Takada 関数A 関数A&B 関数B キャッシュ上 バイナリコード (メインメモリ上） 関数AとBが，たまたま 同一ラインにキャッシュ されるように配置される と，大幅に性能が低下 26 リアルタイム性保証技術 並行実行の影響 ▶ プログラムの実行中に割込みが発生すると，割込みハン ドラの中でキャッシュの内容が置き換わる → キャッシュミスの増加 ▶ 高優先度タスクにプリエンプトされた場合も同じ 注） 割込みハンドラや高優先度タスクそのものの実行時間 は，リアルタイムスケジューリング理論で扱える ▶ MMUのTLBや分岐予測にも同じ問題 並行実行の影響の考慮 ▶ 最も単純な方法は，割込み/プリエンプトの発生の度に，す べてのキャッシュが置き換わると考え，キャッシュミスによる 実行時間の増加を評価する方法 ! 数多くの研究がされている Hiroaki Takada 27 リアルタイム性保証技術 リアルタイムスケジューリング理論 Hiroaki Takada 28 リアルタイム性保証技術 リアルタイムスケジューリング理論の位置付け スケジューリングの重要性 ▶ 与えられた処理能力下で，各処理の時間制約を満たすた めにできる最も重要なことは，スケジューリングである リアルタイムスケジューリング理論とは？ ▶ 複数の時間制約を持った処理をスケジュールするための 方法と，各処理が時間制約を満たすことができるかどうか を数学的に証明するための理論 リアルタイムスケジューリング理論の歴史 ▶ 古典的な研究は1970年代にさかのぼる ▶ 1980年代後半から米国を中心に研究が進む ▶ 軍事システムの複雑化により，体系的なリアルタイムシ ステム設計手法が求められた ▶ 代表的な成果：rate monotonic analysis（RMA） Hiroaki Takada 29 リアルタイム性保証技術 システムに対する最⼤負荷 ▶ すべての処理が厳密に時間制約を満たして実行できるこ とを保証するためには，システムに対する最大負荷が決 まっていなければならない ▶ システムに対する最大負荷が決定できないか，最大負荷 を考えてシステム設計するのが現実的でない場合には， 現実的な最大負荷を想定して設計し，想定を超えた場合 に対する対策を実施する ▶ 最大負荷を決定/想定してシステムを設計 ▶ 最大負荷の一つの記述方法（タスクは繰り返し実行される ことを想定） 最大負荷 ＝ Σ1回の最大実行時間×最大実行頻度 各タスク Hiroaki Takada 30 リアルタイム性保証技術 Rate Monotonic Analysis (RMA) ▶ 代表的なリアルタイムスケジューリング理論体系 理論の基本的な前提 ▶ 静的優先度割付け下でプリエンプティブな優先度ベース スケジューリング ▶ システムの最大負荷が見積もれることが「保証」の基本的 な前提 ▶ 周期タスク（または最小起動間隔がわかっている非周期 タスク）を基本とする ▶ タスクの起動毎の最大実行時間がわかっていること ▶ シングルプロセッサを基本とする 理論ができること ▶ タスクがデッドラインを守ることを保証 ▶ 最適な（またはそれに近い）優先度割付け方法を与える Hiroaki Takada 31 リアルタイム性保証技術 Critical Instant 定理 ! RMAの出発点になる重要な定理 タスクセットに対する仮定 1. 周期タスク（または最小起動間隔がわかっている非周期タ スク）のみを考える 2. 各タスクの最大実行時間はあらかじめわかっている 3. 各タスクは周期の始めに実行可能になる 4. 各タスクのデッドラインは周期の終わり … 時間制約 5. タスク間に同期・通信がない 6. タスクは自ら実行を中断することはない 7. タスク切換え等のオーバヘッドは考えない 8. プロセッサが 1つのケースのみ考える ! タスクの起動位相（＝初期起動時刻）については何も仮定 しない（つまり任意の位相で起動されるものとして考える） Hiroaki Takada 32 リアルタイム性保証技術 定義（critical instant） ▶ あるタスクに対する critical instant とは，そのタスクが起動 されてから終了するまでの時間が最も長くなる状況 定理（critical instant 定理） ▶ 静的な優先度割付け下でプリエンプティブな優先度ベー ススケジューリングを行った場合，あるタスクに対する critical instant は，以下に挙げる前提条件下で，そのタス クが起動されると同時に，そのタスク以上の優先度を持つ すべてのタスクが同時に起動された場合 前提条件 ▶ タスクがデッドラインまでに実行を終える範囲（つまり，タ スクが多重に起動されることはない範囲）のみを考える ! すべてのタスクが時間制約を満たすかどうかを検証した い場合には，この前提条件で問題ない Hiroaki Takada 33 リアルタイム性保証技術 Critical Instant 定理から⾔えること スケジュール可能性の必要十分条件 ※ スケジュール可能： どんな状況でもタスクが時間制約 を満たせること ▶ critical instant に起動された場合でもデッドライン内に実 行が終わるなら，そのタスクはスケジュール可能 ▶ その逆も成立 ▶ タスクi（タスクのインデックスは優先度の高い順につける） がスケジュール可能となる必要十分条件式 i #t% ∃t, 0 < t ≤ Ti, ∑ Cj $ & ≤ t $ Tj & j=1 Tj：優先度が j番目のタスクの周期 Cj：優先度が j番目のタスクの最大実行時間 Hiroaki Takada 34 リアルタイム性保証技術 スケジュール可能性検証の例 ▶ 例に用いるタスクセット j 周期（Tj） 最大実行時間（Cj） 使用率（負荷） 1 5 2 40% 2 8 2 25% 3 14 3 21.4% タスク3に対する critical instant タスク1 タスク2 タスク3 0 5 10 15 t タスク3の最大応答時間は13 Hiroaki Takada 35 リアルタイム性保証技術 必要十分条件式による評価 i #t% ▶ 右式にあてはめると ∃t, 0 < t ≤ Ti, ∑ Cj $ & ≤ t $ Tj & j=1 !13 # !13 # !13 # t = 13 ≤ 14 で2 " $ + 2 " $ + 3" $ = 13 ≤ 13 " 5 $ " 8 $ "14 $ グラフでの表現 不等式の左辺（タスク1〜3によるプロセッサ 時間の最大要求量） 13 最初に交わった点が 最大応答時間 10 5 0 Hiroaki Takada 不等式の右辺（プロセッ サ時間の供給量） 5 10 13 t 36 リアルタイム性保証技術 最適な優先度割付け ▶ Critical instant定理と同じ前提条件下で，タスクにどのよう に優先度を割り付けるのが最適か？ ※ 最適の意味： その優先度割付けでスケジュールできないな ら，他の割付けでもスケジュールできない Rate Monotonic Scheduling（RMS） ▶ 周期が短いタスクほど高い優先度を割り付ける 急ぐタスクほど高い優先度 ▶ ここから Rate Monotonic Analysis という名称がついた 証明の本質部分 デッドライン 高優先度 低優先度 実行順序を交換してもデッドラインを満たせる Hiroaki Takada 37 リアルタイム性保証技術 プロセッサ使⽤率によるスケジュール可能性判定 ! RMAで最も有名な結果 RMSでタスクセットがスケジュール可能になる十分条件 n 右辺 Cj ≤ n(21/n −1) 1 1 j=1 Tj 2 0.83 3 0.78 n ： タスク数 ∞ 0.69 Tj ： 優先度が j 番目のタスクの周期 Cj ： 優先度が j 番目のタスクの最大実行時間 左辺： プロセッサの使用率 → 悲観的な上限値（あくまで十分条件） ! 失った使用率（最大31%）は，優先度を静的に割り付けて いることからくる本質的な限界 n ∑ Hiroaki Takada 38 リアルタイム性保証技術 静的優先度割付けの本質的な限界 1回めの周期 2回めの周期 タスクA タスクB 1回めの周期 デッドラインミス 2回めの周期 ▶ タスクBの1回めの周期の絶対デッドラインは，タスクAの2 回めの周期の絶対デッドラインよりも早いが，相対デッドラ インはタスクAの方が短いため，タスクAに対して高い優先 度が割り付けられている 優先度を固定していることから生じる本質的な限界 Hiroaki Takada 39 リアルタイム性保証技術 動的優先度割付けの場合 ▶ 優先度割付けを動的に変化させてもよい場合は，どうする のが最適か？（タスクセットに対する仮定は変えない） Earliest Deadline First Scheduling（EDFS） ▶ 絶対デッドラインが早いタスクから順に高い優先度を割り 付ける EDFSでタスクセットがスケジュール可能になる必要十分条件 n Cj ∑ Tj ≤ 1 j=1 プロセッサの能力を 100%使える n ： タスク数 Tj ： 優先度が j 番目のタスクの周期 Cj ： 優先度が j 番目のタスクの最大実行時間 左辺： プロセッサの使用率 Hiroaki Takada 40 リアルタイム性保証技術 RMSとEDFSの比較 ▶ EDFSの方がプロセッサを有効に利用できる ▶ RMSで優先度を静的に割り付けてくることから来る本質 的な限界 ▶ 周期の長いタスクの方が絶対デッドラインが早い場合 ▶ RMSの方が一時的な過負荷時の振舞いが予測しやすい ▶ （おおよそ）優先度の低いタスクから順にデッドラインを ミスする ▶ RMSの方が優先度のビット長が短くてよい ▶ RMS：8ビットあれば十分 ▶ EDFS：32ビットは欲しい ▶ RMSでは優先度の高いタスクに対してジッタが小さい ! EDFS擁護派からは反論もある → 一概にどちらが良いというわけではない Hiroaki Takada 41 リアルタイム性保証技術 タスクセットに対する仮定を緩める ▶ ここまで仮定していたタスクセットに対する仮定は，実際の システムに適用するには強すぎるため，仮定を緩めるため に数多くの理論拡張がされている デッドラインが周期の終わりと一致しない ▶ デッドラインが周期より短い場合 ▶ critical instant定理はそのまま成り立つ ▶ 相対デッドラインが短いタスクほど高い優先度を割り付 ける方法（deadline monotonic scheduling）が最適 ▶ デッドラインが周期より長い場合 ▶ critical instant定理は成り立たない ▶ 複雑にはなるが，それに相当する定理があり，最悪応 答時間の解析は可能 ▶ deadline monotonicが最適にならない場合がある Hiroaki Takada 42 リアルタイム性保証技術 タスク間に同期・通信がある ▶ 低優先度タスクに待たされる最大時間（これを最大ブロッ ク時間：Bi）がわかれば，その効果を入れた判定式を作る ことができる i $t& ∀i, ∃t, 0 < t ≤ Ti, ∑ Cj % ' + Bi ≤ t % Tj ' j=1 ▶ 最大ブロック時間を最小にする方策が重要になる 非周期タスクがある ▶ 最小起動間隔がない（つまり，連続して到着する可能性が ある）非周期タスクは扱えない（負荷に上限がない） ▶ 周期タスクが時間制約を満たすことを保証しつつ，非周期 タスクをできる限り早く実行する方法が提案されている Hiroaki Takada 43 リアルタイム性保証技術 マルチフレームタスクモデル ▶ タスクの周期毎の実行時間が長い周期で変動する場合 ▶ タスクが自ら実行を中断するケースにも適用可能 タスク切換えのオーバヘッドを考慮に入れる ▶ タスク間に同期・通信がない場合には，タスク切換え2回の 時間を，各タスクの最大実行時間に加えればよい ▶ タスク切換えの最大実行時間がわかっていることが前提 マルチプロセッサ ▶ 各タスクを実行するプロセッサを固定すれば，プロセッサ 毎に解析が可能 ▶ タスク間に同期・通信がある場合のアルゴリズムも提案され ている（かなり複雑） ▶ プロセッサを固定しないスケジューリングアルゴリズムも多 数存在するが，最悪時のプロセッサ使用率は低い Hiroaki Takada 44 リアルタイム性保証技術 優先度逆転 (Priority Inversion) ▶ 優先度の高い処理が優先度の低い処理に待たされること ▶ タスク間に同期（典型的には，排他制御）がある場合に は，優先度逆転は避けられない ▶ 最大ブロック時間とは，優先度逆転の最大時間 ▶ これが求まれば，スケジュール可能性解析が可能 制御できない（Uncontrolled）優先度逆転 ▶ 優先度逆転が無意味に長時間続く現象 ▶ 処理が時間制約を満たせなくなる大きな原因の1つ ▶ 処理能力に余裕があるにもかかわらず，（突然）時間制 約違反を起こす（ように見える） ▶ この問題が発生した有名な例：Mars Pathfinder ▶ 「制御できない優先度逆転」のことを単に「優先度逆転」と 呼ぶケースもある Hiroaki Takada 45 リアルタイム性保証技術 ▶ 高優先度タスクと低優先度タスクが，資源を共有しており， それに対する排他制御をセマフォSで実現している場合 実行可能に セマフォSを要求 優先度逆転 セマフォSを獲得 高優先度タスク セマフォSを獲得 セマフォSを解放 中優先度タスク 低優先度タスク t0 t1 t2 t3 t’4 時刻 優先度逆転の例 Hiroaki Takada 46 リアルタイム性保証技術 ▶ 高優先度タスクと低優先度タスクが，資源を共有しており， それに対する排他制御をセマフォSで実現している場合 実行可能に セマフォSを要求 セマフォSを獲得 優先度逆転 高優先度タスク 中優先度タスク 低優先度タスク t0 t1 t2 t3 t4 時刻 制御できない優先度逆転の例 Hiroaki Takada 47 リアルタイム性保証技術 優先度逆転の解決アプローチ クリティカルセクション中のタスク切換えの制限 ▶ クリティカルセクション中では，タスク切換えを行わない ▶ 割込みも禁止してしまう手もある ▶ 優先度上限プロトコル（Immediate Priority Ceiling Protocol， IPCP） 優先度継承 ▶ 優先度継承プロトコル（Priority Inheritance Protocol） ▶ 優先度上限プロトコル（Original Priority Ceiling Protocol， OPCP） クリティカルセクションのアボート ▶ 高優先度タスクを待たせる低優先度タスクのクリティカルセ クションの実行をアボートし，後で再実行する ▶ 低優先度タスクには，再実行のオーバヘッドがある Hiroaki Takada 48 リアルタイム性保証技術 優先度継承プロトコル ▶ 基本優先度継承プロトコル（Basic Priority Inheritance Protocol）と呼ぶ場合もある 着眼点 ▶ 高優先度のタスクを待たせている低優先度タスクは，待た せているタスクの（高い）優先度で実行すべきである ▶ 待たせているタスクの優先度を継承（inherit）する 正確に言うと… ▶ タスクは，自分自身の優先度と，自分が待たせているタス クの優先度の中で，最も高い優先度で実行する 利点 ▶ 優先度逆転の時間の上限を押さえることができる 欠点 ▶ 連鎖ブロッキング（chain blocking）が起こる Hiroaki Takada 49 リアルタイム性保証技術 実行可能に セマフォSを要求 優先度逆転 セマフォSを獲得 高優先度タスク 優先度継承 中優先度タスク セマフォSを解放 低優先度タスク t0 t1 t2 t3 t4 t5 時刻 優先度を継承しているため プリエンプトされない Basic Priority Inheritance Protocol による解決 Hiroaki Takada 50 リアルタイム性保証技術 ▶ 高優先度タスクと中優先度タスクがセマフォS1，中優先度 タスクと低優先度タスクがセマフォS2で排他制御している 場合 セマフォS1を要求 優先度逆転 セマフォS1を獲得 優先度 継承 セマフォS2を獲得 優先度継承 セマフォS2を要求 セマフォS1,S2を 解放 セマフォS2を解放 Chain Blocking（連鎖ブロッキング） Hiroaki Takada 51 リアルタイム性保証技術 優先度上限プロトコル (OPCP) ▶ 優先度上限プロトコル（Priority Ceiling Protocol）という名 称で最初に提案された手法 着眼点 ▶ 連鎖ブロッキングが起こらないように，クリティカルセクショ ンに入る時点で，早めにブロッキングする 正確に言うと… ▶ セマフォを取る可能性のあるタスクの中で，最も高い優先 度を持つタスクの優先度を，そのセマフォの優先度上限と 言う ▶ 自タスク以上の優先度上限を持ったセマフォが獲得されて いれば，クリティカルセクションに入らず，そのセマフォを 獲得しているタスクに優先度を継承させる Hiroaki Takada 52 リアルタイム性保証技術 利点 ▶ 低優先度タスクのクリティカルセクションに，高々1回しか待 たされない（single blocking） ▶ つまり，連鎖ブロッキングは起こらない ▶ デッドロック回避が実現できる 欠点 ▶ アルゴリズムがやや複雑で，直感的に理解しにくい Hiroaki Takada 53 リアルタイム性保証技術 優先度上限プロトコル (IPCP) ▶ 多くのRTOSで採用されており，単に優先度上限プロトコ ルというと，こちらを指すことが多い 着眼点 ▶ クリティカルセクションの中は優先度を上げて実行し，自分 をブロックする可能性のあるタスクは実行させない 正確に言うと… ▶ セマフォを獲得したら（クリティカルセクションに入ったら）， タスクの優先度をそのセマフォの優先度上限まで引き上 げる ▶ セマフォを解放したら元に戻す 利点 ▶ single blocking，デッドロック回避を実現できる ▶ 単純で実装オーバヘッドが小さい Hiroaki Takada 54 リアルタイム性保証技術 ▶ 高優先度タスクと中優先度タスクがセマフォS1，中優先度 タスクと低優先度タスクがセマフォS2で排他制御している 場合 セマフォS1を獲得． セマフォS1を要求 優先度をS1の優先度 上限まで引き上げる 優先度逆転 セマフォS2を獲得． 優先度をS2の優先度 上限まで引き上げる セマフォS2を要求 セマフォS1,S2を 解放 セマフォS2を解放 Immediate Ceiling Priority Protocol（IPCP）による解決 Hiroaki Takada 55 リアルタイム性保証技術 RTOSによるプロセッサ時間保護機能との関係 ▶ あるアプリケーションがプロセッサ時間を使い過ぎた結果， 他のアプリケーションが時間制約を違反しては困る ▶ 保護の単位となるアクセス主体が，与えられた以上のプロ セッサ時間を使うことを防止する μITRON4.0仕様のオーバランハンドラ機能 ▶ 最も基本的なプロセッサ時間保護機能 ▶ タスクが指定されたプロセッサ時間を使ったことを検出し， 例外処理を行うためのオーバランハンドラを起動する ▶ オーバランハンドラでどのような処理を行うかは，ユーザに 任されている（例えば，そのタスクの優先度を下げる と いった対応も可能） Hiroaki Takada 56 リアルタイム性保証技術 AUTOSAR OS仕様におけるタイミング保護機能 ▶ 処理単位毎のプロセッサ時間保護 ▶ タスクとISR（カテゴリ2のみ）の実行時間に上限を設ける ▶ タスクとISR（カテゴリ2のみ）の到着間隔に下限を設ける → RMAにおける Tj と Cj の違反を検出できる ▶ 排他制御区間のプロセッサ時間保護 ▶ タスクや割込みハンドラが，割込みを禁止する時間や， リソースを取得している時間に上限を設ける → RMAにおける Bj の違反を検出できる ▶ 違反時の振舞い いずれも，違反があった場合には，例外処理のためのプ ロテクションフックを起動 Hiroaki Takada 57 リアルタイム性保証技術 最後に宣伝 このセミナーを1日コースで聞きたい方は… ▶ NCES人材育成プログラム（NEP） 「リアルタイム性保証技術」 ▶ 日時：2017年1月13日（金）9：30〜17：00 ▶ 場所：名古屋大学 東山キャンパス ▶ 講師：高田広章，松原豊（名古屋大学） ▶ 受講料：2万円 ☞ http://www.nces.is.nagoya-u.ac.jp/NEP/courses.html 検索： NEP リアルタイム性保証技術 2016 Hiroaki Takada 58
© Copyright 2024 ExpyDoc
