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

Size: px

Start display at page:

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

ふじきみさかわ
5 years ago
Views:

1 ET/IoT2016 IPA SEC 先端技術入門ゼミリアルタイム性保証技術制限時間内に処理が終了することを保証するには? 2016 年広章名古屋学学院情報科学研究科教授附属組込みシステム研究センター NPO 法 TOPPERS プロジェクト会 APTJ 株式会社代表取締役会 CTO URL: 1

2 1 コースのセミナーの次リアルタイムシステムとリアルタイム性保証リアルタイムシステムの性能指標と最悪実行時間解析の困難性リアルタイム処理の性能評価リアルタイムスケジューリング理論 Rate Monotonic Analysis Critical Instant 定理, 最適な優先度割り付けプロセッサ使用率によるスケジュール可能性判定優先度逆転とその解決アプローチ, 非周期タスクの扱い過負荷に対する対策と QoS 制御リアルタイムスケジューリング理論の適用事例最悪実行時間解析アプリケーション統合のためのスケジューリング 2

3 本のセミナーの次リアルタイムシステムとリアルタイム性保証最悪実行時間解析のさわりだけリアルタイムシステムの性能指標と最悪実行時間解析の困難性リアルタイム処理の性能評価リアルタイムスケジューリング理論を簡単にの前半だけを簡単にを簡単に Rate Monotonic Analysis Critical Instant 定理, 最適な優先度割り付けプロセッサ使用率によるスケジュール可能性判定優先度逆転とその解決アプローチ, 非周期タスクの扱い過負荷に対する対策と QoS 制御リアルタイムスケジューリング理論の適用事例アプリケーション統合のためのスケジューリング 3

4 リアルタイムシステムとリアルタイム性保証 4

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

6 用語説明 : 最悪実行時間, 最大実行時間多くの場合, 着目する時間が最も長くなる状況が最悪であるため, 一般には, 最大時間のことを最悪時間という WCET(Worst Case Execution Time)= 最悪実行時間用語説明 : 悲観的な解析, 安全な解析, タイトな解析解析結果が, 真の最悪実行時間以上の値である場合に, 安全な解析と呼ぶ解析結果と真の最悪実行時間の差が大きい場合に, 悲観的 (pessimistic) な解析という. 逆に, 差が小さい場合に, タイト (tight) な解析という最悪実行時間解析にとって, 安全であることは必須. タイトであることが望ましい性能評価やテストは, 安全な解析ではない 6

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

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

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

10 リアルタイム OS (RTOS) とは? 文字通り, リアルタイムシステムの構築に用いるための OS RTOS の特徴具体的には, 次のような特徴を持つ OS( これらの特徴をすべて持っているとは限らない ) (1) リアルタイムシステム向けの機能を持つ (2) 予測可能性を持つ (3) 時間制約を管理一部の研究ベースの RTOS (4) 高速に応答 ( 制御対象に対して十分に ) RTOS の最重要機能マルチタスク機能とタスクスケジューリング機能が, システムが時間制約を満たすようにするために最も重要な機能 10

11 マルチタスクとスケジューリングタスクとは?! ここでのタスクは, スレッドと同義プログラムの並行実行の単位 1つのタスク中のプログラムは逐次的に実行される異なるタスクのプログラムは並行して実行されるプロセッサを抽象化多重化したものプロセッサマルチタスク機能抽象化多重化複数のタスクを疑似並列に実行するための機能タスク仮想化されたプロセッサシングルプロセッサシステムでは, 実際に同時に実行できるタスクは 1 つのみ複数のタスクが同時に実行しているかのように見せる 11

12 用語説明ディスパッチ ( タスクディスパッチ, タスク切換え ) プロセッサが実行するタスクを切り換えることディスパッチを実現する OS 内のモジュールがディスパッチャスケジューリング ( タスクスケジューリング ) どの時間にどのタスクを実行するかを決定すること多くの RTOS においては, 次に実行するタスクを決定する処理スケジューリングを実現する OS 内のモジュールがスケジューラ (UNIX/Linux のスケジューラは, スケジューリングに加えて, ディスパッチも行う ) スケジューリングアルゴリズムどのようにして次に実行するタスクを決定するか? 12

13 プリエンプティブな優先度ベーススケジューリング! ほとんどの RTOS で採用されているスケジューリング方式 (RTOS によっては他の方式もサポートしている ) 優先度ベーススケジューリング最も優先度の高いタスクが実行される優先度の高いタスクが実行できなくなるまで, 優先度の低いタスクは実行されない同一優先度タスク間では FCFS(First Come First Served) プリエンプティブスケジューリング優先度の高いタスクが実行可能になると, 優先度の低いタスクが実行途中でも, タスク切換えが起こる実行可能になるきっかけは割込み! 汎用 OS のスケジューリングとは大きく異なる 13

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

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

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

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

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

19 最悪実時間解析 19

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

