Зачем lock-free

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

Lock-free очереди избегают этого, используя атомарные операции, всегда делающие прогресс без блокировки ядра. Компромисс: корректность требует тщательного упорядочивания памяти, а ошибки реализации — тихие, редкие и катастрофические.

Эта статья охватывает два паттерна: SPSC (один производитель, один потребитель) — простейший и быстрейший, и MPSC (много производителей, один потребитель) — покрывает большинство реальных многопоточных конвейеров.

SPSC — простейшая lock-free очередь

SPSC имеет один инвариант: только один поток пишет (производитель) и только один читает (потребитель). Это ограничение открывает очень эффективный дизайн на основе кольцевого буфера.

Дизайн

head ──────────────────────────────────┐
     [ _ ][ A ][ B ][ C ][ _ ][ _ ][ _ ]
               ↑                    ↑
            tail                  capacity
  • tail принадлежит производителю — только производитель его пишет
  • head принадлежит потребителю — только потребитель его пишет
  • Очередь пуста, когда head == tail
  • Очередь полна, когда (tail + 1) % capacity == head

Поскольку владение эксклюзивно, нам нужны только атомарные чтения индекса другой стороны — никакого compare-and-swap, никакого спинлока.

Реализация

 1template <typename T, size_t Capacity>
 2class SpscQueue {
 3    static_assert((Capacity & (Capacity - 1)) == 0,
 4                  "Ёмкость должна быть степенью двойки");
 5public:
 6    bool push(const T& item) {
 7        const size_t tail = tail_.load(std::memory_order_relaxed);
 8        const size_t next = (tail + 1) & (Capacity - 1);
 9
10        // Устаревшее чтение допустимо — если head продвинулся, видим меньше слотов
11        if (next == head_.load(std::memory_order_acquire))
12            return false;  // полная
13
14        buffer_[tail] = item;
15        tail_.store(next, std::memory_order_release);
16        return true;
17    }
18
19    bool pop(T& item) {
20        const size_t head = head_.load(std::memory_order_relaxed);
21
22        if (head == tail_.load(std::memory_order_acquire))
23            return false;  // пустая
24
25        item = buffer_[head];
26        head_.store((head + 1) & (Capacity - 1), std::memory_order_release);
27        return true;
28    }
29
30private:
31    alignas(64) std::atomic<size_t> head_{0};
32    alignas(64) std::atomic<size_t> tail_{0};
33    T buffer_[Capacity];
34};

Объяснение упорядочивания памяти

Путь push:

  1. tail_.load(relaxed) — производитель читает свой индекс; синхронизация не нужна
  2. head_.load(acquire) — acquire в паре с release-записью потребителя head_, гарантируя видимость всех записей, сделанных потребителем до продвижения head_
  3. buffer_[tail] = item — запись данных
  4. tail_.store(release) — release гарантирует видимость записи данных до продвижения индекса; acquire-загрузка tail_ потребителем увидит оба

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

Ложное разделение

alignas(64) на каждом атомарном значении предотвращает ложное разделение (false sharing) — кэш-линия CPU обычно 64 байта. Если head_ и tail_ делили бы кэш-линию, запись tail_ производителем инвалидировала бы кэш-линию в L1-кэше потребителя и наоборот. Их разделение стоит 64 байта памяти и даёт значительный прирост пропускной способности на многоядерных системах.

MPSC — несколько производителей, один потребитель

MPSC нужен, когда несколько потоков (пул воркеров, потоки I/O, обработчики прерываний) питают один поток обработки. Классический пример: логгер, получающий сообщения из многих потоков и записывающий на выделенном I/O-потоке.

Дизайн

Задача: несколько производителей конкурируют за слот. Нужен атомарный compare-and-swap (CAS) для разрешения гонки.

Простейший корректный подход — связанный список MPSC (очередь Майкла-Скотта, упрощённая для одного потребителя):

 1template <typename T>
 2class MpscQueue {
 3    struct Node {
 4        T data;
 5        std::atomic<Node*> next{nullptr};
 6    };
 7
 8public:
 9    MpscQueue() {
10        // Сторожевой узел — head всегда указывает на заглушку
11        Node* dummy = new Node{};
12        head_.store(dummy, std::memory_order_relaxed);
13        tail_ = dummy;
14    }
15
16    // Вызывается производителями (любым потоком)
17    void push(T item) {
18        Node* node = new Node{std::move(item)};
19        // Атомарно заменяем head, связываем новый узел с предыдущим head
20        Node* prev = head_.exchange(node, std::memory_order_acq_rel);
21        prev->next.store(node, std::memory_order_release);
22    }
23
24    // Вызывается потребителем (только одним потоком)
25    bool pop(T& item) {
26        Node* tail = tail_;
27        Node* next = tail->next.load(std::memory_order_acquire);
28        if (!next) return false;  // пустая
29
30        item = std::move(next->data);
31        tail_ = next;
32        delete tail;  // удалить старый сторожевой узел
33        return true;
34    }
35
36    ~MpscQueue() {
37        T discard;
38        while (pop(discard)) {}
39        delete tail_;
40    }
41
42private:
43    alignas(64) std::atomic<Node*> head_;
44    alignas(64) Node* tail_;   // только для потребителя, атомарный не нужен
45};

