Chapter 13

優先度逆転と優先度継承 — 火星探査機を止めたバグ

この章がなぜ必要なのか——優先度の設計が「効かなくなる」現象がある.

06 章の規則は「最高優先度の Ready タスクが必ず走る」だった。 だがこの規則は、「Ready なら」という条件付きである。

高優先度タスクが資源を待ってブロックしているとき、その資源を持っているのは 低優先度タスクかもしれない。すると——優先度の順序が実質的に逆転する。

これは理論上の話ではない。1997 年、火星に着陸した探査機がこれで再起動を繰り返した。

この章で使う既出の用語（定義は各リンク先）. TCB（02 章 2 節）、タスク（02 章 2 節）、Blocked（04 章 1 節）、Ready（04 章 1 節）、イベントリスト（04 章 4 節）、FreeRTOS（06 章 4 節）、バイナリセマフォ（12 章 5 節）

1. 事件 — Mars Pathfinder, 1997

1997 年 7 月、NASA の火星探査機 Mars Pathfinder は着陸後まもなく、 原因不明のシステムリセットを繰り返すという不具合に見舞われた。

原因はこうだった。

1. ASI/MET（低） が共有バスのミューテックスを取る
2. bc_dispatch（高） が同じミューテックスを要求 → ブロック
3. 通信タスク（中） が Ready になり、ASI/MET（低）をプリエンプト
4. ASI/MET は走れない → ミューテックスを返せない → bc_dispatch も走れない
5. bc_dispatch が周期実行に間に合わない → ウォッチドッグがシステムをリセット

高優先度タスクが、中優先度タスクに実質的に負けている。 これが優先度逆転である。

JPL のエンジニアはこれをどう直したか.

使っていた VxWorks には優先度継承の機能があったが、無効になっていた （性能上の理由でオフにされていた）。

地上でシミュレーションして原因を突き止めた後、 火星の探査機に「優先度継承を有効にする」パッチを無線で送信した。 それでリセットは止まった。

この事例は、リアルタイムシステムの教科書に必ず載っている。 「優先度継承は性能のために切ってよい機能ではない」という教訓である。

2. 優先度逆転の 2 つの型

有界な優先度逆転（避けられない・許容できる）

時刻 →
低 L: ██████░░░░░░░░░░░░░░░░
高 H: ░░░░░░[待ち]███████████
              ↑
        L がロックを解放するまで待つ

高優先度タスクが、低優先度タスクのクリティカルセクションの長さだけ待たされる。

これは避けられない。 資源を共有する以上、誰かが使っている間は待つしかない。 だが待ち時間の上限はクリティカルセクションの実行時間なので、計算できる。 これを「有界 (bounded)」と呼ぶ。

無制限の優先度逆転（これが問題）

時刻 →
低 L: ███░░░░░░░░░░░░░░░░░░░░░░░░░░██░░░░
中 M: ░░░████████████████████████░░░░░░░░
高 H: ░░[━━━━━━━ 待たされる ━━━━━━]███

中優先度タスクが割り込んできて、低優先度タスクの実行を止める。 すると高優先度タスクの待ち時間は、中優先度タスクの実行時間に依存する。

中優先度タスクが何個いるか、それぞれが何 ms 走るかは事前に分からない。 だから待ち時間の上限が計算できない。これを「無制限 (unbounded)」と呼ぶ。

リアルタイムシステムでは、これは致命的である。

優先度逆転を見る

3 つのタスクの実行時間とロック区間を変えて、 優先度継承の有無で待ち時間がどう変わるかを比較できる。

3. 優先度継承 — FreeRTOS の解決策

ロックを持っている低優先度タスクの優先度を、 待っている最高優先度タスクと同じまで一時的に引き上げる。

時刻 →
低 L: ███[優先度を H に昇格]███░░░░░
中 M: ░░░░░░░░░░░░░░░░░░░░░░░████████
高 H: ░░[待ち]░░░░░░░░░░░░░░░███░░░░░
             ↑            ↑
        H が待ち始めた    L が解放 → H が走る
        → L を H の優先度に昇格         → L は元の優先度に戻る

