C++. Практика многопоточного программирования

Предисловие..................................................................................................................16

Благодарности...............................................................................................................18
О книге..........................................................................................................................20
Структура издания................................................................................................20
Для кого предназначена эта книга........................................................................21
Порядок чтения.....................................................................................................21
Условные обозначения и загрузка кода.................................................................22
Требования к программным средствам..................................................................22
Форум, посвященный книге...................................................................................22
Об авторе......................................................................................................................24
Об иллюстрации на обложке.........................................................................................25
От издательства............................................................................................................26
Глава 1. Здравствуй, мир конкурентности в C++!.........................................................27
1.1. Что такое конкурентность.....................................................................................28
1.1.1. Конкурентность в компьютерных системах..................................................28
1.1.2. Подходы к конкурентности.........................................................................31
1.1.3. Сравнение конкурентности и параллелизма................................................33
1.2. Зачем используется конкурентность......................................................................34
1.2.1. Конкурентность для разделения неотложных задач....................................34
1.2.2. Конкурентность для повышения производительности:
параллелизм задач и данных......................................................................35
1.2.3. Когда не нужна конкурентность..................................................................36
1.3. Конкурентность и многопоточность в C++............................................................37
1.3.1. История поддержки многопоточности в C++...............................................38
1.3.2. Поддержка конкурентности в стандарте C++11..........................................39
1.3.3. Расширение поддержки конкурентности и параллелизма в C++14
и C++17.....................................................................................................39
1.3.4. Эффективность, обеспеченная библиотекой потоков C++..........................40
1.3.5. Средства, ориентированные на использование конкретной
платформы.................................................................................................41
1.4. Приступаем к практической работе.......................................................................41
1.4.1. Здравствуй, мир конкурентности.................................................................42
Резюме..........................................................................................................................43
Глава 2. Управление потоками.....................................................................................44
2.1. Основы управления потоками...............................................................................45
2.1.1. Запуск потока.............................................................................................45
2.1.2. Ожидание завершения потока....................................................................48
2.1.3. Ожидание в исключительных обстоятельствах............................................49
2.1.4. Запуск потоков в фоновом режиме.............................................................51
2.2. Передача аргументов функции потока..................................................................53
2.3. Передача права владения потоком........................................................................55
2.4. Выбор количества потоков в ходе выполнения программы....................................60
2.5. Идентификация потоков........................................................................................63
Резюме..........................................................................................................................64
Глава 3. Совместное использование данных несколькими потоками.............................65
3.1. Проблемы совместного использования данных несколькими потоками..................66
3.1.1. Состояние гонки.........................................................................................68
3.1.2. Пути обхода проблемных состояний гонок..................................................69
3.2. Защита совместно используемых данных с применением мьютексов.....................70
3.2.1. Использование мьютексов в C++................................................................70
3.2.2. Структуризация кода для защиты совместно используемых данных............72
3.2.3. Обнаружение состояния гонки, присущего интерфейсам............................74
3.2.4. Взаимная блокировка: проблема и решение...............................................81
3.2.5. Дополнительные рекомендации по обходу взаимных блокировок...............84
3.2.6. Гибкая блокировка с применением std::unique_lock....................................91
3.2.7. Передача владения мьютексом между областями видимости......................92
3.2.8. Блокировка с соответствующей степенью детализации...............................94
3.3. Альтернативные средства защиты совместно используемых данных......................97
3.3.1. Защита совместно используемых данных во время инициализации.............97
3.3.2. Защита редко обновляемых структур данных............................................101
3.3.3. Рекурсивная блокировка...........................................................................103
Резюме........................................................................................................................104
Глава 4. Синхронизация конкурентных операций.......................................................105
4.1. Ожидание наступления события или создания другого условия..........................106
4.1.1. Ожидание выполнения условий с применением условных
переменных..............................................................................................107
4.1.2. Создание потокобезопасной очереди с условными переменными..............110
4.2. Ожидание единичных событий с помощью фьючерсов........................................115
4.2.1. Возвращение значений из фоновых задач................................................116
4.2.2. Связывание задачи с фьючерсом..............................................................119
4.2.3. Создание промисов std::promise................................................................121
4.2.4. Сохранение исключения на будущее.........................................................124
4.2.5. Ожидание сразу в нескольких потоках......................................................125
4.3. Ожидание с ограничением по времени................................................................128
4.3.1. Часы.........................................................................................................128
4.3.2. Продолжительность..................................................................................130
4.3.3. Моменты времени.....................................................................................131
4.3.4. Функции, принимающие сроки ожидания..................................................133
4.4. Применение синхронизации операций для упрощения кода................................135
4.4.1. Функциональное программирование с применением фьючерсов...............135
4.4.2. Синхронизация операций путем передачи сообщений...............................141
4.4.3. Конкурентность, организованная в стиле продолжений
с применением Concurrency TS..................................................................146
4.4.4. Выстраиваем продолжения в цепочку.......................................................148
4.4.5. Ожидание готовности более чем одного фьючерса...................................151
4.4.6. Ожидание первого фьючерса в наборе с when_any...................................153
4.4.7. Защелки и барьеры в Concurrency TS........................................................156
4.4.8. Базовый тип защелки std::experimental::latch............................................156
4.4.9. Основной барьер std::experimental::barrier................................................157
4.4.10. Барьер std::experimental::flex_barrier — более гибкий соратник
барьера std::experimental::barrier..............................................................159
Резюме........................................................................................................................161
Глава 5. Модель памяти C++ и операции над атомарными типами............................162
5.1. Основы модели памяти........................................................................................163
5.1.1. Объекты и их размещение в памяти..........................................................163
5.1.2. Объекты, области памяти и конкурентность..............................................165
5.1.3. Очередность внесения изменений.............................................................166
5.2. Атомарные операции и типы в C++.....................................................................166
5.2.1. Стандартные атомарные типы...................................................................167
5.2.2. Операции над std::atomic_flag...................................................................171
5.2.3. Операции над std::atomic<bool>...............................................................173
5.2.4. Операции над std::atomic<T*>: арифметика указателей..........................176
5.2.5. Операции над стандартными атомарными целочисленными типами..........177
5.2.6. Шаблон первичного класса std::atomic<>.................................................178
5.2.7. Свободные функции для атомарных операций..........................................180
5.3. Синхронизация операций и принудительное упорядочение.................................183
5.3.1. Отношение «синхронизируется с»............................................................184
5.3.2. Отношение «происходит до»....................................................................185
5.3.3. Упорядочение доступа к памяти для атомарных операций........................187
5.3.4. Последовательности освобождений и отношения
«синхронизируется с»...............................................................................207
5.3.5. Барьеры....................................................................................................209
5.3.6. Упорядочение неатомарных операций с помощью атомарных операций.....211
5.3.7. Упорядочение неатомарных операций......................................................212
Резюме........................................................................................................................216
Глава 6. Разработка конкурентных структур данных с блокировками.........................217
6.1. Что означает разработка структур данных для конкурентного доступа...............218
6.1.1. Рекомендации по разработке структур данных для конкурентного
доступа.....................................................................................................219
6.2. Конкурентные структуры данных с блокировками...............................................220
6.2.1. Потокобезопасный стек, использующий блокировки.................................221
6.2.2. Потокобезопасная очередь с использованием блокировок
и условных переменных............................................................................224
6.2.3. Потокобезопасная очередь с использованием подробной
детализации блокировок и условных переменных.....................................228
6.3. Разработка более сложных структур данных с использованием блокировок........240
6.3.1. Создание потокобезопасной поисковой таблицы с использованием блокировок.............240
6.3.2. Создание потокобезопасного списка с использованием блокировок..........246
Резюме........................................................................................................................250
Глава 7. Разработка конкурентных структур данных без блокировок..........................251
7.1. Определения и выводы.......................................................................................252
7.1.1. Типы структур данных, не подвергаемых блокировкам.............................252
7.1.2. Структуры данных, свободные от блокировок...........................................254
7.1.3. Структуры данных, свободные от ожиданий..............................................254
7.1.4. Все за и против создания структур данных, свободных от блокировок......255
7.2. Примеры структур данных, свободных от блокировок.........................................256
7.2.1. Создание потокобезопасного стека без блокировок..................................257
7.2.2. Устранение утечек: управление памятью в структурах данных,
свободных от блокировок.........................................................................261
7.2.3. Определение узлов, не подлежащих утилизации, с помощью
указателей опасности...............................................................................266
7.2.4. Определение используемых узлов путем подсчета ссылок........................274
7.2.5. Применение модели памяти к свободному от блокировок стеку................281
7.2.6. Создание потокобезопасной очереди без блокировок...............................285
7.3. Рекомендации по созданию структур данных без блокировок..............................298
7.3.1. Для создания прототипа используйте std::memory_order_seq_cst.............298
7.3.2. Воспользуйтесь схемой утилизации памяти, свободной от блокировок.....299
7.3.3. Остерегайтесь проблемы ABA...................................................................299
7.3.4. Выявляйте циклы активного ожидания и организуйте помощь другому потоку.................300
Резюме........................................................................................................................301
Глава 8. Разработка конкурентного кода....................................................................302
8.1. Способы распределения работы между потоками................................................303
8.1.1. Распределение данных между потоками до начала обработки..................304
8.1.2. Рекурсивное распределение данных.........................................................305
8.1.3. Распределение работы по типам задач.....................................................309
8.2. Факторы, влияющие на производительность конкурентного кода........................312
8.2.1. А сколько у нас процессоров?...................................................................313
8.2.2. Конкуренция при обращении к данным и перебрасывание данных
в кэш-памяти процессоров........................................................................314
8.2.3. Ложное совместное использование памяти...............................................317
8.2.4. Насколько близко расположены по отношению друг к другу
ваши данные?...........................................................................................318
8.2.5. Переоценка вычислительных возможностей и чрезмерное количество переключений задач.........319
8.3. Разработка структур данных для высокопроизводительных
многопоточных приложений................................................................................320
8.3.1. Распределение элементов массива для сложных операций.......................320
8.3.2. Схемы доступа к данным в других структурах данных...............................322
8.4. Дополнительные факторы, учитываемые при разработке
конкурентных программ......................................................................................324
8.4.1. Безопасность исключений в параллельных алгоритмах.............................325
8.4.2. Масштабируемость и закон Амдала...........................................................332
8.4.3. Компенсация потерь на ожидание за счет применения
нескольких потоков..................................................................................333
8.4.4. Повышение отзывчивости за счет конкурентности....................................334
8.5. Разработка конкурентного кода на практике.........................................................336
8.5.1. Параллельная реализация std::for_each....................................................337
8.5.2. Параллельная реализация std::find...........................................................339
8.5.3. Параллельная реализация std::partial_sum...............................................345
Резюме........................................................................................................................354
Глава 9. Усовершенствованное управление потоками................................................355
9.1. Пулы потоков......................................................................................................356
9.1.1. Простейший пул потоков..........................................................................356
9.1.2. Ожидание завершения задач, переданных пулу потоков..........................358
9.1.3. Задачи, ожидающие завершения других задач.........................................362
9.1.4. Предотвращение конкуренции при обращении к очереди работ...............365
9.1.5. Перехват работы.......................................................................................367
9.2. Прерывание потоков...........................................................................................371
9.2.1. Запуск и прерывание другого потока........................................................371
9.2.2. Обнаружение того, что поток был прерван...............................................373
9.2.3. Прерывание ожидания на условной переменной.......................................374
9.2.4. Прерывание ожидания на std::condition_variable_any................................377
9.2.5. Прерывание других блокирующих вызовов...............................................379
9.2.6. Обработка прерываний.............................................................................380
9.2.7. Прерывание фоновых задач при выходе из приложения...........................381
Резюме........................................................................................................................382
Глава 10. Алгоритмы параллельных вычислений.......................................................383
10.1. Перевод стандартных библиотечных алгоритмов в режим параллельных вычислений...........383
10.2. Политики выполнения.........................................................................................384
10.2.1. Общие последствия от задания политики выполнения..............................385
10.2.2. std::execution::sequenced_policy................................................................386
10.2.3. std::execution::parallel_policy.....................................................................387
10.2.4. std::execution::parallel_unsequenced_policy................................................388
10.3. Параллельные алгоритмы из стандартной библиотеки C++................................388
10.3.1. Примеры использования параллельных алгоритмов..................................391
10.3.2. Подсчет посещений..................................................................................393
Резюме........................................................................................................................395
Глава 11. Тестирование и отладка многопоточных приложений.................................396
11.1. Типы ошибок, связанных с конкурентностью.........................................................397
11.1.1. Нежелательная блокировка......................................................................397
11.1.2. Состояния гонки.......................................................................................398
11.2. Приемы обнаружения ошибок, связанных с конкурентностью.............................399
11.2.1. Просмотр кода с целью поиска возможных ошибок...................................400
11.2.2. Обнаружение ошибок, связанных с конкурентностью,
путем тестирования..................................................................................402
11.2.3. Разработка кода с прицелом на удобство тестирования............................404
11.2.4. Приемы тестирования многопоточного кода.............................................406
11.2.5. Структурирование многопоточного тестового кода...................................408
11.2.6. Тестирование производительности многопоточного кода..........................411
Резюме........................................................................................................................412
Приложения
Приложение А. Краткий справочник по некоторым функциям языка C++11.............414
A.1. Ссылки на r-значения..........................................................................................414
A.1.1. Семантика перемещений...........................................................................415
A.1.2. Ссылки на r-значения и шаблоны функций...............................................418
A.2. Удаленные функции............................................................................................419
A.3. Функции по умолчанию.......................................................................................420
A.4. constexpr-функции...............................................................................................424
A.4.1. constexpr и типы, определенные пользователем.......................................425
A.4.2. constexpr-объекты.....................................................................................428
A.4.3. Требования к constexpr-функциям............................................................428
A.4.4. constexpr и шаблоны.................................................................................430
A.5. Лямбда-функции.................................................................................................430
A.5.1. Лямбда-функции, ссылающиеся на локальные переменные......................432
A.6. Вариативные шаблоны........................................................................................436
A.6.1. Расширение пакета параметров................................................................437
A.7. Автоматическое выведение типа переменной...........................................................440
A.8. Локальные переменные потока...........................................................................441
A.9. Выведение аргументов шаблона класса...............................................................442
Резюме........................................................................................................................443
Приложение Б. Краткое сравнение библиотек для написания конкурентных
программ.....................................................................................................................444
Приложение В. Среда передачи сообщений и полный пример программы
управления банкоматом ............................................................................................ 446
Приложение Г. Справочник по C++ Thread Library....................................................463
Г.1. Заголовок <chrono>............................................................................................463
Г.1.1. Шаблон класса std::chrono::duration.........................................................464
Г.1.2. Шаблон класса std::chrono::time_point......................................................474
Г.1.3. Класс std::chrono::system_clock.................................................................477
Г.1.4. Класс std::chrono::steady_clock..................................................................479
Г.1.5. Псевдоним типа std::chrono::high_resolution_clock.....................................481
Г.2. Заголовок <condition_variable>............................................................................481
Г.2.1. Класс std::condition_variable......................................................................481
Г.2.2. Класс std::condition_variable_any...............................................................490
Г.3. Заголовок <atomic>............................................................................................499
Г.3.1. Псевдонимы типа std::atomic_xxx..............................................................501
Г.3.2. Макросы ATOMIC_xxx_LOCK_FREE.............................................................501
Г.3.3. Макрос ATOMIC_VAR_INIT.........................................................................502
Г.3.4. Перечисление std::memory_order..............................................................502
Г.3.5. Функция std::atomic_thread_fence.............................................................503
Г.3.6. Функция std::atomic_signal_fence..............................................................504
Г.3.7. Класс std::atomic_flag................................................................................504
Г.3.8. Шаблон класса std::atomic........................................................................508
Г.3.9. Специализации шаблона std::atomic.........................................................520
Г.3.10. Специализации std::atomic<integral-type>.................................................521
Г.4. Заголовок <future>.............................................................................................539
Г.4.1. Шаблон класса std::future.........................................................................540
Г.4.2. Шаблон класса std::shared_future..............................................................546
Г.4.3. Шаблон класса std::packaged_task ...........................................................552
Г.4.4. Шаблон класса std::promise .....................................................................558
Г.4.5. Шаблон функции std::async......................................................................565
Г.5. Заголовок <mutex>.............................................................................................566
Г.5.1. Класс std::mutex.......................................................................................567
Г.5.2. Класс std::recursive_mutex........................................................................570
Г.5.3. Класс std::timed_mutex.............................................................................572
Г.5.4. Класс std::recursive_timed_mutex..............................................................577
Г.5.5. Класс std::shared_mutex............................................................................582
Г.5.6. Класс std::shared_timed_mutex..................................................................586
Г.5.7. Шаблон класса std::lock_guard..................................................................594
Г.5.8. Шаблон класса std::scoped_lock................................................................596
Г.5.9. Шаблон класса std::unique_lock ...............................................................598
Г.5.10. Шаблон класса std::shared_lock ...............................................................608
Г.5.11. Шаблон функции std::lock.........................................................................619
Г.5.12. Шаблон функции std::try_lock...................................................................620
Г.5.13. Класс std::once_flag..................................................................................621
Г.5.14. Шаблон функции std::call_once.................................................................621
Г.6. Заголовок <ratio>...............................................................................................622
Г.6.1. Шаблон класса std::ratio ..........................................................................623
Г.6.2. Псевдоним шаблона std::ratio_add............................................................624
Г.6.3. Псевдоним шаблона std::ratio_subtract......................................................624
Г.6.4. Псевдоним шаблона std::ratio_multiply......................................................625
Г.6.5. Псевдоним шаблона std::ratio_divide.........................................................626
Г.6.6. Шаблон класса std::ratio_equal..................................................................626
Г.6.7. Шаблон класса std::ratio_not_equal...........................................................627
Г.6.8. Шаблон класса std::ratio_less....................................................................627
Г.6.9. Шаблон класса std::ratio_greater ..............................................................628
Г.6.10. Шаблон класса std::ratio_less_equal..........................................................628
Г.6.11. Шаблон класса std::ratio_greater_equal.....................................................628
Г.7. Заголовок <thread>............................................................................................628
Г.7.1. Класс std::thread.......................................................................................629
Г.7.2. Пространство имен this_thread..................................................................639