Параллельное программирование на современном C++

Райнер Гримм

Параллельное программирование  
на современном C++

Concurrency  
with Modern C++ 

What every professional C++ programmer  
should know about concurrency

Rainer Grimm

Параллельное 
программирование  
на современном C++

Что каждый профессионал должен знать  
о параллельном программировании

Райнер Гримм

Москва, 2022

УДК 004.4
ББК 32.973.202
Г84

Гримм Р.
Г84  Параллельное программирование на современном C++ / пер. с англ. В. 
Ю. Винника. – М.: ДМК Пресс, 2022. – 616 с.: ил. 

ISBN 978-5-97060-957-6

Книга во всех подробностях освещает параллельное программирование на 
современном C++. Особое внимание уделено опасностям и трудностям параллельного программирования (например, гонке данных и мертвой блокировке) и способам борьбы с ними. Приводятся многочисленные примеры кода, позволяющие 
читателю легко закрепить теорию на практических примерах.
Издание адресовано читателям, которые хотят освоить параллельное программирование на одном из наиболее распространенных языков.

УДК 004.4
ББК 32.973.202

Copyright Concurrency with Modern C++ published by Rainer Grimm. Copyright @2020 
Rainer Grimm

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

 
© Rainer Grimm, 2020
ISBN 978-5-97060-957-6 (рус.)  
©  Перевод, оформление, издание,  
ДМК Пресс, 2022

Дизайн обложки разработан с использованием ресурса freepik.com.

Содержание

От издательства ....................................................................................................17

Введение ..................................................................................................................18

КРАТКИЙ ОБЗОР .............................................................................................22

1. Параллельное программирование и современный  
язык C++ ...................................................................................................................23

1.1. Стандарты C++ 11 и C++ 14: закладка фундамента ........................................24
1.1.1. Модели памяти .............................................................................................24
1.1.1.1. Атомарные переменные ......................................................................25
1.1.2. Управление потоками .................................................................................25
1.1.2.1. Классы для поддержки потоков .........................................................25
1.1.2.2. Данные в совместном доступе ...........................................................26
1.1.2.3. Локальные данные потока ..................................................................27
1.1.2.4. Переменные условия ...........................................................................27
1.1.2.5. Кооперативное прерывание потоков (стандарт C++ 20) ................28
1.1.2.6. Семафоры (стандарт C++ 20) ...............................................................28
1.1.2.7. Защёлки и барьеры (стандарт C++ 20) ...............................................28
1.1.2.8. Задания ..................................................................................................28
1.1.2.9. Синхронизированные потоки вывода (стандарт С++ 20) ...............29
1.2. Стандарт C++ 17. Параллельные алгоритмы в стандартной библиотеке ....29
1.2.1. Политики выполнения ................................................................................30
1.2.2. Новые параллельные алгоритмы ..............................................................30
1.3. Сопрограммы в стандарте C++ 20 .....................................................................30
1.4. Учебные примеры ...............................................................................................31
1.4.1. Вычисление суммы элементов вектора ...................................................31
1.4.2. Потокобезопасное создание объекта-одиночки .....................................31
1.4.3. Поэтапная оптимизация с использованием инструмента CppMem ....31
1.4.4. Быстрая синхронизация потоков ..............................................................31
1.4.5. Вариации на тему фьючерсов ....................................................................31
1.4.6. Модификации и обобщения генераторов ................................................32
1.4.7. Способы управления заданиями ...............................................................32
1.5. Будущее языка C++ ..............................................................................................32
1.5.1. Исполнители .................................................................................................32
1.5.2. Расширенные фьючерсы ............................................................................33
1.5.3. Транзакционная память .............................................................................33
1.5.4. Блоки заданий ..............................................................................................33
1.5.5. Библиотека для векторных вычислений ..................................................34
1.6. Шаблоны и эмпирические правила ..................................................................34

1.6.1. Шаблоны синхронизации ...........................................................................34
1.6.2. Шаблоны параллельной архитектуры ......................................................34
1.6.3. Эмпирические правила ...............................................................................35
1.7. Структуры данных ...............................................................................................35
1.8. Сложности параллельного программирования .............................................35
1.9. Библиотека для работы со временем ...............................................................35
1.10. Обзор инструментального средства CppMem ...............................................35
1.11. Пояснение некоторых терминов ....................................................................36

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ 
В ПОДРОБНОСТЯХ .........................................................................................37

