Struktury danych bez blokad: kompletny przewodnik z przykładami w językach C++, Java i .NET

Mutex jest prosty. Blokujesz go, modyfikujesz współdzielony stan, odblokowujesz. Każdy wątek, który chce uzyskać dostęp, czeka na swoją kolej. Problem polega na tym, że „czekasz na swoją kolej” – przy dużej liczbie rdzeni i wysokiej przepustowości ta serializacja staje się pułapem. Wątek trzymający blokadę może zostać wywłaszczony, powodując, że wszystkie inne wątki pozostaną bezczynne. Inwersja priorytetów może spowodować, że wątki o niskim priorytecie zablokują wątki o wysokim priorytecie. W systemach przetwarzających miliony operacji na sekundę na dziesiątkach rdzeni, rywalizacja o mutex nie tylko spowalnia działanie, ale także obniża przepustowość.

Struktury danych bez blokad zastępują wzajemne wykluczanie operacjami atomowymi. Zamiast zapobiegać konfliktom, tolerują je i odzyskują po nich sprawność. Wątek, który nie przejdzie próby porównania i zamiany, ponawia próby z zaktualizowanym stanem. Żaden wątek nigdy nie blokuje innego. Przynajmniej jeden wątek zawsze robi postępy. Rezultatem jest znacząco lepsza przepustowość przy dużej rywalizacji, przewidywalne opóźnienie bez efektu konwoju oraz eliminacja impasu i inwersji priorytetów z założenia. Ceną jest złożoność implementacji: problem ABA, zagrożenia związane z odzyskiwaniem pamięci, fałszywe współdzielenie i subtelne wymagania dotyczące kolejności pamięci to pułapki, które nie występują w kodzie opartym na blokadach. Niniejszy artykuł omawia je wszystkie, omawiając konkretny kod.

Lock-Free vs Wait-Free vs Mutex: Którego wybrać?

Przed wyborem metody implementacji, właściwym pytaniem jest, jakiej gwarancji postępu system faktycznie potrzebuje. Te trzy modele różnią się pod względem tego, co obiecują w przypadku rywalizacji wątków.

Model	Gwarancja postępu	Typowe opóźnienie	Złożoność	Najlepsze dla:
Mutex / blokada oparta	Blokowanie, wątki czekają	Nieprzewidywalny w obliczu rywalizacji	Niski	Współdzielony stan o niskim poziomie zawartości, proste wymagania poprawności
Bez blokady	W całym systemie postępuje co najmniej jeden wątek	Niski poziom rywalizacji	Wysoki	Kolejki o dużej przepustowości, stosy, liczniki
Bez czekania	Każdy wątek kończy się w ograniczonych krokach	Ograniczony najgorszy przypadek	Bardzo wysoka	Systemy czasu rzeczywistego, bezpieczeństwo krytyczne, rygorystyczne umowy SLA dotyczące opóźnień
Bez przeszkód	Postęp solo, tylko gdy nie ma przeszkód	Nisko bez rywalizacji	Średni	Prototypy pamięci transakcyjnej, konteksty badawcze

Brak blokad to praktyczne rozwiązanie domyślne dla systemów produkcyjnych o wysokiej współbieżności. Kolejka Michaela-Scotta, stos Treibera i większość buforów pierścieniowych MPMC w środowisku produkcyjnym są wolne od blokad. Poszczególne wątki mogą zanikać w przypadku ekstremalnej rywalizacji, ale system jako całość robi postępy.

Metoda bez czekania gwarantuje ograniczony postęp dla każdego wątku, ale wymaga znacznie bardziej złożonych algorytmów. Istnieją uniwersalne konstrukcje, ale wiążą się z dużym narzutem. Algorytmy bez czekania są odpowiednie dla trudnych kontekstów czasu rzeczywistego, w których opóźnienie ogonowe ma większe znaczenie niż średnia przepustowość.

Technologia „obstruction-free” rzadko jest wykorzystywana bezpośrednio w środowisku produkcyjnym. Pojawia się w niektórych implementacjach pamięci transakcyjnej i służy jako krok milowy w dowodzeniu poprawności algorytmu.

W przypadku większości systemów o wysokiej współbieżności: używaj mutexu, gdy rywalizacja jest niska, a poprawność prosta, używaj trybu bezblokadowego, gdy przepustowość przy rywalizacji ma znaczenie, używaj trybu bezczekania tylko wtedy, gdy najgorsze opóźnienie na wątek jest wymaganiem.

