Патерни потокобезпеки

1. Патерн «Блокування без блокувань» (Lock-Free / Wait-Free)

Ви вже знаєте, що Concurrent колекції є потокобезпечними. Але як вони роблять це без того, щоб ви обвішували свій код блоками lock? Відповідь криється в просунутих алгоритмах — lock-free (без блокувань) і wait-free (без очікування).

Коротке пояснення концепцій lock-free і wait-free алгоритмів

Lock-Free (без блокувань)

Суть: Гарантує, що принаймні один потік завжди зможе зробити крок уперед, навіть якщо інші стикаються із затримками або перериваннями.

Відмінність від lock: Під час використання lock конкуруючі потоки чекають, поки звільниться блокування. У lock-free алгоритмах потоки не чекають одне одного в класичному сенсі: у разі конфлікту вони просто повторюють спробу.

Приклад: Черга до каси: з lock ви стоїте й чекаєте. У lock-free ви підходите, бачите, що зайнято, і пробуєте знову за мить — без очікування у спільній черзі.

Wait-Free (без очікування)

Суть: Більш сильна гарантія: кожен потік просунеться за скінченну кількість власних кроків, незалежно від інших. Ніхто не «крутиться» нескінченно.

Відмінність: У lock-free потік може безкінечно перезапускати операцію через конфлікти; у wait-free цього не відбувається.

На практиці: Реалізувати wait-free суттєво складніше, тож частіше трапляються lock-free або гібридні підходи.

2. Як Concurrent колекції досягають потокобезпечності

Базовий будівельний блок lock-free алгоритмів — це атомарні операції рівня процесора. У .NET до них звертаємося через клас System.Threading.Interlocked.

Операції Interlocked

Швидкі атомарні операції над примітивами (int, long): наприклад, Interlocked.Increment, Interlocked.Decrement, Interlocked.CompareExchange.

Приклади: Interlocked.Increment(ref value) — атомарне збільшення; Interlocked.CompareExchange(ref location, value, comparand) — атомарно порівнює і, якщо значення збігається, оновлює.

CAS (Compare-And-Swap) — порівняння та обмін

Операція CAS реалізована в .NET як Interlocked.CompareExchange. Загальна логіка:

1. Прочитати поточне значення змінної.
2. Обчислити нове значення на основі прочитаного.
3. Спробувати записати його лише якщо змінна все ще дорівнює вихідному значенню. Якщо ні — повторити спробу.

Приклад: простий lock-free лічильник з Interlocked

using System.Threading;
using System.Threading.Tasks;

class CounterExample
{
    static int regularCounter = 0;
    static int interlockedCounter = 0;

    static void IncrementRegular(int iterations)
    {
        for (int i = 0; i < iterations; i++)
        {
            regularCounter++; // Непотокобезпечно!
        }
    }

    static void IncrementInterlocked(int iterations)
    {
        for (int i = 0; i < iterations; i++)
        {
            Interlocked.Increment(ref interlockedCounter); // Атомарно!
        }
    }
}

// У Main:
Task t1 = Task.Run(() => IncrementRegular(500_000));
Task t2 = Task.Run(() => IncrementRegular(500_000));
Task.WaitAll(t1, t2);
Console.WriteLine($"Звичайний лічильник: {regularCounter}"); // майже завжди буде меншим за 1_000_000

regularCounter = 0; // Скидаємо для наступного тесту
t1 = Task.Run(() => IncrementInterlocked(500_000));
t2 = Task.Run(() => IncrementInterlocked(500_000));
Task.WaitAll(t1, t2);
Console.WriteLine($"Interlocked лічильник: {interlockedCounter}"); // Буде рівно 1_000_000

Метод Interlocked.Increment гарантує атомарність інкременту: дані не губляться навіть за конкурентного доступу багатьох потоків.

3. Чому це важливо для масштабованості та продуктивності

Зменшує накладні витрати: класичні блокування (lock) можуть призводити до перемикань контексту та очікувань у ядрі ОС. Lock-free підходи мінімізують ці витрати.

Немає взаємоблокувань: потоки не чекають одне одного — немає підстав для взаємоблокування (deadlock).

Краща масштабованість: на багатоядерних системах потоки менше заважають одне одному, немає «вузького місця» одного спільного блокування.

Краща відгукливість: ніхто не «зависає» на тривалих очікуваннях.

Дуже короткий погляд на внутрішній устрій ConcurrentQueue<T>

