1 コースのセミナーの 次 リアルタイムシステムとリアルタイム性保証リアルタイムシステムの性能指標と最悪実行時間解析の困難性 リアルタイム処理の性能評価リアルタイムスケジューリング理論 Rate Monotonic Analysis Critical Instant 定理, 最適な優先度割り付け プ

Hiroaki Takada

リアルタイム性保証技術⼊⾨

〜制限時間内に処理が終了することを保証するには？〜

⾼⽥ 広章

2016年11⽉17⽇ 1 リアルタイム性保証技術 名古屋⼤学 ⼤学院情報科学研究科 教授 附属組込みシステム研究センター⻑ NPO法⼈ TOPPERSプロジェクト 会⻑ APTJ株式会社 代表取締役会⻑・CTO

Email: [email protected] URL: http://www.ertl.jp/~hiro/

Hiroaki Takada

1⽇コースのセミナーの⽬次

リアルタイムシステムとリアルタイム性保証 リアルタイムシステムの性能指標と最悪実行時間解析の困難性 リアルタイム処理の性能評価 リアルタイムスケジューリング理論

▶ Rate Monotonic Analysis

▶ Critical Instant定理，最適な優先度割り付け ▶ プロセッサ使用率によるスケジュール可能性判定 ▶ 優先度逆転とその解決アプローチ，非周期タスクの扱い ▶ 過負荷に対する対策とQoS制御 ▶ リアルタイムスケジューリング理論の適用事例 最悪実行時間解析 アプリケーション統合のためのスケジューリング 2 リアルタイム性保証技術

Hiroaki Takada

本⽇のセミナーの⽬次

リアルタイムシステムとリアルタイム性保証 最悪実行時間解析 リアルタイムシステムの性能指標と最悪実行時間解析の困難性 リアルタイム処理の性能評価 リアルタイムスケジューリング理論

▶ Rate Monotonic Analysis

▶ Critical Instant定理，最適な優先度割り付け ▶ プロセッサ使用率によるスケジュール可能性判定 ▶ 優先度逆転とその解決アプローチ，非周期タスクの扱い ▶ 過負荷に対する対策とQoS制御 ▶ リアルタイムスケジューリング理論の適用事例 アプリケーション統合のためのスケジューリング 3 リアルタイム性保証技術 のさわりだけ の前半だけを簡単に を簡単に を簡単に

Hiroaki Takada

リアルタイムシステムと

リアルタイム性保証

4 リアルタイム性保証技術

Hiroaki Takada

リアルタイムシステムとは?

JISによる「実時間処理」の定義 ▶ 計算機外部の処理に関係を持ちながら，かつ外部の処理 によって定められる時間要件にしたがって，計算機の行な うデータ処理 リアルタイムシステム研究者の間で一般的な定義 ▶ 処理結果の正しさが，出力される結果値の正しさに加えて， 結果を出す時刻にも依存するようなシステム ! 単に速い応答を求められるシステムをリアルタイムシステム と呼ぶわけではない 多くの組込みシステムはリアルタイムシステム ▶ 組込みシステムは，機械・機器を制御するシステムであり， 制御対象の時間要件にしたがうことが必要 ▶ 一部の処理のみにリアルタイム性が求められる場合も 5 リアルタイム性保証技術

Hiroaki Takada

用語説明：最悪実行時間，最大実行時間

▶ 多くの場合，着目する時間が最も長くなる状況が最悪であ

るため，一般には，最大時間のことを最悪時間という

※ _{WCET（Worst Case Execution Time）＝最悪実行時間}

用語説明：悲観的な解析，安全な解析，タイトな解析 ▶ 解析結果が，真の最悪実行時間以上の値である場合に， 安全な解析と呼ぶ ▶ 解析結果と真の最悪実行時間の差が大きい場合に，悲観 的（_{pessimistic）な解析という．逆に，差が小さい場合に，タ} イト（tight）な解析という ▶ 最悪実行時間解析にとって，安全であることは必須．タイト であることが望ましい ▶ 性能評価やテストは，安全な解析ではない 6 リアルタイム性保証技術

Hiroaki Takada

リアルタイム性保証技術とは？

リアルタイム性保証技術の目的 ▶ システムが時間制約を満たすことを保証すること リアルタイム性保証技術の内容 ▶ リアルタイム性解析技術 … 狭い意味ではこちらだけ ▶システムの時間的な振舞い（特に，最悪実行時間や最 悪応答時間）を解析（ないしは予測）するための技術 ▶ リアルタイムシステム構築技術 ▶時間制約を満たすようにシステムを構築するための技 術 ▶時間的な振舞いを解析しやすいようにシステムを構築 するための技術 7 リアルタイム性保証技術