2. Модель памяти ................................................................................................38
2.1. Начальное представление о модели памяти ..................................................38
2.1.1. Что такое область памяти? .........................................................................39
2.1.2. Что происходит, когда два потока обращаются к одной области 
памяти .....................................................................................................................39
2.2. Модель памяти как контракт ............................................................................40
2.2.1. Основы ...........................................................................................................42
2.2.2. Трудности ......................................................................................................42
2.3. Атомарные переменные ....................................................................................43
2.3.1. Отличие сильной модели памяти от слабой ............................................44
2.3.1.1. Сильная модель памяти ......................................................................44
2.3.1.2. Слабая модель памяти .........................................................................46
2.3.2. Атомарный флаг ...........................................................................................47
2.3.2.1. Циклическая блокировка ....................................................................48
2.3.2.2. Сравнение циклической блокировки с мьютексом ........................50
2.3.2.3. Синхронизация потоков......................................................................53
2.3.3. Шаблон std::atomic .......................................................................................54
2.3.3.1. Фундаментальный атомарный интерфейс ......................................55
2.3.3.2. Атомарные типы с плавающей точкой в стандарте C++ 20 ............66
2.3.3.3. Атомарный тип указателя ...................................................................67
2.3.3.4. Атомарные целочисленные типы ......................................................67
2.3.3.5. Псевдонимы типов ...............................................................................70
2.3.4. Функции-члены атомарных типов ...........................................................71
2.3.5. Свободные функции над атомарными типами ......................................73
2.3.5.1. Особенности типа std::shared_ptr (до стандарта C++ 20) ................74
2.3.6. Шаблон класса std::atomic_ref в стандарте C++ 20 ..................................76
2.3.6.1. Мотивация .............................................................................................76
2.3.6.2. Специализации шаблона std::atomic_ref ..........................................80
2.3.6.3. Полный список атомарных операций ...............................................82
2.4. Синхронизация и порядок доступа к памяти .................................................83
2.4.1. Шесть вариантов модели памяти в языке C++ ........................................83
2.4.1.1. Виды атомарных операций.................................................................84
2.4.1.2. Ограничения на синхронизацию и порядок доступа .....................85
2.4.2. Последовательно-согласованное выполнение ........................................86

2.4.3. Семантика захвата и освобождения .........................................................88
2.4.3.1. Транзитивность ....................................................................................90
2.4.3.2. Типичное недоразумение ...................................................................93
2.4.3.3. Последовательность освобождений ..................................................97
2.4.4. Модель памяти std::memory_order_consume ..................................................99
2.4.4.1. Порядок захвата и освобождения ....................................................100
2.4.4.2. Порядок освобождения и потребления ...........................................101
2.4.4.3. Различие порядков «освобождение-захват»  
и «освобождение-потребление» ....................................................................102
2.4.4.4. Зависимости данных в модели std::memory_order_consume .............102
2.4.5. Ослабленная семантика ............................................................................104
2.4.5.1. Отсутствие ограничений на синхронизацию и порядок  
операций ...........................................................................................................104
2.5. Барьеры ...............................................................................................................106
2.5.1. Барьер std::atomic_thread_fence ................................................................106
2.5.1.1. Что такое барьеры памяти ................................................................106
2.5.1.2. Три барьера .........................................................................................107
2.5.1.3. Барьеры захвата и освобождения ....................................................109
2.5.1.4. Синхронизация с использованием атомарных переменных 
и барьеров .........................................................................................................111
2.5.2. Барьер std::atomic_signal_fence ................................................................116

3. Управление потоками ................................................................................117
3.1. Базовые потоки: класс std::thread ..................................................................117
3.1.1. Создание потока ........................................................................................118
3.1.2. Время жизни потоков ................................................................................119
3.1.2.1. Функции join и detach .........................................................................120
3.1.3. Передача аргументов при создании потока ..........................................122
3.1.3.1. Передача по значению и по ссылке .................................................122
3.1.4. Перечень функций-членов .......................................................................125
3.2. Усовершенствованные потоки: класс std::jthread (стандарт С++ 20) ........129
3.2.1. Автоматическое присоединение к потоку .............................................129
3.2.2. Прерывание по запросу в классе std::jthread ........................................131
3.3. Данные в совместном доступе ........................................................................133
3.3.1. Мьютексы ....................................................................................................134
3.3.1.1. Затруднения с мьютексами...............................................................138
3.3.2. Блокировщики ...........................................................................................141
3.3.2.1. Тип std::lock_guard ..............................................................................141
3.3.2.2. Тип std::scoped_lock ............................................................................142
3.3.2.3. Тип std::unique_lock ............................................................................143
3.3.2.4. Блокировщик std::shared_lock ..........................................................144
3.3.3. Функция std::lock ......................................................................................148
3.3.4. Потокобезопасная инициализация ........................................................151
3.3.4.1. Константные выражения ...................................................................151
3.3.4.2. Функция std::call_once и флаг std::once_flag .................................152
3.3.4.3. Локальные статические переменные ..............................................156
3.4. Данные с потоковой длительностью хранения ............................................157

