Бесблокировочные структуры данных: полное руководство с примерами на C++, Java и .NET

Мьютекс прост. Вы блокируете его, изменяете общее состояние, разблокируете. Каждый поток, желающий получить доступ, ждет своей очереди. Проблема заключается в «ожидании своей очереди»: при большом количестве ядер и высокой пропускной способности сериализация становится пределом. Поток, удерживающий блокировку, может быть вытеснен, в результате чего все остальные потоки остаются бездействующими. Инверсия приоритетов может привести к тому, что потоки с низким приоритетом будут блокировать потоки с высоким приоритетом. В системах, обрабатывающих миллионы операций в секунду на десятках ядер, конкуренция за мьютекс не просто замедляет работу; она обрушивает пропускную способность.

В структурах данных без блокировок взаимное исключение заменяется атомарными операциями. Вместо предотвращения конфликтов они допускают их и восстанавливаются после них. Поток, которому не удается выполнить операцию сравнения и обмена, повторяет попытку с обновленным состоянием. Ни один поток никогда не блокирует другой. По крайней мере один поток всегда продолжает работу. В результате достигается значительно более высокая пропускная способность при высокой конкуренции, предсказуемая задержка без эффектов конвоя и устранение взаимоблокировок и инверсии приоритетов по умолчанию. Цена — сложность реализации: проблема ABA, опасности освобождения памяти, ложное разделение и тонкие требования к порядку доступа к памяти — все это ловушки, которых нет в коде, основанном на блокировках. В этой статье все они рассматриваются на конкретных примерах кода.

Блокировка без блокировок, ожидание без блокировок или мьютекс: что использовать?

Прежде чем выбирать подход к реализации, важно задаться вопросом, какая именно гарантия прогресса необходима системе. Три модели различаются тем, что они обещают при конкуренции потоков.

Модель	Гарантия выполнения работ	Типичная задержка	Многогранность	Best For
Мьютекс / блокировка на основе	Блокировка, потоки ожидают	Непредсказуемо в условиях конкуренции	Низкий	Общее состояние с низкой конкуренцией, простые требования к корректности.
Без блокировки	В масштабах всей системы, по крайней мере, один поток продолжает развиваться.	Низкий уровень конкуренции	Высокий	Высокопроизводительные очереди, стеки, счетчики
Без ожидания	В рамках каждого потока выполнение завершается за ограниченное количество шагов.	Ограниченный наихудший случай	Очень высоко	Системы реального времени, критически важные для безопасности, с жесткими требованиями к задержке и соблюдению соглашений об уровне обслуживания (SLA).
Без препятствий	Самостоятельное продвижение вперед, только при отсутствии препятствий.	Низкий уровень без споров	Средний	Прототипы транзакционной памяти, контексты исследований

Без блокировки Это практический вариант по умолчанию для высокопроизводительных производственных систем. Очередь Майкла-Скотта, стек Трейбера и большинство производственных кольцевых буферов MPMC не используют блокировки. Отдельные потоки могут испытывать дефицит ресурсов при сильной конкуренции, но система в целом продолжает развиваться.

Без ожидания Гарантирует ограниченный прогресс для каждого потока, но требует значительно более сложных алгоритмов. Существуют универсальные конструкции, но они сопряжены с высокими накладными расходами. Алгоритмы без ожидания подходят для жестких условий реального времени, где задержка в хвосте распределения важнее, чем средняя пропускная способность.

Без препятствий В производственной среде используется редко. Она встречается в некоторых реализациях транзакционной памяти и служит промежуточным этапом при доказательстве корректности алгоритма.

Для большинства систем с высокой степенью параллелизма: используйте мьютекс, когда конкуренция за ресурсы низкая и корректность работы не имеет значения; используйте протокол без блокировок, когда важна пропускная способность при наличии конкуренции; используйте протокол без ожидания только тогда, когда жестко задана наихудшая задержка для каждого потока.

