OS面接：優先度逆転はどのように発生し、優先度継承は何を保証するのか？

問題と適用可能なコンテキスト

シングルコア、固定優先度、プリエンプティブなリアルタイムシステムに3つのタスクがあります。優先度の数値が大きいほど優先度が高いことを意味します：

t=0の時点で、Lがミューテックスを保持しています。その後Hが起床し、Lをプリエンプトしてミューテックスの獲得を試み、ブロックされます。Hがブロックされてから1ms後、Mが実行可能（runnable）になります。通常のミューテックスと優先度継承（PI）を用いた場合の実行順序を説明し、Hのロック待ち時間の上限を計算した上で、以下の点について答えてください：

• 何がこれを「非有界（unbounded）」な優先度逆転にしているのか；
• 複数のミューテックス、待機タスク、およびネストされたブロックが存在する場合、優先度はどのように伝播され、復元されるのか；
• 優先度継承と優先度上限（Priority-Ceiling）プロトコルのトレードオフ；
• 通常のセマフォ、タイムスライスの短縮、またはHの優先度のさらなる引き上げが同等な解決策にならない理由；
• スケジューラトレースとデッドライン指標によって、修正が機能していることをどのように証明できるか。

この質問は、組み込み、RTOS、リアルタイムLinux、ロボティクス、オーディオ/ビデオ、産業制御、およびシステムソフトウェアの職種に適しています。優先度および3ms、20ms、10msという値は演習用の制約であり、特定のRTOSの優先度範囲やプロダクション環境のしきい値を主張するものではありません。

面接官が見ているポイント

第1のレイヤーは、直接的なリソースブロックと無関係な処理によってもたらされる遅延を分離して理解できているかです。HがLによるリソース解放を待つこと自体はすでに優先度逆転です。予測可能性を完全に損なう要因は、Mがそのリソースを使用しないにもかかわらず、低優先度のロック所有者であるLを繰り返しプリエンプトでき、中優先度の処理によってHの待ち時間がいくらでも引き伸ばされてしまう点にあります。

第2のレイヤーは、単に定義を暗唱するのではなく、イベントの時系列シーケンスを描き出せるかです。通常のミューテックスでは、Hがブロックされた後にLが実行可能になりますが、Mが起床するとプリエンプトされます。HはMの20msに加えてLの残りの3ms、つまり約23ms待つことになり、10msのデッドラインを超過します。優先度継承を使用すると、Hはブロックされた瞬間に実効優先度90をLに供与（寄付）します。MはLをプリエンプトできないため、設問の前提下ではHの待ち時間はLの残りの約3msにスケジューラオーバーヘッドを加えた程度になります。

第3のレイヤーは、実装の内部状態を理解しているかです。ロックには所有者と優先度順に並んだ待機者リストが必要です。タスクが複数のロックを保持している場合、その実効優先度は基本優先度とすべてのアクティブな供与優先度の最大値になります。最も優先度の高い待機者がタイムアウトした、キャンセルされた、あるいはロック解放によって待機を終了した場合、優先度は無条件に基本値へリセットされるのではなく、再計算される必要があります。ブーストされた所有者が別のロックでブロックされた場合、優先度供与はPIチェーンに沿って伝播しなければなりません。

第4のレイヤーは、メカニズムの境界を把握しているかです。優先度継承は、中優先度タスクによって引き起こされる非有界な遅延を制限します。クリティカルセクション内のI/O、割り込み禁止領域、プリエンプション禁止コード、ハードウェア処理の時間を短縮するものではなく、デッドロックを解消するものでもありません。優先度上限プロトコルは、事前設定を必要とする代わりに、より静的なブロック解析を可能にします。一意の所有者を持たないカウンティングセマフォには、優先度をブーストすべき特定のタスクが存在しません。

最後に、面接官は検証の厳密さを評価します。優れた回答では、ロック待ち時間、ロック保持中にLが実行可能だが実行されていない時間、Mがその区間に割り込んでいるかどうか、Hのデッドラインミス、ならびにネストされたロックやタイムアウトのパスを比較検証します。平均CPU使用率や「システムがハングアップしなかった」という事実だけでは、リアルタイムの境界を証明したことにはなりません。