Hiroaki Takada 時間制約解析_{/保証のアプローチ} ▶ 徹底的なテストによる解析/保証 ▶ 現実的な方法で広く使われているが，限界がある ▶ テスト漏れを防ぐためには，時間制約を満たすのが難し くなる条件がわかっていること（最低限の予測可能性） が必要 ▶ 動作原理や理論に基づいた解析/保証 ▶ システムの動作原理に基づいて，時間制約が保証でき るかを理論的に解析する ▶ このアプローチが望ましいのは言うまでもないが，適用 できる状況が限定されたり，悲観的な結果になる場合 が多い ! 両者を補完的に使用するのが望ましい 8 リアルタイム性保証技術

Hiroaki Takada

リアルタイムシステムの構築⽅法と解析/保証⽅法

RTOS無しでのシステム構築 ▶ 周期的に繰り返し実行する1つのループで，必要な処理を 順に実行する ▶ ループ内の処理が，周期内に完了するかの保証が必要 RTOSを用いたシステム構築 ▶ RTOS（リアルタイムOS）を用いて必要な処理を実行する ▶ 各タスクの最悪実行時間を解析した後，それらを並行実 行した場合のリアルタイム性保証を行う アプリケーション統合 ▶ 複数のアプリケーションを，1つの計算機上に統合する ▶ 個々のアプリケーションでリアルタイム性を保証すれば，統 合後の再保証はしなくて良いのが望ましい 9 リアルタイム性保証技術

Hiroaki Takada

リアルタイムOS (RTOS) とは?

▶ 文字通り，リアルタイムシステムの構築に用いるためのOS RTOSの特徴 ▶ 具体的には，次のような特徴を持つOS（これらの特徴をす べて持っているとは限らない） （１） リアルタイムシステム向けの機能を持つ （２） 予測可能性を持つ （３） 時間制約を管理 ← _{一部の研究ベースのRTOS} （４） 高速に応答（制御対象に対して十分に） RTOSの最重要機能 ▶ マルチタスク機能とタスクスケジューリング機能が，システ ムが時間制約を満たすようにするために最も重要な機能 10 リアルタイム性保証技術

Hiroaki Takada

マルチタスクとスケジューリング

タスクとは？ ▶ プログラムの並行実行の単位 ▶1つのタスク中のプログラムは逐次的に実行される ▶異なるタスクのプログラムは並行して実行される ▶ プロセッサを抽象化・多重化したもの マルチタスク機能 ▶ 複数のタスクを疑似並列に実行するための機能 ▶シングルプロセッサシステムでは，実際に同時に実行で きるタスクは1つのみ ▶複数のタスクが同時に実行しているかのように見せる 11 リアルタイム性保証技術 … 仮想化されたプロセッサ プロセッサ 抽象化 多重化 タスク ! ここでの「タスク」は，「スレッド」と同義

Hiroaki Takada 用語説明 ▶ ディスパッチ（タスクディスパッチ，タスク切換え） ▶  プロセッサが実行するタスクを切り換えること ▶ ディスパッチを実現するOS内のモジュールがディスパッ チャ ▶ スケジューリング（タスクスケジューリング） ▶ どの時間にどのタスクを実行するかを決定すること ▶  多くのRTOSにおいては，次に実行するタスクを決定す る処理 ▶  スケジューリングを実現するOS内のモジュールがスケ ジューラ（_{UNIX/Linuxのスケジューラは，スケジューリン} グに加えて，ディスパッチも行う） ▶  スケジューリングアルゴリズム ▶ どのようにして次に実行するタスクを決定するか？ 12 リアルタイム性保証技術

Hiroaki Takada プリエンプティブな優先度ベーススケジューリング ! ほとんどのRTOSで採用されているスケジューリング方式 （_{RTOSによっては他の方式}もサポートしている） ▶ 優先度ベーススケジューリング ▶ 最も優先度の高いタスクが実行される ▶ 優先度の高いタスクが実行できなくなるまで，優先度の 低いタスクは実行されない

▶ 同一優先度タスク間では FCFS（First Come First Served）

▶ プリエンプティブスケジューリング ▶ 優先度の高いタスクが実行可能になると，優先度の低 いタスクが実行途中でも，タスク切換えが起こる ▶ 実行可能になるきっかけは割込み ! 汎用OSのスケジューリングとは大きく異なる 13 リアルタイム性保証技術

Hiroaki Takada

マルチタスクの必要性

タスク分割の基本的な考え方 ▶ 独立した処理の流れを独立したタスクに ▶複数のサブシステムに対する処理 ▶別々の入出力装置/イベントに対する処理　など リアルタイムシステムにおけるタスク分割の意義 ▶ 論理的な処理の順序と時間的な処理の順序を分離 ▶プログラムは論理的な処理順序で記述 ▶RTOSは時間的な処理順序に従って実行する ▶ プログラムの保守性・再利用性の向上 ▶ 外部で開発されたソフトウェア部品の導入を容易に 14 リアルタイム性保証技術