Что такое структура данных без блокировок?

Структура данных — это без блокировки Если алгоритм гарантирует, что хотя бы один поток из всех работающих с ним потоков завершит свою работу за конечное число шагов, независимо от того, что делают другие потоки или как они запланированы. Это формальное определение имеет точное следствие: ни один алгоритм без блокировок не может привести к взаимоблокировке. Если один поток остановлен, приостановлен или работает медленно, другие потоки продолжают продвигаться вперед.

Механизм основан на атомарных операциях, инструкциях ЦП, которые выполняются как единое неделимое целое. Универсальным примитивом является Метод сравнения и обмена (CAS):

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

CAS является атомарной системой на аппаратном уровне. На архитектуре x86 это CMPXCHG инструкция. На ARM она реализована через LDXR/STXR (загрузка с эксклюзивным условием/сохранение с эксклюзивным условием), что является вариантом LL/SC (загрузка с привязкой к значению/сохранение с условным условием). Поток считывает значение, вычисляет новое значение и использует CAS для его установки только в том случае, если никто другой не изменил его за это время. Если CAS не удается, поток повторяет попытку с новым значением.

В C++11 и более поздних версиях это доступно через 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 Это примитив CAS. В случае сбоя он обновляется. expected Автоматически присваивает текущее значение, что делает цикл повторных попыток идиоматичным.

Проблема ABA: самая опасная ловушка системы Lock-Free.

Проблема ABA — это наиболее неинтуитивная угроза корректности в программировании без блокировок. CAS проверяет, содержит ли ячейка памяти ожидаемое значение, прежде чем установить новое. Она не может обнаружить, было ли это значение изменено, а затем возвращено в исходное состояние между чтением и проверкой CAS. Ячейка по-прежнему выглядит как исходное значение, но базовое состояние системы изменилось таким образом, который CAS не может увидеть.

Пошаговое описание сценария

Рассмотрим стек без блокировок, использующий единственный указатель. top:

1. Ветка A читает top = Node1Следующий указатель узла 1 — узел 2.
2. Поток A прерывается до завершения своего завершения.
3. Поток B удаляет Node1 (верхний узел становится Node2), затем удаляет Node2 (верхний узел становится пустым).
4. Поток B добавляет новый узел, который, как оказалось, выделен по тому же адресу памяти, что и Node1 (что характерно для распределителей памяти по списку свободных ячеек). Top = Node1 (тот же указатель, другое содержимое).
5. Поток A возобновляется. Его CAS видит top == Node1 (ожидаемое значение), успешно выполняется и устанавливает top = Node2Но Node2 уже был освобожден. Катастрофа.

Проблема ABA проявляется по-разному в каждой структуре данных:

• СтекОперация CAS выполняется успешно, но устанавливает устаревший указатель next, что приводит к использованию освобожденной памяти после освобождения.
• ОчередьГоловной или хвостовой указатель выглядит неизменным, но структура изменилась.
• Связанный списокУзел, по-видимому, все еще находится на своем месте, но был удален и перераспределен.

Позволяет ли метод LL/SC избежать проблем, связанных с ABA-терапией?

Да, LL/SC (Load-Linked/Store-Conditional) предоставляет сильнее В отличие от CAS, здесь используется более сложная семантика, позволяющая избежать ABA. LL помечает загруженный адрес памяти как «связанный». SC по тому же адресу завершается неудачей, если после LL была произведена какая-либо запись по этому адресу, даже если значение было восстановлено до исходного состояния. История изменений отслеживается на аппаратном уровне, а не только текущее значение.

Однако реализация LL/SC на реальном оборудовании имеет практические ограничения. На ARM и POWER случайные сбои LL/SC могут возникать даже без конфликтов (переключения контекста, вытеснение из кэша). Код должен учитывать циклы повторных попыток даже без реальных конфликтов. На x86 нет встроенной реализации LL/SC; аппаратным примитивом является CAS. Для кода x86 необходимо предотвращать ABA программным способом.

