Інші проблеми: Livelock і Starvation

1. Вступ

Livelock — це ситуація в багатопоточному застосунку, коли два або більше потоків намагаються уникнути взаємного блокування (Deadlock), але в підсумку лише нескінченно реагують на дії одне одного, не просуваючись уперед. На відміну від Deadlock, де потоки завмерли й нічого не можуть зробити, за Livelock програма виглядає «живою»: потоки працюють, але жоден із них не робить корисної роботи.

Це ніби ви з колегою у вузькому коридорі постійно робите крок назад, щоб пропустити одне одного, і через це так і не проходите. Збоку це смішно, у програмі — жахливо.

Приклад Livelock: програмісти у дверях

Уявіть двох дуже ввічливих програмістів, які йдуть назустріч одне одному вузьким коридором. Вони одночасно опиняються перед дверима й обидва вирішують поступитися: відходять убік, щоб дати пройти іншому. Знову бачать, що ситуація не змінилася, і знову намагаються поступитися — нескінченно. Ніхто не стоїть на місці, усі рухаються, але ніхто не проходить через двері.

У багатопоточній програмі це виглядає так: потік бачить, що ресурс зайнятий, відступає, перевіряє знову, знову поступається — і так без кінця.

2. Livelock на практиці

Спробуймо відтворити аналогічну ситуацію в коді. Припустімо, у нас є два ресурси (наприклад, два банківські рахунки), і два потоки одночасно намагаються переказати гроші одне одному, щоб не заблокувати одне одного.

class Account
{
    public int Balance { get; set; }
    public object LockObj { get; } = new object();
}

public class Program
{
    static void Transfer(Account from, Account to, int amount)
    {
        while (true)
        {
            bool lockedFrom = false;
            bool lockedTo = false;
            try
            {
                Monitor.TryEnter(from.LockObj, 100, ref lockedFrom); 
                Monitor.TryEnter(to.LockObj, 100, ref lockedTo);

                if (lockedFrom && lockedTo)
                {
                    from.Balance -= amount;
                    to.Balance += amount;
                    break; // Переказ виконано!
                }
            }
            finally
            {
                if (lockedFrom) Monitor.Exit(from.LockObj);
                if (lockedTo) Monitor.Exit(to.LockObj);
            }
            // Не вийшло? Відступаємо і пробуємо знову — ввічливо!
            Thread.Sleep(1);
        }
    }
    // ... Запуск двох потоків з Transfer(A, B, ...); Transfer(B, A, ...);
}

У цьому прикладі обидва потоки багаторазово намагаються захопити блокування. Але якщо вони постійно бачать, що блокування зайняті, і щоразу поступаються, усе зводиться до «ввічливого» відступання, а переказ так і не відбувається. Покладатися на випадковість планувальника — погана стратегія для надійної програми. Додавайте паузи та backoff, не робіть коротких «порожніх» циклів із Monitor.TryEnter і Thread.Sleep.

Порівняння Livelock vs Deadlock

3. Starvation (голодування): коли до ресурсу ніяк не доходить черга

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

На відміну від Deadlock і Livelock, тут ніхто не заблокований назавжди й ніхто нескінченно не поступається — просто деяким потокам постійно не дістається «шматок пирога».

Ілюстрація: аналогія з реального життя

Уявіть їдальню з двома чергами: «VIP» (наприклад, каса для співробітників року) і «для всіх інших». VIP-черга коротка, але туди завжди хтось встигає раніше. «Звичайні» відвідувачі стоять по півгодини й дивляться, як VIP знову проходять уперед. Оце й є Starvation!

4. Starvation у C#: практика і налагодження

Розгляньмо ситуацію з lock, коли один потік із вищим пріоритетом постійно встигає увійти в критичну секцію, а інший «відстає»:

private static readonly object _locker = new object();

static void Greedy()
{
    while (true)
    {
        lock (_locker)
        {
            Console.WriteLine("Жадібний потік захопив ресурс...");
            Thread.Sleep(10); // довше утримує блокування
        }
        Thread.Sleep(1);
    }
}

static void Poor()
{
    while (true)
    {
        lock (_locker)
        {
            Console.WriteLine("Бідний потік увійшов...");
        }
    }
}

Якщо запустити обидва потоки, то «Greedy» («Жадібний») довго утримує блокування й швидко захоплює його знову, а «Poor» («Бідний») майже не потрапляє всередину критичної секції й фактично «голодує» без ресурсу. У реальних задачах starvation може бути менш очевидним: наприклад, якщо в одного з потоків нижчий пріоритет або його частіше витісняє ОС.

Де трапляється starvation?

• У потоках із низьким пріоритетом.
• За неправильної організації черг завдань (немає чесної FIFO-політики).
• У ReaderWriterLockSlim із налаштуваннями за замовчуванням: якщо записувач приходить рідко, а читачі йдуть нескінченним потоком, то записувач увесь час «голодуватиме», бо читачі займають Read Lock і не дають отримати Write Lock.

5. Чому Starvation — не завжди помилка, але завжди проблема

Starvation, на відміну від Deadlock, не призводить до повної зупинки програми, але результат роботи стає непередбачуваним і несправедливим: дані обробляються нерівномірно, деякі завдання чекають нескінченно, продуктивність падає. Це особливо критично в серверних застосунках, де всі мають отримувати рівні шанси.

Як виявити й діагностувати Livelock і Starvation

• Суттєво зросло споживання CPU, але завдання «стоїть на місці» — можливо, у вас Livelock.
• Потоки наче працюють, але деякі завдання ніколи не завершуються — імовірний Starvation.
• Журнали: якщо журнал подій показує, що певні потоки або завдання ніколи не отримують доступ до ресурсу — стовідсоткове «голодування».

Як уникнути Livelock

• Не обмежуйтеся спробами захоплення ресурсів лише «поступливими» неблоківними методами на кшталт Monitor.TryEnter. Якщо не вийшло, додавайте випадкові паузи (Thread.Sleep(Random.Next(1, 10))), щоб потоки не збігалися у часі.
• Не використовуйте постійні короткі цикли із захопленням ресурсу — інакше цикл «відступив — спробував» стане нескінченним.
• Інколи допомагає змінити алгоритм: увести «право старшого», щоб лише один потік міг поступатися, а інший — ні.

Як уникнути Starvation

• Стежте за пріоритетами потоків: фонові або високопріоритетні завдання не мають вічно заважати іншим.
• Використовуйте черги (ConcurrentQueue<T>, канали, чергу завдань) із чесною політикою FIFO, щоб завдання оброблялися в порядку надходження.
• У ReaderWriterLockSlim можна призупинити нових читачів на користь записувачів, щоб записувач таки дочекався Write Lock.
• Застосовуйте таймаути й журнали: якщо потік намагається отримати блокування надто довго, виводьте попередження.
• Зменшуйте тривалість утримання блокувань і розносіть критичні секції.

Порівняння Deadlock, Livelock і Starvation