Livelock と Starvation: 定義と例

1. Livelock 入門

deadlock はスレッド同士が互いに待ち続けて永遠に停止する状態であり、livelock（ライブロック）はスレッドが生きていて常に何かを行い、互いに譲り合っているのに…誰も前進しない状態です。狭い廊下での礼儀正しい二人を想像してください。「お先にどうぞ！」—「いえ、どうぞ！」—「いえいえ、どうぞ！」—これが延々と続くようなものです。

形式的な定義

Livelock とは、スレッドはブロックされていないものの、他スレッドの動作に反応して自分の状態を絶えず変更し続けるため、処理を完了できない状況です。スレッドは「生きて」いて活発に反応していますが、有益な仕事をしていません。

実際にはどう見えるか？

• スレッドは永久にブロックされてはいないが、譲り合いの無限ループにハマる。
• システムは固まってはいないが、本来すべき処理が進まない。

身近な例

• 狭い通路ですれ違う必要がある二台のロボットが、毎回同時に互いの側へ避けてしまい、再び邪魔をしてしまう。
• ある資源が使用中であることを毎回検出しては、互いに譲り合い続ける二つのスレッド…が無限に続く。

2. Java による livelock の例

コードで livelock をシミュレートしてみましょう。簡単のため、一本のスプーンを必要とする二人の「作業者」を用います。deadlock と違い、スプーンが占有されていたら、彼らは礼儀正しく譲って再試行します—ただし同時に、同期して。

コード例：「礼儀正しい作業者」

public class LivelockDemo {
    static class Spoon {
        private Worker owner;

        public Spoon(Worker owner) {
            this.owner = owner;
        }

        public Worker getOwner() {
            return owner;
        }

        public synchronized void setOwner(Worker owner) {
            this.owner = owner;
        }

        public synchronized void use() {
            // スプーンの使用（何もしない）
        }
    }

    static class Worker {
        private final String name;
        private boolean isHungry = true;

        public Worker(String name) {
            this.name = name;
        }

        public String getName() {
            return name;
        }

        public boolean isHungry() {
            return isHungry;
        }

        public void eatWith(Spoon spoon, Worker other) {
            while (isHungry) {
                // スプーンが自分のものではない場合は待つ
                if (spoon.getOwner() != this) {
                    try {
                        Thread.sleep(1); // スプーンが空くまで待つ
                    } catch (InterruptedException ignored) {}
                    continue;
                }
                // 相手が空腹ならスプーンを譲る
                if (other.isHungry()) {
                    System.out.println(name + ": スプーンを譲ります " + other.getName());
                    spoon.setOwner(other);
                    continue;
                }
                // 食べる！
                System.out.println(name + ": 食事中です！");
                spoon.use();
                isHungry = false;
                System.out.println(name + ": 食べ終わりました！");
                spoon.setOwner(other);
            }
        }
    }

    public static void main(String[] args) {
        final Worker alice = new Worker("アリス");
        final Worker bob = new Worker("ボブ");
        final Spoon spoon = new Spoon(alice);

        Thread t1 = new Thread(() -> alice.eatWith(spoon, bob));
        Thread t2 = new Thread(() -> bob.eatWith(spoon, alice));

        t1.start();
        t2.start();
    }
}

何が起こっているのか？

• アリスとボブはどちらも空腹で、スプーンは最初アリスが持っています。
• アリスはボブも空腹だと見て、スプーンを譲ります。
• 今度はボブがスプーンを持ちますが、アリスが空腹だと見て彼女に譲ります。
• スプーンが作業者の間を「行ったり来たり」するだけで、誰も食べない—進捗がありません。

出力はどう見えるか？

アリス: スプーンを譲ります ボブ
ボブ: スプーンを譲ります アリス
アリス: スプーンを譲ります ボブ
ボブ: スプーンを譲ります アリス
...

livelock をどう防ぐか？

livelock を避けるには、スレッドの「礼儀」を少し薄めるとよいです。再試行の前にランダムな待機（例えば Thread.sleep）を入れると、スレッドが同期して反応しなくなります。より「粘る」戦略も有効です：一度譲ったら、次の試行まで少し長めに待つ。アルゴリズムでの過度な譲り合いは禁物—行き過ぎた譲歩もハングの原因になります。

3. Starvation（スレッドの飢餓）

livelock が「永遠の譲り合い」だとすれば、starvation（飢餓）は、他のスレッドが常に先行してしまうために、あるスレッドが資源や CPU に全く（またはほとんど）アクセスできないことです。

形式的な定義

Starvation とは、他のスレッドに常に先を越されるため、スレッドが必要な資源（CPU、メモリ、ロック）にアクセスできない状況です。その結果、「飢餓」状態のスレッドはごく稀にしか実行されないか、全く実行されません。

starvation の原因

• 不公平なロック。 例えば通常の synchronized ブロックは、最も長く待っているスレッドが先に入れることを保証しません。
• スレッド優先度。 高優先度のスレッドが常に CPU を専有していると、低優先度のスレッドは「飢餓」状態になり得ます（setPriority）。
• 他スレッドの無限ループ。 誰かが CPU を譲らない（Thread.sleep や Thread.yield() を呼ばない）場合、他のスレッドは実行時間を得られないことがあります。

