Wzorce bezpieczne dla wątków

1. Wzorzec „blokowanie bez blokowania” (Lock-Free / Wait-Free)

Już wiecie, że kolekcje Concurrent są bezpieczne dla wątków. Ale jak robią to bez tego, żebyście owijali swój kod blokami lock? Odpowiedź leży w zaawansowanych algorytmach — lock-free (bez blokad) i wait-free (bez oczekiwania).

Krótka wyjaśnienie koncepcji lock-free i wait-free algorytmów

Lock-Free (bez blokad)

Sedno: Gwarantuje, że przynajmniej jeden wątek zawsze będzie mógł wykonać krok naprzód, nawet jeśli inne napotykają opóźnienia lub przerwania.

Różnica od lock: Przy użyciu lock konkurujące wątki czekają, aż blokada zostanie zwolniona. W algorytmach lock-free wątki nie czekają na siebie w klasycznym sensie: przy konflikcie po prostu powtarzają próbę.

Przykład: Kolejka do kasy: przy lock stoisz i czekasz. W lock-free podchodzisz, widzisz, że jest zajęte i próbujesz ponownie za chwilę — bez „stania” w jednej wspólnej kolejce.

Wait-Free (bez oczekiwania)

Sedno: Silniejsza gwarancja: każdy wątek posunie się naprzód w skończonej liczbie własnych kroków, niezależnie od innych. Nikt nie „kręci się” bez końca.

Różnica: W lock-free wątek może w nieskończoność restartować operację z powodu konfliktów; w wait-free to się nie zdarza.

Praktyka: Implementacja wait-free jest znacząco trudniejsza, dlatego częściej spotyka się lock-free lub hybrydowe podejścia.

2. Jak kolekcje Concurrent osiągają bezpieczeństwo wątkowe

Główny budulec algorytmów lock-free — operacje atomowe na poziomie procesora. W .NET odwołujemy się do nich przez klasę System.Threading.Interlocked.

Interlocked-operacje

Szybkie atomowe operacje na prymitywach (int, long): na przykład, Interlocked.Increment, Interlocked.Decrement, Interlocked.CompareExchange.

Przykłady: Interlocked.Increment(ref value) — atomowe zwiększenie; Interlocked.CompareExchange(ref location, value, comparand) — atomowo porównuje i, jeśli pasuje, aktualizuje.

CAS (Compare-And-Swap) — Porównaj-i-Zamień

Operacja CAS zaimplementowana jest w .NET jako Interlocked.CompareExchange. Ogólna logika:

1. Odczytać bieżącą wartość zmiennej.
2. Obliczyć nową wartość na podstawie odczytu.
3. Spróbować zapisać ją tylko jeśli zmienna nadal równa się wartości wyjściowej. Jeśli nie — powtórzyć próbę.

Przykład: prosty lock-free licznik z użyciem 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++; // Nie jest thread-safe!
        }
    }

    static void IncrementInterlocked(int iterations)
    {
        for (int i = 0; i < iterations; i++)
        {
            Interlocked.Increment(ref interlockedCounter); // Atomowo!
        }
    }
}

//W Main:
Task t1 = Task.Run(() => IncrementRegular(500_000));
Task t2 = Task.Run(() => IncrementRegular(500_000));
Task.WaitAll(t1, t2);
Console.WriteLine($"Zwykły licznik: {regularCounter}"); // prawie zawsze będzie mniej niż 1_000_000

regularCounter = 0; // Resetujemy przed następnym testem
t1 = Task.Run(() => IncrementInterlocked(500_000));
t2 = Task.Run(() => IncrementInterlocked(500_000));
Task.WaitAll(t1, t2);
Console.WriteLine($"Interlocked licznik: {interlockedCounter}"); // Będzie dokładnie 1_000_000

Metoda Interlocked.Increment gwarantuje atomowość inkrementacji: dane nie giną nawet przy równoczesnym dostępie wielu wątków.

3. Dlaczego to ważne dla skalowalności i wydajności

Zmniejsza narzut: klasyczne blokady (lock) mogą powodować przełączania kontekstu i oczekiwania w jądrze systemu. Lock-free minimalizuje te koszty.

Brak deadlocków: wątki nie czekają na siebie — nic nie blokuje się wzajemnie.

Lepsza skalowalność: na systemach wielordzeniowych wątki mniej sobie przeszkadzają, nie ma „wąskiego gardła” jednej wspólnej blokady.