Czym jest struktura danych wolna od blokad?

Struktura danych jest wolna od blokad, jeśli gwarantuje, że co najmniej jeden wątek spośród wszystkich wątków na niej działających zakończy działanie w skończonej liczbie kroków, niezależnie od tego, co robią inne wątki i jak są one zaplanowane. Ta formalna definicja ma wyraźną implikację: żaden algorytm wolny od blokad nie może się zablokować. Jeśli jeden wątek zostanie zatrzymany, zawieszony lub będzie działał wolno, inne wątki będą kontynuować działanie.

Mechanizm ten opiera się na operacjach atomowych, czyli instrukcjach procesora, które są wykonywane jako pojedyncza, niepodzielna jednostka. Uniwersalnym prymitywem jest metoda „Porównaj i zamień” (CAS) :

CAS(location, expected, new_value):
  if *location == expected:
    *location = new_value
    return true
  else:
    return false  // someone else changed it first

CAS jest atomowy na poziomie sprzętowym. Na x86 jest to CMPXCHG Instrukcja. Na ARM jest ona implementowana poprzez LDXR/STXR (load-exclusive/store-exclusive), czyli wariant LL/SC (Load-Linked/Store-Conditional). Wątek odczytuje wartość, oblicza nową wartość i używa CAS do jej zainstalowania tylko wtedy, gdy nikt inny jej w międzyczasie nie zmienił. Jeśli CAS się nie powiedzie, wątek próbuje ponownie z nową wartością.

W C++11 i nowszych wersjach jest to widoczne poprzez std::atomic:

Cpp

#include <atomic>

// Atomic increment using CAS loop
void atomic_add(std::atomic<int>& counter, int delta) {
    int expected = counter.load(std::memory_order_relaxed);
    while (!counter.compare_exchange_weak(
        expected,
        expected + delta,
        std::memory_order_release,
        std::memory_order_relaxed))
    {
        // expected is updated on failure -- retry with fresh value
    }
}

compare_exchange_weak jest prymitywem CAS. W przypadku awarii aktualizuje się expected automatycznie do bieżącej wartości, dzięki czemu pętla ponawiania prób staje się idiomatyczna.

Problem ABA: najniebezpieczniejsza pułapka w systemie Lock-Free

Problem ABA to najbardziej nieintuicyjne zagrożenie poprawności w programowaniu bez blokady. CAS sprawdza, czy dana komórka pamięci nadal zawiera wartość oczekiwaną przed zainstalowaniem nowej. Nie jest w stanie wykryć, czy wartość ta została zmieniona i przywrócona między odczytem a CAS. Lokalizacja nadal wygląda jak wartość pierwotna, ale stan bazowy systemu zmienił się w sposób niewidoczny dla CAS.

Scenariusz krok po kroku

Rozważ stos bez blokady, używając pojedynczego wskaźnika top:

1. Wątek A czyta top = Node1Następnym wskaźnikiem dla węzła Node1 jest węzeł Node2.
2. Wątek A zostaje wywłaszczony przed zakończeniem pobierania.
3. Wątek B usuwa Węzeł 1 (górny staje się Węzłem 2), a następnie usuwa Węzeł 2 (górny staje się nullem).
4. Wątek B wprowadza nowy węzeł, który jest przydzielony pod tym samym adresem pamięci co Node1 (typowe dla alokatorów z listą wolnych). Top = Node1 (ten sam wskaźnik, inna zawartość).
5. Wątek A wznawia działanie. Jego CAS widzi top == Node1 (oczekiwana wartość), kończy się powodzeniem i ustawia top = Node2, ale Node2 został już uwolniony. Katastrofa.

Problem ABA objawia się inaczej w każdej strukturze danych:

• Stos: CAS kończy się powodzeniem, ale instaluje nieaktualny wskaźnik do następnego użycia, powodując konieczność użycia po zwolnieniu
• kolejka:Wskaźnik głowy lub ogona wydaje się niezmieniony, ale struktura uległa zmianie
• Połączona lista:Węzeł wydaje się nadal znajdować na swoim miejscu, ale został usunięty i ponownie przydzielony

Czy LL/SC unika problemu ABA?