Hiroaki Takada

論理的な処理順序と時間的な処理順序の分離

例として次の処理を行う場合を考える ▶ モータの制御処理を10ミリ秒周期で行う．1回の処理に最 大5ミリ秒かかる ▶ それと並行して，ビデオカメラで撮影した画像を認識する 処理を行う．_{1回の処理に最大100ミリ秒かかる} RTOS無しで実現するには… ▶ モータの制御処理を，10ミリ秒周期で回るメインループで 実行する ▶ 画像認識プログラムを，5ミリ秒単位の20個の処理に分割 し，メインループの中で_{1つずつ順に実行する} 画像認識プログラムの保守性・再利用性が低下 15 リアルタイム性保証技術

Hiroaki Takada RTOS（マルチタスク機能）を用いると… ▶ 2つの処理を別々のタスク（モータ制御タスクと画像認識タ スク）で実現 ▶ モータ制御タスクの方に高い優先度を与える ▶ モータ制御タスクは10ミリ秒周期で起動する 画像認識プログラムを分割する必要はなく，保守性・再 利用性が向上 16 リアルタイム性保証技術 プリエンプト 実行継続 実行継続 起動 _終了 起動 _終了 モータ制御
 タスク 画像認識
 タスク

Hiroaki Takada 論理的な処理順序と時間的な処理順序の分離が本質 ▶ モータ制御処理と画像認識処理は，論理的には独立の処 理 ▶ 時間的には，画像認識処理の途中にモータ制御処理を 割り込ませないと間に合わない ▶ プログラムは論理的な処理順序で（つまり両処理を独立し て）記述し，それを時間的な処理順序で実行するのは RTOSに任せる ▶  時間制約を持ったプログラムの保守性・再利用性の向上 ▶ 外部で開発されたソフトウェア部品の導入を容易に ! ただし，この例の場合には，RTOSを使わずに，メインルー プと割込み処理で実現する方法もある 17 リアルタイム性保証技術

Hiroaki Takada

RTOSを⽤いたシステムの時間制約保証

時間制約保証の流れ ▶ まず，各タスクの最悪実行時間を求める ▶最悪実行時間解析 ▶リアルタイム処理の性能評価 ▶ 次に，マルチタスク環境下において，各タスクが時間制約 を満たすかを，リアルタイムスケジューリング理論により解 析する 最悪実行時間解析の課題 ▶ 最近のプロセッサ技術では，正確な最悪実行時間解析が 難しい．どうしても悲観的な結果になる ▶ 最悪実行時間解析と性能評価を併用することで，各タスク の最悪実行時間を見積もるのが現実的なアプローチ 18 リアルタイム性保証技術

Hiroaki Takada

最悪実⾏時間解析

19 リアルタイム性保証技術

Hiroaki Takada

最悪実⾏時間解析

最悪実行時間解析とは？ ▶ （プログラムを単に実行するだけでなく）プログラムのソース コード，オブジェクトコードや，そこから抽出した構造情報 を用いて，プログラムの最悪実行時間（最大実行時間や 最小実行時間）を解析すること 最悪実行時間解析アプローチの分類 ▶ 静的解析 … 狭い意味での最悪実行時間解析 ▶タイミングスキーマによる解析 ▶最適化問題への帰着による解析 ▶ 測定ベース解析 … 性能評価による方法 ▶ ハイブリッド解析 20 リアルタイム性保証技術

Hiroaki Takada 静的解析 ▶ 対象プログラムのソースコードまたはオブジェクトコードを， 実際に実行することなく（静的に）解析し，最悪実行時間を 求める 測定ベース解析 ▶ プログラムの実際に実行し，実行時間を計測することで， 最悪実行時間を求める ハイブリッド解析 ▶ 静的解析と測定ベース解析を組み合わせた手法 1.  ソースコードの基本ブロック単位で，実行時間を測定 する（測定ベース解析） 2.  ソースコードの構造やパスを解析する（静的解析） 3.  各実行パスの基本ブロックに，_{1の測定結果を当ては} め，最悪実行時間を求める 21 リアルタイム性保証技術

