【第4回】元東大教員から学ぶリアルタイムシステム「リアルタイムシステムの予測性の深掘り」

こういった私から学べます．

前回を読んでいない方はこちらからどうぞ．

リアルタイムシステムの記事一覧はこちらからどうぞ．

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

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

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

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

リアルタイムシステムの予測性の深掘り

今回は前回学んだリアルタイムシステムの予測性を深掘りします．

今回の内容はとても難しいので，スキップしても構いません．

きちんと理解したい人は是非チャレンジして下さい！

リアルタイムシステムの中でもデッドラインミスが許されないハードリアルタイムシステムでは，予測性を高めることが重要な要素の一つです．

しかし，ハードウェアが持つ機能により予測性が低下してしまう場合があります．

例えば，プロセッサは以下の機能によりスループット（平均の処理性能）を向上するメリットがあります．

• 命令のプリフェッチ
• パイプライン処理
• キャッシュ
• Direct Memory Access（DMA）

デメリットとして最悪実行時間（WCET：Worst-Case Execution Times）の予測が困難になり，非決定的（Non-deterministic）な処理になってしまいます．

※非決定的とは，決定的（deterministic）とは対照的に，同じ入力の場合でも実行毎に異なる動作を示す可能性があることです．

予測性に影響する理由を以下の項目で詳しく紹介していきます．

• DMA
• キャッシュ
• 割り込み
• システムコール
• セマフォ
• メモリ管理
• プログラミング言語

DMA

Direct Memory Access（DMA）はデバイスとメモリ間のデータを転送するために多くの周辺機器で使われているハードウェアの機能です．

DMAの目的は，I/O転送を制御するタスクをプロセッサから解放することです．

CPUとI/Oデバイスは同じ転送路（バス）を共有するので，DMAデバイスによりデータ転送する際はCPUをブロックしなければなりません．

DMAでデータ転送する際の手法として以下を紹介します．

• Cycle Stealing
• Time-Slice Method

Cycle Stealing

Cycle Stealingは一番使われている方法で，DMAがデータ転送を実行するためにプロセッサの時間を確保します．

DMAの処理中はI/O転送とプロセッサのプログラムを並列に実行します．

ただし，プロセッサとDMAが同時にメモリアクセスを要求する場合は，DMAデバイスがバス権の獲得を優先し，プロセッサはDMAの処理が終わるまで待ちます．

Cycle Stealingを使う場合，プロセッサは実行中のタスクがDMAデバイスの転送を待たなければなりませんが，どれくらい待つのかを予測する方法がありません．

なので，タスクの応答時間（最悪実行時間+他の処理を待つ時間）を正確に解析することができなくなってしまいます．

Time-Slice Method

Time-Slice Methodは，各々のメモリサイクルを2つの隣接スロットに分けます．1つはプロセッサ用に，もう1つはDMAデバイス用に割り当てられます．

Time-Slice MethodはCycle-Stealingよりスループットが低下しますが予測性は向上します．

実際，プロセッサとDMAデバイスは衝突しないので，タスクの応答時間はDMA処理により長くなりません．なので，高い精度でタスクの応答時間を予測できます．

キャッシュ

キャッシュは，スループットを向上させるためにCPUとメモリ（RAM：Random Access Memory）の間にある高速なメモリのことです．

キャッシュは，メモリ管理ユニット（MMU：Memory Management Unit）の後に物理的に配置されることが多く，その振る舞いはソフトウェアから隠蔽されています．

メモリ配置の物理アドレスが決まった場合，ハードウェアは要求されるデータがキャッシュにあるかどうかチェックします．

もしキャッシュにある場合，データをキャッシュから読み込みます．

キャッシュにない場合，データをメモリから取ってきてます．また，アクセスしたデータと隣接したデータを一緒にキャッシュにコピーします．

この手法では，次にアクセスした隣接したデータは，メモリにアクセスせずにキャッシュからデータを読むことができます．

このバッファリング手法は，高頻度でメモリにアクセスする領域は小さいアドレス空間に制限されるという統計的な性質「参照の局所性」に基づいています．

例えば，1MBのメモリと8KBのキャッシュを持つ場合，プログラムから要求されるデータの80%はキャッシュにあるということです．つまり，キャッシュのヒット率は80%ということです．

リアルタイムシステムでは，キャッシュは非決定的な処理になる原因になります．

実際，統計的に要求されるデータの80%はキャッシュにあることがわかっていたとしても，残り20%の場合はキャッシュミスにより性能が低下します．

もしデータがキャッシュにない場合，データへのアクセス時間はメモリからキャッシュへのデータ転送が必要になり長くなってしまいます．

統計的な調査によると，メモリアクセスの90%は読み込み処理で10%は書き込み処理ということがわかっています．

しかし，これらの統計的な調査はアプリケーションの平均的な振る舞いの推定のみを提供しているだけで，最悪のケースの上限を判断できるわけではありません．

プリエンプティブ（タスクの実行を横取り可能）なシステムでは，キャッシュの振る舞いはプリエンプションの回数にも影響されます．