Спрощено: черга складається зі звʼязаних сегментів. Під час Enqueue потік атомарно просуває «хвіст» через CompareExchange; під час TryDequeue — атомарно зсуває «голову» лише якщо вона не змінилася. Реальні реалізації складніші (вирішують проблему ABA й ураховують збирання сміття), але ключ — атомарні операції замість «важких» блокувань.

4. Продуктивність Concurrent колекцій

Порівняння продуктивності з lock на звичайних колекціях

За низької конкуренції різниця невелика, а іноді простий lock на звичайній колекції може бути порівнюваним. Але за високої конкуренції Concurrent-колекції, як правило, значно швидші через відсутність очікувань на спільному блокуванні.

Приклад: порівняння (ідея, без запуску)

using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Diagnostics; // Для Stopwatch
using System.Threading.Tasks;

class PerformanceTest
{
    static List<int> regularList = new List<int>();
    static ConcurrentQueue<int> concurrentQueue = new ConcurrentQueue<int>();
    static object lockObject = new object();

    const int Iterations = 1_000_000;
    const int NumTasks = 4; // Кількість паралельних завдань

    public static void RunTests()
    {
        Console.WriteLine("Тест продуктивності (додавання):");

        // Тест зі звичайним List і lock
        regularList.Clear();
        Stopwatch sw = Stopwatch.StartNew();
        Parallel.For(0, NumTasks, (i) =>
        {
            for (int j = 0; j < Iterations / NumTasks; j++)
            {
                lock (lockObject)
                {
                    regularList.Add(j);
                }
            }
        });
        sw.Stop();
        Console.WriteLine($"List з lock: {sw.ElapsedMilliseconds} мс. Count: {regularList.Count}");

        // Тест із ConcurrentQueue
        concurrentQueue.Clear();
        sw = Stopwatch.StartNew();
        Parallel.For(0, NumTasks, (i) =>
        {
            for (int j = 0; j < Iterations / NumTasks; j++)
            {
                concurrentQueue.Enqueue(j);
            }
        });
        sw.Stop();
        Console.WriteLine($"ConcurrentQueue: {sw.ElapsedMilliseconds} мс. Count: {concurrentQueue.Count}");
        // Очікуйте, що ConcurrentQueue буде значно швидшою, коли NumTasks > 1
    }
}

Висновок: Якщо ви бачите lock навколо колекцій, це часто сигнал перейти на Concurrent-аналоги.

5. Корисні нюанси

Вплив contention на продуктивність

Contention — це коли багато потоків одночасно звертаються до одного ресурсу. Чим вища конкуренція, тим більше очікувань і гірша продуктивність.

Concurrent-колекції спроєктовані для зниження конкуренції: наприклад, ConcurrentBag<T> використовує потоково-локальні сховища, а ConcurrentDictionary<TKey, TValue> — сегментовані блокування (striped locking).

Ключ до продуктивності — зменшення contention: за можливості розділяйте дані між потоками або використовуйте кілька колекцій.

Вибір правильної колекції для конкретного сценарію

ConcurrentQueue<T>

ConcurrentStack<T>

ConcurrentBag<T>

ConcurrentDictionary<TKey, TValue>

6. Поради з оптимізації

Уникайте частого ToArray() у «гарячих» місцях

ToArray() створює нову копію всієї колекції — це дорого за памʼяттю та часом. Використовуйте лише коли потрібен «моментальний знімок» — і якнайрідше. Для кількості є Count (памʼятайте, що це знімок на момент виклику).

Обережно з ітерацією Concurrent-колекцій

Ітератори не гарантують стабільність під час паралельних модифікацій: можна пропустити елементи або побачити неузгоджений стан. Щоб отримати стабільне представлення, спершу зробіть знімок через ToArray().

// Погано: може пропустити елементи або побачити зміни під час ітерації
foreach (var item in myConcurrentQueue) { /* ... */ }

// Добре: ітерація за фіксованим знімком
var snapshot = myConcurrentQueue.ToArray();
foreach (var item in snapshot) { /* ... */ }

Мінімізуйте «трафік» через колекцію

Групуйте завдання та дані: менше викликів Add/Take — менше потенційного contention. Наприклад, замість 1 000 окремих повідомлень — один «пакет» із 1 000.

Відстежуйте джерела конкуренції

Якщо спостерігаєте деградацію, виміряйте, де найбільший contention. Можливо, варто змінити дизайн так, щоб потоки працювали з локальними даними або різними колекціями.

1

Опитування

Concurrent-колекції, рівень 58, лекція 4

Недоступний

Concurrent-колекції

Потокобезпечні колекції

Відкрити