21 静的解析対象プログラムのソースコードまたはオブジェクトコードを, 実際に実行することなく ( 静的に ) 解析し, 最悪実行時間を求める測定ベース解析プログラムの実際に実行し, 実行時間を計測することで, 最悪実行時間を求めるハイブリッド解析静的解析と測定ベース解析を組み合わせた手法 1. ソースコードの基本ブロック単位で, 実行時間を測定する ( 測定ベース解析 ) 2. ソースコードの構造やパスを解析する ( 静的解析 ) 3. 各実行パスの基本ブロックに,1 の測定結果を当てはめ, 最悪実行時間を求める 21

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

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

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

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

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

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

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

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

30 システムに対する最負荷すべての処理が厳密に時間制約を満たして実行できることを保証するためには, システムに対する最大負荷が決まっていなければならないシステムに対する最大負荷が決定できないか, 最大負荷を考えてシステム設計するのが現実的でない場合には, 現実的な最大負荷を想定して設計し, 想定を超えた場合に対する対策を実施する最大負荷を決定 / 想定してシステムを設計最大負荷の一つの記述方法 ( タスクは繰り返し実行されることを想定 ) 最大負荷 = Σ 1 回の最大実行時間最大実行頻度各タスク 30

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

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

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

34 Critical Instant 定理からえることスケジュール可能性の必要十分条件スケジュール可能 : どんな状況でもタスクが時間制約を満たせること critical instant に起動された場合でもデッドライン内に実行が終わるなら, そのタスクはスケジュール可能その逆も成立タスク i( タスクのインデックスは優先度の高い順につける ) がスケジュール可能となる必要十分条件式 t, 0 < t Ti, i Cj j=1 T j : 優先度が j 番目のタスクの周期 C j : 優先度が j 番目のタスクの最大実行時間 # $ t Tj % & t 34

35 スケジュール可能性検証の例例に用いるタスクセット j 周期 (T j ) 最大実行時間 (C j ) 使用率 ( 負荷 ) % % % タスク 3 に対する critical instant タスク 1 タスク 2 タスクタスク 3 の最大応答時間は t 35

36 必要十分条件式による評価右式にあてはめると t =13 14 で! 2 13 " 5 グラフでの表現 t, 0 < t Ti, # $ + 2! 13 " i Cj j=1 # $ + 3! 13 " 14 # $ t Tj % & t # $ =13 13 不等式の左辺 ( タスク1 3によるプロセッサ時間の最大要求量 ) t 最初に交わった点が最大応答時間不等式の右辺 ( プロセッサ時間の供給量 ) 36

37 最適な優先度割付け Critical instant 定理と同じ前提条件下で, タスクにどのように優先度を割り付けるのが最適か? 最適の意味 : その優先度割付けでスケジュールできないなら, 他の割付けでもスケジュールできない Rate Monotonic Scheduling(RMS) 周期が短いタスクほど高い優先度を割り付ける急ぐタスクほど高い優先度ここから Rate Monotonic Analysis という名称がついた証明の本質部分高優先度低優先度デッドライン実行順序を交換してもデッドラインを満たせる 37

38 プロセッサ使率によるスケジュール可能性判定! RMA で最も有名な結果 RMS でタスクセットがスケジュール可能になる十分条件 n Cj j=1 Tj n(2 1/n 1) n : タスク数 Tj : 優先度が j 番目のタスクの周期 Cj : 優先度が j 番目のタスクの最大実行時間左辺 : プロセッサの使用率悲観的な上限値 ( あくまで十分条件 ) n 右辺 ! 失った使用率 ( 最大 31%) は, 優先度を静的に割り付けていることからくる本質的な限界 38

39 静的優先度割付けの本質的な限界タスク A 1 回めの周期 2 回めの周期タスク B 1 回めの周期 2 回めの周期デッドラインミスタスク B の 1 回めの周期の絶対デッドラインは, タスク A の 2 回めの周期の絶対デッドラインよりも早いが, 相対デッドラインはタスク A の方が短いため, タスク A に対して高い優先度が割り付けられている優先度を固定していることから生じる本質的な限界 39

40 動的優先度割付けの場合優先度割付けを動的に変化させてもよい場合は, どうするのが最適か?( タスクセットに対する仮定は変えない ) Earliest Deadline First Scheduling(EDFS) 絶対デッドラインが早いタスクから順に高い優先度を割り付ける EDFS でタスクセットがスケジュール可能になる必要十分条件 n Cj j=1 Tj 1 n : タスク数プロセッサの能力を 100% 使える Tj : 優先度が j 番目のタスクの周期 Cj : 優先度が j 番目のタスクの最大実行時間左辺 : プロセッサの使用率 40

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

42 タスクセットに対する仮定を緩めるここまで仮定していたタスクセットに対する仮定は, 実際のシステムに適用するには強すぎるため, 仮定を緩めるために数多くの理論拡張がされているデッドラインが周期の終わりと一致しないデッドラインが周期より短い場合 critical instant 定理はそのまま成り立つ相対デッドラインが短いタスクほど高い優先度を割り付ける方法 (deadline monotonic scheduling) が最適デッドラインが周期より長い場合 critical instant 定理は成り立たない複雑にはなるが, それに相当する定理があり, 最悪応答時間の解析は可能 deadline monotonic が最適にならない場合がある 42

