Многопоточность на C++ через практику и замеры

— подумайте, сколько condition variable вам нужно и почему.

Проверка: тесты на порядок элементов (FIFO для одного производителя), на блокировку при заполнении, на таймаут try_pop_for, на закрытие при ждущих производителях и потребителях; стресс-тест 4 на 4 потока, ёмкость 8, каждый элемент получен ровно один раз; всё под TSan 10 раз подряд.

Задача 3.3 (средняя). Пинг-понг и хоровод

Два потока по очереди печатают ping и pong, N раз каждый, строго чередуясь: ping, pong, ping, pong…

Затем обобщите: K потоков с номерами 0..K−1 печатают свои номера строго по кругу (0, 1, 2, …, K−1, 0, 1, …), всего N кругов.

Требования: никакого активного ожидания (sleep в цикле или пустой цикл не годятся), никаких глобальных переменных.

Проверка: вывод собирается в вектор и сравнивается в тесте с ожидаемой последовательностью; при K = 8, N = 10 000 загрузка CPU во время работы низкая (потоки спят, а не крутятся); TSan чист. Подумайте, что произойдёт с производительностью при notify_all и при notify_one, и объясните, почему в одном из этих вариантов программа может зависнуть.

Решения и разбор ваших неизбежных ошибок — в главе «Ответы к задачам» в конце книги.

Глава 4. Железо и ОС: что на самом деле происходит под std::mutex

«Гонок нет, локов нет, а работает в шесть раз медленнее». Добро пожаловать в мир кеш-линий.

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

Эта глава — экскурсия на один уровень вниз: процессор, кеши, планировщик, сигналы. Не ради эрудиции, а потому что без этой модели в голове невозможно ни объяснить модель памяти C++ (глава 5), ни понять результаты бенчмарков, ни ответить на senior-собеседовании на вопрос «почему ваш шардированный кеш не масштабируется дальше 8 ядер».

К концу главы вы:

— поймёте, как устроены кеши и почему процессор работает с кеш-линиями, а не байтами;

— научитесь находить и устранять false sharing;

— узнаете, что такое store buffer и почему процессор «переставляет» операции с памятью;

— поймёте, как устроен мьютекс в Linux (futex) и сколько он стоит;

— освоите законы Амдала и Густафсона — главные «отрезвители» в разговорах о масштабировании;

— научитесь привязывать потоки к ядрам и узнаете, когда это вредно;

— поймёте, чем опасен fork() в многопоточной программе;

— научитесь правильно обрабатывать сигналы в многопоточном процессе;

— разобьёте хранилище shardkv на шарды и научите сервер останавливаться по SIGTERM.

4.1. Кеши и кеш-линии

Обращение к оперативной памяти занимает порядка 100 нс. За это время современное ядро могло бы выполнить сотни инструкций. Поэтому между ядром и памятью стоит иерархия кешей:

— L1 — свой у каждого ядра, десятки килобайт, доступ за несколько тактов;

— L2 — обычно свой у каждого ядра, от сотен килобайт до пары мегабайт, около десятка тактов;

— L3 — общий для всех ядер процессора, десятки мегабайт, несколько десятков тактов;

— память — гигабайты, сотни тактов.

Главное, что нужно запомнить: кеш работает блоками фиксированного размера — кеш-линиями. На x86-64 и большинстве ARM это 64 байта (на Apple M-серии — 128). Когда вы читаете один байт, процессор загружает всю линию, в которой он лежит. Когда вы пишете один байт, процессор должен получить всю линию в своё эксклюзивное владение.

Это легко увидеть:

Листинг 4.1 — процессор читает память кеш-линиями, а не байтами (ex02_cache_stride.cpp)

На моей машине:

Листинг 4.2 — стоимость обращений с разным шагом

От шага 1 до шага 64 обращений стало в 64 раза меньше, а время упало только в 4 раза. Потому что мы платим не за обращения, а за загрузку кеш-линий, и их приходится загружать те же самые. (После шага 64 время продолжает падать, но не пропорционально: в игру вступает аппаратный префетчер, который угадывает следующие линии заранее. Железо сложнее любой модели, поэтому мы и меряем.)

Отсюда первое правило производительности: данные, которые используются вместе, должны лежать рядом (массив структур, std::vector вместо std::list). А в многопоточном коде появляется второе правило, и оно хитрее.

4.2. Когерентность кешей и false sharing