回答前に確認すべき質問

• 優先度の数値の方向とスケジューリングポリシーは何か？ 設問では90が50より高く、シングルコアの固定優先度プリエンプティブと指定されています。RTOSによっては優先度の数値が逆向きに定義されている場合があり、通常のタイムシェアリングスケジューラではこのタイムラインをそのまま再現できません。
• 3msは実時間（wall-clock time）か、それとも実際のCPU実行時間か？ ここではLのクリティカルセクション内での残りのCPU処理時間です。PIはデバイス待ちやプリエンプション禁止領域を物理的に高速化することはできません。
• Hの10msのデッドラインはいつ開始するのか？ ここではHが起床した時点から開始します。デッドラインがリクエストの到着時や周期的なリリース時点から始まる場合は、それ以前のキューイング遅延も応答時間の計算に含める必要があります。
• 優先度90より上の割り込みやタスクは存在するか？ この演習では最初の計算からそれらを除外しています。現実の境界計算には、より高優先度の干渉、最大割り込み禁止時間、スケジューラオーバーヘッド、キャッシュの影響を含める必要があります。
• bus_mutexは実際に所有者を追跡するミューテックスか？ バイナリセマフォは似たように見えるかもしれませんが、所有者の概念、所有者のみによるアンロック、またはPIセマンティクスを持たない場合があります。
• Lは別のロックを保持しているか、あるいは別のロックを待っているか？ これにより、供与を再帰的に伝播させる必要があるかどうかが決まり、デッドロック解析とブロック上限の両方が変化します。
• 対象の実装はどのプロトコルをサポートしているか？ POSIXはPTHREAD_PRIO_INHERITとPTHREAD_PRIO_PROTECTを規定しています。複数ロック、タイムアウト、再帰ロック、および優先度引き下げ（deboosting）に対するRTOSの挙動は異なるため、正確なバージョンのドキュメントを確認することが重要です。

30秒で答える要点フレームワーク

「通常のミューテックスでは、Lがbus_mutexを保持しているためHはブロックされます。Lは通常であれば残りの3msを完了できますが、1ms後に優先度50のMが優先度10のLをプリエンプトし、20ms間実行されます。Mはミューテックスに一切触れないにもかかわらず、優先度90のHを間接的に待たせることになります。したがって、Hのロック待ち時間は約20 + 3 = 23msとなり、10msのデッドラインを超過します。中優先度のジョブが到着し続ける可能性がある場合、この余分な待ち時間はLのクリティカルセクションの長さによって制限されなくなります。

優先度継承を使用すると、HがブロックされたことでLの実効優先度が90に引き上げられます。Mが起床してもLをプリエンプトすることはできません。Lは約3ms後にミューテックスを解放し、残りの待機タスクおよび保持しているミューテックスに基づいて自身の優先度を再計算し、Hがロックを獲得します。PIは無関係な中優先度タスクによる遅延を抑制します。ただし、ブロック時間をゼロにすることを保証するものではなく、長いクリティカルセクション、デッドロック、または割り込み禁止コードを修正するものでもありません。

決定論的なリリースシーケンスを実行し、Hのブロックとアンブロック、Lの所有期間、Mの実行区間、および通常ミューテックスとPIミューテックスのデッドラインミスを記録します。また、連鎖的な優先度供与、複数の待機タスク、待機者のタイムアウト、および複数ロックの段階的解放をテストし、優先度のブーストと引き下げの両方が正しく行われることを証明します。」

ステップごとの詳細解説

ステップ1：通常のミューテックスにおける非有界な優先度逆転のタイムラインを描く

Hの起床を相対時間0msとします。Lはすでにロックを保持しており、3msのCPU処理が残っています：

Hは起床からミューテックス獲得までに約23ms待機することになり、10msのデッドラインを逃します。Hがブロックされている間にMのようなジョブが継続して到着し得る場合、Hの待ち時間はLの残りの3msのクリティカルセクションによって制限されなくなります。これがここでの「非有界な逆転（unbounded inversion）」です。これは数学的に無限の待機が不可避であることを意味するのではなく、設計上、保護対象のリソースから導出される有限で監査可能なブロック上限が存在しないことを意味します。