Hiroaki Takada 各解析アプローチの利点と欠点 22 リアルタイム性保証技術 手法 利点 欠点 静的解析 ・実行時間が最悪となるパスを特 定できる ・実機での動作が不要 ・解析結果の精度が，アーキテクチャ のモデルの精度に依存してしまう ・モデルを作成するのが容易ではない ・複雑なプログラムを解析する場合， 多くの注釈情報を与える必要がある 測定ベー ス解析 ・最悪実行パスに加えて，実行頻 度や実行時間分布を取得できる ・実機やシミュレータを用いること で，実際の環境に近い動作環境 で測定できる ・ソフトウェアテストと組み合わせ て，WCET解析を実施できる ・測定において，実行時間が最長とな るパスを通過させるのが難しく，真の 最悪実行時間よりも短い時間しか観 察できない場合がある（測定の網羅 性の問題） ハイブリッ ド解析 ・静的解析と測定ベース解析の 利点を両方得られる ・測定が必要であるため，精度を高め るためには，高いソースコードカバ レッジが必要（測定ベースアプローチ と同様の課題）

Hiroaki Takada

最悪実⾏時間解析の困難性

23 リアルタイム性保証技術

Hiroaki Takada

最悪実⾏時間解析の困難性

実行パスの変動 ▶ プログラムの実行時間は，入力データによる実行パスの変 動により変化 ▶ 起こり得ない実行パスがあると，部分的に最長実行時間と なるパスの合計が，全体の最長になるとは限らない 動作の予測が難しいハードウェアの影響 ▶ 近年のプロセッサには，プログラムの動作を予測し，予測 が当たった場合に高速に動作する機構が多数採用 ▶ そのような機構は，平均性能を大きく向上させるが，最悪 実行時間を見積もるためには大きな障害となる ▶キャッシュ ▶ MMUのTLB（変換キャッシュ） ▶分岐予測 ▶ 投機的実行 24 リアルタイム性保証技術

Hiroaki Takada キャッシュの影響の考慮 ▶ 命令キャッシュ：プログラムの実行する経路によって， キャッシュのヒット_{/ミスが変わる} → 比較的予測しやすい ▶  データキャッシュ：プログラムのアクセスするメモリ番地に よって，キャッシュのヒット_{/ミスが変わる} → 単純な変数アクセスなら予測しやすいが，配列やポイ ンタアクセスの解析は困難 ! 数多くの研究がされているが，解析を安全に行うと，悲観的 な結果となる場合が多い（条件によってはそれなりに当たる らしい） キャッシュの連想度の問題 ▶ 連想度（アソシアティビティ）不足により，メモリ配置が少し 変わるだけで，最悪実行時間が大きく変わる可能性 25 リアルタイム性保証技術

