Lock-free по нарастающей

Аннотация

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

В качестве панацеи предлагают lock-free структуры, но и тут полно ловушек — банальный регулярный вызов ядра SetEvent способен сжечь весь выигрыш от lock-free. Сами алгоритмы lock-free порой тяжеловесны, не всегда предлагают удачный trade-off и даже не всегда уместны. Но что ещё хуже: будучи применёнными без должной тщательности, они могут не только не дать выигрыша, но даже навредить.

В этой статье мы разберём устройство нескольких базовых объектов библиотеки wxl и познакомимся с концепцией «алгоритм дешевеет под нагрузкой». Мы пройдём путь от трёх базовых инструкций процессора до готового канала, разберём, как продление release-последовательности спасает от ABA, как ленивые триггеры arm/disarm позволяют будить поток только тогда, когда он реально спит, и как заставить данные летать между ядрами без обращений к операционной системе.

Lock-free структуры wxl

Спойлер: в рамках одной статьи рассказать обо всех lock-free структурах и трюках невозможно, эта статья будет первой из цикла публикаций по lock-free тематике. В рамках данного материала мы познакомимся с двумя базовыми примитивами. Читать лучше подряд — каждый следующий раздел отвечает на вопрос, поднятый в предыдущем.

С чего всё начинается

Представьте два потока. Один производит данные, другой их обрабатывает. Между ними нужна быстрая и надёжная очередь.

Учебный ответ — мьютекс в связке с условной переменной (Condition Variable). Мьютекс защищает целостность очереди, а условная переменная отправляет поток-потребитель в сон, если данных нет, чтобы не выжигать процессорное время на бессмысленные проверки. Если два потока сталкиваются на одной очереди, спин-лок в клиентских ОС Windows позволяет ожидающему потоку не уходить в спячку сразу. Эта схема рабочая, пока критическая секция остаётся «короткой». На ней работает более 90% прикладного софта.

Но у блокировок есть неприятное свойство, которое портит идиллию: если текущий владелец мьютекса не успел освободить его до того, как планировщик Windows вытеснит поток из ядра, то остальные потоки-претенденты тоже вынужденно засыпают (блокируются). В этот момент вся параллельность сводится на нет.

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

Причём увеличение приоритета ожидающим потокам не помогает, если ресурс захвачен потоком с низким приоритетом. Эту непростую ситуацию планировщик Windows умеет обнаруживать и разрешать через механизм инверсии приоритетов (Priority Inversion), временно повышая приоритет заблокировавшему ресурс потоку. Однако этот механизм включается лишь тогда, когда блокировка на ресурсе стала совсем уж неприлично долгой или к нему выстроилась внушительная очередь. То есть средство спасения активируется тогда, когда катастрофа уже де-факто происходит.

Разумеется, хотелось бы принципиально другого поведения: чтобы поток, положивший элемент в очередь, физически не мог заблокировать того, кто пытается положить следующий или прочитать имеющийся. Именно это и обещают lock-free структуры данных. Мы же будем исследовать цену этих обещаний, вооружившись здраво-циничным подходом «ничто не даётся даром».

Что даёт процессор для lock-free

Немного. Обычно всего три вида атомарных операций над ячейкой памяти — но их вполне хватает:

• Безусловный обмен (Swap, Exchange). Положить в ячейку новое (известное) значение A и забрать старое (неизвестное) X. Исполняется одной неделимой операцией.

• Условный обмен (CAS, Compare And Swap / Compare And Exchange). Положить в ячейку новое значение A и забрать старое X, но только если в момент исполнения операции выполняется условие: неизвестное X равно ожидаемому B. Аналогично — одной неделимой операцией. Это самая интересная из трёх операций, потому что на ней строится большинство нетривиальной lock-free логики.

• Атомарная арифметика и логика. Инкременты, декременты и операции вида fetch_add (прибавить значение к ячейке памяти и вернуть то, что там было до сложения). Всё выполняется так, чтобы между фазами «прочитать» и «записать» ни у кого не было физической возможности перехватить или изменить модифицируемое значение целевой ячейки памяти.

