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("Alice");
        final Worker bob = new Worker("Bob");
        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();
    }
}

發生了什麼？

• Alice 和 Bob 都很餓，湯匙起初在 Alice 手上。
• Alice 發現 Bob 也很餓，於是讓出湯匙。
• 現在湯匙在 Bob 手上，但他看到 Alice 也很餓，又讓回去。
• 湯匙在兩位工人之間「來回跑」，卻沒有人真正開吃——沒有進度。

輸出會長怎樣？

Alice: 讓出湯匙給 Bob
Bob: 讓出湯匙給 Alice
Alice: 讓出湯匙給 Bob
Bob: 讓出湯匙給 Alice
...

如何避免 livelock？

要避免 livelock，可以讓執行緒少一點「過度禮讓」。加入隨機的重試前暫停（例如使用 Thread.sleep）能避免同步反應。也可採更「堅定」的策略：如果剛讓過，就在下一次嘗試前等久一點。另外別讓演算法太講求紳士風度——過度讓步也會導致卡住。

3. Starvation（執行緒飢餓）

如果 livelock 是「永遠的客氣」，那麼 starvation（飢餓）就是一個或多個執行緒一直拿不到資源或 CPU，因為其他執行緒總是搶先一步。

形式化定義

Starvation —— 指執行緒無法取得所需的資源（CPU、記憶體、鎖），因為其他執行緒不斷搶先。結果是「挨餓」的執行緒不是極少被排程，就是完全沒被執行。

造成 starvation 的原因

• 不公平鎖。 例如一般的 synchronized 區塊不保證等待最久的執行緒會先取得。
• 執行緒優先權。 若高優先權執行緒一直占用處理器，低優先權的可能會「餓死」（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/作業系統中，排程器可能會緩和優先權差異，但在某些系統上飢餓仍相當明顯。

另一個例子：因不公平鎖導致的 starvation

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

    public static void main(String[] args) {
        // 5 個執行緒一直搶占 lock
        for (int i = 0; i < 5; i++) {
            new Thread(() -> {
                while (true) {
                    synchronized (lock) {
                        // 長時間持有 lock
                        try {
                            Thread.sleep(100);
                        } catch (InterruptedException ignored) {}
                    }
                }
            }).start();
        }

        // 一個飢餓的執行緒
        new Thread(() -> {
            while (true) {
                synchronized (lock) {
                    System.out.println("飢餓的執行緒拿到 lock 了！");
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException ignored) {}
                }
            }
        }).start();
    }
}

在這個範例中，如果其他執行緒不斷占用 lock，那麼「挨餓」的執行緒可能很久都拿不到。

5. 如何偵測與預防 livelock 與 starvation

如何偵測？

• Livelock：程式在跑、執行緒沒掛住，但沒有進度（沒有結果、無法跳出迴圈）。
• Starvation：某些執行緒幾乎不執行（日誌訊息很少或沒有）。

工具

• 日誌：標記工作開始/結束、資源的取得/釋放。
• 監控：VisualVM、Java Mission Control —— 觀察哪些執行緒活躍、在做什麼。
• Thread dump：檢查是否有執行緒卡在等待 lock。

如何避免？

針對 livelock：

• 不要過度「有禮」地互相讓步——在重試前加入小幅的隨機延遲（Thread.sleep）。
• 在重試順序引入隨機性，避免執行緒同步反應。
• 使用無鎖/非阻塞的結構或演算法（原子變數、CAS 手法）。

針對 starvation：

• 使用「公平」鎖。例如，ReentrantLock 的公平模式：

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。

錯誤 3：濫用執行緒優先權。 企圖透過 setPriority「加速」重要執行緒，常導致其他執行緒的 starvation。沒有必要就別動優先權。

錯誤 4：缺乏監控與日誌。 沒有日誌很難察覺 Livelock 與 starvation：程式「在跑」，卻沒有結果。請記錄關鍵事件並使用分析器/執行緒傾印。

錯誤 5：臨界區過長。 若執行緒長時間持有 lock，其他執行緒就會等待（甚至「挨餓」）。盡量縮短 synchronized/Lock 區塊內的時間。