Livelock và Starvation: định nghĩa và ví dụ

1. Làm quen với Livelock

Nếu deadlock — là khi các luồng đứng yên và chờ nhau mãi mãi, thì livelock (khóa “sống”) — là khi các luồng vẫn “sống”, liên tục làm gì đó, nhường nhau, nhưng... không ai tiến lên cả! Hãy tưởng tượng hai người lịch sự trong hành lang hẹp: “Ôi, bạn đi trước đi!” — “Không, bạn đi!” — “Không, bạn đi!” — và cứ thế vô tận.

Định nghĩa chính thức

Livelock — tình huống khi các luồng không bị khóa cứng, nhưng do liên tục thay đổi trạng thái để phản ứng với hành vi của các luồng khác nên không thể hoàn thành công việc. Chúng “sống”, phản ứng tích cực, nhưng không tạo ra công việc hữu ích.

Trong thực tế trông ra sao?

• Các luồng không bị khóa vĩnh viễn, nhưng mắc kẹt trong vòng lặp nhường nhịn vô tận.
• Hệ thống không treo, nhưng cũng không làm điều cần làm.

Ví dụ đời thường

• Hai robot cần tránh nhau trong lối đi hẹp, và cả hai mỗi lần đều đồng thời bước sang cùng một phía — lại cản nhau tiếp.
• Hai luồng liên tục phát hiện tài nguyên đang bận và nhường nhau... mãi mãi.

2. Ví dụ livelock với Java

Hãy mô phỏng livelock trong mã. Đơn giản lấy hai “worker” cần dùng chung một cái thìa. Khác với deadlock, nếu thìa đang bận, họ lịch sự nhường và thử lại — nhưng lại làm cùng lúc, đồng bộ với nhau.

Ví dụ mã: “Những worker lịch sự”

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() {
            // Sử dụng thìa (không làm gì)
        }
    }

    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) {
                // Nếu thìa không ở chỗ tôi — chờ
                if (spoon.getOwner() != this) {
                    try {
                        Thread.sleep(1); // Chờ cho đến khi thìa rảnh
                    } catch (InterruptedException ignored) {}
                    continue;
                }
                // Nếu người kia đang đói — nhường thìa
                if (other.isHungry()) {
                    System.out.println(name + ": Nhường thìa cho " + other.getName());
                    spoon.setOwner(other);
                    continue;
                }
                // Ăn thôi!
                System.out.println(name + ": Tôi ăn!");
                spoon.use();
                isHungry = false;
                System.out.println(name + ": Tôi no rồi!");
                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();
    }
}

Điều gì đang xảy ra?

• Alice và Bob đều đói, thìa ban đầu ở chỗ Alice.
• Alice thấy Bob cũng đói, và nhường thìa.
• Bây giờ thìa ở chỗ Bob, nhưng anh ấy thấy Alice đói và nhường lại cho cô.
• Cái thìa “chạy qua chạy lại” giữa các worker, không ai ăn — không có tiến triển.

Trong output sẽ như thế nào?

Alice: Nhường thìa cho Bob
Bob: Nhường thìa cho Alice
Alice: Nhường thìa cho Bob
Bob: Nhường thìa cho Alice
...

Loại bỏ livelock bằng cách nào?

Có thể loại bỏ livelock nếu “giảm bớt” sự lịch sự của các luồng. Thêm một khoảng dừng ngẫu nhiên trước khi thử lại (ví dụ qua Thread.sleep) — khi đó các luồng sẽ không còn phản ứng đồng bộ. Cũng có thể dùng chiến lược “kiên định” hơn: nếu đã nhường, hãy chờ lâu hơn trước khi thử lại. Và đừng quá “quý ông” trong thuật toán — nhường nhịn quá mức cũng dẫn đến treo.

3. Starvation (đói tài nguyên của luồng)

Nếu livelock — là “lịch sự vĩnh viễn”, thì starvation (đói) — là khi một hoặc vài luồng hầu như không bao giờ nhận được tài nguyên hay CPU, vì các luồng khác luôn vượt lên trước.

Định nghĩa chính thức

Starvation — tình huống khi một luồng không thể truy cập tài nguyên cần thiết (CPU, bộ nhớ, khóa) vì các luồng khác liên tục “vượt mặt”. Kết quả là luồng “bị đói” hoặc được chạy rất hiếm khi, hoặc hầu như không được chạy.

Nguyên nhân gây starvation

• Khóa không công bằng. Ví dụ, một khối synchronized thông thường không đảm bảo luồng chờ lâu nhất sẽ vào trước.
• Ưu tiên luồng. Nếu các luồng có ưu tiên cao luôn chiếm CPU, các luồng ưu tiên thấp có thể “chết đói” (setPriority).
• Vòng lặp vô tận ở các luồng khác. Nếu ai đó không nhường CPU (không gọi Thread.sleep hoặc Thread.yield()), các luồng khác có thể không có thời gian chạy.

4. Ví dụ starvation với Java

Ví dụ: Luồng ưu tiên thấp không được chạy