3.5. Переменные условия ........................................................................................160
3.5.1. Использование предиката в функции ожидания .................................163
3.5.2. Утерянные и ложные пробуждения ........................................................164
3.5.3. Процедура ожидания ................................................................................165
3.6. Кооперативное прерывание потоков (стандарт C++ 20) .............................166
3.6.1. Класс std::stop_source ................................................................................167
3.6.2. Класс std::stop_token ..................................................................................168
3.6.3. Класс std::stop_callback .............................................................................169
3.6.4. Общий механизм посылки сигналов ......................................................172
3.6.5. Особенности класса std::jthread ..............................................................175
3.6.6. Новые перегрузки функции wait в классе  
std::condition_variable_any ..................................................................................175
3.7. Семафоры (стандарт C++ 20) ............................................................................178
3.8. Защёлки и барьеры (стандарт C++ 20) ............................................................182
3.8.1. Класс std::latch ...........................................................................................182
3.8.2. Класс std::barrier .......................................................................................187
3.9. Асинхронные задания ......................................................................................190
3.9.1. Отличие заданий от потоков....................................................................191
3.9.2. Функция std::async .....................................................................................192
3.9.2.1. Политика запуска ...............................................................................193
3.9.2.2. Запустить и забыть .............................................................................195
3.9.2.3. Параллельное вычисление скалярного произведения .................196
3.9.3. Тип std::packaged_task ................................................................................198
3.9.4. Типы std::promise и std::future .................................................................203
3.9.4.1. Тип std::promise ...................................................................................205
3.9.4.2. Тип std::future.....................................................................................205
3.9.5. Тип std::shared_future ................................................................................207
3.9.6. Обработка исключений в асинхронных заданиях ................................211
3.9.7. Оповещения ................................................................................................214
3.10. Синхронизированные потоки вывода (стандарт С++ 20) .........................216
3.11. Краткие итоги ..................................................................................................223

4. Параллельные алгоритмы в стандартной библиотеке .............225
4.1. Политики выполнения .....................................................................................226
4.1.1. Параллельное и векторизованное выполнение ....................................227
4.1.1.1. Код без оптимизации .........................................................................228
4.1.1.2. Максимальная оптимизация ............................................................228
4.1.2. Обработка исключений .............................................................................228
4.1.3. Опасность гонок данных и мёртвых блокировок .................................230
4.2. Алгоритмы стандартной библиотеки ............................................................231
4.3. Новые параллельные алгоритмы ....................................................................232
4.3.1. Новые перегрузки ......................................................................................237
4.3.2. Наследие функционального программирования .................................237
4.4. Поддержка в различных компиляторах ........................................................239
4.4.1. Компилятор Microsoft Visual Compiler ....................................................239
4.4.2. Компилятор GCC ........................................................................................240
4.4.3. Будущие реализации параллельных стандартных алгоритмов .........240

4.5. Вопросы производительности ........................................................................241
4.5.1. Компилятор Microsoft Visual Compiler ....................................................243
4.5.2. Компилятор GCC ........................................................................................244
4.6. Краткие итоги ....................................................................................................244

5. Сопрограммы в стандарте C++ 20 .......................................................245

5.1. Функция-генератор ..........................................................................................247
5.2. Особенности сопрограмм ................................................................................249
5.2.1. Типичные сценарии использования.......................................................249
5.2.2. Разновидности сопрограмм .....................................................................249
5.2.3. Требования к сопрограммам ...................................................................250
5.2.4. Преобразование функции в сопрограмму .............................................250
5.2.4.1. Ограничения .......................................................................................251
5.3. Концептуальная модель ...................................................................................251
5.3.1. Объект-обещание.......................................................................................252
5.3.2. Дескриптор сопрограммы ........................................................................252
5.3.3. Кадр сопрограммы ....................................................................................254
5.4. Ожидание отложенного вычисления .............................................................254
5.4.1. Прообраз ожидания ...................................................................................254
5.4.2. Общие требования к контроллерам ожидания .....................................255
5.4.3. Стандартные контроллеры ожидания ....................................................255
5.4.4. Функция initial_suspend ............................................................................256
5.4.5. Функция final_suspend ...............................................................................256
5.4.6. Получение контроллера ожидания .........................................................257
5.5. Процесс функционирования сопрограммы ..................................................258
5.5.1. Управление обещанием ............................................................................258
5.5.2. Управление ожиданием ............................................................................259
5.6. Оператор co_return и жадный фьючерс ..........................................................261
5.7. Оператор co_yield и бесконечный поток данных .........................................263
5.8. Оператор co_await ..............................................................................................266
5.8.1. Запуск задания по запросу .......................................................................266
5.9. Синхронизация потоков ..................................................................................268
5.10. Краткие итоги ..................................................................................................273

