Параллельное программирование на C++ в действии. Практика разработки многопоточных программ

Энтони Уильямс

Параллельное 

программирование 
на C++ в действии

Практика разработки многопоточных программ

M A N N I N G
SHELTER ISLAND

C++ Concurrency
in Action

PRACTICAL MULTITHREADING

ANTHONY WILLIAMS

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

ПРАКТИКА РАЗРАБОТКИ 

МНОГОПОТОЧНЫХ ПРОГРАММ

Москва, 2023

ЭНТОНИ УИЛЬЯМС

2-е издание, электронное

УДК 004.438C++11
ББК 32.973.26-018.2
У36

У36
Уильямс, Энтони.
Параллельное программирование на C++ в действии. Практика разработки 
многопоточных программ / Э. Уильямс ; пер. с англ. А. А. Слинкина. — 2-е изд., 
эл. — 1 файл pdf : 674 с. — Москва : ДМК Пресс, 2023. — Систем. требования: Adobe 
Reader XI либо Adobe Digital Editions 4.5 ; экран 10". — Текст : электронный.
ISBN 978-5-89818-319-6
В наши дни компьютеры с несколькими многоядерными процессорами стали нормой. 
Стандарт C++11 языка C++ предоставляет развитую поддержку многопоточности в приложениях. Поэтому, чтобы сохранять конкурентоспособность, вы должны овладеть принципами и приемами их разработки, а также новыми средствами языка, относящимися к 
параллелизму.
Книга «Параллельное программирование на С++ в действии» не предполагает предварительных знаний в этой области. Вдумчиво читая ее, вы научитесь писать надежные и 
элегантные многопоточные программы на C++11. Вы узнаете о том, что такое потоковая 
модель памяти, и о том, какие средства поддержки многопоточности, в том числе запуска 
и синхронизации потоков, имеются в стандартной библиотеке. Попутно вы познакомитесь 
с различными нетривиальными проблемами программирования в условиях параллелизма.

УДК 004.438C++11 
ББК 32.973.26-018.2

Электронное издание на основе печатного издания: Параллельное программирование на C++ в действии. Практика разработки многопоточных программ / Э. Уильямс ; пер. с англ. А. А. Слинкина. — 
Москва : ДМК Пресс, 2014. — 672 с. — ISBN 978-5-94074-537-2. — Текст : непосредственный.

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

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты 
авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.

ISBN 978-5-89818-319-6
©  by Manning Publications Co.
©  Оформление, перевод на русский язык 
ДМК Пресс, 2014

Ким, Хью и Ирен.

ОГЛАВЛЕНИЕ

Предисловие ............................................. 13
Благодарности ........................................... 15
Об этой книге ............................................. 17
Об иллюстрации на обложке ......................... 21
ГЛАВА 1. Здравствуй, параллельный мир! ...... 22
1.1. Что такое параллелизм?  ................................................... 23
1.1.1. Параллелизм в вычислительных системах ........................ 23
1.1.2. Подходы к организации параллелизма ............................. 26
1.2. Зачем нужен параллелизм?  .............................................. 29
1.2.1. Применение параллелизма для разделения 
обязанностей ............................................................................. 29
1.2.2. Применение параллелизма для повышения 
производительности .................................................................. 30
1.2.3. Когда параллелизм вреден? ............................................. 32
1.3. Параллелизм и многопоточность в C++ ............................. 33
1.3.1. История многопоточности в C++ ....................................... 34
1.3.2. Поддержка параллелизма в новом стандарте ................... 35
1.3.3. Эффективность библиотеки многопоточности для C++ ..... 36
1.3.4. Платформенно-зависимые средства ................................ 37
1.4. В начале пути .................................................................... 38
1.4.1. Здравствуй, параллельный мир ........................................ 38
1.5. Резюме ............................................................................. 40

ГЛАВА 2. Управление потоками ..................... 41
2.1. Базовые операции управления потоками .......................... 41
2.1.1. Запуск потока ................................................................... 42
2.1.2. Ожидание завершения потока .......................................... 45
2.1.3. Ожидание в случае исключения ........................................ 46
2.1.4. Запуск потоков в фоновом режиме ................................... 48
2.2. Передача аргументов функции потока .............................. 51
2.3. Передача владения потоком ............................................. 54
2.4. Задание количества потоков во время выполнения ........... 58
2.5. Идентификация потоков ................................................... 61
2.6. Резюме ............................................................................. 64

Оглавление