昇格した L は中優先度タスク M より高いので、M に邪魔されない。 L は速やかにクリティカルセクションを抜け、ミューテックスを解放する。

結果として、H の待ち時間は L のクリティカルセクションの長さだけになる。 つまり無制限の逆転が、有界の逆転に落ちる。これが優先度継承の効果である。

4. 実装 — 昇格する側

/* xQueueSemaphoreTake の中。ミューテックスが取れなかったとき */
if( pxQueue->uxQueueType == queueQUEUE_IS_MUTEX ) {
    taskENTER_CRITICAL();
    {
        xInheritanceOccurred = xTaskPriorityInherit( pxQueue->u.xSemaphore.xMutexHolder );
    }
    taskEXIT_CRITICAL();
}
vTaskPlaceOnEventList( &( pxQueue->xTasksWaitingToReceive ), xTicksToWait );

xTaskPriorityInherit() の中身:

BaseType_t xTaskPriorityInherit( TaskHandle_t const pxMutexHolder )
{
    TCB_t * const pxTCB = pxMutexHolder;
    BaseType_t xReturn = pdFALSE;

    if( pxMutexHolder != NULL )
    {
        /* 所有者の優先度が、待っているタスクより低いなら昇格 */
        if( pxTCB->uxPriority < pxCurrentTCB->uxPriority )
        {
            /* イベントリストのソート鍵も更新（[07 章](07_Readyリストの実装.md#ready-リストの動作)） */
            if( ( listGET_LIST_ITEM_VALUE( &( pxTCB->xEventListItem ) )
                  & taskEVENT_LIST_ITEM_VALUE_IN_USE ) == 0UL )
            {
                listSET_LIST_ITEM_VALUE( &( pxTCB->xEventListItem ),
                    ( TickType_t ) configMAX_PRIORITIES - ( TickType_t ) pxCurrentTCB->uxPriority );
            }

            /* 所有者が Ready リストにいるなら、正しい優先度のリストへ移す */
            if( listIS_CONTAINED_WITHIN(
                    &( pxReadyTasksLists[ pxTCB->uxPriority ] ),
                    &( pxTCB->xStateListItem ) ) != pdFALSE )
            {
                if( uxListRemove( &( pxTCB->xStateListItem ) ) == 0 ) {
                    portRESET_READY_PRIORITY( pxTCB->uxPriority, uxTopReadyPriority );
                }
                pxTCB->uxPriority = pxCurrentTCB->uxPriority;    /* ★ 昇格 */
                prvAddTaskToReadyList( pxTCB );
            }
            else {
                /* Ready でない（Blocked 中など）なら、値だけ書き換える */
                pxTCB->uxPriority = pxCurrentTCB->uxPriority;
            }
            xReturn = pdTRUE;
        }
        else if( pxTCB->uxBasePriority < pxCurrentTCB->uxPriority ) {
            /* 既に昇格済みだが、元の優先度はもっと低い → 解除が必要 */
            xReturn = pdTRUE;
        }
    }
    return xReturn;
}

ポイントは 3 つ。

uxBasePriority — 元の優先度を覚えておく

#if ( configUSE_MUTEXES == 1 )
    UBaseType_t uxBasePriority;      /* 昇格前の優先度 */
    UBaseType_t uxMutexesHeld;       /* 保持中のミューテックス数 */
#endif

昇格は一時的なものなので、元に戻すために元の値を覚えておく必要がある。 vTaskPrioritySet() を呼ぶと、昇格中なら uxBasePriority だけが変わり、 uxPriority はミューテックス解放時に uxBasePriority に戻る。

5. 実装 — 解除する側

/* xQueueGenericSend の中（ミューテックスを Give したとき） */
if( pxQueue->uxQueueType == queueQUEUE_IS_MUTEX ) {
    xYieldRequired = xTaskPriorityDisinherit( pxQueue->u.xSemaphore.xMutexHolder );
    pxQueue->u.xSemaphore.xMutexHolder = NULL;
}