public class StarvationDemo {
    public static void main(String[] args) {
        Runnable highPriorityTask = () -> {
            while (true) {
                // Tác vụ nặng, không nhường CPU
            }
        };

        Runnable lowPriorityTask = () -> {
            while (true) {
                System.out.println("Tôi là luồng ưu tiên thấp!");
                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();
    }
}

Biểu hiện như thế nào?

• Luồng ưu tiên cao luôn bận làm việc, không nhường CPU.
• Luồng ưu tiên thấp hầu như không được chạy (hoặc thậm chí không chạy).
• Trên JVM/HĐH hiện đại, bộ lập lịch có thể làm “mềm” ưu tiên, nhưng trên một số hệ thống hiện tượng đói vẫn rõ rệt.

Ví dụ khác: starvation do khóa không công bằng

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

    public static void main(String[] args) {
        // 5 luồng luôn chiếm lock
        for (int i = 0; i < 5; i++) {
            new Thread(() -> {
                while (true) {
                    synchronized (lock) {
                        // Giữ lock lâu
                        try {
                            Thread.sleep(100);
                        } catch (InterruptedException ignored) {}
                    }
                }
            }).start();
        }

        // Một luồng bị đói
        new Thread(() -> {
            while (true) {
                synchronized (lock) {
                    System.out.println("Luồng bị đói đã nhận được lock!");
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException ignored) {}
                }
            }
        }).start();
    }
}

Trong ví dụ này, luồng “bị đói” có thể rất lâu mới lấy được lock, nếu các luồng khác liên tục chiếm nó.

5. Cách phát hiện và phòng tránh livelock và starvation

Cách phát hiện?

• Livelock: chương trình vẫn chạy, luồng không treo, nhưng không có tiến triển (không có kết quả, không thoát vòng lặp).
• Starvation: một số luồng hầu như không được chạy (log hiếm khi có thông báo hoặc không có).

Công cụ

• Ghi log: đánh dấu bắt đầu/kết thúc công việc, việc chiếm/thả tài nguyên.
• Giám sát: VisualVM, Java Mission Control — xem luồng nào đang hoạt động và đang làm gì.
• Thread dump: kiểm tra xem các luồng có mắc kẹt khi chờ lock hay không.

Tránh thế nào?

Đối với livelock:

• Đừng nhường nhịn quá “lịch sự” — thêm một độ trễ ngẫu nhiên nhỏ trước khi thử lại (Thread.sleep).
• Thêm tính ngẫu nhiên vào thứ tự thử lại, để tránh hành vi đồng bộ giữa các luồng.
• Dùng cấu trúc/thuật toán không khóa (biến nguyên tử, cách tiếp cận CAS).

Đối với starvation:

• Dùng khóa “công bằng”. Ví dụ, ReentrantLock với fairness:

java.util.concurrent.locks.ReentrantLock lock = new java.util.concurrent.locks.ReentrantLock(true); // chế độ công bằng

• Không lạm dụng ưu tiên luồng — thường để ưu tiên mặc định.
• Tối thiểu hóa thời gian trong miền tới hạn (synchronized/Lock).
• Dùng hàng đợi công việc có thứ tự phục vụ gần với FIFO.

Bảng: Deadlock, Livelock, Starvation — so sánh

So sánh và các thông tin thú vị

• Livelock — như hai người cùng lúc bước sang trái để tránh nhau rồi lại va vào nhau.
• Starvation — như xếp hàng ở cửa hàng nơi thu ngân chỉ phục vụ “người quen”, còn những người khác chờ mãi.

Sự thật thú vị: livelock ít gặp hơn deadlock, nhưng khó phát hiện hơn — chương trình không “treo”, mà vẫn làm gì đó!

6. Các lỗi thường gặp khi làm việc với livelock và starvation

Lỗi số 1: “Nhường nhịn lịch sự” nhưng không có độ trễ. Nếu các luồng quá thường xuyên nhường nhau mà không có tạm dừng, chúng có thể rơi vào livelock. Hãy thêm một độ trễ ngẫu nhiên nhỏ trước khi thử chiếm tài nguyên lại (Thread.sleep).

Lỗi số 2: Chỉ trông chờ vào synchronized, không dùng khóa công bằng. Khi có nhiều luồng, synchronized thông thường không đảm bảo “người đói nhất” sẽ vào được. Hãy dùng ReentrantLock với fairness nếu điều đó là quan trọng.

Lỗi số 3: Lạm dụng ưu tiên luồng. Cố “tăng tốc” luồng quan trọng bằng setPriority thường dẫn đến starvation cho các luồng khác. Đừng chỉnh ưu tiên nếu không thật sự cần.

Lỗi số 4: Thiếu giám sát và ghi log. Livelock và starvation khó nhận ra nếu không có log: chương trình “vẫn chạy”, nhưng không có kết quả. Hãy ghi log các sự kiện quan trọng và dùng profiler/dump luồng.

Lỗi số 5: Miền tới hạn quá dài. Nếu một luồng giữ lock quá lâu, các luồng khác sẽ phải chờ (hoặc “bị đói”). Hãy tối thiểu hóa thời gian trong các khối synchronized/Lock.