ライブロックとは：デッドロックとの違いと5つのポイント

概要¶

ライブロック（Livelock）とは、スレッドがブロックされていないにもかかわらず、互いに反応し合って永遠に進歩できない状態のこと。デッドロックと混同しやすいが「動いているのに進まない」という点が異なる。ランダムバックオフや再試行制限で解消できる。

詳細¶

デッドロック vs ライブロック¶

特性	デッドロック	ライブロック
スレッドの状態	ブロック（停止している）	実行中（動いている）
CPU消費	低い（待機中）	高い（アクティブに動いている）
進行	なし	なし
検出難易度	比較的検出しやすい	発見しにくい
典型例	ミューテックスの循環待ち	互いに譲り合い続けるスレッド

ライブロックのイメージ¶

「廊下で正面衝突した2人が、お互い同じ方向に避け続ける」

  Thread A: 「どうぞ」→ 右に避ける
  Thread B: 「どうぞ」→ 右に避ける
  Thread A: 「どうぞ」→ 左に避ける
  Thread B: 「どうぞ」→ 左に避ける
  ...永遠に繰り返す（礼儀正しすぎて誰も通れない）

発生しやすいコンテキスト¶

1. ロックフリーコード（ブロッキングなし、アトミック操作）
   → CASループで互いの変更を上書きし合い続ける

2. 楽観的同時実行制御（Optimistic Concurrency）
   → 「競合なしを期待、衝突したらリトライ」の設計で
     無限リトライになる

Go での例（ライブロックが発生しうるパターン）¶

// 悪い例：固定の再試行でライブロックになりうる
for {
    if tryAcquireResource() {
        break
    }
    // 毎回同じタイミングで競合すると永遠に解消しない
    time.Sleep(10 * time.Millisecond)
}

// 良い例：ランダムバックオフで競合を回避
for i := 0; i < maxRetries; i++ {
    if tryAcquireResource() {
        break
    }
    // ランダム要素を加えることで競合を分散させる
    jitter := time.Duration(rand.Intn(100)) * time.Millisecond
    time.Sleep(10*time.Millisecond + jitter)
}

5つのポイント（まとめ）¶

1. ライブロック = スレッドが互いに反応し合い、進歩がない状態

2. 例え：「どうぞ」→ 礼儀正しすぎて誰も通れない
         誰も前に進めない

3. スレッドはリトライし続ける → 永遠に譲り合い

4. 発生しやすい場所:
   - ロックフリーコード（アトミック操作）
   - 楽観的同時実行制御（衝突したらリトライ）

5. 解決策:
   - ランダムバックオフを追加する
   - リトライ回数を制限する
   - 調整機構（コーディネーター）を使う

なぜ重要か / いつ使うか¶

並行処理の面接で「デッドロックとライブロックの違いは？」と聞かれたとき
ロックフリーなデータ構造を設計するときの落とし穴として
CASループや楽観的ロックを実装するときの注意点として