6. Учебные примеры ........................................................................................274

6.1. Вычисление суммы элементов вектора .........................................................274
6.1.1. Суммирование элементов вектора в одном потоке .............................274
6.1.1.1. Суммирование в цикле по диапазону .............................................275
6.1.1.2. Суммирование алгоритмом std::accumulate ...................................276
6.1.1.3. Использование блокировщика .........................................................277
6.1.1.4. Использование атомарной переменной .........................................278
6.1.1.5. Сводные данные по однопоточным алгоритмам ..........................280
6.1.2. Многопоточное суммирование с общей переменной .........................281
6.1.2.1. Использование блокировщика .........................................................281
6.1.2.2. Использование атомарной переменной .........................................283
6.1.2.3. Использование атомарной переменной с функцией fetch_add ...285

6.1.2.4. Использование ослабленной семантики ........................................286
6.1.2.5. Сводные данные по алгоритмам с общей переменной................287
6.1.3. Раздельное суммирование в потоках .....................................................287
6.1.3.1. Использование локальной переменной .........................................287
6.1.3.2. Использование переменных с потоковым временем жизни ......292
6.1.3.3. Использование асинхронных заданий ...........................................294
6.1.3.4. Сводные данные .................................................................................296
6.1.4. Суммирование вектора: подведение итогов .........................................297
6.1.4.1. Однопоточные алгоритмы ................................................................297
6.1.4.2. Многопоточные алгоритмы с общей переменной ........................297
6.1.4.3. Многопоточные алгоритмы с локальными переменными ..........297
6.2. Потокобезопасное создание объекта-одиночки ..........................................299
6.2.1. Шаблон «Блокировка с двойной проверкой» ........................................300
6.2.2. Измерение производительности .............................................................301
6.2.3. Потокобезопасный вариант реализации Мейерса ...............................304
6.2.4. Реализации на основе блокировщика ....................................................305
6.2.5. Реализация на основе функции std::call_once ......................................307
6.2.6. Решение на основе атомарных переменных .........................................308
6.2.6.1. Семантика последовательной согласованности ............................308
6.2.6.2. Семантика захвата и освобождения ................................................310
6.2.7. Сводные данные .........................................................................................312
6.3. Поэтапная оптимизация с использованием инструмента CppMem .........312
6.3.1. Неатомарные переменные .......................................................................314
6.3.1.1. Анализ программы .............................................................................315
6.3.2. Анализ программы с блокировкой .........................................................320
6.3.3. Атомарные переменные с последовательной согласованностью ......321
6.3.3.1. Анализ программы инструментом CppMem ..................................322
6.3.3.2. Последовательность операций .........................................................326
6.3.4. Атомарные переменные с семантикой захвата и освобождения ......327
6.3.4.1. Анализ программы инструментом CppMem ..................................329
6.3.5. Смесь атомарных и неатомарных переменных ....................................331
6.3.5.1. Анализ программы инструментом CppMem ..................................332
6.3.6. Атомарные переменные с ослабленной семантикой ...........................333
6.3.6.1. Анализ инструментом CppMem .......................................................334
6.3.7. Итоги ............................................................................................................335
6.4. Быстрая синхронизация потоков ...................................................................335
6.4.1. Переменные условия .................................................................................336
6.4.2. Решение на основе атомарного флага ....................................................338
6.4.2.1. Решение с двумя флагами .................................................................338
6.4.2.2. Решение с одним атомарным флагом .............................................340
6.4.3. Решение на основе атомарной логической переменной ....................341
6.4.4. Реализация на семафорах .........................................................................343
6.4.5. Сравнительный анализ .............................................................................345
6.5. Вариации на тему фьючерсов .........................................................................345
6.5.1. Ленивый фьючерс ......................................................................................348
6.5.2. Выполнение сопрограммы в отдельном потоке ...................................351
6.6. Модификации и обобщения генераторов .....................................................355