43 タスク間に同期通信がある低優先度タスクに待たされる最大時間 ( これを最大ブロック時間 :Bi) がわかれば, その効果を入れた判定式を作ることができる i, t, 0 < t Ti, 最大ブロック時間を最小にする方策が重要になる非周期タスクがある i Cj j=1 最小起動間隔がない ( つまり, 連続して到着する可能性がある ) 非周期タスクは扱えない ( 負荷に上限がない ) 周期タスクが時間制約を満たすことを保証しつつ, 非周期タスクをできる限り早く実行する方法が提案されている $ % t Tj & ' + Bi t 43

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

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

46 高優先度タスクと低優先度タスクが, 資源を共有しており, それに対する排他制御をセマフォ S で実現している場合セマフォ S を獲得高優先度タスク中優先度タスク実行可能にセマフォ S を要求セマフォ S を獲得セマフォ S を解放優先度逆転低優先度タスク t 0 t 1 t 2 t 3 t 4 優先度逆転の例時刻 46

47 高優先度タスクと低優先度タスクが, 資源を共有しており, それに対する排他制御をセマフォ S で実現している場合セマフォ S を獲得高優先度タスク実行可能にセマフォ S を要求優先度逆転中優先度タスク低優先度タスク t 0 t 1 t 2 t 3 t 4 制御できない優先度逆転の例時刻 47

48 優先度逆転の解決アプローチクリティカルセクション中のタスク切換えの制限クリティカルセクション中では, タスク切換えを行わない割込みも禁止してしまう手もある優先度上限プロトコル (Immediate Priority Ceiling Protocol, IPCP) 優先度継承優先度継承プロトコル (Priority Inheritance Protocol) 優先度上限プロトコル (Original Priority Ceiling Protocol, OPCP) クリティカルセクションのアボート高優先度タスクを待たせる低優先度タスクのクリティカルセクションの実行をアボートし, 後で再実行する低優先度タスクには, 再実行のオーバヘッドがある 48

49 優先度継承プロトコル基本優先度継承プロトコル (Basic Priority Inheritance Protocol) と呼ぶ場合もある着眼点高優先度のタスクを待たせている低優先度タスクは, 待たせているタスクの ( 高い ) 優先度で実行すべきである待たせているタスクの優先度を継承 (inherit) する正確に言うとタスクは, 自分自身の優先度と, 自分が待たせているタスクの優先度の中で, 最も高い優先度で実行する利点優先度逆転の時間の上限を押さえることができる欠点連鎖ブロッキング (chain blocking) が起こる 49

50 セマフォ S を獲得高優先度タスク実行可能にセマフォSを要求優先度逆転中優先度タスク低優先度タスク優先度継承セマフォ S を解放 t 0 t 1 t 2 t 3 t 4 t 5 時刻優先度を継承しているためプリエンプトされない Basic Priority Inheritance Protocol による解決 50

51 高優先度タスクと中優先度タスクがセマフォS1, 中優先度タスクと低優先度タスクがセマフォS2で排他制御している場合セマフォS1を要求セマフォ S1 を獲得セマフォ S2 を獲得優先度継承優先度逆転セマフォS2を要求セマフォS1,S2を解放優先度継承セマフォ S2 を解放 Chain Blocking( 連鎖ブロッキング ) 51

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

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

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

55 高優先度タスクと中優先度タスクがセマフォ S1, 中優先度タスクと低優先度タスクがセマフォ S2 で排他制御している場合セマフォ S1 を獲得. 優先度を S1 の優先度上限まで引き上げるセマフォ S2 を獲得. 優先度を S2 の優先度上限まで引き上げる優先度逆転セマフォ S2 を解放セマフォ S1 を要求セマフォS2を要求セマフォS1,S2を解放 Immediate Ceiling Priority Protocol(IPCP) による解決 55

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

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

58 最後に宣伝このセミナーを 1 日コースで聞きたい方は NCES 人材育成プログラム (NEP) リアルタイム性保証技術日時 :2017 年 1 月 13 日 ( 金 )9:30 17:00 場所 : 名古屋大学東山キャンパス講師 : 高田広章, 松原豊 ( 名古屋大学 ) 受講料 :2 万円検索 : NEP リアルタイム性保証技術

2015 TRON Symposium セッション組込み機器のための機能安全対応 TRON Safe Kernel TRON Safe Kernel の紹介 2015/12/10 株式会社日立超 LSIシステムズ製品ソリューション設計部トロンフォーラム TRON Safe Kernel WG 幹事

2015 TRON Symposium セッション組込み機器のための機能安全対応 TRON Safe Kernel TRON Safe Kernel の紹介 2015/12/10 株式会社日立超 LSIシステムズ製品ソリューション設計部トロンフォーラム TRON Safe Kernel WG 幹事 2015 TRON Symposium セッション組込み機器のための機能安全対応 TRON Safe Kernel TRON Safe Kernel の紹介 2015/12/10 株式会社日立超 LSIシステムズ製品ソリューション設計部トロンフォーラム TRON Safe Kernel WG 幹事豊山祐一 Hitachi ULSI Systems Co., Ltd. 2015. All rights