Tak, LL/SC (Load-Linked/Store-Conditional) zapewnia silniejszą semantykę niż CAS i naturalnie unika ABA. LL oznacza załadowany adres pamięci jako „linkowany”. SC na tym samym adresie kończy się niepowodzeniem, jeśli od czasu LL nastąpiło jakiekolwiek zapisanie pod tym adresem, nawet jeśli wartość została przywrócona do stanu pierwotnego. Historia modyfikacji jest śledzona na poziomie sprzętowym, a nie tylko na poziomie bieżącej wartości.

Implementacje LL/SC na rzeczywistym sprzęcie mają jednak ograniczenia praktyczne. Na ARM i POWER pozorne awarie LL/SC mogą wystąpić nawet bez konfliktów (przełączanie kontekstu, usuwanie pamięci podręcznej). Kod musi uwzględniać pętle ponawiania prób nawet bez rzeczywistych konfliktów. Na platformie x86 nie ma natywnego LL/SC; CAS jest prymitywem sprzętowym. W kodzie x86 należy programowo zapobiegać ABA.

Naprawianie ABA: trzy podejścia

1. Liczniki wersji (oznaczone wskaźniki)

Umieść licznik wersji w tym samym słowie atomowym co wskaźnik. Każde pomyślne wykonanie CAS zwiększa licznik. Nawet jeśli wskaźnik powróci do swojej pierwotnej wartości, licznik będzie się różnić:

Cpp

#include <atomic>
#include <cstdint>

struct TaggedPtr {
    uintptr_t ptr : 48;  // pointer (48-bit virtual address space)
    uintptr_t tag : 16;  // version counter
};

std::atomic<TaggedPtr> top;

bool cas_with_tag(std::atomic<TaggedPtr>& loc,
                  TaggedPtr expected,
                  void* new_ptr) {
    TaggedPtr desired = { (uintptr_t)new_ptr, expected.tag + 1 };
    return loc.compare_exchange_strong(expected, desired);
}

To standardowe podejście w praktyce. 16-bitowy znacznik zawija się po 65 536 operacjach, co teoretycznie jest niebezpieczne, ale w praktyce wystarczające dla większości systemów. Jest niezwykle mało prawdopodobne, aby wątek został wywłaszczony dokładnie po 65 536 cyklach CAS w tej samej lokalizacji.

2. Wskaźniki zagrożenia

Każdy wątek utrzymuje niewielki zestaw „wskaźników zagrożeń”, czyli wskaźników do węzłów, do których aktualnie uzyskuje dostęp. Przed zwolnieniem dowolnego węzła wątek sprawdza wszystkie rejestry wskaźników zagrożeń, aby upewnić się, że żaden inny wątek nie uzyskuje do niego dostępu. Węzeł, który pojawia się we wskaźniku zagrożenia, jest odkładany do momentu jego wyczyszczenia:

Cpp

// Simplified hazard pointer pattern
thread_local void* hazard_ptr = nullptr;

void* safe_load(std::atomic<void*>& head) {
    void* ptr;
    do {
        ptr = head.load(std::memory_order_acquire);
        hazard_ptr = ptr;                          // announce we are using this
        // memory fence ensures announcement is visible before validation
        std::atomic_thread_fence(std::memory_order_seq_cst);
    } while (ptr != head.load(std::memory_order_acquire)); // validate still valid
    return ptr;
}

void safe_release() {
    hazard_ptr = nullptr;
}

Wskaźniki zagrożeń uniemożliwiają ABA na poziomie odzyskiwania pamięci: węzeł nie może zostać ponownie użyty, dopóki którykolwiek wątek posiada do niego wskaźnik zagrożenia. Wymaga to przeskanowania wszystkich wskaźników zagrożenia wątku przed zwolnieniem, co zwiększa narzut proporcjonalny do liczby wątków.

3. Rekultywacja oparta na epoce (EBR)

Wątki działają w globalnie śledzonych „epokach”. Wycofane węzły są buforowane dla każdej epoki i zwalniane dopiero po przejściu wszystkich wątków poza epokę, w której węzeł został wycofany. EBR jest prostszy w użyciu niż wskaźniki zagrożeń i charakteryzuje się niższym narzutem na operację, kosztem ograniczonego, ale nieprzewidywalnego wzrostu pamięci w okresach spoczynku.

