Вытеснение потоков, это «сборка мусора» для упорядочивания памяти (2019)

Пост 2019 года, вновь всплывший в обсуждении на Hacker News, переворачивает привычный взгляд на вытеснение потока планировщиком ОС (preemption). Обычно оно считается врагом неблокирующего (лок-фри) программирования в пользовательском пространстве: поток может быть прерван в середине операции, и это усложняет гарантии корректности. Автор утверждает обратное, раз вытеснение всё равно происходит и мы уже «платим» за него, его стоит воспринимать как невозвратные издержки, вроде сборки мусора, и извлекать из него пользу.

Механизм строится на свойстве x86: возврат из обработчика прерывания полностью сериализует выполнение, любая инструкция пользовательского кода либо целиком завершилась до прерывания, либо будет выполнена заново уже после возврата в пользовательское пространство. Это можно использовать, чтобы гарантировать порядок обращений к памяти без явных барьеров (fence-инструкций). Техника дополняет другой приём автора, Bounded TSO, который меряет аппаратный лимит одновременно «в полёте» находящихся инструкций записи, чтобы гарантировать progress без барьеров и почти без накладных расходов, но плохо переводит число инструкций в реальное время. Отслеживание прерываний, наоборот, позволяет понять, когда прошло достаточно реального времени, чтобы более ранние записи точно «осели», ценой более консервативной (то есть более длинной) задержки.

Автор пришёл к этой идее, работая над двумя лок-фри примитивами синхронизации: event count (счётчик событий/версий) и асимметричные флаги-переключатели, применяемые в hazard pointers и epoch-based reclamation (техниках безопасного отложенного освобождения памяти в лок-фри структурах). Разбирается классическая проблема пропущенного пробуждения (lost wake-up) у переменных условия без корректной защиты мьютексом: из шести возможных переплетений действий «будильника» (writer) и «ожидающего» (waiter) один сценарий, WSSW, приводит к тому, что ожидающий поток пропускает пробуждение и рискует уснуть навсегда. Event count решает это не блокировкой, а обнаружением: ожидающий может понять, что версия счётчика уже изменилась, и не заснуть впустую, сохраняя лок-фри (и даже wait-free) свойства кода. Пример применения, кольцевой буфер: вместо активного ожидания (спина) на указателе записи потребитель блокируется на event count, кодирующем этот указатель, и не жжёт процессор впустую.

Для эффективной реализации event count поверх ОС-примитивов (футексов на Linux, аналогичный шим есть в OpenBSD) используется управляющее слово, где часть бит хранит счётчик версии, а один бит, флаг «есть ожидающие потоки» (sleepers flag). Инкремент версии, атомарная операция fetch-and-add; если флаг был установлен, поток дополнительно атомарно сбрасывает его и делает системный вызов на пробуждение спящих. Такая схема используется, в частности, в библиотеке Folly (Facebook) и, по словам автора, даёт неплохую производительность при нескольких конкурентных писателях.

Далее автор разбирает частный, но важный случай, кольцевой буфер с ровно одним производителем (single-producer). В этом случае увеличение указателя записи не обязано быть атомарным: под моделью памяти x86-TSO достаточно записи с release-семантикой, потому что видимость увеличения указателя после записи данных и так гарантирована. Заменять такой указатель полноценным атомарным event count в этом случае избыточно. Автор предлагает делать сам инкремент немного «нечестной» неатомарной инструкцией (inc mem или xadd mem, reg), опираясь на гарантии x86-TSO о буфере записи и атомарных LOCK-инструкциях, чтобы не терять обновления флага ожидающих и версии счётчика даже без полной атомарности инкремента. Изложение этой части обрывается на разборе гарантий планировщика и миграции потоков, предоставленный текст источника заканчивается на середине рассуждения.

Ключевые факты

Тезис: preemption (вытеснение потока планировщиком) стоит использовать как бесплатный источник барьеров памяти в лок-фри коде, а не только терпеть как помеху, по аналогии со сборкой мусора, за которую всё равно уже «заплачено»
Механизм: на x86 возврат из обработчика прерывания полностью сериализует выполнение, инструкция либо целиком выполнена до прерывания, либо переисполняется после возврата, и это гарантирует упорядочивание доступов к памяти без явных барьеров
Техника дополняет приём автора Bounded TSO: та считает инструкции записи «в полёте», а привязка к прерываниям определяет упорядочивание по реальному времени, ценой более консервативной задержки
Разобраны event count поверх футексов (как в Facebook Folly) с флагом «есть ожидающие» и классическая проблема пропущенного пробуждения (lost wake-up), которую event count решает обнаружением, а не блокировкой
Для кольцевого буфера с одним производителем предложена оптимизация: неатомарный инкремент (inc/xadd) вместо атомарного, за счёт гарантий модели памяти x86-TSO

Почему это важно

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

Кому это важно

Разработчикам системного и высокопроизводительного ПО, авторам лок-фри структур данных, ядер ОС, рантаймов и библиотек конкурентности. В тексте прямо упоминаются реальные проекты: Concurrency Kit (куда автор закоммитил реализацию event count) и Facebook Folly, использующая похожую схему на футексах; также затронуты особенности футекс-примитивов в Linux и OpenBSD.

Как это применить

Показан рабочий код (в виде псевдокода) для event count поверх футекса: управляющее слово хранит счётчик версии плюс бит «есть ожидающие», инкремент делается атомарным fetch-and-add, ожидание, через compare-and-swap флага и условный системный вызов сна. Отдельно предложена оптимизация для кольцевого буфера с одним производителем: заменить атомарный инкремент на неатомарную инструкцию (inc mem или xadd mem, reg), полагаясь на гарантии модели памяти x86-TSO о буфере записи, чтобы не терять обновления версии и флага ожидающих.

Можно ли доверять

Это авторский технический разбор с конкретным псевдокодом, ссылками на реальные открытые проекты (Concurrency Kit, собственный проект автора barrierd) и внешний обзорный материал в ACM Queue. Пост впервые опубликован в 2019 году и сейчас переоткрыт на Hacker News, но обсуждение пока скромное (36 баллов, 6 комментариев на момент сбора), независимого разбора или опровержений в текущей ветке не видно. Рассуждения опираются на низкоуровневые детали формальной модели памяти x86-TSO и требуют экспертной проверки, а не рассчитаны на восприятие без критического чтения.

Риски и подводные камни

Техника явно завязана на x86: сериализующее поведение при возврате из прерывания там гарантировано, а для других архитектур автор лишь предполагает («и, без сомнения, на других платформах»), не приводя доказательств переносимости. По сравнению с Bounded TSO задержки более консервативные, то есть потенциально хуже в худшем случае. Ручные рассуждения о модели памяти хрупки и требуют экспертного уровня: сам автор оговаривает краевой случай ложного срабатывания при переполнении (wrap-around) счётчика версии, ошибка в подобной ручной оптимизации означает новую гонку в коде, который по замыслу должен быть без блокировок.

«Я теперь считаю, что вытеснение потока стоит рассматривать как невозвратные издержки, вроде сборки мусора: мы и так уже платим за него, так почему бы не извлечь из этого пользу.»

— автор блога pvk.ca