実際，プリエンプションはプログラムの局所性を壊し，プリエンプションするタスクにキャッシュがメモリに追い出されたことでキャッシュミスの回数が増えます．

さらには，キャッシュに関連するプリエンプションの遅延（CRPD：Cache-Related Preemption Delay）は，プリエンプションするタスクが発生したタイミングに依存します．

なので，CRPDを正確に予測することは困難です．

割り込み

I/O周辺機器から発生する割り込みは，リアルタイムシステムの予測に対して大きな問題になります．

適切に割り込みをハンドリングできなければ，無制限の遅延が発生するからです．

ほとんどのOSでは，割り込みシグナルの到着は，デバイスドライバによる割り込みサービスルーチン（関連デバイスの管理に専念する処理）の実行を引き起こします．

この手法の利点はドライバの中にデバイスのハードウェアの詳細をカプセル化（隠蔽）できることです．

また，この手法はアプリケーションタスクのサーバとして振る舞います．

例えば，I/Oデバイスからデータを取得するためには，各々のタスクは割り込みを発生するためにハードウェアを有効化し，割り込みを待ち，デバイスドライバと共有するメモリからデータを取得しなければなりません．

多くのOSでは，各々のデバイスドライバは固定優先度でスケジューリングされてタスクより優先度が高く設定されています．なので，割り込みのデバイスドライバも固定優先度で処理されます．

この割り当てルールは，割り込みハンドリングルーチンはたいていリアルタイム制約を持つI/Oデバイスで処理するが，ほとんどのアプリケーションはリアルタイム制約がない，という事実に基づいています．

しかし，リアルタイムシステムでは，この想定は正しくないです．

この理由は，制御タスクは割り込みハンドリングルーチンより緊急度が高いからです．

一般的に，タスクが実行する状況での先験的に割り込みの回数の上限を解析することは難しいので，割り込み処理の遅延は予測不可能です．

アプリケーションタスクが実行する状況でデバイスドライバの干渉を減らしつつ外部とのI/O処理を遂行するためには，周辺デバイスが異なる方法でハンドリングされなければなりません．

これらを実現するための3つの手法を紹介します．

• 全ての外部割り込みの禁止
• 専用カーネルルーチンの周期実行
• 全ての外部割り込みを有効にした状態でデバイスドライバを省サイズ化

全ての外部割り込みの禁止

割り込みの干渉を除去する最も過激な方法は，基本的なシステム処理に必要なタイマ以外の全ての割り込みを禁止することです．

この方法では，アプリケーションタスクが全ての周辺デバイスのレジスタに直接アクセスしなければなりません．

割り込みが発生しないので，データ転送はポーリングで処理します．

I/Oデバイスへの直接アクセスはプログラミングの柔軟性を許し，デバイスドライバの実行による遅延を除去します．

結果として，データ転送に必要な時間は正確に解析することができ，タスクの実行に必要な時間を確保することができます．

この手法のもう一つの利点は，I/Oデバイスが置換や追加された場合にカーネルの修正が不要なことです．

この手法の欠点は，デバイスのレジスタにアクセスする間，タスクがビジーウェイトすることが原因でI/O処理におけるプロセッサの効率が低下することです．

他には，アプリケーションタスクはハンドリングするデバイスの全ての詳細を知らなければならないことが挙げられます．

しかし，アプリケーションタスクにより呼ばれるライブラリ関数のセットの中に全てのデバイスに依存するルーチンをカプセル化すれば，この欠点は簡単に解決できます．

専用カーネルルーチンの周期実行

周期タイマで専用カーネルルーチンを起動する手法は，デバイスドライバの割り込み処理が原因の上限のない遅延を除去することができます．

また，1つもしくは複数の周期カーネルタスクの全てのI/O処理を制限することができます．

リアルタイムシステムでは，I/Oデバイスは速度によって2つのクラスに分割できます．

遅いデバイスは1つの長い周期のI/O処理タスクとして多重実行されます．

速いデバイスは1つの短い周期のシステムタスクとして専用実行されます．

この手法の利点は周辺デバイスの全てのハードウェアの詳細はカーネルの処理でカプセル化できることで，アプリケーションタスクはその詳細を知らなくてよいことです．

この手法では，割り込みを無効にしたことが原因で，カーネルのI/Oハンドリングルーチンのビジーウェイトを引き起こしてしまいます．

また，I/O処理のデータを交換するために，アプリケーションタスクとI/Oカーネルルーチンでコミュニケーションが要求されるため，システムの過負荷が発生してしまいます．

デバイスハンドリングルーチンはカーネルの一部なので，あるデバイスが置換や追加された場合は修正しなければなりません．

全ての外部割り込みを有効にした状態でデバイスドライバを省サイズ化

全ての外部割り込みを有効にした状態でデバイスドライバを省サイズ化する手法により，各々のデバイスドライバを管理するために必要なタスクのみを起動します．

一度タスクを起動した場合，デバイスマネージャータスクはリアルタイムOSの管理化で実行し，他のアプリケーションタスクと同様にスケジューリングされることが保証されます．

