ライブロックとスタベーションの発生と対策

「止まっていないのに進まない」二つの病

/os/deadlock/は全員が完全に停止する膠着でした。本記事が扱う2つは、それと似て非なる障害です。

ライブロック（livelock） は、各処理が「衝突したら一歩引く」という良かれと思った応答を取り続けた結果、状態は絶えず変化するのに全体としてどの処理も完了しない状態です。狭い通路で人がすれ違おうと互いに同じ方向へよける動作を延々繰り返す様子が典型例です。CPUは100%回り続け、ロックも握られないのに前進ゼロ——デッドロックより発見が難しいのはこのためです。

スタベーション（starvation、飢餓） は、システム全体は前進しているのに、ある特定の処理だけが必要な資源をいつまでも獲得できず後回しにされ続ける状態です。こちらは「全体の進行」と「個々の進行保証」が別物だという点を突いた障害です。

ライブロックの発生機構

ライブロックは「衝突を検知して譲る」設計から生まれます。横取り不可を崩すために/os/deadlock/で触れた「取れなければ持っている資源を手放してやり直す」予防策が、皮肉にも温床になります。

スレッド1: lock(A) 取得 → lock(B) を試す → 失敗
          → デッドロック回避のため A を手放してリトライ
スレッド2: lock(B) 取得 → lock(A) を試す → 失敗
          → 同じく B を手放してリトライ
両者が完全に同期して同時に手放し、同時に取り直す
→ 毎回ぴったり衝突し、永遠に B も A も揃わない

ここでの本質は同期したリトライです。2スレッドが同じタイミングで「取得→失敗→解放→再取得」のサイクルを刻むため、ロックを手放す瞬間も取りに行く瞬間も常に一致し、衝突が再生産され続けます。デッドロックの4条件のうち循環待ちは「手放す」ことで形式的には崩れているのに、手放しと取り直しの位相が揃っているせいで実質的な膠着が残るわけです。CASループでも同型の現象が起きます。2つのコアが同じキャッシュ行を更新しようと/os/lock-free-cas/のCASを撃ち合うと、互いに相手の更新で expected 値が外れて再試行を繰り返し、どちらも成功しない——ロックフリーであってもリブネスは保証されない好例です。

ランダム化と指数バックオフ

ライブロックの根が「同期した譲り合い」にある以上、対策は位相を意図的にずらすことに尽きます。最も基本的なのが、リトライ前に待つ時間をランダム化することです。

naive:   失敗 → 即リトライ        （位相が揃ったままで衝突再発）
random:  失敗 → random(0..W) 待つ → リトライ（位相がばらけて一方が先着）

各スレッドが独立な乱数でずれた時間だけ待てば、次の取得タイミングが一致する確率が下がり、どちらかが先に資源を揃えて前進できます。さらに衝突が続くほど待ち窓 W を倍々に広げるのが指数バックオフ（exponential backoff） です。Ethernetの衝突回避（truncated binary exponential backoff）やTCPの再送、分散ロックのリトライで広く使われる定石です。

試行 n 回目: W = base * 2^min(n, cap)   の範囲で待ち時間を一様乱択
            （capで上限を設け、無制限な遅延爆発を防ぐ）

指数で広げる理由は、競合の度合いに待ち窓を自動追従させるためです。衝突が頻発する＝多数が同じ資源を争っている局面では W を大きく取って分散させ、競合が収まれば窓は小さく保ってレイテンシを削れます。ランダム化が無く決定的に倍々で待つだけだと、複数スレッドが同じ倍率で広げてしまい位相が揃ったままになり得ます。ランダム化と指数増加は必ずセットで効きます。

スタベーションの発生機構

スタベーションは、資源配分の方式そのものに偏りがあると生じます。代表的な発生源を押さえます。

• 優先度ベースのスケジューリング：高優先度タスクが切れ目なく到着すると、低優先度タスクへCPUが回らない。/os/realtime-scheduling/の固定優先度方式に内在する弱点です。
• LIFO的な待ち行列：後から来た要求を先に処理すると、先着の要求が後発に追い越され続け、最初に並んだ者が永久に取れない。
• 読者書込者ロックの偏り：読者を無制限に通す実装では、読者が途切れず到着する限り書込者が待たされ続ける（書込者飢餓）。逆に書込者を最優先にすれば読者飢餓が起きる。
• スピンロックの奪い合い：単純なスピンロックは解放時に取れた者勝ちのため、運の悪いコアが何度も負ける。

共通項は、「全体は進んでいる」ことと「全員が進む」ことが両立していない点です。システムのスループットを見ても飢餓は見えず、個々の処理の最大待ち時間（最悪レイテンシ）を見て初めて表面化します。

公平性保証によるスタベーション回避

スタベーションを確率任せでなく構造的に消すのが公平性保証です。中核は「待っている要求に有界な待ち時間を約束する」ことで、強さに段階があります。

最も実用的なのが待ち行列のFIFO化です。資源待ちを到着順のキューで管理し、解放時は必ず先頭の要求へ渡せば、後発が先着を追い越せず追い越し回数の上限がゼロになります。/os/spinlock-design-variants/のティケットロックは、銀行の整理券と同じく「取得時に番号を引き、いま呼ばれている番号と一致したら入れる」方式で、ハードウェアレベルでFIFOを実現しスピンロックの奪い合い飢餓を解消します。MCSロックは各待ち手を連結リストにつなぎ、解放者が次のノードだけを起こすことで、FIFO性を保ちつつキャッシュ行の奪い合いも避けます。

スケジューラ側の公平性も同型の発想です。/os/cfs-scheduler-internals/のCFSは各タスクの累積実行時間（vruntime）を記録し、常に最も「走っていない」タスクへCPUを渡すことで、優先度に基づく飢餓を防ぎます。nice値は配分の重みを変えるだけで、低優先度タスクのvruntimeもいずれ最小になり順番が回る——配分が偏っても誰もゼロにはならない設計です。読者書込者ロックの書込者飢餓も、「待機中の書込者がいたら新規読者の入場を止める」フェアな変種で解消します。

まとめ

• ライブロックは、衝突検知後の譲り合いが同期して再生産され、状態は変わるのに全体が前進しない膠着。CPUは飽和するためデッドロックより検知が難しい。
• 対策はランダム化と指数バックオフで譲り合いの位相をずらすこと。両者はセットで効き、競合度に待ち窓を自動追従させる。ただし個別の飢餓は防げない。
• スタベーションは、優先度・LIFO待ち行列・読者書込者の偏りなどで、全体は進むのに特定処理だけが資源を取れない状態。最悪レイテンシで初めて表面化する。
• 構造的解決は公平性保証で、待ち行列のFIFO化（ティケット／MCSロック）による有界待ち、CFSのvruntimeによる公平配分が代表例。
• 基礎は/os/concurrency-control/、対になる膠着は/os/deadlock/も参照。