Hiroaki Takada 例）キャッシュの連想度不足による性能低下 ▶ ダイレクトマップ（1ウェイセットアソシエイティブ）方式の命 令キャッシュを考える 26 リアルタイム性保証技術 関数_A() { for (……) { 関数B(); } } 関数_B() { ……… } ソースコード バイナリコード (メインメモリ上） 関数_A 関数_B キャッシュ上 関数_A&B 関数AとBが，たまたま 同一ラインにキャッシュ されるように配置される と，大幅に性能が低下

Hiroaki Takada 並行実行の影響 ▶ プログラムの実行中に割込みが発生すると，割込みハン ドラの中でキャッシュの内容が置き換わる → キャッシュミスの増加 ▶ 高優先度タスクにプリエンプトされた場合も同じ 注） _{割込みハンドラや高優先度タスクそのものの実行時間} は，リアルタイムスケジューリング理論で扱える ▶ MMUのTLBや分岐予測にも同じ問題 並行実行の影響の考慮 ▶ 最も単純な方法は，割込み/プリエンプトの発生の度に，す べてのキャッシュが置き換わると考え，キャッシュミスによる 実行時間の増加を評価する方法 ! 数多くの研究がされている 27 リアルタイム性保証技術

Hiroaki Takada

リアルタイムスケジューリング理論

28 リアルタイム性保証技術

Hiroaki Takada

リアルタイムスケジューリング理論の位置付け

スケジューリングの重要性 ▶ 与えられた処理能力下で，各処理の時間制約を満たすた めにできる最も重要なことは，スケジューリングである リアルタイムスケジューリング理論とは？ ▶ 複数の時間制約を持った処理をスケジュールするための 方法と，各処理が時間制約を満たすことができるかどうか を数学的に証明するための理論 リアルタイムスケジューリング理論の歴史 ▶ 古典的な研究は1970年代にさかのぼる ▶ 1980年代後半から米国を中心に研究が進む ▶軍事システムの複雑化により，体系的なリアルタイムシ ステム設計手法が求められた

▶ 代表的な成果：rate monotonic analysis（RMA）

29 リアルタイム性保証技術

Hiroaki Takada

システムに対する最⼤負荷

▶ すべての処理が厳密に時間制約を満たして実行できるこ とを保証するためには，システムに対する最大負荷が決 まっていなければならない ▶  システムに対する最大負荷が決定できないか，最大負荷 を考えてシステム設計するのが現実的でない場合には， 現実的な最大負荷を想定して設計し，想定を超えた場合 に対する対策を実施する ▶  最大負荷を決定/想定してシステムを設計 ▶ 最大負荷の一つの記述方法（タスクは繰り返し実行される ことを想定） 30 リアルタイム性保証技術 最大負荷 ＝ 1

Σ

回の最大実行時間×最大実行頻度 各タスク

Hiroaki Takada

Rate Monotonic Analysis (RMA)

▶ 代表的なリアルタイムスケジューリング理論体系 理論の基本的な前提 ▶ 静的優先度割付け下でプリエンプティブな優先度ベース スケジューリング ▶ システムの最大負荷が見積もれることが「保証」の基本的 な前提 ▶周期タスク（または最小起動間隔がわかっている非周期 タスク）を基本とする ▶タスクの起動毎の最大実行時間がわかっていること ▶ シングルプロセッサを基本とする 理論ができること ▶ タスクがデッドラインを守ることを保証 ▶ 最適な（またはそれに近い）優先度割付け方法を与える 31 リアルタイム性保証技術

Hiroaki Takada

Critical Instant 定理

タスクセットに対する仮定 1.  周期タスク（または最小起動間隔がわかっている非周期タ スク）のみを考える 2.  各タスクの最大実行時間はあらかじめわかっている 3.  各タスクは周期の始めに実行可能になる 4.  各タスクのデッドラインは周期の終わり … 時間制約 5.  タスク間に同期・通信がない 6.  タスクは自ら実行を中断することはない 7.  タスク切換え等のオーバヘッドは考えない 8.  プロセッサが 1つのケースのみ考える ! タスクの起動位相（＝初期起動時刻）については何も仮定 しない（つまり任意の位相で起動されるものとして考える） 32 リアルタイム性保証技術 ! RMAの出発点になる重要な定理

Hiroaki Takada 定義（_{critical instant）} ▶ あるタスクに対する critical instant とは，そのタスクが起動 されてから終了するまでの時間が最も長くなる状況 定理（_{critical instant 定理）} ▶ 静的な優先度割付け下でプリエンプティブな優先度ベー ススケジューリングを行った場合，あるタスクに対する critical instant は，以下に挙げる前提条件下で，そのタス クが起動されると同時に，そのタスク以上の優先度を持つ すべてのタスクが同時に起動された場合 前提条件 ▶ タスクがデッドラインまでに実行を終える範囲（つまり，タ スクが多重に起動されることはない範囲）のみを考える ! すべてのタスクが時間制約を満たすかどうかを検証した い場合には，この前提条件で問題ない 33 リアルタイム性保証技術

Hiroaki Takada

Critical Instant 定理から⾔えること

スケジュール可能性の必要十分条件 ※ _{スケジュール可能： どんな状況でもタスクが時間制約} を満たせること ▶ critical instant に起動された場合でもデッドライン内に実 行が終わるなら，そのタスクはスケジュール可能 ▶ その逆も成立 ▶ タスクi（タスクのインデックスは優先度の高い順につける） がスケジュール可能となる必要十分条件式 T_j：優先度が _{j番目のタスクの周期} C_j：優先度が _{j番目のタスクの最大実行時間} 34 リアルタイム性保証技術

∃t, 0 < t ≤ T

i

,

C

j

t

T

j

#

$$

%

&&

j=1 i

∑

≤ t

Hiroaki Takada スケジュール可能性検証の例 ▶ 例に用いるタスクセット 35 リアルタイム性保証技術 j 周期（_Tj） 最大実行時間（_Cj） 使用率（負荷） 1 5 2 40% 2 8 2 25% 3 14 3 21.4% タスク1 タスク2 タスク3 t 15 10 5 0 タスク₃に対する _{critical instant} タスク₃の最大応答時間は₁₃

Hiroaki Takada 必要十分条件式による評価 ▶ 右式にあてはめると グラフでの表現 36 リアルタイム性保証技術

t = 13 ≤ 14

2

13

5

!

""

#

$$

+ 2

13

8

!

""

#

$$

+ 3

13

14

!

""

#

$$

= 13 ≤ 13

で

∃t, 0 < t ≤ T

i

,

C

j

t

T

j

#

$$

%

&&

j=1 i

∑

≤ t

最初に交わった点が 最大応答時間 不等式の右辺（プロセッ サ時間の供給量） （タスク1〜3によるプロセッサ 時間の最大要求量） 不等式の左辺 t 0 5 10 13 5 13 10

Hiroaki Takada

最適な優先度割付け

▶ Critical instant定理と同じ前提条件下で，タスクにどのよう に優先度を割り付けるのが最適か？ ※ _{最適の意味： その優先度割付けでスケジュールできないな} ら，他の割付けでもスケジュールできない

Rate Monotonic Scheduling（RMS）

▶ 周期が短いタスクほど高い優先度を割り付ける

急ぐタスクほど高い優先度

▶ ここから Rate Monotonic Analysis という名称がついた

証明の本質部分 37 リアルタイム性保証技術 実行順序を交換してもデッドラインを満たせる 高優先度 低優先度 デッドライン

Hiroaki Takada

プロセッサ使⽤率によるスケジュール可能性判定

! RMAで最も有名な結果 RMSでタスクセットがスケジュール可能になる十分条件 n ： タスク数

T

j ： 優先度が j 番目のタスクの周期

C

j ： 優先度が j 番目のタスクの最大実行時間 左辺： プロセッサの使用率 → 悲観的な上限値（あくまで十分条件） ! 失った使用率（最大_{31%）は，優先度を静的に割り付けて} いることからくる本質的な限界 38 リアルタイム性保証技術

C

j

T

j

≤ n(2

1/n

−1)

j=1 n

∑

n 右辺 1 1 2 0.83 3 0.78 ∞ _0.69

Hiroaki Takada 静的優先度割付けの本質的な限界 ▶ タスクBの1回めの周期の絶対デッドラインは，タスクAの2 回めの周期の絶対デッドラインよりも早いが，相対デッドラ インはタスク_{Aの方が短いため，タスクAに対して高い優先} 度が割り付けられている 優先度を固定していることから生じる本質的な限界 39 リアルタイム性保証技術 タスクA タスクB 1回めの周期 2回めの周期 1回めの周期 2回めの周期 デッドラインミス

Hiroaki Takada

動的優先度割付けの場合

▶ 優先度割付けを動的に変化させてもよい場合は，どうする

のが最適か？（タスクセットに対する仮定は変えない） Earliest Deadline First Scheduling（EDFS）

▶ 絶対デッドラインが早いタスクから順に高い優先度を割り 付ける EDFSでタスクセットがスケジュール可能になる必要十分条件 n ： タスク数

T

j ： 優先度が j 番目のタスクの周期

C

j ： 優先度が j 番目のタスクの最大実行時間 左辺： プロセッサの使用率 40 リアルタイム性保証技術

C

j

T

j

≤ 1

j=1 n

∑

プロセッサの能力を

_100%

_使える

Hiroaki Takada RMSとEDFSの比較 ▶ EDFSの方がプロセッサを有効に利用できる ▶ RMSで優先度を静的に割り付けてくることから来る本質 的な限界 ▶ 周期の長いタスクの方が絶対デッドラインが早い場合 ▶ RMSの方が一時的な過負荷時の振舞いが予測しやすい ▶ （おおよそ）優先度の低いタスクから順にデッドラインを ミスする ▶ RMSの方が優先度のビット長が短くてよい ▶ RMS：8ビットあれば十分 ▶ EDFS：32ビットは欲しい ▶ RMSでは優先度の高いタスクに対してジッタが小さい ! EDFS擁護派からは反論もある → 一概にどちらが良いというわけではない 41 リアルタイム性保証技術

Hiroaki Takada

タスクセットに対する仮定を緩める

▶ ここまで仮定していたタスクセットに対する仮定は，実際の システムに適用するには強すぎるため，仮定を緩めるため に数多くの理論拡張がされている デッドラインが周期の終わりと一致しない ▶ デッドラインが周期より短い場合 ▶critical instant定理はそのまま成り立つ ▶相対デッドラインが短いタスクほど高い優先度を割り付

ける方法（deadline monotonic scheduling）が最適

▶ デッドラインが周期より長い場合 ▶critical instant定理は成り立たない ▶複雑にはなるが，それに相当する定理があり，最悪応 答時間の解析は可能 ▶deadline monotonicが最適にならない場合がある 42 リアルタイム性保証技術

Hiroaki Takada タスク間に同期・通信がある ▶ 低優先度タスクに待たされる最大時間（これを最大ブロッ ク時間：_Bi）がわかれば，その効果を入れた判定式を作る ことができる ▶ 最大ブロック時間を最小にする方策が重要になる 非周期タスクがある ▶ 最小起動間隔がない（つまり，連続して到着する可能性が ある）非周期タスクは扱えない（負荷に上限がない） ▶ 周期タスクが時間制約を満たすことを保証しつつ，非周期 タスクをできる限り早く実行する方法が提案されている 43 リアルタイム性保証技術

∀i, ∃t, 0 < t ≤ T

i

,

C

j

t

T

j

$

%%

&

''

j=1 i

∑

+ B

i

≤ t

Hiroaki Takada マルチフレームタスクモデル ▶ タスクの周期毎の実行時間が長い周期で変動する場合 ▶ タスクが自ら実行を中断するケースにも適用可能 タスク切換えのオーバヘッドを考慮に入れる ▶ タスク間に同期・通信がない場合には，タスク切換え2回の 時間を，各タスクの最大実行時間に加えればよい ▶ タスク切換えの最大実行時間がわかっていることが前提 マルチプロセッサ ▶ 各タスクを実行するプロセッサを固定すれば，プロセッサ 毎に解析が可能 ▶ タスク間に同期・通信がある場合のアルゴリズムも提案され ている（かなり複雑） ▶ プロセッサを固定しないスケジューリングアルゴリズムも多 数存在するが，最悪時のプロセッサ使用率は低い 44 リアルタイム性保証技術

Hiroaki Takada

優先度逆転 (Priority Inversion)

▶ 優先度の高い処理が優先度の低い処理に待たされること ▶タスク間に同期（典型的には，排他制御）がある場合に は，優先度逆転は避けられない ▶ 最大ブロック時間とは，優先度逆転の最大時間 ▶これが求まれば，スケジュール可能性解析が可能 制御できない（_{Uncontrolled）優先度逆転} ▶ 優先度逆転が無意味に長時間続く現象 ▶ 処理が時間制約を満たせなくなる大きな原因の1つ ▶処理能力に余裕があるにもかかわらず，（突然）時間制 約違反を起こす（ように見える） ▶ この問題が発生した有名な例：Mars Pathfinder ▶ 「制御できない優先度逆転」のことを単に「優先度逆転」と 呼ぶケースもある 45 リアルタイム性保証技術

Hiroaki Takada ▶ 高優先度タスクと低優先度タスクが，資源を共有しており， それに対する排他制御をセマフォ_{Sで実現している場合} 46 リアルタイム性保証技術 優先度逆転の例 実行可能に セマフォSを要求 セマフォSを獲得 高優先度タスク 中優先度タスク 低優先度タスク 時刻

t

₀

t

₁

t

₂

t

₃

t’

₄ セマフォSを獲得 セマフォSを解放 優先度逆転

Hiroaki Takada ▶ 高優先度タスクと低優先度タスクが，資源を共有しており， それに対する排他制御をセマフォ_{Sで実現している場合} 47 リアルタイム性保証技術 制御できない優先度逆転の例 優先度逆転 実行可能に セマフォSを要求 セマフォSを獲得 高優先度タスク 中優先度タスク 低優先度タスク 時刻

t

₀

t

₁

t

₂

t

₃

t

₄

Hiroaki Takada

優先度逆転の解決アプローチ

クリティカルセクション中のタスク切換えの制限

▶ クリティカルセクション中では，タスク切換えを行わない

▶割込みも禁止してしまう手もある

▶ 優先度上限プロトコル（Immediate Priority Ceiling Protocol，

IPCP） 優先度継承

▶ 優先度継承プロトコル（Priority Inheritance Protocol）

▶ 優先度上限プロトコル（Original Priority Ceiling Protocol，

OPCP） クリティカルセクションのアボート ▶ 高優先度タスクを待たせる低優先度タスクのクリティカルセ クションの実行をアボートし，後で再実行する ▶ 低優先度タスクには，再実行のオーバヘッドがある 48 リアルタイム性保証技術

Hiroaki Takada

優先度継承プロトコル

▶ 基本優先度継承プロトコル（Basic Priority Inheritance

Protocol）と呼ぶ場合もある 着眼点 ▶ 高優先度のタスクを待たせている低優先度タスクは，待た せているタスクの（高い）優先度で実行すべきである ▶待たせているタスクの優先度を継承（inherit）する 正確に言うと… ▶ タスクは，自分自身の優先度と，自分が待たせているタス クの優先度の中で，最も高い優先度で実行する 利点 ▶ 優先度逆転の時間の上限を押さえることができる 欠点 ▶ 連鎖ブロッキング（chain blocking）が起こる 49 リアルタイム性保証技術

Hiroaki Takada 50 リアルタイム性保証技術

Basic Priority Inheritance Protocol による解決

実行可能に セマフォSを要求 セマフォSを獲得 高優先度タスク 中優先度タスク 低優先度タスク 時刻

t

₀

t

₁

t

₂

t

₃

t

₄

t

₅ 優先度継承 優先度逆転 セマフォSを解放 優先度を継承しているため
 プリエンプトされない

Hiroaki Takada ▶ 高優先度タスクと中優先度タスクがセマフォS1，中優先度 タスクと低優先度タスクがセマフォ_{S2で排他制御している} 場合 51 リアルタイム性保証技術 Chain Blocking（連鎖ブロッキング） 優先度逆転 優先度
 継承 優先度継承 セマフォS2を獲得 セマフォS1を獲得 セマフォS1を要求 セマフォS2を要求 セマフォS2を解放 セマフォS1,S2を 解放

Hiroaki Takada

優先度上限プロトコル (OPCP)

▶ 優先度上限プロトコル（Priority Ceiling Protocol）という名

称で最初に提案された手法 着眼点 ▶ 連鎖ブロッキングが起こらないように，クリティカルセクショ ンに入る時点で，早めにブロッキングする 正確に言うと… ▶ セマフォを取る可能性のあるタスクの中で，最も高い優先 度を持つタスクの優先度を，そのセマフォの優先度上限と 言う ▶ 自タスク以上の優先度上限を持ったセマフォが獲得されて いれば，クリティカルセクションに入らず，そのセマフォを 獲得しているタスクに優先度を継承させる 52 リアルタイム性保証技術

Hiroaki Takada 利点 ▶ 低優先度タスクのクリティカルセクションに，高々1回しか待 たされない（_{single blocking）} ▶ つまり，連鎖ブロッキングは起こらない ▶ デッドロック回避が実現できる 欠点 ▶ アルゴリズムがやや複雑で，直感的に理解しにくい 53 リアルタイム性保証技術

Hiroaki Takada

優先度上限プロトコル (IPCP)

▶ 多くのRTOSで採用されており，単に優先度上限プロトコ ルというと，こちらを指すことが多い 着眼点 ▶ クリティカルセクションの中は優先度を上げて実行し，自分 をブロックする可能性のあるタスクは実行させない 正確に言うと… ▶ セマフォを獲得したら（クリティカルセクションに入ったら）， タスクの優先度をそのセマフォの優先度上限まで引き上 げる ▶ セマフォを解放したら元に戻す 利点 ▶ single blocking，デッドロック回避を実現できる ▶ 単純で実装オーバヘッドが小さい 54 リアルタイム性保証技術

Hiroaki Takada ▶ 高優先度タスクと中優先度タスクがセマフォS1，中優先度 タスクと低優先度タスクがセマフォ_{S2で排他制御している} 場合 55 リアルタイム性保証技術

Immediate Ceiling Priority Protocol（IPCP）による解決

優先度逆転 セマフォS2を獲得．
 優先度をS2の優先度 上限まで引き上げる セマフォS1を獲得．
 優先度をS1の優先度 上限まで引き上げる セマフォS1を要求 セマフォS2を要求 セマフォS2を解放 セマフォS1,S2を 解放

Hiroaki Takada

RTOSによるプロセッサ時間保護機能との関係

▶ あるアプリケーションがプロセッサ時間を使い過ぎた結果， 他のアプリケーションが時間制約を違反しては困る ▶ 保護の単位となるアクセス主体が，与えられた以上のプロ セッサ時間を使うことを防止する μITRON4.0仕様のオーバランハンドラ機能 ▶ 最も基本的なプロセッサ時間保護機能 ▶ タスクが指定されたプロセッサ時間を使ったことを検出し， 例外処理を行うためのオーバランハンドラを起動する ▶ オーバランハンドラでどのような処理を行うかは，ユーザに 任されている（例えば，そのタスクの優先度を下げる と いった対応も可能） 56 リアルタイム性保証技術

Hiroaki Takada AUTOSAR OS仕様におけるタイミング保護機能 ▶ 処理単位毎のプロセッサ時間保護 ▶ タスクとISR（カテゴリ2のみ）の実行時間に上限を設ける ▶ タスクとISR（カテゴリ2のみ）の到着間隔に下限を設ける → RMAにおける T_j と C_j の違反を検出できる ▶ 排他制御区間のプロセッサ時間保護 ▶ タスクや割込みハンドラが，割込みを禁止する時間や， リソースを取得している時間に上限を設ける → RMAにおける B_j の違反を検出できる ▶ 違反時の振舞い いずれも，違反があった場合には，例外処理のためのプ ロテクションフックを起動 57 リアルタイム性保証技術

Hiroaki Takada

最後に宣伝

このセミナーを1日コースで聞きたい方は… ▶ NCES人材育成プログラム（NEP） 「リアルタイム性保証技術」 ▶日時：2017年1月13日（金）9：30〜17：00 ▶場所：名古屋大学 東山キャンパス ▶講師：高田広章，松原豊（名古屋大学） ▶受講料：2万円 ☞ _{http://www.nces.is.nagoya-u.ac.jp/NEP/courses.html} 58 リアルタイム性保証技術 NEP リアルタイム性保証技術 2016 検索：