デッドロック、スタベーション（飢餓）、および過負荷（オーバーロード）を区別してください。デッドロックには待機の循環が存在し、どのタスクも必要なリソースを解放できません。スタベーションはロック所有者が関与していなくても発生します。CPU過負荷では一般的に複数のタスクがデッドラインを逃します。優先度逆転の証拠チェーンは明確です：HはLが所有するリソースを待っており、そのリソースに依存していないMがLの実行を妨げています。

ステップ2：優先度継承を追加して再計算する

0msでHがブロックされると、ミューテックスは最も優先度の高い待機者であるHの優先度90を所有者Lに供与します。Lは基本優先度10を維持しつつ、一時的に実効優先度90を持ちます：

3msという結論は設問の前提に依存しています：より高優先度のタスク、長い割り込み禁止領域、プリエンプション禁止セクション、ページフォールト、ブロッキングI/Oが存在せず、ミューテックスが真にPIを実装しているという前提です。現実の応答時間には、H自身の実行時間やすべての高優先度タスクの干渉も含める必要があります。PIの最大の利点は、Mの20msがHのリソースブロック区間に混入しなくなることです。

ブーストは実効優先度を変更するものであり、Lの基本優先度を恒久的に上書きしてはなりません。アンロック後に他の供与が残っていなければ、Lは10に戻ります。Lが保持している別のミューテックスで優先度80の待機者がまだ待機している場合、Lは直接10に戻るのではなく、80にのみ引き下げられる必要があります。

ステップ3：複数の待機タスク、複数のロック、およびPIチェーンを処理する

LがR1とR2の両方を保持しており、H90がR1を待ち、X70がR2を待っていると仮定します。Lの実効優先度は90です。LがR1を解放した後、HはLに優先度を供与しなくなりますが、Xは依然としてR2を待っているため、Lは70に引き下げられます。R2を解放して初めて基本優先度10に戻ります。最も高い待機者のタイムアウトやキャンセルが発生した場合も、同様の再計算がトリガーされなければなりません。

次に、LがKの保持するR3を待っていると仮定します。Lのみをブーストしても、L自身が待機状態から先に進めないため、Hのロックを解放することはできません。優先度90はH → R1 → L → R3 → Kに沿って伝播する必要があります。KがR3を解放することで、Lが進むことができ、最終的にR1が解放されます。Linuxのrt-mutexは、各ミューテックスの優先度順の待機者セットと、所有する各ミューテックスからの最優先待機者を所有者のPI待機者セットに保持することでこれを管理しています。

連鎖的な供与があっても、不適切なロック順序は修正されません。LがKを待ち、KがLを待っている場合、PIは待機サイクルのタスクをブーストするだけであり、実行可能な解放パスは現れません。グローバルなロック順序の遵守、ネスト深度の制限、ミューテックス保持中のブロッキングI/Oの排除、および最悪ケースのクリティカルセクション期間の監査といったエンジニアリング統制が依然として必要です。

ステップ4：優先度継承と優先度上限（Priority Ceiling）を比較する

POSIXのミューテックスプロトコルを見ると、その違いが明確になります：

• PTHREAD_PRIO_INHERIT：所有者は、自身がより高優先度のスレッドを実際にブロックしたときにのみブーストされます。その実効優先度は、基本優先度とアクティブな待機者からの供与の最大値となり、ネストされたブロックは再帰的に伝播します。
• PTHREAD_PRIO_PROTECT：スレッドがミューテックスを保持している間は、現在待機者が存在するかどうかにかかわらず、少なくともそのミューテックスに設定された優先度上限で実行されます。

優先度継承は、競合が発生した際にランタイムの管理コストとチェーン伝播コストを支払いますが、すべての利用者の最大優先度を事前に把握しておく必要はありません。優先度上限プロトコルは、より静的で解析可能なブロック境界を得る代わりに、タスクとリソースのセットが既知であり、正しく設定されていることを要求します。特定の優先度上限プロトコルがある種のデッドロックを防止できるかどうかは、そのシステムの完全な上限アドミッションルールにも依存します。「上限（ceiling）」という言葉だけでデッドロックフリーが証明されるわけではありません。

