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