Если у каждого ядра свой кеш, что будет, когда два ядра работают с одной и той же линией? Процессор гарантирует когерентность: все ядра видят согласованное содержимое каждой линии. На x86 для этого используется протокол семейства MESI. Каждая линия в каждом кеше находится в одном из состояний:

— Modified — линия изменена этим ядром и есть только у него;

— Exclusive — линия есть только у этого ядра, не изменена;

— Shared — линия есть у нескольких ядер, только для чтения;

— Invalid — копия недействительна.

Чтобы записать в линию, ядро должно перевести её в Modified, а для этого — инвалидировать копии во всех остальных кешах. Если два ядра поочерёдно пишут в одну линию, она постоянно «перепрыгивает» между ними: каждая запись требует обмена сообщениями между ядрами. Это называют ping-pong кеш-линии.

Самое коварное: ядрам не обязательно писать в одну и ту же переменную. Достаточно писать в разные переменные, которые лежат в одной линии. Это и есть false sharing (ложное разделение):

Листинг 4.3 — у каждого потока свой счётчик (ex01_false_sharing.cpp)

Результат на моей машине:

Листинг 4.4 — false sharing: плотные и выровненные счётчики

Два потока, у каждого свой счётчик, никаких общих данных с точки зрения программы, — и разница в 3,4–6 раз. Лечение — разложить данные, которые пишут разные потоки, по разным кеш-линиям: alignas(64) или явный padding.

hardware_destructive_interference_size

В C++17 появилась константа std::hardware_destructive_interference_size из — минимальное расстояние между объектами, чтобы избежать false sharing. Две оговорки:

— не все стандартные библиотеки её предоставляют (проверяйте макрос __cpp_lib_hardware_interference_size);

— GCC предупреждает при её использовании (-Winterference-size): значение зависит от флагов -mtune/-mcpu, и если оно попадёт в ABI (например, в размер структуры в заголовке библиотеки), разные единицы трансляции могут разойтись.

Практичное решение — своя константа с запасным значением:

Листинг 4.5 — размер кеш-линии для выравнивания, с запасным вариантом (cacheline.hpp)

Где искать false sharing

— массивы структур «по одной на поток»: счётчики, статистика, локальные буферы;

— мьютекс и защищаемые им данные рядом с мьютексом другого объекта (массив шардов, у каждого свой мьютекс — наш случай в шаге 4);

— флаг остановки рядом с часто изменяемыми полями;

— атомарный счётчик ссылок рядом с данными, которые читают все (это одна из причин, почему std::shared_ptr под нагрузкой бывает медленным).

И не нужно выравнивать всё подряд: каждая структура размером 64 байта вместо 8 — это в 8 раз больше памяти и меньше данных в кеше. Выравнивают только то, что разные потоки часто пишут.

4.3. Store buffer: почему процессор «переставляет» операции

Запись в память даже через кеш — дорогая операция: нужно получить линию в эксклюзивное владение. Чтобы не ждать, каждое ядро складывает записи в свой store buffer — маленькую очередь, — и продолжает выполнять следующие инструкции. Запись попадает в кеш (и становится видна другим ядрам) чуть позже.

Последствие: другое ядро может увидеть ваши операции не в том порядке, в котором они написаны в программе. Классический пример (store-load reordering):

Листинг 4.6 — переупорядочивание записи и чтения на двух ядрах

Интуиция говорит: хотя бы одно из r1, r2 будет равно 1. Но на реальном x86 возможен результат r1 == 0 и r2 == 0: обе записи ещё лежат в store buffer'ах, а чтения уже выполнились из кеша. Вы поймаете этот эффект своими руками в задаче 4.2.

Разные архитектуры разрешают разные перестановки. x86 довольно строгий: он переставляет только «запись, потом чтение другого адреса». ARM и POWER разрешают почти всё. Поэтому код, который «годами работал на x86», ломается при переезде на ARM-сервера или Apple Silicon.

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

4.4. Как устроен мьютекс в Linux: futex

Как можно сделать мьютекс, который почти ничего не стоит, когда свободен? В Linux ответ — futex (fast userspace mutex). Идея:

— состояние мьютекса — обычное целое число в памяти процесса (0 — свободен, 1 — захвачен, 2 — захвачен и есть ждущие);

— захват без конкуренции: одна атомарная операция compare-and-swap 0 → 1, полностью в пространстве пользователя. Никаких системных вызовов;

— захват при конкуренции: если CAS не удался, поток (обычно после короткого активного ожидания) вызывает системный вызов futex(FUTEX_WAIT), и ядро усыпляет его;