以下にPOSIXの初期化スケッチを示します。プロダクションコードでは、実装のサポート状況、戻り値、スケジューリング権限、およびミューテックスのライフタイムをチェックする必要があります：

pthread_mutexattr_t attr;
int rc = pthread_mutexattr_init(&attr);
if (rc == 0) {
  rc = pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
}
if (rc == 0) {
  rc = pthread_mutex_init(&bus_mutex, &attr);
}
pthread_mutexattr_destroy(&attr);

Linux上で通常のSCHED_OTHERスレッドにこの属性を設定しても、ハードリアルタイムのデッドラインが保証されるわけではありません。スケジューリングクラス、リアルタイム優先度権限、PREEMPT_RTまたは対象カーネルの挙動、およびアプリケーションのその他すべてのブロック要因の検証が依然として必要です。

ステップ5：適切なプリミティブの選択とクリティカルセクションの短縮

PIは明確な所有者に依存します。高優先度の待機者がブロックされたとき、カーネルはどのタスクをブーストすべきかを把握していなければなりません。共有状態は、所有者によってアンロックされる所有者追跡ミューテックスで保護してください。リソースカウントや通知に使用されるカウンティングセマフォには一意の所有者が存在しない可能性があり、信頼できる供与対象を提供できません。バイナリセマフォも、値が0か1に制限されているというだけでミューテックスのPIセマンティクスを獲得するわけではありません。

PIを使用する場合でも、クリティカルセクションは計算可能にしておく必要があります。ロック下では必要な状態のコピーのみを行います。デバイス転送、ログ記録、メモリ割り当て、スリープする可能性のある呼び出しはロックの外に移動します。低速デバイスへのシリアルアクセスには、専用の高優先度サービスタスクとメッセージパッシングを用いたアーキテクチャの方が適している場合があります。ロックフリー構造はミューテックスによるブロックを減らすことができますが、メモリ解放、ABA問題、リトライ、および最悪ケース実行時間（WCET）の悪化を招く可能性があります。単なる名称ではなく、デッドライン解析に基づいて選択してください。

Hの優先度をさらに上げても、この問題は解決しません：Hはすでに最優先タスクであり、ブロック中は実行できません。タイムスライスを短くしても、単にMがより頻繁にスケジュールされるだけであり、優先度10のLが優先度50のMより優先されるわけではありません。プリエンプションを無効化すると、すべてのタスクの応答レイテンシが増大し、問題がプリエンプション禁止領域に移行するだけです。

ステップ6：再現可能なトレースによるブロック上限の検証

確定的なリリース順序を作成します：まずLがロックを獲得し、バリアによって所有権を確認し、Hがリリースされ、Hがブロックされてから1ms後にMがリリースされます。通常ミューテックス、PIミューテックス、優先度上限ミューテックスの各バリアントを繰り返し実行し、以下を記録します：

• Hのミューテックス獲得レイテンシ分布と10msデッドラインミスの回数；
• ミューテックスを保持している間にLが実行可能だが実行されていない累積時間；
• Hがブロックされている間のMの実行区間；
• Lの基本優先度と実効優先度、ミューテックス所有者、最優先待機者、およびアンロック時刻；
• スケジューラスイッチ、起床、割り込み禁止時間、およびプリエンプション禁止区間。

通常ミューテックスのトレースでは、Mがその区間に割り込み、Hが約23ms待機する様子が示されるはずです。PIバリアントでは、Hが待機中でLがミューテックスを保持して実行可能な区間において、Mがプリエンプトしてはなりません。設問の負荷条件下では、Hの待機時間は23msではなく3ms近くになるはずです。優先度70の第2の待機者、ネストされたミューテックス、待機者のタイムアウト、およびLが持つ2つのロックの段階的解放を追加し、現在のアクティブな最高供与優先度に対してブーストと引き下げが正しく機能することを検証します。

合否判定基準を単に「PIを導入したからタイムアウトがなくなった」としてはなりません。条件付きの上限を使用します：測定された最大クリティカルセクション、最高優先度の干渉、最大割り込み禁止時間、およびスケジューラオーバーヘッドの予算を前提として、負荷テストやフォールトインジェクション環境下を含め、Hの最悪ケース応答時間が10ms未満に収まることを検証します。