BaseType_t xTaskPriorityDisinherit( TaskHandle_t const pxMutexHolder )
{
    TCB_t * const pxTCB = pxMutexHolder;

    if( pxMutexHolder != NULL )
    {
        configASSERT( pxTCB == pxCurrentTCB );      /* 所有者本人しか解放できない */
        ( pxTCB->uxMutexesHeld )--;

        if( pxTCB->uxPriority != pxTCB->uxBasePriority )
        {
            /* ★ まだ他のミューテックスを持っているなら、戻してはいけない */
            if( pxTCB->uxMutexesHeld == 0 )
            {
                if( uxListRemove( &( pxTCB->xStateListItem ) ) == 0 ) {
                    portRESET_READY_PRIORITY( pxTCB->uxPriority, uxTopReadyPriority );
                }
                pxTCB->uxPriority = pxTCB->uxBasePriority;      /* 元に戻す */
                listSET_LIST_ITEM_VALUE( &( pxTCB->xEventListItem ),
                    ( TickType_t ) configMAX_PRIORITIES - ( TickType_t ) pxTCB->uxPriority );
                prvAddTaskToReadyList( pxTCB );
                xReturn = pdTRUE;
            }
        }
    }
    return xReturn;
}

uxMutexesHeld == 0 の判定が重要である.

1 つのタスクが複数のミューテックスを持っていることがある。 そのうち 1 つを解放しただけで優先度を戻すと、 まだ持っている別のミューテックスで待たれているタスクが、また逆転する。

だから「全部返すまで昇格を維持する」。 安全側に倒した実装である。

6. FreeRTOS の優先度継承の限界

FreeRTOS の実装は単純化されている。次の 2 点は完全ではない。

限界 1: 連鎖的な継承（chained inheritance）が不完全

H が M1 を待つ → M1 の所有者 L1 を昇格
L1 が M2 を待っている → M2 の所有者 L2 も昇格すべき

理想的には、継承が連鎖して伝播するべきである。 FreeRTOS はこの伝播を行わない（1 段だけ）。

限界 2: 解除のタイミングが粗い

if( pxTCB->uxMutexesHeld == 0 )

正確には「そのミューテックスを待っているタスクのうち最高優先度」まで下げるべきだが、 FreeRTOS は「全部返したら元の値に戻す」という単純な規則を使う。

その結果、必要以上に長く昇格が続くことがある。 安全側なので実害は小さいが、厳密ではない。

FreeRTOS 公式ドキュメントも、これを明記している.

"The priority inheritance mechanism implemented in FreeRTOS is a simplified implementation... it is not a full priority inheritance implementation."

より厳密な保証が必要なら、 優先度上限プロトコル (Priority Ceiling Protocol) を採用した OS を使う。

ただし——実務では FreeRTOS の実装で十分な場合がほとんどである。 限界が問題になるのは、ミューテックスを多段にネストする設計をしたときだけであり、 そういう設計自体を避けるべきである（19 章）。

7. 優先度上限プロトコル（比較のために）

もう 1 つの古典的な解法である。FreeRTOS にはないが、考え方を知っておく価値がある。

各ミューテックスに「上限優先度」を決めておく。 それは「そのミューテックスを使う可能性のあるタスクの最高優先度」。 ミューテックスを取ったタスクは、即座にその上限優先度まで昇格する。

PCP の強みは、デッドロックが構造的に起きなくなることである。 弱みは、すべてのタスクとミューテックスの関係を事前に洗い出す必要があること。

µITRON / TOPPERS、OSEK/VDX（自動車）は上限プロトコルを採用している. 自動車の OSEK では、全リソースの上限優先度を設定ファイルに静的に記述する。 これによりデッドロックが起きないことをビルド時に保証できる。

8. 実務上の指針

「ミューテックスを持ったままブロックしない」が最も重要である.

xSemaphoreTake( xMutex, portMAX_DELAY );
    xQueueReceive( q, &item, portMAX_DELAY );    /* ← 危険 */
xSemaphoreGive( xMutex );

キューにデータが来るまで、ミューテックスを持ったまま寝てしまう。 その間、このミューテックスを待つ全タスクが止まる。 優先度継承をもってしても、これは救えない（昇格しても、寝ているものは走らない）。

クリティカルセクションの中には、必ず終わる処理だけを書くこと。

9. この章のまとめ

次章では、キューやセマフォよりはるかに軽い通知の仕組みを見る。