デバイスハンドリングタスクに割り当てた優先度は他の優先度と完全に独立していて，アプリケーションの要求にしたがって設定することが可能です．

例えば，制御タスクはデバイスハンドリングタスクより高い優先度を持つことができます．

このアイデアの概要は下図で説明します．

イベントEは割り込みを発生し，関連するデバイスドライバを実行させます．

他の手法とは異なり，このデバイスドライバは，直接デバイスをハンドリングせず，実際のデバイスマネージャーになる専用タスク\(J_E\)を起動します．

この手法の利点は，I/O処理の間のビジーウェイトを除去することです．

さらには，タスクが実行している間のデバイスドライバによる無制限の遅延を劇的に削減できることです．（完全に除去できるわけではないので注意して下さい．）

なので，タスクの実行時間がより高い精度で予測可能になります．

実際として，小さいデバイスドライバの実行による小さい無制限のオーバヘッドはシステムには存在しますが，ほとんどの実用的なケースで無視できます．

システムコール

システムの予測性は，どのようにカーネルの仕組みが実行されているかに依存します．

全てのシステムコール（アプリケーションからカーネルの機能の呼び出し）を含めたアプリケーションのスケジュール可能性を解析すべきです．

このスケジューリング可能性解析を簡略化するためには，カーネルの仕組みはプリエンプティブであることが要求されます．

実際，ノンプリエンプティブなセクションは起動や重要な処理の実行を遅延させてしまい，デッドラインミスを引き起こします．

セマフォ

一般的なOSで使われている典型的なセマフォのメカニズムは，優先度逆転問題が発生するので，リアルタイムアプリケーションには適しません．

優先度逆転問題とは，高優先度タスクが低優先度タスクに無制限の実行区間でブロックされることです．

優先度逆転問題は重要なタスクを無制限に遅延してしまうので，リアルタイムシステムでは避けなければなりません．

優先度逆転問題は，クリティカルセクションに入りたいタスクに適切なプロトコルを利用することで避けることができます．

詳細は後ほど解説しますが，以下に例を示します．

• 優先度継承プロトコル（PIP：Priority Inheritance Protocol）
• 優先度上限プロトコル（PCP：Priority Ceiling Protocol）
• スタックリソースポリシー（SRP：Stack Resource Policy）

これらのプロトコルのアイデアは，現在のリソースの利用に基づいてタスクの優先度を修正したり，各々のクリティカルセクションに入る時にテストすることでリソースの割り当てを制御したりします．

このテストの目標は，クリティカルセクションを共有するタスクのブロック時間の上限を解析することです．

これらのプロトコルの実装には，カーネルの修正が必要になるかもしれません．

特に，waitやsignalコールだけでなく，タスク管理用のデータ構造やメカニズムを考慮する必要があります．

メモリ管理

他のカーネルメカニズムのように，メモリ管理はリアルタイム処理の実行中に非決定的な遅延を引き起こさないかもしれません．

例えば，ページ要求処理では，リアルタイム性を保証しなければならないリアルタイムアプリケーションには適していません．

なぜなら，ページフォールトやページの置換は大きく予測不可能な遅延を引き起こすからです．

ほとんどのリアルタイムシステムでの典型的な解決方法は，固定されたメモリ管理スキームでのメモリセグメンテーションルールを遵守することです．

静的なメモリ割り当てはアプリケーションが似たようなメモリ量を要求する時に特に効果的です．

一般的にリソースやメモリ割り当ての静的な割り当てはシステムの予測性を向上しますが，動的な環境での柔軟性が低下します．

特定のアプリケーションの要求に依存して，システムの設計者は予測性と柔軟性のトレードオフを考慮して最適な選択をしなければなりません．

プログラミング言語

マシンのハードウェアの特徴やカーネルに実装されている内部メカニズムのほかに，リアルタイムシステムの予測性を決める要素があります．

それは，アプリケーションの開発に使われるプログラミング言語です．

リアルタイムシステムが複雑になるほど，プログラミング言語による高い抽象化が要求されます．

残念ながら，現在のプログラミング言語ではリアルタイム性の保証を設定する機構がありません．

例えば，プログラミング言語Ada（アメリカ国防省からリアルタイムアプリケーション向けに使うことを要求される言語）だと，タスクの実行中の明示的な時間制約を定義できません．

他にもReal-Time EuclidやReal-Time Concurrent Cという言語が登場しましたが，どれもあまり使われていません．

なので，現実的な選択肢として，リアルタイムシステムにおけるリアルタイムOSやリアルタイムアプリケーションの開発に使われる言語はC/C++が一般的です．

まとめ

リアルタイムシステムの重要な性質である予測性を深掘りしました．特に，予測性に関する以下の項目を解説しました．

• DMA
• キャッシュ
• 割り込み
• システムコール
• セマフォ
• メモリ管理
• プログラミング言語

今回は難しい内容ですが，ハードウェア，OS，C言語を習得している方はなんとか理解できたのではないでしょうか．

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

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

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

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

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