模範解答の例

「まず、優先度の方向と時間の原点を定義します：90が最高優先度であり、Hの10msはHが起床した時点から始まります。通常のミューテックスでは、HがLをプリエンプトしますが、bus_mutexが保持されていることを検知してブロックされます。Lは1ms間実行を再開しますが、その後優先度50のMが起床し、Lを20ms間プリエンプトします。Lはようやく残りの2msを実行してアンロックします。したがって、Hは起床からミューテックス獲得までに約23msを要し、デッドラインを確実に逃します。Mはミューテックスを一切使用しませんが、最優先タスクであるHの実行を間接的に妨げます。中優先度の処理が継続的に到着し得る場合、Lの3msのクリティカルセクションではこの余分なブロック時間を抑えることができません。

優先度継承を使用すると、Hがブロックされた時点でLに優先度90が供与されます。Lの基本優先度は10のままで実効優先度が90になるため、1msの時点でMがプリエンプトすることはできません。Lは約3msでクリティカルセクションを完了してミューテックスを解放し、その後Hがそれを獲得します。したがって、設問の前提下ではリソースブロック時間は10ms未満に抑えられます。高優先度タスク、割り込み禁止時間、スケジューラオーバーヘッドはこの数値から除外されており、実際の応答時間解析ではそれらを加算する必要があります。

実装において単一のブーストフラグ（Boolean）だけを保持することはできません。各ミューテックスには所有者と最優先待機者が必要です。各所有者は、基本優先度と所有するすべてのミューテックスにわたる供与優先度の最大値を取ります。最優先待機者のタイムアウトや1つのロックの解放が発生すると、再計算が行われます。LがKのロックでブロックされている場合、優先度90はPIチェーンに沿ってKに伝播しなければなりません。待機の循環がある場合、優先度をブーストしてもリソースは解放されないため、ロック順序の遵守とデッドロックチェックは依然として不可欠です。

1つのリリースシーケンスを用いて通常ミューテックスとPTHREAD_PRIO_INHERITミューテックスを比較し、スケジューラスイッチ、ロック所有権、実効優先度、Hのブロック時間、デッドラインミスをキャプチャします。直接的な合格証拠となるのは、Hがブロックされ実行可能なLがミューテックスを保持している間にMが実行されなくなること、そしてHの待ち時間が約23msからLの残り約3msのクリティカルセクション＋計上されたシステム干渉へと収束することです。第2の待機者、ネストされたロック、タイムアウト、および1つずつのアンロックを追加することで、連鎖的なブーストと正しい優先度の引き下げを検証します。」

よくある間違い

• 「低優先度タスクが高優先度タスクをブロックする」とだけ答える → Mが有限のクリティカルセクションを非有界な干渉に変えてしまう仕組みが抜け落ちています → 「Hがブロック、Lが実行可能、Mがプリエンプト」という完全なシーケンスを描いてください。
• Hの待ち時間を3msとだけ計算する → 通常ミューテックス下でのMによる20msのプリエンプションを無視しています → イベントの順序を追って約23msを導き、10msと比較してください。
• PIがあらゆる優先度逆転を排除すると主張する → Hは依然としてLの残りのクリティカルセクションを待つ必要があります → PIは無関係な中優先度タスクによる非有界な引き伸ばしを排除するものであると述べてください。
• 1つのアンロック後にLを直接10にリセットする → 保持している別のミューテックスに高優先度の待機者が残っている可能性があります → すべてのアクティブな供与から実効優先度を再計算してください。
• 直接の所有者のみをブーストする → 別のロックでブロックされている所有者は依然として実行できません → PIチェーンに沿って伝播させ、チェーンの深さを制限・監視してください。
• PIをデッドロックの解決策として扱う → 待機サイクルにあるブーストされたタスクには実行可能な解放パスがありません → ロック順序、タイムアウトポリシー、およびデッドロック検出を維持してください。
• PIを前提としながらミューテックスをバイナリセマフォに置き換える → セマフォには所有者が存在しない場合があり、ブーストすべきタスクがありません → リソース保護にはPIを明示的にサポートする所有者ミューテックスを使用してください。
• PTHREAD_PRIO_INHERITをハードリアルタイムの万能スイッチとして扱う → スケジューリングクラス、権限、カーネルのプリエンプション、割り込み、およびその他の待機がデッドラインに影響を与えます → プラットフォーム全体を検証し、最悪ケース応答時間を計算してください。
• 平均レイテンシの改善のみを確認する → 優先度の引き下げ、ネストされた伝播、またはタイムアウトパスにバグが残っている可能性があります → テールレイテンシ、デッドラインミス、実効優先度、および複数ロックの境界を検証してください。