4. Java による starvation の例

例：低優先度スレッドが実行されない

public class StarvationDemo {
    public static void main(String[] args) {
        Runnable highPriorityTask = () -> {
            while (true) {
                // 集中的な処理で CPU を譲らない
            }
        };

        Runnable lowPriorityTask = () -> {
            while (true) {
                System.out.println("私は低優先度のスレッドです！");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException ignored) {}
            }
        };

        Thread high1 = new Thread(highPriorityTask);
        Thread high2 = new Thread(highPriorityTask);
        Thread low = new Thread(lowPriorityTask);

        high1.setPriority(Thread.MAX_PRIORITY); // 10
        high2.setPriority(Thread.MAX_PRIORITY); // 10
        low.setPriority(Thread.MIN_PRIORITY);   // 1

        high1.start();
        high2.start();
        low.start();
    }
}

どう現れるか？

• 高優先度スレッドが常に忙しく、CPU を譲らない。
• 低優先度スレッドはほとんど実行されない（あるいは全く実行されない）。
• 最近の JVM/OS ではスケジューラが優先度を平滑化することもありますが、システムによっては飢餓がはっきり出ます。

もう一つの例：不公平なロックによる starvation

public class StarvationLockDemo {
    private static final Object lock = new Object();

    public static void main(String[] args) {
        // 常に lock を取得し続ける 5 つのスレッド
        for (int i = 0; i < 5; i++) {
            new Thread(() -> {
                while (true) {
                    synchronized (lock) {
                        // lock を長時間保持する
                        try {
                            Thread.sleep(100);
                        } catch (InterruptedException ignored) {}
                    }
                }
            }).start();
        }

        // 1 つの飢餓状態のスレッド
        new Thread(() -> {
            while (true) {
                synchronized (lock) {
                    System.out.println("飢餓状態のスレッドが lock を取得しました！");
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException ignored) {}
                }
            }
        }).start();
    }
}

この例では、他のスレッドが常に lock を占有していると、「飢餓」スレッドが lock に非常に長い間アクセスできないことがあります。

5. livelock と starvation の検出と防止

検出方法

• Livelock：プログラムは動いており、スレッドもハングしていないのに、進捗がない（結果が出ない、ループから抜けない）。
• Starvation：一部のスレッドがほとんど実行されない（ログに稀にしか現れない、または全く現れない）。

ツール

• ログ記録：開始/終了、資源の取得/解放を記録する。
• モニタリング：VisualVM、Java Mission Control—どのスレッドがアクティブで何をしているかを見る。
• Thread dump：スレッドが lock の待機で詰まっていないか確認する。

回避方法

livelock の場合：

• 「礼儀正しい」譲り合いをやり過ぎない—再試行前に小さなランダム遅延を入れる（Thread.sleep）。
• 再試行の順序にランダム性を入れて、スレッドの同期的な振る舞いを避ける。
• ノンブロッキングのデータ構造/アルゴリズム（アトミック変数、CAS（Compare-And-Swap）アプローチ）を使う。

starvation の場合：

• 「公平」なロックを使う。例えば、ReentrantLock の fairness：

java.util.concurrent.locks.ReentrantLock lock = new java.util.concurrent.locks.ReentrantLock(true); // フェアモード

• スレッド優先度の乱用は避ける—基本はデフォルト優先度のままにする。
• クリティカルセクション内の時間を最小化する（synchronized/Lock）。
• FIFO に近い順序で処理されるタスクキューを使う。

表：Deadlock、Livelock、Starvation の比較

たとえと豆知識

• Livelock：すれ違うために同時に左に一歩寄る二人のようで、またぶつかってしまう。
• Starvation：店のレジで、店員が「知り合い」だけを優先して、他の人は永遠に待たされる行列のようなもの。

豆知識：livelock は deadlock より稀ですが、検出はより難しい—プログラムは「固まって」いないのに、何かをしているためです。

6. livelock と starvation に関する典型的なミス

ミス1：「礼儀正しい譲り合い」に遅延がない。 スレッドが休止せずに互いに譲り合い続けると、livelock に陥る可能性があります。資源の再取得を試みる前に小さなランダム遅延（Thread.sleep）を入れましょう。

ミス2：synchronized のみで待機し、公平なロックを使わない。 スレッド数が多いと、通常の synchronized は「最も飢餓状態の」スレッドにアクセスを保証しません。重要であれば ReentrantLock の fairness を使いましょう。

ミス3：スレッド優先度の乱用。 重要スレッドを「加速」しようとして setPriority を使うと、他のスレッドの starvation を招くことがよくあります。実際に必要な場合を除き、優先度はいじらないでください。

ミス4：モニタリングやログ記録の不足。 Livelock や starvation は、ログがないと気づきにくいものです：プログラムは「動いている」のに、結果が出ません。重要イベントをログに残し、プロファイラやスレッドダンプを活用しましょう。

ミス5：クリティカルセクションが長すぎる。 スレッドが lock を長時間保持すると、他のスレッドは待たされ（あるいは「飢餓」状態になります）。synchronized/Lock ブロック内の滞在時間を最小化しましょう。