Улучшение ABA-терапии: три подхода

1. Счетчики версий (помеченные указатели)

В то же атомарное слово, что и указатель, поместите счетчик версий. Каждое успешное выполнение операции CAS увеличивает счетчик. Даже если указатель возвращается к своему исходному значению, счетчик все равно будет другим:

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);
}

На практике это стандартный подход. 16-битный тег обнуляется после 65 536 операций, что теоретически небезопасно, но практически достаточно для большинства систем, поскольку крайне маловероятно, что поток будет вытеснен ровно на 65 536 циклов CAS в одном и том же месте.

2. Указатели опасности

Каждый поток поддерживает небольшой набор «указателей опасности» — указателей на узлы, к которым он в данный момент обращается. Перед освобождением любого узла поток проверяет все реестры указателей опасности, чтобы убедиться, что к нему не обращается другой поток. Работа с узлом, который фигурирует в указателе опасности, откладывается до тех пор, пока этот указатель не будет очищен.

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;
}

Указатели опасности предотвращают ABA на уровне освобождения памяти: узел не может быть использован повторно, пока какой-либо поток удерживает указатель опасности на него. Это требует сканирования всех указателей опасности потоков перед освобождением памяти, что добавляет накладные расходы, пропорциональные количеству потоков.

3. Эпохальная рекультивация (ЭИР)

Потоки работают в глобально отслеживаемых «эпохах». Удаленные узлы буферизуются для каждой эпохи и освобождаются только тогда, когда все потоки прошли эпоху, в которой узел был удален. EBR проще в использовании, чем указатели на конфликтные ситуации, и имеет меньшие накладные расходы на операцию, но ценой ограниченного, но непредсказуемого роста объема памяти в периоды покоя.

В Java AtomicStampedReference Проблема ABA решается напрямую путем сопоставления ссылки с целочисленной меткой:

Ява

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));
}

Реализации очередей без блокировок

Очереди — наиболее часто используемая структура, не требующая блокировок. Канонической очередью без блокировок является очередь Майкла-Скотта, которая использует два указателя (начало и конец) и узел-сторож для обеспечения одновременных операций добавления и извлечения элементов из очереди.

Очередь SPSC: максимальная производительность при минимальной синхронизации

Очередь с одним производителем и одним потребителем исключает все конфликты при записи и чтении. Один поток записывает данные в конец очереди, другой — читает из начала. Только указатель на начало очереди используется совместно производителем и потребителем.

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) Запись в начало и конец кэша имеет решающее значение. Без этого оба элемента помещаются на одной и той же строке кэша. Каждая запись в конец кэша вызывает аннулирование строки кэша, видимое для основного считывающего устройства, и наоборот, что приводит к ложному разделению, которое сериализует операции, которые должны быть независимыми.

Очередь MPMC: несколько производителей и множество потребителей

Полностью параллельная очередь MPMC значительно сложнее. В производственных реализациях для координации производителей и потребителей без блокировки используется порядковый номер для каждого слота:

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: как это работает внутри

.NET ConcurrentQueue<T> В .NET 5+ используется структура сегментированного массива. Каждый сегмент представляет собой массив фиксированного размера с индексами начала и конца, управляемыми с помощью Interlocked операции (которые отображаются на CAS на базовом оборудовании). Сегменты связаны через энергозависимый канал. _nextSegment указатель. Функция enqueue добавляет элементы в текущий хвостовой сегмент, расширяя цепочку сегментов по мере заполнения. Функция dequeue считывает данные из головного сегмента и атомарно перемещает индекс головного сегмента.

Ключевое проектное решение заключается в предотвращении глобальной зависимости. Производители конкурируют только по показателю «хвостовой части» текущего сегмента. Потребители конкурируют только по показателю «головной части». Ни один производитель никогда не конкурирует с потребителем. Это делает ConcurrentQueue<T> высокоэффективны для цепочек поставок «производитель-потребитель»:

острый

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);

Согласованность кэша и ложное разделение в коде без блокировок

В реализациях без блокировок согласованность кэша — это невидимая переменная производительности. Когда ядро ​​записывает данные в ячейку памяти, вся 64-байтовая строка кэша, содержащая эту ячейку, становится недействительной во всех кэшах других ядер. Им необходимо получить обновленную строку, прежде чем читать данные. В коде без блокировок с частыми атомарными обновлениями эта недействительность строки кэша может стать основной статьей расходов.

Ложное распространение информации Это происходит, когда два потока изменяют разные переменные, которые случайно используют одну и ту же кэш-строку. Ни один из потоков не обращается к одним и тем же данным, но протокол когерентности кэша рассматривает всю кэш-строку как конкурирующую:

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
};

Протокол MESI (Modified, Exclusive, Shared, Invalid) описывает, как процессоры x86 координируют владение кэш-линиями. Когда ядро ​​хочет записать данные в область, которую оно разделяет с другими ядрами (состояние Shared), оно должно отправить широковещательный запрос на запись, дождаться подтверждения от всех разделяющих ядер и перейти в состояние Modified. Этот цикл обмена данными с протоколом когерентности занимает от 50 до 300 и более циклов в многопроцессорной системе. Ложное разделение преобразует независимые локальные операции потоков в трафик когерентности кэша, что приводит к снижению производительности, которая должна масштабироваться линейно с количеством ядер.

Выявление ложных сообщений: использование perf stat -e cache-misses,L1-dcache-load-misses в Linux или в профилировщике производительности ЦП Visual Studio в Windows. Высокий процент промахов кэша L1 в многопоточной программе, которая помещается в кэш, является сильным признаком ложного разделения ресурсов.

Порядок хранения в памяти: зачем? memory_order_relaxed Этого не всегда достаточно.

C + + std::atomic Операции раскрывают весь спектр порядка доступа к памяти в модели памяти C++11. Выбор неправильного порядка доступа является второй по распространенности ошибкой в ​​коде без блокировок после проблемы 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);

Распространенная ошибка: использование relaxed для флага выпуска. Поток, который устанавливает ready = true с relaxed Порядок не гарантирует, что предыдущие записи будут выполнены. data видны другим веткам обсуждения, которые читают readyПара «приобретение/освобождение» создает взаимосвязь «происходит до», которая соединяет автора и читателя.

Стек Трейбера: стек без блокировок в C++

Стек Трейбера — это простейшая нетривиальная структура данных без блокировок. Он использует цикл CAS на одном устройстве. top указатель:

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
    }
};