Wyższa responsywność: nikt nie „zawiesza się” na długim oczekiwaniu.

Bardzo krótkie spojrzenie na wewnętrzną budowę ConcurrentQueue<T>

Uproszczone: kolejka składa się z powiązanych segmentów. Przy Enqueue wątek atomowo przesuwa „tail” przez CompareExchange; przy TryDequeue — atomowo przesuwa „head” tylko jeśli się nie zmienił. Rzeczywiste implementacje są bardziej złożone (rozwiązują problem ABA i uwzględniają garbage collection), ale klucz to operacje atomowe zamiast „ciężkich” blokad.

4. Wydajność kolekcji Concurrent

Porównanie wydajności z lock na zwykłych kolekcjach

Przy niskiej konkurencji różnica jest niewielka, a czasem prosty lock na zwykłej kolekcji może być porównywalny. Ale przy wysokiej konkurencji kolekcje Concurrent zwykle są znacznie szybsze z powodu braku oczekiwań na wspólną blokadę.

Przykład: porównanie (pomysł, bez uruchamiania)

using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Diagnostics; // Dla 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; // Liczba zadań równoległych

    public static void RunTests()
    {
        Console.WriteLine("Test wydajności (dodawanie):");

        // Test ze zwykłym List i 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 z lock: {sw.ElapsedMilliseconds} ms. Count: {regularList.Count}");

        // Test z 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} ms. Count: {concurrentQueue.Count}");
        // Oczekuj, że ConcurrentQueue będzie znacznie szybsza przy NumTasks > 1
    }
}

Wniosek: Jeśli widzisz lock wokół kolekcji, to często sygnał, by przejść na odpowiedniki Concurrent.

6. Przydatne niuanse

Wpływ contention na wydajność

Contention — gdy wiele wątków jednocześnie odwołuje się do jednego zasobu. Im większa konkurencja, tym więcej oczekiwań i gorsza wydajność.

Kolekcje Concurrent zaprojektowano, by zmniejszać contention: na przykład, ConcurrentBag<T> używa lokalnych dla wątku magazynów, a ConcurrentDictionary<TKey, TValue> — segmentowanych blokad (striped locking).

Klucz do wydajności — zmniejszenie contention: w miarę możliwości dziel dane między wątki lub używaj wielu kolekcji.

Wybór właściwej kolekcji do konkretnego scenariusza

ConcurrentQueue<T>

ConcurrentStack<T>

ConcurrentBag<T>

ConcurrentDictionary<TKey, TValue>

7. Wskazówki dotyczące optymalizacji

Unikaj częstego wywoływania ToArray() w „gorących” miejscach

ToArray() tworzy nową kopię całej kolekcji — kosztowne pamięciowo i czasowo. Używaj tylko gdy potrzebujesz „momentu złączenia” i jak najrzadziej. Dla liczby elementów jest Count (pamiętaj, że to zrzut stanu w momencie wywołania).

Uważaj przy iteracji po kolekcjach Concurrent

Iteratory nie gwarantują stabilności przy równoległych modyfikacjach: możesz pominąć elementy lub otrzymać niekonsystentny widok. Dla stabilnej reprezentacji najpierw rób zrzut przez ToArray().

// Źle: może pominąć elementy lub zobaczyć zmiany podczas iteracji
foreach (var item in myConcurrentQueue) { /* ... */ }

// Dobrze: iteracja po stałym zrzucie
var snapshot = myConcurrentQueue.ToArray();
foreach (var item in snapshot) { /* ... */ }

Minimalizuj „ruch” przez kolekcję

Grupuj zadania/dane: mniej wywołań Add/Take — mniej potencjalnego contention. Na przykład, zamiast 1000 oddzielnych wiadomości — jeden „pakiet” z 1000.

Śledź źródła konkurencji

Jeśli obserwujesz degradację, zmierz, gdzie jest największe contention. Możliwe, że można zmienić projekt tak, by wątki operowały na lokalnych danych lub na różnych kolekcjach.

2

Zadanie

C# SELF, poziom 58, lekcja 4

Niedostępne

Wątkowo-bezpieczny licznik z użyciem Interlocked

Wątkowo-bezpieczny licznik z użyciem Interlocked

Otwórz

1

Ankieta/quiz

Kolekcje concurrent, poziom 58, lekcja 4

Niedostępny

Kolekcje concurrent

Kolekcje bezpieczne dla wątków

Otwórz