— освобождение: атомарная запись 0; если были ждущие — системный вызов futex(FUTEX_WAKE), чтобы разбудить одного.

Померим:

Листинг 4.7 — сколько стоит мьютекс без конкуренции и с ней (ex03_mutex_cost.cpp)

(Цифры с виртуальной машины; на голом железе захват без конкуренции обычно в разы быстрее.) Даже на этом простом примере видно: при конкуренции каждая операция дороже в 2–3 раза, а ведь критическая секция здесь — один инкремент. Когда секции длиннее, а потоки засыпают в ядре, разница достигает микросекунд: переключение контекста, холодные кеши после пробуждения.

Отсюда вывод для проектирования: проблема не в мьютексах, а в конкуренции за них. Сотня мьютексов, на которых никто не сталкивается, дешевле одного, на котором толкаются все. Это ровно та идея, на которой построен шаг 4 проекта.

4.5. Законы Амдала и Густафсона

Закон Амдала. Если доля работы p распараллеливается идеально, а доля (1 − p) выполняется последовательно, то максимальное ускорение на N ядрах:

S(N) = 1 / ((1 — p) + p / N)

Если 95% работы параллельны, то на бесконечном числе ядер ускорение не превысит 1 / 0,05 = 20. Если параллельно 90% — не больше 10. Последовательная часть программы (в том числе критические секции под глобальным мьютексом!) задаёт потолок, который не пробить никаким количеством ядер.

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

Закон Густафсона — оптимистичный взгляд с другой стороны: на практике с ростом числа ядер растёт и объём задачи (больше пользователей, больше данных), а последовательная часть часто остаётся прежней. Тогда ускорение на «большей задаче» почти линейно.

Оба закона верны, они отвечают на разные вопросы. Амдал: «насколько быстрее станет та же задача?» Густафсон: «насколько бо́льшую задачу я решу за то же время?» На собеседовании полезно знать оба и уметь сказать, какой из них применим в обсуждаемой ситуации.

4.6. NUMA

На серверах с несколькими процессорными сокетами память физически разделена: у каждого сокета своя «ближняя» память. Обращение к «дальней» памяти (подключённой к другому сокету) заметно дороже. Это называется NUMA (non-uniform memory access).

Что важно знать:

— Linux по умолчанию выделяет физическую память на том узле, где поток впервые к ней обратился (first touch). Если главный поток инициализировал огромный массив, вся память оказалась на его узле, и рабочие потоки на другом сокете будут постоянно ходить в дальнюю память;

— поток, который планировщик перенёс на другой сокет, теряет и кеши, и близость к своей памяти;

— false sharing между сокетами стоит ещё дороже, чем внутри одного процессора.

Инструменты: numactl для запуска с политикой размещения, lscpu и numactl --hardware для просмотра топологии. На ноутбуке и в большинстве облачных виртуалок NUMA-узел один (у меня тоже), и эти эффекты не видны. На двухсокетном сервере базы данных — ещё как видны.

4.7. Планировщик, приоритеты и привязка к ядрам

Стандартный C++ ничего не знает о приоритетах потоков и ядрах. Когда это нужно, используется native_handle() — нативный дескриптор потока (в Linux — pthread_t), с которым работают системные API:

Листинг 4.8 — привязка потока к ядру через native_handle() (ex04_affinity.cpp)

Когда привязка (affinity) полезна:

— задачи с жёсткими требованиями к задержкам: поток на изолированном ядре не вытесняется и не теряет кеши (подробнее о real-time — в главе 12);

— архитектура thread-per-core, где каждое ядро обслуживает свою часть данных (тоже глава 12);

— NUMA: держать поток рядом с его памятью.

Когда вредна — почти во всех остальных случаях. Планировщик Linux неплохо балансирует нагрузку сам. Привязанный поток не может уйти на свободное ядро, если его ядро занято. Привязка, которая дала +10% на бенчмарке, может дать −50% в продакшене, где рядом крутятся другие процессы.

Про приоритеты: обычные политики планирования Linux (SCHED_OTHER) почти не дают гарантий; real-time политики (SCHED_FIFO, SCHED_RR) дают, но требуют прав и аккуратности — поток с real-time приоритетом в бесконечном цикле может заморозить систему. Это тема главы 12.

4.8. fork() в многопоточном процессе

fork() создаёт копию процесса. Но в дочернем процессе оказывается только один поток — тот, который вызвал fork(). Все остальные потоки просто исчезают. А память, включая состояние всех мьютексов, копируется как есть.

Сценарий катастрофы:

1. Поток A захватил мьютекс внутри malloc (у аллокатора есть внутренние блокировки).

2. Поток B в этот момент вызывает fork().

3. В дочернем процессе мьютекс аллокатора «захвачен», но потока A, который должен его отпустить, там нет.

4. Дочерний процесс вызывает malloc и зависает навсегда.

То же самое с любыми мьютексами: логгер, пул соединений, ваш собственный кеш.

Правило: в многопоточном процессе после fork() в дочернем процессе можно вызывать только async-signal-safe функции до вызова exec(). Фактически — только сразу заменить процесс через exec. Если нужно запустить внешнюю программу, используйте posix_spawn() — он сделан именно для этого. Если нужен fork без exec (например, для снапшота памяти, как в Redis), делайте его до создания потоков или проектируйте систему так, чтобы дочерний процесс не трогал ничего, что могло быть захвачено.

4.9. Сигналы и потоки

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

Кому достанется сигнал. Процессно-направленный сигнал (например, SIGTERM от kill) доставляется любому потоку, у которого он не заблокирован. Какому именно — решает ядро.

Обработчик прерывает поток в произвольной точке. Например, посреди malloc или посреди критической секции с захваченным мьютексом. Поэтому внутри обработчика сигнала можно вызывать только async-signal-safe функции (их список есть в man signal-safety): никакого malloc, никакого printf, никаких мьютексов. Если обработчик попытается захватить мьютекс, который уже держит прерванный поток, это мгновенный дедлок: прерванный поток не продолжится, пока не закончится обработчик.

Что можно сделать в обработчике. Почти ничего: записать в переменную типа volatile std::sig_atomic_t или в lock-free std::atomic, и выйти. Это единственный законный случай для volatile в многопоточной теме (подробнее в главе 5).

Правильный шаблон: выделенный поток сигналов

Вместо асинхронных обработчиков используем синхронное ожидание:

1. в самом начале main, до создания любых потоков, блокируем нужные сигналы через pthread_sigmask. Маска сигналов наследуется, поэтому все потоки, созданные дальше, тоже их блокируют;

2. создаём выделенный поток, который ждёт сигналы через sigwait (или sigtimedwait);

3. sigwait возвращает номер сигнала как обычное значение функции, и дальше это обычный код: можно брать мьютексы, логировать, аллоцировать;

4. поток сигналов переводит сигнал в понятный остальной программе механизм — например, request_stop() на общем stop_source.

Листинг 4.9 — сигналы в многопоточной программе (ex05_signal_thread.cpp)

Почему sigtimedwait, а не sigwait: чтобы поток сигналов мог выйти сам, когда программа завершается по другой причине (например, из-за фатальной ошибки). sigwait ждал бы вечно, и деструктор jthread повис бы на join.

Рабочие потоки при этом ничего не знают о сигналах — только о stop_token. Это правильное разделение: обработка ОС-специфичных событий в одном месте, остальной код переносим.

4.10. Грабли с ревью

— Массив счётчиков или структур «по одной на поток» без выравнивания.

— Выравнивание всего подряд «на всякий случай» — память и кеш тоже не бесплатные.

— Код, который полагается на порядок операций с памятью без синхронизации («на x86 же работает»).

— Один горячий мьютекс на весь сервис и надежда, что ядра помогут.

— Привязка потоков к ядрам без замеров в реальном окружении.

— fork() без немедленного exec() в многопоточной программе.

— printf, malloc, мьютексы или логирование внутри обработчика сигнала.

— Обработка сигналов через signal() в многопоточной программе вместо выделенного потока.

4.11. Что спросят на собеседовании

Что такое false sharing и как его найти? (middle/senior) Разные потоки пишут в разные переменные в одной кеш-линии, линия прыгает между ядрами. Найти — профилировщиком (perf c2c на Linux) или по симптому «нет общих данных, а не масштабируется». Лечить — разносить по линиям.

Что такое кеш-линия и почему это важно для многопоточности? (middle) Единица обмена между памятью и кешем (обычно 64 байта); когерентность работает на уровне линий, поэтому записи соседних данных разными ядрами конфликтуют.

Почему процессор может переставить операции с памятью? (senior) Store buffer, внеочередное исполнение, оптимизации компилятора. x86 переставляет store-load, ARM почти всё. Модель памяти C++ абстрагирует это.

Сколько стоит мьютекс? (senior) Без конкуренции — атомарная операция в пространстве пользователя (futex), при конкуренции — системные вызовы и переключение контекста. Проблема в конкуренции, а не в мьютексе.