Трюк с exchange

head_.exchange(node, acq_rel) атомарно заменяет указатель head и возвращает старый. Несколько производителей могут конкурировать здесь, и каждый выигрывает ровно один слот — порядок определяется последовательностью exchange. Затем prev->next.store(release) связывает цепочку с точки зрения потребителя.

Потребитель обходит tail_->next для извлечения — видит узлы в LIFO-порядке с точки зрения exchange, который становится FIFO при обходе от tail_ вперёд.

Выделение памяти

MPSC на связанном списке выделяет узел на каждый push — вызов new на сообщение. Это может быть дорого. Для высокопроизводительных систем используйте пул узлов:

1// Предварительно выделить фиксированный пул, lock-free захват/освобождение узлов
2// Это выходит за рамки — тема для статьи про аллокаторы

Для низкопроизводительного логирования или диспетчеризации событий стоимость выделения несущественна.

SPSC vs MPSC — когда использовать

Сценарий Тип очереди
Поток-производитель → поток-потребитель (этап конвейера) SPSC
N рабочих потоков → поток логирования/I/O MPSC
Аудио callback → поток обработки SPSC
Демультиплексирование сетевых пакетов → один декодер SPSC (на поток) или MPSC
Обработчик прерывания → главная задача (встраиваемый, без RTOS) SPSC
Задачи FreeRTOS → задача логгера MPSC или xQueueSend

Правило: если можно гарантировать ровно одного записывателя, используйте SPSC — он быстрее и проще. Если записыватели динамические или нельзя обеспечить их количество, используйте MPSC.

Никогда не используйте SPSC-очередь с несколькими производителями. Гонка на tail_ тихо испортит индекс. Ошибка воспроизведётся раз на 10 миллионов операций, при специфических условиях кэша, и только в релизных сборках.

Бенчмарк

Приблизительная пропускная способность на современном x86 (Ryzen 5800X, один сокет):

Тип очереди Пропускная способность Задержка (пустая → pop)
std::mutex + std::queue ~80 М оп/с ~200 нс
Кольцевой буфер SPSC ~600 М оп/с ~10 нс
Связанный список MPSC ~150 М оп/с ~30 нс
std::atomic спинлок-очередь ~200 М оп/с ~15 нс (нечестно)

Преимущество SPSC — от отсутствия CAS, отсутствия конкуренции за любую кэш-линию между потоками (при правильном выравнивании) и кэш-дружественного паттерна доступа кольцевого буфера.

На встраиваемых платформах

На Cortex-M (ARM) модель памяти слабее, чем на x86. На одноядерных МК (большинство встраиваемых платформ) для SPSC не нужны атомарные — достаточно volatile индекса и барьера вокруг копирования данных.

На многоядерных Cortex-A нужны те же порядки, что на x86, но набор инструкций делает их явными (ldar/stlr для acquire/release).

Для bare-metal SPSC между ISR и главным циклом на одноядерном Cortex-M:

1// ISR пишет в tail, главный цикл читает tail
2// Нужно только предотвратить переупорядочивание компилятором — __DMB() или atomic_signal_fence
3void ISR_handler() {
4    buffer[tail_] = new_sample;
5    std::atomic_signal_fence(std::memory_order_release);  // только барьер компилятора
6    tail_ = (tail_ + 1) & MASK;
7}

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

Что может пойти не так

Проблема ABA (MPSC): при повторном использовании узлов и гонке производителя и потребителя на одном адресе CAS может успешно завершиться на повторно используемом узле. Дизайн на связанном списке выше не имеет этой проблемы, поскольку сторожевой узел не используется повторно.

Освобождение памяти: потребитель удаляет старый сторожевой в pop(). Если производитель удерживает указатель на узел, который потребитель только что удалил — теоретически невозможно в MPSC, поскольку exchange производителя завершается до продвижения потребителя — но сложно, если расширять дизайн.

Ёмкость и степень двойки: кольцевой SPSC использует & (Capacity - 1) вместо % Capacity для остатка — требует ёмкости как степени двойки, но избегает деления при каждом push/pop.

Итоги

  • SPSC: кольцевой буфер, два атомарных индекса, эксклюзивное владение с каждой стороны, упорядочивание acquire/release. ~600 М оп/с.
  • MPSC: связанный список, атомарный exchange на head, tail только для потребителя. ~150 М оп/с. Нет ограничения на количество производителей.
  • Упорядочивание памяти не опционально — ошибитесь и очередь будет работать корректно 99,9999% времени, затем тихо испортит данные.
  • Всегда выравнивайте состояние производителя и потребителя по отдельным кэш-линиям.

Что дальше