障害・アンチパターン図鑑 · 基礎から応用へ

優先度逆転

高優先度の待機者が依存するロック所有者を追い、優先度継承の効果と時間上限の限界を理解します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 高優先度でも資源を待つ
  2. 低・中・高の実行順を紙上で追う
  3. 所有者の実効優先度を引き上げる
  4. 入れ子の依存で継承が伝わる
  5. mutexの契約と測定対象をそろえる
  6. 時間上限と改善の条件を確かめる
  7. この記事をロゲイアに質問する理解を確かめる

高優先度でも資源を待つ

優先度逆転は、高優先度の仕事が低優先度の仕事の持つ資源を待ち、その所有者の進行が中優先度の仕事によって遅れる現象です。スケジューラが設定通りに高い優先度から実行していても、資源を取得できない仕事は先へ進めません。低優先度の所有者を進めることが、高優先度の待機者を進めるための前提になります。単にロックを待つ時間があることと、無関係な中優先度の仕事がその待ちを延ばすことを分けます。デッドロックのような待機の循環は必須ではありません。問題を見つけるには、待機者の優先度だけでなく、必要な資源、所有者、その所有者を実行できなくしている仕事を一つの依存として追う必要があります。

低・中・高の実行順を紙上で追う

説明用に単一CPUと固定優先度を仮定し、Lがmutexを取得した後でHが到着するとします。Hは同じmutexを要求し、取得できずに待ちます。次にMが実行可能になると、MはLより高優先度なのでLより先に動きます。HはMより高いのに、Hの必要なmutexを解放できるLが動けません。Lが残り1msで解放できる仮定でも、Mが20ms動けば待ちはLの残り時間だけでは説明できません。この数値は順序を考えるための仮定で、実測や期限保証ではありません。Mが繰り返し到着する場合、単純な優先度規則だけでは、無関係な仕事による延長を抑えられないことがあります。複数CPUでは実行場所などの条件も追加されます。

所有者の実効優先度を引き上げる

優先度継承では、高優先度の待機者を妨げるmutex所有者の実効優先度を一時的に引き上げます。LがHの優先度を継承してMより先に進めば、保護した処理を終えて解放し、Hが実行できるようになります。H自身の優先度をさらに上げても、Hが資源待ちで実行不能なら同じ効果にはなりません。Linuxのrt-mutexはこの関係を扱う実装です。所有者の明確なmutexと、通知や資源数だけを表すsemaphoreは契約が違います。名前が似た同期APIだから、同じ継承が使えると判断しないようにします。実際に選んだ言語、ライブラリ、OS、属性設定で継承が有効かを確認し、利用できなかった場合を単に成功扱いしてはいけません。

入れ子の依存で継承が伝わる

HがL1のロックを待ち、L1も別のロックをL2から待っている場合、Hを助けるにはL2の進行が必要です。継承を直接の所有者だけで止めると、依存の奥にある仕事を進められません。Linuxの実装はこのような連鎖へ優先度を伝え、待機者や保持状態の変化に応じて実効優先度を調整します。解放後に元へ戻す処理も、他に高優先度の待機者が残るかを含めて扱う必要があります。ただし優先度継承はロック取得順の循環をなくすものではありません。デッドロックの条件、再帰的な取得、タイムアウトやキャンセルの処理は別に設計します。優先度を上げる規則を追加しただけで共有状態の不変条件まで守られるわけでもありません。

mutexの契約と測定対象をそろえる

観測ではHの取得要求と取得成功、Lの保持区間、Mの実行区間を対応させます。Hの待ち時間だけが長いというログでは、長いI/O、CPU quota、停止中の所有者、他の待機原因を区別できません。スケジューリング方針、優先度の設定に成功したか、CPU affinity、mutex属性、対象カーネルを記録します。実時間スケジューリングへ権限なしで設定した試験が失敗したのに、通常のスケジューラの結果を優先度継承の評価として使わないようにします。計測コード自体のロックや出力が実行順へ影響する場合もあります。まず図やイベント列で依存を説明し、その仮説に必要な範囲だけを観測します。観測対象以外の仕事も含めて優先度を一律に上げる変更は避けます。

時間上限と改善の条件を確かめる

対策の基本はクリティカルセクションを短くし、予測できないI/Oや外部呼び出しを保持区間から外すことです。必要なら継承や優先度上限の方式を持つ同期を選びますが、いずれも前提を確認します。所有者が無期限の外部応答を待つなら、実効優先度を上げても待ちの上限は得られません。割込み、非プリエンプト区間、入れ子のロック、CPU割当ても期限の議論へ入ります。変更後はHの待機分布と期限超過、他の仕事の飢餓や処理率を比較します。全仕事へ高優先度を配ることが解決ではありません。どの依存を短くしたか、その結果として必要な仕事がどの条件で間に合うかを、測定と設計上の前提の両方から説明します。

優先度上限方式を使う場合も、資源を利用する全仕事と上限の設定が分析の前提に合うかを確認します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 18

サーバーの中で起きていること · STEP 15

学習コースから次を選ぶ