フォローアップ質問と回答

フォローアップ1：ここでMの実行時間が正確に20msであるのに、なぜ「非有界（Unbounded）」と呼ぶのか？

この演習にはMのジョブが1つしか含まれていないため、結果は約23msと算出できます。「非有界」とは、追加される遅延に対してLのクリティカルセクションに基づく上限が存在しないメカニズムを表しています。Mクラスのジョブが継続的にリリースされ得る場合、LはCPUを割り当てられないまま実行可能状態にとどまり、Hの待ち時間はMの処理量に応じて増大します。PIはこのブロック区間からMの干渉を排除します。残る上限はクリティカルセクションと高優先度の干渉から導かれます。

フォローアップ2：HがLを待ち、LがKを待っている場合はどうなるか？

Hの90をLに供与し、さらにLが待機しているミューテックスを通じて所有者Kに伝播させます。Kは実効優先度90でクリティカルセクションを実行して解放し、それによってLが進むことができ、最終的にHのロックが解放されます。トレースでは、H → mutex1 → L → mutex2 → Kにわたるブーストと逆順の引き下げが確認できるはずです。Lのブーストだけを観察しても、連鎖的なPIが正しいことの証明にはなりません。

フォローアップ3：高優先度の待機者がタイムアウトした後、Lの優先度はどうなるべきか？

残っている最も高い要求値を使用します。H90がタイムアウトしても、Lが保持する別のミューテックスをX70がまだ待っている場合、Lは90から70に引き下げられます。すべての供与が消滅して初めて基本優先度10に戻ります。待機タスクの追加、離脱、タイムアウト、キャンセル、および各アンロックにおいて、この優先度順の状態を維持しなければなりません。

フォローアップ4：優先度上限（Priority Ceiling）は常に優先度継承より優れているか？

いいえ。タスクセットとリソースアクセス関係が静的で安定している場合、優先度上限は静的なブロック解析を可能にしますが、不適切な上限設定は正当なアクセスを拒絶したり解析を無効化したりする可能性があります。優先度継承は実際の競合発生時にブーストするため事前設定が少なくて済みますが、待機者リストの管理、チェーン伝播、および動的な優先度引き下げを処理する必要があります。RTOSの正確なプロトコル、タスクセットの安定性、および許容可能な実行時オーバーヘッドに基づいて選択してください。

フォローアップ5：ロック保持中のI/OをPIで解決できないのはなぜか？

ブーストは、所有者が実行可能（runnable）である場合にのみ、より早くCPUを獲得できるように支援します。LがSPI転送、ストレージアクセス、ページフォールト、その他のイベントでスリープしている場合、スリープ状態のままです。また、割り込み禁止またはプリエンプション禁止で実行されている場合、スケジューラは介入できません。低速な処理はクリティカルセクションの外に移動するか、サービスタスクや非同期プロトコルを使用し、ハードウェアの最悪完了時間を予算に含めてください。

フォローアップ6：Linuxのユーザ空間でこの属性が実際に機能していることをどのように証明するか？

pthread_mutexattr_setprotocolとpthread_mutex_initの戻り値、_POSIX_THREAD_PRIO_INHERITのサポート状況、スレッドの実際のスケジューリングポリシー、およびリアルタイム優先度権限を確認します。次に、制御されたH/M/Lワークロードを実行し、スケジューリングおよびfutexやロックのイベントをトレースします。Lの実効ブースト、クリティカルな区間におけるMの不在、ならびにアンロック後や待機者のタイムアウト後における正しい優先度の引き下げを確認します。初期化の成功や偶発的なp99値の改善だけでは不十分な証拠です。