Lock-Free структурыStructures

Compare-And-Swap — аппаратная инструкция (на x86 — CMPXCHG), атомарно выполняющая: "если текущее значение ячейки памяти равно ожидаемому — записать новое значение и вернуть успех; иначе — обновить ожидаемое значение текущим и вернуть неудачу". Это единственная примитивная операция, на которой строится практически весь lock-free код — она позволяет реализовать любое "прочитать-изменить-записать" без блокировки: прочитать текущее значение, вычислить новое на его основе, попытаться CAS; при неудаче (значение поменял кто-то другой) — повторить с начала.Compare-And-Swap is a hardware instruction (CMPXCHG on x86) that atomically does: "if the memory cell's current value equals the expected value, write the new value and report success; otherwise, update the expected value to the current one and report failure." It's the single primitive operation nearly all lock-free code is built on — it lets you implement any "read-modify-write" without a lock: read the current value, compute a new one from it, attempt a CAS; on failure (someone else changed it), retry from the top.

std::atomic<int> value{0};

void incrementLockFree() {
    int expected = value.load();
    while (!value.compare_exchange_weak(expected, expected + 1)) {
        // compare_exchange_weak при неудаче сам обновил expected текущим значением — повтор// compare_exchange_weak already updated expected to the current value on failure — retry
    }
}

compare_exchange_weak может провалиться "ложно" (spurious failure) даже когда значение фактически совпадает с ожидаемым — на архитектурах без единой атомарной CAS-инструкции (load-linked/store-conditional, например ARM) это дешевле реализовать, чем гарантировать отсутствие ложных провалов. compare_exchange_strong не имеет ложных провалов, но может быть менее эффективен внутри циклов — отсюда правило: `_weak` в цикле retry, `_strong` для одиночной попытки.compare_exchange_weak can fail "spuriously" even when the value actually matches expected — on architectures without a single atomic CAS instruction (load-linked/store-conditional, e.g. ARM), this is cheaper to implement than guaranteeing no spurious failures. compare_exchange_strong has no spurious failures, but can be less efficient inside loops — hence the rule: `_weak` inside a retry loop, `_strong` for a single attempt.

Классическая учебная структура — стек на связном списке, где вершина обновляется через CAS вместо мьютекса:The classic teaching structure — a linked-list stack where the head is updated via CAS instead of a mutex:

template<typename T>
class LockFreeStack {
    struct Node {
        T value;
        Node* next;
    };
    std::atomic<Node*> head{nullptr};
public:
    void push(T value) {
        Node* node = new Node{std::move(value), head.load()};
        while (!head.compare_exchange_weak(node->next, node)) {
            // node->next обновится текущим head автоматически при неудаче — повтор// node->next auto-updates to the current head on failure — retry
        }
    }

    bool pop(T& out) {
        Node* old_head = head.load();
        while (old_head &&
               !head.compare_exchange_weak(old_head, old_head->next)) {
            // old_head обновился текущим head при неудаче — повтор// old_head is updated to the current head on failure — retry
        }
        if (!old_head) return false;
        out = std::move(old_head->value);
        // delete old_head здесь небезопасен без защиты от ABA/use-after-free (см. ниже) — упрощено для иллюстрации// delete old_head here is unsafe without ABA/use-after-free protection (see below) — simplified for illustration
        return true;
    }
};

Эта версия push корректна и достаточна для собеседования, но pop намеренно упрощён — реальная безопасная реализация требует решения проблемы ABA и безопасного освобождения памяти (hazard pointers или epoch-based reclamation), разобранных ниже.This version of push is correct and sufficient for an interview, but pop is deliberately simplified — a real, safe implementation requires solving the ABA problem and safe memory reclamation (hazard pointers or epoch-based reclamation), covered below.

CAS проверяет только текущее значение, а не историю изменений. Если поток 1 читает значение A, приостанавливается, за это время поток 2 меняет значение A → B → снова A (например, освобождает и переиспользует ту же ячейку памяти под новый объект), а затем поток 1 просыпается и выполняет CAS — CAS УСПЕШНО пройдёт, хотя логически состояние структуры изменилось кардинально между чтением и CAS потока 1.CAS only checks the current value, not the history of changes. If thread 1 reads value A, gets suspended, and during that time thread 2 changes A → B → back to A (e.g., frees and reuses that exact memory cell for a new object), and then thread 1 wakes up and performs its CAS — the CAS will SUCCEED, even though the structure's logical state changed dramatically between thread 1's read and its CAS.

В контексте lock-free стека проблема ABA конкретно проявляется как use-after-free: поток 1 держит указатель на old_head, но пока он "спал", узел был выдан pop-ом, удалён, и его память переиспользована аллокатором под новый push — CAS потока 1 может пройти успешно над уже освобождённой и переиспользованной памятью.In the context of a lock-free stack, the ABA problem concretely manifests as use-after-free: thread 1 holds a pointer to old_head, but while it was "asleep," that node was popped, freed, and its memory reused by the allocator for a new push — thread 1's CAS can succeed over memory that's already been freed and reused.

Классическое решение — тегированные указатели (tagged pointers): вместе с указателем атомарно хранится счётчик поколений (generation counter), инкрементируемый при каждом изменении; CAS сравнивает пару (указатель, счётчик) целиком, так что даже если указатель "вернулся" к старому значению, счётчик уже другой. Современная альтернатива — hazard pointers или epoch-based reclamation (используется, например, в реализациях folly::AtomicHashMap), откладывающие физическое освобождение памяти, пока какой-либо поток потенциально всё ещё держит указатель на неё.The classic fix is tagged pointers: alongside the pointer, a generation counter is stored atomically, incremented on every change; CAS compares the (pointer, counter) pair as a whole, so even if the pointer "returns" to its old value, the counter has moved on. A more modern alternative is hazard pointers or epoch-based reclamation (used, e.g., in folly::AtomicHashMap's implementation), which defer physically freeing memory until no thread might still hold a pointer to it.

• cppreference — std::atomic::compare_exchange_weak/strong
• Anthony Williams — C++ Concurrency in Action (2nd ed.), ch. 7