Chapter 20

リアルタイム性の解析 — 「間に合う」を計算で保証する

この章がなぜ必要なのか——「動いているから大丈夫」は保証ではない.

RTOS の「RT」は Real-Time——リアルタイムである。 だがリアルタイムとは「速い」ことではない。

「決められた時刻までに、必ず終わることが保証されている」ことである。

テストで動いても、最悪のタイミングが重なったときに間に合うとは限らない。 それを計算で確かめる方法が確立している。この章はその入門である。

この章で使う既出の用語（定義は各リンク先）. コンテキスト（01 章 6 節）、タスク（02 章 2 節）、固定優先度（06 章 1 節）、追加（07 章 2 節）、不可（16 章 4 節）、正確（17 章 5 節）

1. リアルタイムとは何か

「速い」と「リアルタイム」は別物である.

平均 1 µs で応答するが、最悪 100 ms かかることがあるシステムは、 リアルタイムではない。

平均 10 ms だが、絶対に 20 ms を超えないシステムは、リアルタイムである。

リアルタイム性とは、最悪値の保証である。 平均値には意味がない。

2. 用語

保証すべき条件は、すべてのタスクについて \(R_i \le D_i\) である。

多くの場合、\(D_i = T_i\) とする（次の起動までに終わっていること）。これを暗黙のデッドラインと呼ぶ。

3. CPU 利用率

\(U > 1\) なら、どんなスケジューラでも間に合わない（物理的に不可能）。 だが \(U \le 1\) でも間に合うとは限らない。優先度の付け方が問題になる。

4. レートモノトニック (RM) — 優先度の付け方

周期が短いタスクほど、優先度を高くする。

Liu と Layland（1973）が証明した重要な結果:

固定優先度スケジューリングにおいて、 レートモノトニックは「最適」である。 RM で間に合わないなら、他のどんな固定優先度の付け方でも間に合わない。

これは直感に反することがある.

「表示は 20 ms もかかる重い処理だから優先度を上げよう」——これは間違いである。 実行時間ではなく、周期の短さで優先度を決める。

重い処理を高優先度にすると、短周期のタスクが待たされて期限を破る。

例外: デッドラインが周期と違う場合

\(D_i \ne T_i\) のときは、デッドラインモノトニック (DM) を使う。

デッドラインが早いタスクほど、優先度を高くする。

これも最適であることが証明されている。

5. 利用率境界による判定

Liu と Layland は、簡単な十分条件も示した。

これを満たせば、RM で必ず全タスクが期限を守る。

\(n \to \infty\) での極限は \(\ln 2 \approx 69.3\%\) である。

「CPU 使用率を 70 % 以下に抑える」という経験則の出どころがこれである.

ただし——これは十分条件であって、必要条件ではない。 \(U = 0.9\) でも間に合う場合はいくらでもある。

境界を超えたら「間に合わないかもしれない」だけであって、 「間に合わない」ではない。もっと正確な判定が必要になる。

利用率境界を確かめる

タスクの周期と実行時間を変えて、利用率と境界の関係を確かめられる。

6. 応答時間解析 — 正確な判定

利用率境界より厳密な方法が応答時間解析 (Response Time Analysis) である。

タスク \(i\) の最悪応答時間 \(R_i\) は、次の再帰式の不動点として求まる。

ここで \(hp(i)\) は「\(i\) より優先度の高いタスクの集合」である。

式の意味

天井関数 \(\lceil \cdot \rceil\) が重要である。 「\(R_i\) の間に \(j\) が何回来るか」は、切り上げで数える必要がある （起動のタイミングが最悪の場合を考えるため）。

解き方 — 反復計算

\(R_i\) が両辺にあるので、反復で解く。

\(R_i^{(k+1)} = R_i^{(k)}\) になったら収束。それが \(R_i\) である。 \(R_i > D_i\) になったら、その時点で「間に合わない」と判定できる（発散する）。

計算例

\(U = 1/4 + 2/6 + 2/12 = 0.25 + 0.333 + 0.167 = 0.75\)

\(n = 3\) の利用率境界は \(0.780\) なので、\(0.75 < 0.780\) で十分条件を満たす。 念のため応答時間解析でも確かめる。

タスク A（最高優先度）:

タスク B:

\(R_B = 3\ \text{ms} \le 6\ \text{ms}\) ✓

タスク C:

\(R_C = 6\ \text{ms} \le 12\ \text{ms}\) ✓

全タスクが期限を守る。

応答時間解析を実行する

タスクセットを編集して、応答時間の反復計算と判定を確かめられる。

7. 現実の補正項

上の式は理想化されている。実際には次の項を足す必要がある。

\(B_i\) の求め方（優先度継承あり）

優先度継承を使っている場合、\(B_i\) は 「\(i\) より低優先度のタスクが持つ、\(i\) が使う可能性のあるミューテックスの、 最長クリティカルセクション」の和で上から抑えられる。

これが 13 章で「有界な逆転」と呼んだものの正体である.

優先度継承がないと、\(B_i\) に中優先度タスクの実行時間が全部入る。 つまり計算不能になる。

優先度継承は「\(B_i\) を計算可能にするための装置」である。 性能の話ではなく、保証可能性の話である。

\(I_{\text{isr}}\) の扱い

割り込みは、どんなタスクよりも優先度が高い。 だから ISR は「周期 \(T_{\text{isr}}\)、実行時間 \(C_{\text{isr}}\) の最高優先度タスク」として、 \(hp(i)\) に含めて計算する。

ここで「ISR は 10 µs 以下」の意味が分かる（18 章）.

1 ms 周期の割り込みが 100 µs かかると、\(10\%\) の CPU を無条件に奪う。 そしてそれは全タスクの応答時間に上乗せされる。

ISR を軽くすることは、全システムの応答時間を改善する。

8. WCET（最悪実行時間）をどう求めるか

これが実務では最も難しい。

実測の方法

/* 高分解能タイマで測る */
uint32_t t0 = DWT->CYCCNT;      /* Cortex-M のサイクルカウンタ */
    do_work();
uint32_t dt = DWT->CYCCNT - t0;

if( dt > worst_case ) { worst_case = dt; }

WCET を大きくする要因

キャッシュのあるマイコンでは、WCET の見積りが極端に難しくなる.

Cortex-M7 や Cortex-A では、キャッシュヒットとミスで 実行時間が 10 倍以上変わることがある。

ハードリアルタイム性が要るなら——

• キャッシュを無効にする（遅くなるが予測可能になる）
• 重要な関数を TCM（密結合メモリ）に置く
• キャッシュをロックする（対応していれば）

「予測可能性のために性能を捨てる」——リアルタイム設計ではよくある判断である。

9. 実務的な指針

実測で検証する方法

/* 周期タスクの応答時間を測る */
void vControlTask( void *pv )
{
    TickType_t xLastWake = xTaskGetTickCount();

    for (;;) {
        if( xTaskDelayUntil( &xLastWake, pdMS_TO_TICKS( 10 ) ) == pdFALSE ) {
            deadline_miss_count++;      /* ★ 周期に間に合っていない */
        }

        uint32_t t0 = DWT->CYCCNT;
        do_control();
        uint32_t dt = DWT->CYCCNT - t0;
        if( dt > wcet_observed ) { wcet_observed = dt; }
    }
}

xTaskDelayUntil() の戻り値でデッドラインミスが検出できる（08 章）。 これを本番でもカウントしておくと、 フィールドで期限を破っているかどうかが分かる。非常に有用である。

10. この章のまとめ

次章では、ここまでの解析に必要な「見る」道具—— デバッグとトレースを扱う。