Традиционно арифметические и логические атомарные операции присутствовали не во всех архитектурах (они почти всегда были в CISC и почти никогда в RISC), но их можно выразить через CAS примерно таким образом:

int fetch_add(int volatile& target, int value) {    int old_value = target;         while (true) {         // CAS(ячейка, что записать, что должно быть в ячейке на момент операции)        const int actual_value = CAS(target, old_value + value, old_value);                // Если актуальное значение совпало с ожидаемым, обмен удался        if (actual_value == old_value)            return old_value;            // Если не совпало, значит, кто-то нас опередил.        // Пробуем ещё раз...        old_value = actual_value;    }}

Плюс две вспомогательные команды, которые не меняют данные в памяти напрямую, но управляют поведением железа:

• Барьер (std::atomic_thread_fence). Строгий запрет переупорядочивать инструкции чтения и записи. Процессор и компилятор обожают менять порядок независимых операций ради оптимизации, и в обычном коде это никого не волнует. В многопоточном коде — волнует, и ещё как. Без барьера некоторые алгоритмы, зависящие от упорядоченных причинно-следственных связей, банально не работают. Существуют менее строгие барьеры, например, обеспечивающие одностороннюю зависимость. Весь этот «градиент гарантий» принято называть «моделью памяти» и об этом будет подробней в одной из следующих статей.

• Пауза (core::cpu_pause()). Сигнал процессору: «я сейчас кручусь в холостом цикле ожидания, займи мои исполнительные блоки чем-нибудь полезным». На архитектурах с поддержкой SMT (Hyper-Threading) эта команда временно отдаёт вычислительные ресурсы ядра соседнему аппаратному потоку.

Что значит «lock-free»

Рассмотрим типичный отрывок lock-free кода — это цикл до успешного выполнения CAS:

Node* top = top_.load(std::memory_order_relaxed);do {    element->next_ = top;                                   // подготовились} while (!top_.compare_exchange_weak(top, element, ...));   // попробовали

Такая конструкция на первый взгляд может вызвать беспокойство: а что, если обмен не произойдёт никогда? Формально в рамках одного потока такое возможно. Но присмотритесь, что на самом деле означает неудачный CAS? Сравнение не прошло только по одной причине: кто-то другой успел изменить top_ мгновением раньше.

В этом и заключается гарантия lock-free: система в целом движется всегда. Отдельному потоку в конкретный момент может не повезти, но затормозить остальных он физически не способен — в отличие от зависшего владельца мьютекса, которого ОС не вовремя сняла с процессора. Лишний круг в цикле CAS — не дефект алгоритма, а плата за то, что соседнему потоку прямо сейчас повезло больше.

При отсутствии конкуренции этот цикл выполняется ровно один раз. И отсюда же понятно, почему вероятность столкновения и повторного захода в цикл невероятно мала — из-за крайне узкого временного окна потенциального столкновения «шириной» в длительность одной interlocked-инструкции.

Именно поэтому lock-free структуры ведут себя так эффективно в реальных условиях: фактическая конкуренция за одну и ту же ячейку памяти — это невероятно редкое событие в хорошо спроектированных системах.

Именно поэтому в wxl нет специальных средств обыгрывания конкуренции на атомарных операциях. В классической теории конкурентных lock-free алгоритмов предлагается обыгрывание через экспоненциальное увеличение времени между попытками при повторяющемся невезении на CAS (этот приём называется exponential back-off), но в наших структурах никакого дополнительного обыгрывания невезения нет — тем более что любое обыгрывание небесплатно.

Вместо обобщённого обыгрывания на низком уровне можно использовать эти знания на более высоких слоях. Это знание выражается не через ухудшение метрики зацепления статического API типов, а через учёт особенностей динамики lock-free алгоритмов низкого уровня.

Как это работает в целом? Неудачная попытка на нашей стороне означает, что выигравший гонку конкурентный поток не будет прямо сейчас повторно долбить в ту же ячейку. Это позволяет ограничиться самым простым (и полезным для системы в целом) ожиданием на единичном cpu_pause(), а иногда и вовсе обходиться без таких ожиданий за ненадобностью.

Общая же рекомендация простая — избегать постоянного давления на одну ячейку, чтобы не генерировать паразитный трафик поддержания когерентности между кэшами ядер. Стараться делать максимум полезной работы с локальными данными между операциями обращения к разделяемой памяти. Большинство необходимых прикладных операций дано «из коробки» — эти рекомендации уже зашиты в ДНК кода wxl. Но поскольку все структуры открыты для построения кастомных пайплайнов, для вашего собственного кода озвученные рекомендации становятся не просто «пожеланиями», а строгими инженерными требованиями.

atomic_trigger: кто из нас первый?

Простейшая, но крайне полезная lock-free структура. Иногда между потоками нужно передать не массив данных, а одно-единственное событие или скоординировать некоторое решение: например, «пора останавливаться». Причём сделать это так, чтобы связанные с решением действия выполнились ровно один раз — сколько бы потоков одновременно ни пытались взвести или сбросить этот триггер.

core::atomic_trigger — это легковесный флаг, решающий задачи такого рода. Он заменяет классическую связку из булевой переменной и мьютекса, позволяя конкурирующим потокам не блокировать друг друга.

Основное API:

bool set();                 // true, если флаг взвёл именно яbool reset();               // true, если флаг сбросил именно я[[nodiscard]] bool read();  // прочитать и сбросить

И жёсткие гарантии — целевое действие будет совершено строго однократно и именно тем потоком, который выиграл гонку на триггере:

if (stop_trigger_.set())     task_queue_.signal();   // выполнится ровно один раз

После вызова метода set() (или зеркального reset()) вы достоверно знаете не просто текущий статус флага, а сам факт того, стали ли именно вы автором этого изменения. Для проигравших потоков ответ false означает: «кто-то уже совершил это действие до нас либо прямо сейчас меняет состояние флага».

Небольшой нюанс: метод read() делает ровно то же самое, что и reset(), но назван исходя из своей семантики и снабжён атрибутом [[nodiscard]]. Смысл вызова read() — в обязательном получении возвращаемого значения, тогда как смысл reset() — в самом факте сброса флага. Разница между ними продиктована принципом «комментировать следует только тот код, который при чтении вызывает вопросы». Различающиеся идентификаторы и добавочное ограничение на возвращаемый по read() результат при одинаковой механике служат сугубо для удобства выражения прикладной логики над триггером.

drain_stack: стек, у которого забирают всё сразу

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

Благодаря интрузивности стек не требует алокаций в процессе работы:

void push(Node* element, std::memory_order order = std::memory_order_release) noexcept {    Node* top = top_.load(std::memory_order_relaxed);    do {        element->next_ = top;                                    // (1)    } while (!top_.compare_exchange_weak(top, element, order,    // (2)                                         std::memory_order_relaxed));}

Без конкуренции всё это стоит ровно одну атомарную операцию на элемент. При этом вызывать push можно параллельно хоть из сотни потоков.

А теперь — главный архитектурный ход. Потребитель не снимает элементы по одному. Он забирает весь стек целиком, одной атомарной командой:

Node* pop_all() noexcept {    if (top_.load(std::memory_order_relaxed) == nullptr) [[likely]]         return nullptr;            return top_.exchange(nullptr, std::memory_order_acquire);}

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

Почему эта схема обходит проблему ABA

ABA — классический шоу-стоппер CAS-алгоритмов над данными. Классический стек Трайбера, забирающий элементы по одному, болеет этой проблемой с рождения и требует дополнительных действий для обеспечения корректности работы. С решением этой проблемы полезно познакомиться именно на примере drain_stack, поскольку здесь ABA физически не способна нам навредить.

Посмотрите на точки (1) и (2) в коде push. Между этими инструкциями другой поток может забрать элемент, на который сейчас смотрит наш next_, а затем вернуть этот же элемент обратно на вершину до того, как мы доберёмся до строки (2). Это и есть классический признак ABA-проблемы. Целевой узел мог быть даже освобождён в общую кучу, затем повторно выделен и снова помещён в стек.

Многие lock-free алгоритмы, которые полагаются на принцип «тот же самый адрес означает тот же самый объект», ломаются прямо здесь, перезаписывая свои ячейки устаревшими невалидными данными.

А что у нас? Наш CAS увидит на вершине знакомый адрес и пройдёт успешно, хотя стек между чтением и модификацией изменился. Однако, что бы ни случилось между шагами (1) и (2), после успешного CAS состояние стека гарантированно остаётся корректным, и ни один узел не теряется. Мы всего лишь дописываем свой новый элемент в голову той цепочки, которую увидели по факту.

Итог: стратегия изъятия всей цепочки данных разом вместо поштучного запроса элементов не устраняет сам сценарий ABA, но делает алгоритм иммунным к этой проблеме — состояние стека остаётся достоверно валидным при любой комбинаторике возникающих ABA-ситуаций.

Порядок памяти

Процедура push публикует данные через release, потребитель в pop_all забирает их через acquire — и этой пары гарантированно хватает для синхронизации всей цепочки элементов, а не только самой вершины. Причина здесь по-своему красивая: каждый следующий push — это тоже атомарная операция класса read-modify-write над вершиной. Согласно стандарту C++, такой шаг продлевает общую release-последовательность (release sequence), начатую самым первым элементом. В итоге одного-единственного acquire на стороне потребителя достаточно, чтобы надёжно синхронизироваться со всеми писателями сразу.

Параметр order существует здесь ради специфического сценария, когда компонент mpsc_channel читает другую атомарную переменную сразу после вызова push, и ему критически важно, чтобы эти два обращения были упорядочены между собой. Классический release обеспечить упорядочивание в духе «сначала моя запись, затем чужое чтение» (Store-Load) не способен. В одной из следующих статей будет подробный разбор Store-Load гонок. Мы увидим, как достигаемые минимальными затратами межпоточные гарантии позволяют всё так же красиво — простыми операциями над всего одной атомарной переменной — решать нетривиальные прикладные задачи, которые обычно требуют сложных структур данных и непростых алгоритмов поверх них.

mpsc_queue: очередь, которая дешевеет под нагрузкой

У базового lock-free стека есть два очевидных неудобства: элементы из него выходят пачкой и в строго обратном порядке (LIFO). Реализацияmpsc_queue убирает оба недостатка — и попутно приобретает уникальное свойство, ради которого всё и замышлялось.

Раз нижележащий контейнер умеет выдавать данные только по принципу «забрать всё разом», то очередь хранит локальный указатель на текущую обработанную порцию и монопольно раздаёт элементы из неё поштучно:

Node* pop_one() noexcept {    if (Node* node = reader_node_) {          // дёшево: ни одной атомарной операции        reader_node_ = node->next_;        return node;    }    if (Node* element = stack_.pop_all()) {   // одна атомарная операция на всю порцию        if constexpr (order == drain_order::fifo)            element = details::reverse_linked_list(element);        reader_node_ = element->next_;        return element;    }    return nullptr;}

Вся порция разворачивается ровно один раз прямо в момент захвата (если выбран режим FIFO, хотя для многих задач сохранения порядка и не требуется — именно поэтому дисциплина обработки зашита в параметр шаблона, а не в аргумент конструктора). После этого каждый последующий вызов pop_one сводится к дешёвому чтению неатомарного поля и присваиванию. Никаких атомарных операций, никакой синхронизации.

А теперь считаем накладные расходы:

• Запись в очередь стоит одну атомарную инструкцию на элемент.

• Чтение стоит одну атомарную инструкцию на целую пачку.

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

Расплата за такую скорость — жёсткий контракт MPSC (Multi-Producer Single-Consumer): отправлять данные в очередь можно из какого угодно количества потоков, но читать их следует строго из одного потока. Поле reader_node_ — это самое обычное неатомарное поле, принадлежащее читателю, и городить вокруг него потоковую синхронизацию значило бы потерять весь выигрыш. По этой же причине метод empty() возвращает валидный статус только при вызове на потоке-потребителе. Это фундаментальное свойство всех MPSC-объектов в экосистеме wxl, и оно зафиксировано в док-комментариях к коду.

False sharing

Отдельного упоминания стоит внутренняя топология класса. Взгляните на поля mpsc_queue:

alignas(std::hardware_destructive_interference_size) drain_stack<Node> stack_;alignas(std::hardware_destructive_interference_size) size_t pops_since_claim_;Node* reader_node_;

При доступе к соседним ячейкам памяти из разных потоков в полный рост встаёт проблема false sharing (ложного разделения).

Писатели постоянно бьют в атомарную вершину stack_, переводя кэш-линию в состояние Modified, в то время как единственный читатель монопольно крутит счётчик pops_since_claim_ и неатомарный reader_node_. Если бы эти переменные оказались в одной 64-байтной кэш-линии процессора, потоки непрерывно инвалидировали бы кэши друг другу, перегружая аппаратные механизмы обеспечения когерентности приватной памяти ядер процессора.

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

mpsc_channel: ждать, не заходя в ядро

Осталось решить последнюю критическую задачу: что делать потребителю, когда внутренняя очередь пуста? Ответ очевиден — ждать. Но именно на этом шаге традиционные lock-free подходы сталкиваются с суровой рантайм-реальностью.

При проведении измерений выяснилось, что вызовы функций ОС, работающих с тяжёлыми объектами ядра (семафорами, событиями), стоят непозволительно дорого. В сценариях, максимально близких к боевым, минимизация количества системных вызовов подняла общую пропускную способность каналов передачи данных от 7 до 30+ раз. Причём этот эффект проявляется тем ярче, чем мельче идут порции данных.

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

Компонент mpsc_channel спроектирован поверх mpsc_queue и решает именно эту проблему. Ключевая идея: производитель трогает системный примитив синхронизации только тогда, когда потребитель действительно заснул. Узнаёт он об этом по специальному атомарному триггеру, который читатель «взводит» перед тем, как уйти в сон — отсюда и названия методов механизма: arm() и disarm().

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

Этот протокол взаимодействия выглядит обманчиво просто, но в нём скрыто классическое «тонкое место» — race condition окно, когда писатель уже проверил статус триггера, а читатель физически ещё не успел уснуть. Полный разбор этого граничного сценария с математическим доказательством того, что пробуждение потока никогда не потеряется, а также пояснения к детальной расстановке барьеров памяти вынесены в отдельную обещанную статью.

При интеграции межпоточного канала в ваши проекты стоит обратить внимание на следующее:

• Примитив ожидания вынесен в параметр шаблона. Внешнему коду часто требуется ожидать данные не на одном изолированном канале, а в рамках групповой операции — например, через WaitForMultipleObjects либо IOCP-хэндл в Windows или select/poll-подобные механизмы в других системах. Для поддержки таких сценариев класс предоставляет методы get_wait_object() и wait_handle(). Если внешний код самостоятельно обслуживает уход потока в сон и пробуждение, то он должен сам же вести протокол синхронизации arm() / disarm().

• Метод receive() работает по контракту, аналогичному Condition Variable. Он возвращает bool, при этом значение false не является гарантированным свидетельством таймаута: здесь легитимны ложные пробуждения (spurious wakeups). Вызывающий поток обязан крутить проверку в цикле по собственному предикату ровно так же, как это делается при работе с условными переменными:

while (!channel.receive(element)) {    if (stop_requested) return;}

Отсюда же автоматически вытекает ответ на частый вопрос: «Как принудительно остановить поток-читатель?». Сам канал этого делать не умеет и по правилам разделения ответственности уметь не должен. Метод signal(force = true) всего лишь принудительно будит спящий поток один раз, а финальное решение о выходе из цикла обработки принимает внешний флаг остановки, который контролируется владельцем бизнес-логики.

Исходники:

• drain_stack.ixx

• mpsc_queue.ixx

• mpsc_channel.ixx

• atomic_trigger.ixx.

Впереди по этой теме:

• Протокол arm/disarm. Схема Деккера и немного дискретной математики, приложенной к моделям памяти.

• Турникет. Как надёжно закрыться, когда все вышли.

• Lock-free Future с монадическим интерфейсом. Почему они ходят задом наперёд.

• «Дышащая» SPSC-очередь. Решение, которое работает примерно вдвое эффективнее схемы, реализованной в LMAX Disruptor.

• task_tree. Как счётчик с флагом в одной атомарной переменной делает динамику на порядки мощнее статики.