ГЛАВА 3. Разделение данных между потоками 65
3.1. Проблемы разделения данных между потоками ................ 66
3.1.1. Гонки ................................................................................. 68
3.1.2. Устранение проблематичных состояний гонки .................. 69
3.2. Защита разделяемых данных с помощью мьютексов ........ 70
3.2.1. Использование мьютексов в C++ ...................................... 71
3.2.2. Структурирование кода для защиты разделяемых 
данных ....................................................................................... 73
3.2.3. Выявление состояний гонки, внутренне присущих 
интерфейсам ............................................................................. 74
3.2.4. Взаимоблокировка: проблема и решение ......................... 83
3.2.5. Дополнительные рекомендации, как избежать 
взаимоблокировок ..................................................................... 86
3.2.6. Гибкая блокировка с помощью std::unique_lock  ................ 94
3.2.7. Передача владения мьютексом между контекстами .......... 95
3.2.8. Выбор правильной гранулярности блокировки ................. 97
3.3. Другие средства защиты разделяемых данных ............... 100
3.3.1. Защита разделяемых данных во время инициализации .....100
3.3.2. Защита редко обновляемых структур данных .................. 105
3.3.3. Рекурсивная блокировка ................................................. 107
3.4. Резюме ........................................................................... 108

ГЛАВА 4. Синхронизация параллельных 
операций ................................................ 110
4.1. Ожидание события или иного условия ............................ 111
4.1.1. Ожидание условия с помощью условных переменных ..... 112
4.1.2. Потокобезопасная очередь на базе условных 
переменных ............................................................................. 115
4.2. Ожидание одноразовых событий с помощью механизма 
будущих результатов ............................................................. 121
4.2.1. Возврат значения из фоновой задачи ............................. 122
4.2.2. Ассоциирование задачи с будущим результатом ............ 125
Передача задач между потоками .............................................. 127
4.2.3. Использование std::promise ............................................ 129
4.2.4. Сохранение исключения в будущем результате .............. 131
4.2.5. Ожидание в нескольких потоках ...................................... 133
4.3. Ожидание с ограничением по времени ........................... 136
4.3.1. Часы ............................................................................... 137
4.3.2. Временные интервалы .................................................... 138
4.3.3. Моменты времени .......................................................... 140
4.3.4. Функции, принимающие таймаут .................................... 142
4.4. Применение синхронизации операций для упрощения 
кода ....................................................................................... 144

Оглавление

4.4.1. Функциональное программирование с применением 
будущих результатов ................................................................ 145
4.5. Резюме ........................................................................... 156

ГЛАВА 5. Модель памяти C++ и атомарные 
операции ................................................ 158
5.1. Основы модели памяти ................................................... 159
5.1.1. Объекты и ячейки памяти ................................................ 159
5.1.2. Объекты, ячейки памяти и параллелизм ......................... 161
5.1.3. Порядок модификации ................................................... 162
5.2. Атомарные операции и типы в C++ .................................. 163
5.2.1. Стандартные атомарные типы ........................................ 163
5.2.2. Операции над std::atomic_flag ......................................... 167
5.2.3. Операции над std::atomic<bool> ..................................... 170
5.2.4. Операции над std::atomic<T*>: арифметика указателей ....173
5.2.5. Операции над стандартными атомарными 
целочисленными типами .......................................................... 175
5.2.6. Основной шаблон класса std::atomic<> .......................... 175
5.2.7. Свободные функции для атомарных операций ................ 177
5.3. Синхронизация операций и принудительное 
упорядочение ........................................................................ 180
5.3.1. Отношение синхронизируется-с ..................................... 182
5.3.2. Отношение происходит-раньше ..................................... 183
5.3.3. Упорядочение доступа к памяти для атомарных операций ...185
5.3.4. Последовательности освобождений и отношение 
синхронизируется-с ................................................................. 208
5.3.5. Барьеры .......................................................................... 212
5.3.6. Упорядочение неатомарных операций с помощью 
атомарных................................................................................ 214
5.4. Резюме ........................................................................... 216

ГЛАВА 6. Проектирование параллельных 
структур данных с блокировками ................ 218
6.1. Что понимается под проектированием структур данных, 
рассчитанных на параллельный доступ? ................................ 219
6.1.1. Рекомендации по проектированию структур данных 
для параллельного доступа ...................................................... 220
6.2. Параллельные структуры данных с блокировками ........... 222
6.2.1. Потокобезопасный стек с блокировками ........................ 222
6.2.2. Потокобезопасная очередь с блокировками 
и условными переменными ...................................................... 226
6.2.3. Потокобезопасная очередь с мелкогранулярными 
блокировками и условными переменными ............................... 231

Оглавление