w Jawie, AtomicStampedReference bezpośrednio rozwiązuje problem ABA poprzez połączenie odniesienia ze stemplem całkowitym:

Jawa

import java.util.concurrent.atomic.AtomicStampedReference;

AtomicStampedReference<Node> top =
    new AtomicStampedReference<>(null, 0);

void push(Node newNode) {
    int[] stamp = new int[1];
    Node current;
    do {
        current = top.get(stamp);
        newNode.next = current;
    } while (!top.compareAndSet(current, newNode, stamp[0], stamp[0] + 1));
}

Implementacje kolejek bez blokad

Kolejki to najczęściej potrzebna struktura bez blokad. Kanoniczną kolejką bez blokad jest kolejka Michaela-Scotta, która wykorzystuje dwa wskaźniki (głowę i ogon) oraz węzeł wartowniczy, aby umożliwić jednoczesne operacje dodawania i usuwania z kolejki.

Kolejka SPSC: Maksymalna wydajność przy minimalnej synchronizacji

Kolejka typu „Jeden producent, jeden konsument” eliminuje wszelkie spory o zapis i odczyt. Jeden wątek zapisuje do końca; drugi wątek odczytuje z nagłówka. Producent i konsument współdzielą tylko wskaźnik do nagłówka:

Cpp

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class SPSCQueue {
    std::array<T, Capacity> buffer;
    alignas(64) std::atomic<size_t> head{0}; // consumer reads head
    alignas(64) std::atomic<size_t> tail{0}; // producer writes tail
    // alignas(64) puts each on a separate cache line -- prevents false sharing

public:
    bool push(const T& item) {
        size_t t = tail.load(std::memory_order_relaxed);
        size_t next = (t + 1) % Capacity;
        if (next == head.load(std::memory_order_acquire))
            return false; // full
        buffer[t] = item;
        tail.store(next, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t h = head.load(std::memory_order_relaxed);
        if (h == tail.load(std::memory_order_acquire))
            return false; // empty
        item = buffer[h];
        head.store((h + 1) % Capacity, std::memory_order_release);
        return true;
    }
};

alignas(64) Kluczowe jest powiązanie między głową i ogonem. Bez niego oba mieszczą się w tej samej linii pamięci podręcznej. Każdy zapis do ogona powoduje unieważnienie linii pamięci podręcznej widoczne dla odczytującego ją rdzenia, i odwrotnie, fałszywe współdzielenie, które serializuje operacje, które powinny być niezależne.

Kolejka MPMC: wielu producentów, wielu konsumentów

W pełni współbieżna kolejka MPMC jest znacznie bardziej złożona. Implementacje produkcyjne wykorzystują numer sekwencyjny dla każdego slotu, aby koordynować producentów i konsumentów bez blokady:

Cpp

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class MPMCQueue {
    struct Slot {
        std::atomic<size_t> sequence;
        T data;
    };

    alignas(64) std::array<Slot, Capacity> slots;
    alignas(64) std::atomic<size_t> enqueue_pos{0};
    alignas(64) std::atomic<size_t> dequeue_pos{0};

public:
    MPMCQueue() {
        for (size_t i = 0; i < Capacity; ++i)
            slots[i].sequence.store(i, std::memory_order_relaxed);
    }

    bool push(const T& item) {
        size_t pos = enqueue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        // wait for the slot to be ready for writing
        while (seq != pos) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        slot.data = item;
        slot.sequence.store(pos + 1, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t pos = dequeue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        while (seq != pos + 1) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        item = slot.data;
        slot.sequence.store(pos + Capacity, std::memory_order_release);
        return true;
    }
};

.NET ConcurrentQueue: Jak to działa wewnętrznie

.NET ConcurrentQueue<T> W .NET 5+ zastosowano strukturę tablicy segmentowanej. Każdy segment to tablica o stałym rozmiarze z indeksem nagłówka i ogona zarządzanym za pomocą Interlocked operacje (które są mapowane na CAS na sprzęcie bazowym). Segmenty są połączone za pomocą nietrwałego _nextSegment Wskaźnik. Kolejka dodaje do bieżącego segmentu końcowego, powiększając łańcuch segmentów po jego zapełnieniu. Kolejka odczytuje z segmentu głównego i atomowo przesuwa indeks głównego.

Kluczową decyzją projektową jest uniknięcie globalnej blokady. Producenci konkurują tylko o indeks ogonowy bieżącego segmentu. Konsumenci konkurują tylko o indeks główny. Żaden producent nigdy nie konkuruje z konsumentem. To sprawia, że ConcurrentQueue<T> wysoka wydajność dla rurociągów producent-konsument:

csharp

using System.Collections.Concurrent;
using System.Threading;

// .NET ConcurrentQueue -- lock-free, thread-safe, FIFO
var queue = new ConcurrentQueue<int>();

// Producer thread
var producer = Task.Run(() => {
    for (int i = 0; i < 1_000_000; i++)
        queue.Enqueue(i);
});

// Consumer thread
var consumer = Task.Run(() => {
    long sum = 0;
    while (!queue.IsEmpty || !producer.IsCompleted) {
        if (queue.TryDequeue(out int item))
            sum += item;
        else
            Thread.SpinWait(1);  // brief spin before retry
    }
    return sum;
});

await Task.WhenAll(producer, consumer);

Spójność pamięci podręcznej i fałszywe udostępnianie w kodzie bez blokad

Spójność pamięci podręcznej to niewidoczna zmienna wydajności w implementacjach bez blokad. Gdy rdzeń zapisuje dane do określonej lokalizacji pamięci, cała 64-bajtowa linia pamięci podręcznej zawierająca tę lokalizację zostaje unieważniona w pamięci podręcznej wszystkich pozostałych rdzeni. Muszą one pobrać zaktualizowaną linię przed odczytem. W kodzie bez blokad z częstymi aktualizacjami atomowymi, unieważnienie linii pamięci podręcznej może stać się dominującym kosztem.

Fałszywe współdzielenie występuje, gdy dwa wątki modyfikują różne zmienne, które współdzielą linię pamięci podręcznej. Żaden z wątków nie uzyskuje dostępu do tych samych danych, ale protokół spójności pamięci podręcznej traktuje całą linię pamięci podręcznej jako zarezerwowaną:

Cpp

// BAD: head and tail on the same cache line
struct BadQueue {
    std::atomic<size_t> head;   // bytes 0-7
    std::atomic<size_t> tail;   // bytes 8-15
    // both fit in the same 64-byte cache line
    // producer writing tail invalidates head in consumer's cache
};

// GOOD: head and tail on separate cache lines
struct GoodQueue {
    alignas(64) std::atomic<size_t> head;
    alignas(64) std::atomic<size_t> tail;
    // each on its own cache line -- no false sharing
};

Protokół MESI (Modified, Exclusive, Shared, Invalid) opisuje sposób, w jaki procesory x86 koordynują własność linii pamięci podręcznej. Gdy rdzeń chce zapisać dane w lokalizacji współdzielonej z innymi rdzeniami (stan Shared), musi rozgłosić żądanie zapisu, poczekać na potwierdzenie od wszystkich współużytkowników i przejść do stanu Modified. Ta droga powrotna do protokołu spójności zajmuje 50–300+ cykli w systemie wielogniazdowym. Fałszywe współdzielenie przekształca niezależne operacje lokalne wątków w ruch spójności pamięci podręcznej, co obniża wydajność, która powinna skalować się liniowo wraz z liczbą rdzeni.

Wykrywanie fałszywego udostępniania: posługiwać się perf stat -e cache-misses,L1-dcache-load-misses w systemie Linux lub w narzędziu do profilowania wydajności procesora programu Visual Studio w systemie Windows. Wysoki wskaźnik braków w pamięci podręcznej L1 w programie wielowątkowym, który mieści się w pamięci podręcznej, jest silnym wskaźnikiem fałszywego współdzielenia.

Porządkowanie pamięci: dlaczego memory_order_relaxed Nie zawsze wystarczy

C + + std::atomic Operacje ujawniają pełen zakres uporządkowania pamięci z modelu pamięci C++11. Wybór niewłaściwego uporządkowania jest drugim najczęstszym błędem w kodzie bez blokad, po problemie ABA.

Cpp

// The five memory orderings and when each applies:

// relaxed: no synchronization, only atomicity
// Use for: counters where only the final value matters
counter.fetch_add(1, std::memory_order_relaxed);

// acquire: reads see all writes by threads that released this location
// Use for: reading shared state protected by a flag
if (ready.load(std::memory_order_acquire)) {
    use(data); // guaranteed to see all writes made before ready was set
}

// release: writes are visible to threads that acquire this location
// Use for: publishing shared state
data = compute();
ready.store(true, std::memory_order_release);

// acq_rel: acquire + release in one operation
// Use for: read-modify-write operations like CAS in the middle of a chain
node.compare_exchange_strong(expected, desired,
    std::memory_order_acq_rel,   // success
    std::memory_order_acquire);  // failure

// seq_cst: total order across all seq_cst operations, all cores
// Use for: when you need a global consistent view (but slowest)
flag.store(true, std::memory_order_seq_cst);

Częsty błąd: używanie relaxed dla flagi wydania. Wątek, który ustawia ready = true w relaxed zamówienie nie gwarantuje, że poprzednie zapisy są data są widoczne dla innych wątków, które czytają readyPara „pozyskaj/udostępnij” tworzy relację „dzieje się wcześniej”, która łączy autora i czytelnika.

Stos Treibera: stos bez blokad w C++

Stos Treibera to najprostsza, nietrywialna struktura danych bez blokad. Wykorzystuje pętlę CAS na jednym top wskaźnik:

Cpp

#include <atomic>

template<typename T>
class TreiberStack {
    struct Node {
        T data;
        Node* next;
        explicit Node(T d) : data(std::move(d)), next(nullptr) {}
    };

    std::atomic<Node*> top{nullptr};

public:
    void push(T data) {
        Node* node = new Node(std::move(data));
        node->next = top.load(std::memory_order_relaxed);
        while (!top.compare_exchange_weak(
            node->next,          // expected -- updated on failure
            node,                // desired
            std::memory_order_release,
            std::memory_order_relaxed))
        { /* retry */ }
    }

    bool pop(T& result) {
        Node* node = top.load(std::memory_order_acquire);
        while (node) {
            if (top.compare_exchange_weak(
                node,
                node->next,      // new top
                std::memory_order_acquire,
                std::memory_order_relaxed))
            {
                result = std::move(node->data);
                // WARNING: cannot free node here safely without hazard pointers or EBR
                // delete node; -- ABA hazard if another thread reads node->next
                return true;
            }
        }
        return false; // empty
    }
};

Komentarz do delete node jest krytyczny: naiwne usunięcie to zagrożenie ABA opisane wcześniej. W produkcyjnym stosie Treibera odzyskiwanie węzłów wymaga wskaźników zagrożenia, odzyskiwania opartego na epoce lub zbierania śmieci (Java/C# obsługuje to automatycznie).

Struktury danych Java bez blokad

Standardowa biblioteka języka Java zapewnia implementacje bez blokad o jakości produkcyjnej java.util.concurrent:

Klasa	Structure	Postęp	Komentarz
AtomicReference<T>	Pojedyncza wartość	Bez blokady	CAS w odniesieniu do obiektu
AtomicStampedReference<T>	Wartość + znaczek	Bez blokady	Zapobieganie ABA poprzez licznik wersji
ConcurrentLinkedQueue<T>	Kolejka Michaela-Scotta	Bez blokady	FIFO, nieograniczone
ConcurrentLinkedDeque<T>	Deque bez blokady	Bez blokady	Obydwa końce
LongAdder	Przeciwdziałać	Bez blokady	Liczenie paskowe o dużej przepustowości

LongAdder Warto zwrócić na to szczególną uwagę. Zamiast pojedynczego licznika atomowego konkurującego we wszystkich wątkach, utrzymuje on rozproszoną tablicę liczników, z których każdy jest dostępny dla podzbioru wątków. Konflikt jest rozłożony na pasma, a nie skoncentrowany w jednym miejscu. Suma jest leniwie sumowana na sum()W przypadku operacji inkrementacji o wysokiej częstotliwości w wielu wątkach, LongAdder dramatycznie przewyższa AtomicLong.incrementAndGet():

Jawa

import java.util.concurrent.atomic.LongAdder;

// BAD for high-concurrency counting: all threads contend on one location
AtomicLong counter = new AtomicLong(0);
counter.incrementAndGet(); // single CAS -- all threads collide

// GOOD for high-concurrency counting: contention distributed across stripes
LongAdder adder = new LongAdder();
adder.increment();  // updates thread-local stripe -- minimal contention
long total = adder.sum(); // sum all stripes lazily

W jaki sposób SMART TS XL Wspiera rozwój systemu bez blokady

Kod bez blokad jest jednym z najtrudniejszych do poprawnego napisania. Błędy są niedeterministyczne, pojawiają się tylko w określonych przeplotach i często tylko w środowisku produkcyjnym na dużą skalę. Analiza statyczna rozwiązuje ten problem, badając właściwości strukturalne kodu przed wykonaniem, zamiast czekać na wystąpienie warunku wyścigu.

SMART TS XL Analizuje pełne ścieżki wykonywania kodu współbieżnego, śledząc związek operacji atomowych z chronionymi przez nie lokalizacjami w pamięci. W systemach, które łączą kod bez blokad ze starszymi komponentami lub architekturami wielojęzycznymi, zapewnia on widoczność transgraniczną, której nie mogą zapewnić narzędzia jednojęzyczne: jak współdzielony obszar pamięci, do którego uzyskuje dostęp komponent C++ bez blokad, odnosi się do usługi Java, która z niego odczytuje, lub jak kolejka współbieżna zasila potok przetwarzania oparty na języku COBOL.

Funkcja statycznej analizy kodu identyfikuje wzorce związane z zagrożeniami współbieżności: obciążenia atomowe bez odpowiadającej im semantyki pozyskiwania, pętle CAS, które nie aktualizują oczekiwanej wartości w przypadku awarii, współdzielone struktury danych, w których pola dostępne dla różnych wątków są zlokalizowane w tym samym miejscu bez dopełnienia wyrównania. Funkcja analizy wpływu śledzi, które komponenty niższego rzędu zależą od współdzielonej, współbieżnej struktury danych, dzięki czemu zmiany w interfejsie struktury lub strategii odzyskiwania mogą być poprawnie określone przed ich wprowadzeniem.

W przypadku systemów korporacyjnych, w których komponenty bez blokad muszą współistnieć ze starszymi systemami przetwarzania wsadowego, oprogramowaniem pośredniczącym do kolejkowania wiadomości i nowoczesnymi warstwami usług, SMART TS XL'S mapowanie zależności zapewnia architektoniczny widok tego, w jaki sposób współbieżne ścieżki danych łączą komponenty napisane w różnych językach w całym stosie systemu.

Kiedy blokada bezkluczykowa to zły wybór

Struktura bezblokadowa nie zawsze jest lepsza niż mutex. Argumenty przemawiające za strukturami bezblokadowymi zależą od rzeczywistego profilu rywalizacji obciążenia. Przy niskiej liczbie wątków lub niskiej rywalizacji, dobrze zaimplementowany mutex jest szybszy, ponieważ unika narzutu związanego z atomowymi pętlami ponawiania prób i unieważnianiem linii pamięci podręcznej w rdzeniach.

Użyj mutexu, gdy:

• Liczba wątków jest niska (poniżej 4-8) lub konflikty występują rzadko
• Krytyczny odcinek jest długi i skomplikowany (pętle bez blokad stają się droższe w porównaniu z pozostałymi odcinkami)
• Poprawność jest ważniejsza niż przepustowość, a algorytm jest prostszy z blokadą
• Platforma ma wydajne blokowanie oparte na futexie (Linux pthread_mutex, Windows SRWLOCK)

Używaj trybu bez blokady, gdy:

• Liczba wątków jest wysoka, a konflikty utrzymują się
• Operacje są krótkie (obciążenie pętli CAS jest niewielkie w porównaniu do operacji)
• Blokowanie jest niedopuszczalne (wątki czasu rzeczywistego, obsługa przerwań, obsługa sygnałów)
• Komponowanie z innymi strukturami bez blokad, w których blokada wprowadziłaby zależności kolejności blokad

Użyj opcji „wait-free”, gdy:

• Każdy wątek musi zakończyć się w ograniczonym czasie, niezależnie od innych wątków
• Wymagania dotyczące czasu rzeczywistego lub bezpieczeństwa krytycznego, w których niedopuszczalne jest głodzenie
• Algorytm można skonstruować tak, aby obsługiwał wykonywanie ograniczonych kroków na wątek

Dyscyplina programowania bez blokad polega nie na wybieraniu go wszędzie, ale na wybieraniu go dokładnie tam, gdzie jego właściwości, takie jak nieblokujący postęp, eliminacja blokad, tolerancja wywłaszczania, odpowiadają rzeczywistym wymaganiom systemu.