Комментарий к delete node Это критически важно: наивное удаление — это описанная ранее опасность ABA. В производственной среде Treiber для освобождения ресурсов узлов требуются указатели на опасности, освобождение ресурсов на основе эпох или сборка мусора (Java/C# обрабатывают это автоматически).

Бесблокировочные структуры данных в Java

Стандартная библиотека Java предоставляет высококачественные реализации без блокировок. java.util.concurrent:

Класс	Структура:	Прогресс	Заметки
AtomicReference<T>	Одно значение	Без блокировки	CAS по ссылке на объект
AtomicStampedReference<T>	Стоимость + марка	Без блокировки	Предотвращение ABA с помощью счетчика версий
ConcurrentLinkedQueue<T>	Очередь Майкла-Скотта	Без блокировки	FIFO, неограниченный
ConcurrentLinkedDeque<T>	Деке без замка	Без блокировки	Оба конца
LongAdder	Счетчик	Без блокировки	Полосатый высокопроизводительный подсчет

LongAdder Стоит особо отметить следующее. Вместо единого атомарного счетчика, конкурирующего между всеми потоками, используется полосатый массив счетчиков, к каждому из которых обращается подмножество потоков. Конкуренция распределяется по полосам, а не концентрируется в одном месте. Сумма суммируется лениво. sum()Для высокочастотных операций инкремента в нескольких потоках, LongAdder значительно превосходит ожидания AtomicLong.incrementAndGet():

Ява

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

Как SMART TS XL Поддерживает разработку систем без блокировок.

Код без блокировок — один из самых сложных для правильной реализации. Ошибки носят недетерминированный характер, проявляются только при определённых вариантах чередования и часто только в масштабах, используемых в производственной среде. Статический анализ решает эту проблему, изучая структурные свойства кода до его выполнения, а не ожидая появления состояния гонки.

SMART TS XL Анализирует полные пути выполнения параллельного кода, отслеживая, как атомарные операции связаны с областями памяти, которые они защищают. Для систем, сочетающих код без блокировок с устаревшими компонентами или многоязычными архитектурами, он обеспечивает межплатформенную видимость, недоступную для одноязычных инструментов: как область общей памяти, к которой обращается компонент C++ без блокировок, связана с Java-сервисом, который считывает из нее данные, или как параллельная очередь передает данные в конвейер обработки на основе COBOL.

статический анализ кода Эта функция позволяет выявлять закономерности, связанные с рисками параллельного доступа: атомарные загрузки без соответствующей семантики получения данных, циклы CAS, которые не обновляют ожидаемое значение при сбое, общие структуры данных, в которых поля, к которым обращаются разные потоки, расположены совместно без выравнивания. анализ воздействия Функция отслеживания определяет, какие компоненты, работающие в потоке, зависят от общей параллельной структуры данных, что позволяет корректно определить область действия изменений в интерфейсе структуры или стратегии высвобождения ресурсов до внесения изменений.

Для корпоративных систем, где компоненты, не требующие блокировок, должны сосуществовать с устаревшей пакетной обработкой, промежуточным программным обеспечением для очередей сообщений и современными сервисными уровнями, SMART TS XLАвтора отображение зависимостей Предоставляет архитектурное представление того, как параллельные пути передачи данных соединяют компоненты, написанные на разных языках, по всему системному стеку.

Когда система без замков — неправильный выбор

Бесблокировочные структуры не всегда лучше мьютексов. Аргументы в пользу бесблокировочных структур зависят от фактического профиля конкуренции в рабочей нагрузке. При малом количестве потоков или низкой конкуренции хорошо реализованный мьютекс работает быстрее, поскольку позволяет избежать накладных расходов на атомарные циклы повторных попыток и аннулирование кэш-линий между ядрами.

Используйте мьютекс, когда:

• Количество нитей невелико (менее 4-8) или конфликты возникают нечасто.
• Критический участок длинный и сложный (петли, исключающие блокировки, обходятся дорого по сравнению с длиной участка).
• Точность важнее пропускной способности, и алгоритм упрощается при наличии блокировки.
• Платформа имеет эффективную систему блокировки на основе futex (Linux). pthread_mutex(Windows SRWLOCK)

Используйте режим без замка, когда:

• Количество потоков велико, и конкуренция сохраняется.
• Операции короткие (накладные расходы на петлю CAS невелики по сравнению с продолжительностью операции).
• Блокировка недопустима (потоки реального времени, обработчики прерываний, обработчики сигналов).
• Композиция с другими структурами без блокировок, где блокировка вводит зависимости порядка блокировок.

Используйте функцию «Без ожидания», когда:

• Каждый поток должен завершиться за ограниченное время, независимо от других потоков.
• Жесткие требования к работе в реальном времени или критически важные для безопасности, где голодание недопустимо.
• Алгоритм может быть структурирован таким образом, чтобы поддерживать завершение с ограниченным количеством шагов для каждого потока.

Суть безблокировочного программирования заключается не в выборе блокировок повсюду, а в выборе их именно там, где их свойства — неблокирующий ход выполнения, устранение взаимоблокировок, устойчивость к вытеснению — соответствуют реальным требованиям системы.