6.3. Проектирование более сложных структур данных с 
блокировками........................................................................ 245
6.3.1. Разработка потокобезопасной справочной таблицы с 
блокировками .......................................................................... 246
6.3.2. Потокобезопасный список с блокировками .................... 253
6.4. Резюме ........................................................................... 258

ГЛАВА 7. Проектирование параллельных 
структур данных без блокировок ................. 260
7.1. Определения и следствия из них ..................................... 261
7.1.1. Типы неблокирующих структур данных............................ 262
7.1.2. Структуры данных, свободные от блокировок ................. 262
7.1.3. Структуры данных, свободные от ожидания .................... 263
7.1.4. Плюсы и минусы структур данных, свободных 
от блокировок .......................................................................... 264
7.2. Примеры структур данных, свободных от блокировок ..... 266
7.2.1. Потокобезопасный стек без блокировок ......................... 266
7.2.2. Устранение утечек: управление памятью в структурах 
данных без блокировок ............................................................ 271
7.2.3. Обнаружение узлов, не подлежащих освобождению, 
с помощью указателей опасности ............................................ 277
7.2.4. Нахождение используемых узлов с помощью подсчета 
ссылок ..................................................................................... 287
7.2.5. Применение модели памяти к свободному от блокировок 
стеку ............................................................................................293
7.2.6. Потокобезопасная очередь без блокировок .................... 299
7.3. Рекомендации по написанию структур данных без 
блокировок ............................................................................ 313
7.3.1. Используйте std::memory_order_seq_cst для создания 
прототипа ................................................................................ 314
7.3.2. Используйте подходящую схему освобождения памяти .. 314
7.3.3. Помните о проблеме ABA ................................................ 315
7.3.4. Выявляйте циклы активного ожидания и помогайте 
другим потокам ........................................................................ 316
7.4. Резюме ........................................................................... 317

ГЛАВА 8. Проектирование параллельных 
программ ................................................ 318
8.1. Методы распределения работы между потоками ............ 319
8.1.1. Распределение данных между потоками до начала 
обработки ................................................................................ 320
8.1.2. Рекурсивное распределение данных .............................. 322
8.1.3. Распределение работы по типам задач ........................... 327

Оглавление

8.2. Факторы, влияющие на производительность параллельного 
кода ....................................................................................... 330
8.2.1. Сколько процессоров? .................................................... 331
8.2.2. Конкуренция за данные и перебрасывание кэша ............ 333
8.2.3. Ложное разделение ........................................................ 335
8.2.4. Насколько близки ваши данные?..................................... 336
8.2.5. Превышение лимита и чрезмерное контекстное 
переключение .......................................................................... 337
8.3. Проектирование структур данных для повышения 
производительности многопоточной программы .................. 338
8.3.1. Распределение элементов массива для сложных 
операций ................................................................................. 339
8.3.2. Порядок доступа к другим структурам данных ................ 342
8.4. Дополнительные соображения при проектировании 
параллельных программ ........................................................ 344
8.4.1. Безопасность относительно исключений 
в параллельных алгоритмах ..................................................... 344
8.4.2. Масштабируемость и закон Амдала ................................ 353
8.4.3. Сокрытие латентности с помощью нескольких потоков ... 355
8.4.4. Повышение быстроты реакции за счет 
распараллеливания ................................................................. 356
8.5. Проектирование параллельного кода на практике........... 359
8.5.1. Параллельная реализация std::for_each .......................... 359
8.5.2. Параллельная реализация std::find ................................. 362
8.5.3. Параллельная реализация std::partial_sum ...................... 369
8.6. Резюме ........................................................................... 380

ГЛАВА 9. Продвинутое управление потоками ...382
9.1. Пулы потоков .................................................................. 383
9.1.1. Простейший пул потоков ................................................ 383
9.1.2. Ожидание задачи, переданной пулу потоков ................... 386
9.1.3. Задачи, ожидающие других задач ................................... 391
9.1.4. Предотвращение конкуренции за очередь работ ............ 394
9.1.5. Занимание работ ............................................................ 396
9.2. Прерывание потоков ....................................................... 401
9.2.1. Запуск и прерывание другого потока .............................. 402
9.2.2. Обнаружение факта прерывания потока ......................... 404
9.2.3. Прерывание ожидания условной переменной ................. 405
9.2.4. Прерывание ожидания std::condition_variable_any ........... 409
9.2.5. Прерывание других блокирующих вызовов ..................... 411
9.2.6. Обработка прерываний ................................................... 412
9.2.7. Прерывание фоновых потоков при выходе из приложения.....413
9.3. Резюме ........................................................................... 415