Livelock и Starvation: определение, примеры

1. Знакомство с Livelock

Если deadlock — это когда потоки стоят и ждут друг друга вечно, то livelock (ожившая блокировка) — это когда потоки вроде бы живы, постоянно что-то делают, уступают друг другу, но... никто не продвигается вперёд! Представьте двух вежливых людей в узком коридоре: «Ой, вы проходите!» — «Нет, вы!» — «Нет, вы!» — и так до бесконечности.

Формальное определение

Livelock — ситуация, когда потоки не заблокированы, но из-за постоянных изменений своего состояния в ответ на действия других потоков не могут завершить работу. Они «живы», активно реагируют, но не выполняют полезной работы.

Как это выглядит на практике?

• Потоки не блокируются навсегда, но застревают в бесконечном цикле уступок.
• Система не висит, но и не делает того, что должна.

Пример из жизни

• Два робота, которые должны разойтись в узком проходе, и оба каждый раз одновременно делают шаг в сторону друг друга — и снова мешают.
• Два потока, которые каждый раз обнаруживают, что ресурс занят, и уступают друг другу... бесконечно.

2. Пример livelock на Java

Давайте смоделируем 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 (голодание) — это когда один или несколько потоков вообще не получают доступ к ресурсу или процессору, потому что другие всё время их опережают.

Формальное определение

Starvation — ситуация, когда поток не может получить доступ к нужному ресурсу (CPU, памяти, блокировке), потому что другие потоки постоянно его опережают. В результате «голодающий» поток либо выполняется крайне редко, либо вообще не выполняется.

Причины starvation

• Несправедливые блокировки. Например, обычный synchronized-блок не гарантирует, что поток, который дольше всех ждёт, зайдёт первым.
• Приоритеты потоков. Если потоки с высоким приоритетом постоянно занимают процессор, низкоприоритетные могут «умирать с голоду» (setPriority).
• Бесконечные циклы в других потоках. Если кто-то не уступает CPU (не вызывает Thread.sleep или Thread.yield()), другие потоки могут не получить время выполнения.

4. Пример starvation на Java

Пример: Поток с низким приоритетом не выполняется

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 с 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-блоков.