Книга исследует различные низкоуровневые механизмы и алгоритмы, лежащие в основе современных параллельных и конкурентных вычислений, в частности реализованные в ядре Linux. Рассмотрены примитивы синхронизации (мьютексы и блокировки), владение данными, валидация, копирование и запись, эвристические методы разработки параллельных и конкурентных алгоритмов, подбор аппаратного обеспечения и другие малоизвестные находки в области параллелизма. Также уделено внимание упрощению и оптимизации параллельных вычислений. Наконец, спрогнозированы возможные тенденции развития параллельного программирования с учётом современных разработок нового аппаратного обеспечения.
Для специалистов по параллельному программированию, Linux, работе с памятью и ресурсами в операционных системах
На фоне затухания закона Мура дальнейшее ускорение и масштабирование вычислений достижимо только через наращивание количества ядер и разработку новых параллельных и конкурентных алгоритмов.
Основы этих технологий заложены более 50 лет назад, но на русском языке пока представлены только в академических работах и разрозненных материалах по конкретным языкам программирования, прежде всего С++. Общим знаменателем между этими разноуровневыми наработками является данная книга, в которой изложен полувековой научный и практический опыт автора.
Книга посвящена низкоуровневому параллельному и конкурентному программированию. Особое внимание уделено малоизвестным проблемам проектирования параллельных систем, работе с высоконагруженными приложениями и ядром Linux.
В книге рассмотрены:
- Цели параллельного программирования и альтернативы этого подхода
- Физические и аппаратные ограничения
- Примитивы и средства конкурентного программирования: блокировки, подсчёт ссылок, синхронизация, мьютексы и др.
- Отладка конкурентных программ, включая их формальную верификацию
- Параллельное программирование в режиме реального времени
- Экстремально низкоуровневые темы: упорядочивание памяти и атомарные операции
- Примеры практических задач: подсчёт ссылок, выход из лабиринта, связные списки, хеш-таблицы и др.
- Тенденции развития параллельного программирования
А также
– Более 500 быстрых вопросов для самопроверки
– Более 600 библиографических источников
– Более 1000 страниц
Как читать книгу
Читать книгу следует с «карандашом в руке» и по ходу работы писать низкоуровневый код, будь то код для ядра Linux или других операционных систем, код для управления базами данных, дорабатывать код библиотек и фреймворков. Материал особенно заинтересует читателей, желающих подробно изучить, как минимальными усилиями добиться максимальной производительности на многоядерном оборудовании.
Книгу “Параллельное программирование – так ли это сложно?” можно купить со скидкой в интернет-магазине издательства “БХВ“.
Предисловие к русскому изданию.. 15
От автора. 16
Параллельное программирование: сложно или возможно?. 17
Нормативные положения. 17
Цветные изображения. 18
Глава 1. Как пользоваться этой книгой. 19
1.1 Структура книги. 20
1.2 Экспресс-тесты. 21
1.3 Альтернативы этой книге. 22
1.4 Пример исходного кода. 24
1.5 О чем эта книга?. 24
Глава 2. Введение. 27
2.1 Исторические трудности параллельного программирования. 28
2.2 Цели параллельного программирования. 29
2.2.1 Производительность. 30
2.2.2 Продуктивность. 32
2.2.3 Универсальность. 33
2.3 Альтернативы параллельному программированию.. 37
2.3.1 Несколько экземпляров последовательного приложения. 37
2.3.2 Использование существующего параллельного ПО.. 37
2.3.3 Оптимизация производительности. 38
2.4 Почему параллельное программирование такое сложное?. 39
2.4.1 Разделение работы. 40
2.4.2 Управление параллельным доступом. 41
2.4.3 Разделение и репликация ресурсов. 42
2.4.4 Взаимодействие с оборудованием. 42
2.4.5 Комбинированные возможности. 43
2.4.6 Как языки и среда помогают в решении этих задач?. 43
2.5 Обсуждение. 44
Глава 3. Аппаратное обеспечение и с чем его едят. 45
3.1 Обзор. 45
3.1.1 Конвейерные процессоры. 46
3.1.2 Ссылки на память. 49
3.1.3 Атомарные операции. 50
3.1.4 Барьеры памяти. 51
3.1.5 Промахи кэша. 51
3.1.6 Операции ввода-вывода. 52
3.2 Накладные расходы. 53
3.2.1 Архитектура аппаратной системы. 53
3.2.2 Затраты на операции. 55
3.2.3 Аппаратная оптимизация. 59
3.3 Бесплатные обеды. 60
3.3.1 3D-интеграция. 61
3.3.3 Свет вместо электронов. 62
3.3.4 Ускорители специального назначения. 63
3.3.5 Существующее параллельное программное обеспечение. 64
3.4 Результаты проектирования программного обеспечения. 64
Глава 4. Инструментарий. 66
4.1 Языки сценариев. 66
4.2 Многопроцессорность в системах POSIX.. 68
4.2.1 Создание и уничтожение процессов POSIX.. 68
4.2.2 Создание и уничтожение потоков POSIX.. 71
4.2.3 Блокировка в POSIX.. 72
4.2.4 Блокировка чтения-записи POSIX.. 77
4.2.5 Атомарные операции (GCC Classic) 82
4.2.6 Атомарные операции (C11) 83
4.2.7 Атомарные операции (Современный GCC) 83
4.2.8 Потоковые переменные. 83
4.3 Альтернативы операциям POSIX.. 84
4.3.1 Организация и инициализация. 84
4.3.2 Создание, уничтожение потоков и управление ими. 85
4.3.3 Блокировка. 88
4.3.4 Доступ к общим переменным. 89
4.3.5 Атомарные операции. 102
4.3.6 Переменные для каждого процессора. 103
4.4 Как выбрать подходящий инструмент?. 105
Глава 5. Подсчет. 106
5.1 Что сложного в конкурентном счете?. 107
5.2 Статистические счетчики. 111
5.2.1 Дизайн. 111
5.2.2 Реализация на основе массива. 111
5.2.3 Реализация на основе переменной потока. 113
5.2.4. Реализация с достижимой согласованностью.. 116
5.2.5 Обсуждение. 118
5.3 Приблизительные предельные счетчики. 119
5.3.1 Дизайн. 119
5.3.2 Реализация простого счетчика пределов. 121
5.3.3 Простой счетчик пределов. 127
5.3.4 Реализация приближенного счетчика предельных значений. 128
5.3.5 Приближенный счетчик предельных значений. 129
5.4 Точные счетчики предельных значений. 129
5.4.1 Реализация атомарного предельных значений. 130
5.4.2 Атомарный счетчик предельных значений: обсуждение. 138
5.4.3 Дизайн счетчика предельных значений с кражей сигналов. 138
5.4.4 Реализация счетчика предельных значений на основе кражи сигналов. 139
5.4.5 Счетчик предельных значений с кражей сигналов: обсуждение. 146
5.4.6 Применение точных счетчиков предельных значений. 146
5.5 Обсуждение параллельного подсчета. 148
5.5.1 Валидация параллельного подсчета. 148
5.5.2 Производительность параллельного счета. 149
5.5.3 Специализации параллельного счета. 150
5.5.4 Уроки параллельного подсчета. 151
Глава 6. Проектирование разделения и синхронизации. 154
6.1 Упражнения на разделение. 155
6.1.1 Проблема обедающих философов. 155
6.1.2 Двусторонняя очередь. 157
6.1.3 Пример разделения: обсуждение. 168
6.2 Критерии дизайна. 168
6.3 Детализация синхронизации. 171
6.3.1 Последовательная программа. 172
6.3.2 Кодовая блокировка. 174
6.3.3 Блокировка данных. 175
6.3.4 Владение данными. 178
6.3.5 Детализация и производительность блокировки. 179
6.4 Параллельный быстрый путь. 182
6.4.1 Блокировка чтения-записи. 183
6.4.2 Иерархическая блокировка. 184
6.4.3 Кэши распределителя ресурсов. 185
6.5 Методы без разделения?. 192
6.5.1 Решатель параллельных лабиринтов с очередью работ. 192
6.5.2 Альтернативный решатель параллельного лабиринта. 195
6.5.3 Проверка лабиринта. 198
6.5.4 Сравнение производительности I 198
6.5.5 Альтернативный последовательный решатель лабиринта. 201
6.5.6 Сравнение производительности II 201
6.5.7 Направления дальнейшего развития и выводы. 203
6.6 Разделение, параллелизм и оптимизация. 204
Глава 7. Блокировка. 205
7.1 Остаться в живых. 206
7.1.1 Взаимная блокировка. 206
7.1.2 Динамическая блокировка и голодание. 218
7.1.3 Несправедливость. 220
7.1.4 Неэффективность. 221
7.2 Типы блокировок. 222
7.2.1 Эксклюзивные блокировки. 222
7.2.2 Блокировки чтения-записи. 223
7.2.3 Прочие средства, помимо блокировок чтения-записи. 225
7.2.4 Блокировка с ограниченной областью действия. 226
7.3 Проблемы с реализацией блокировки. 230
7.3.1 Пример реализации эксклюзивной блокировки на основе атомарного обмена. 230
7.3.2 Другие реализации эксклюзивной блокировки. 231
7.4 Гарантии существования на основе блокировки. 234
7.5 Блокировка: герой или злодей?. 237
7.5.1 Блокировка приложений: герой! 237
7.5.2 Блокировка в параллельных библиотеках: еще один инструмент. 238
7.5.3 Блокировка при распараллеливании последовательных библиотек:
злодей! 242
7.6 Резюме. 245
Глава 8. Владение данными. 246
8.1 Несколько процессов. 247
8.2 Частичное владение данными и pthreads 247
8.3 Доставка функций. 248
8.4 Назначенный поток. 249
8.5 Приватизация. 249
8.6 Другие разновидности владения данными. 250
Глава 9. Отложенная обработка. 252
9.1 Пример запуска. 252
9.2 Подсчет ссылок. 255
9.3 Указатели опасности. 259
9.4 Блокировки последовательности. 267
9.5 Механизм Read-Copy-Update (RCU) 274
9.5.1 Введение в RCU.. 275
9.5.2 Основы RCU.. 285
9.5.3 API RCU ядра Linux. 297
9.5.4 Использование RCU.. 314
9.5.5 Работа, связанная с RCU.. 343
9.6 Что же выбрать?. 348
9.6.1 Что выбрать? Обзор. 348
9.6.2 Что выбрать? Подробный обзор. 350
9.6.3 Что выбрать? Использование в производстве. 354
9.7 А что насчет обновлений?. 356
Глава 10. Структуры данных. 357
10.1 Мотивирующее приложение. 357
10.2 Разделяемые структуры данных. 358
10.2.1 Дизайн хэш-таблицы. 358
10.2.2 Реализация хэш-таблицы. 359
10.2.3 Производительность хэш-таблицы. 363
10.3 Структуры данных преимущественно для чтения. 365
10.3.1 Реализация хэш-таблицы с защитой RCU.. 365
10.3.2 Проверка защищенной RCU хэш-таблицы. 367
10.3.3 Производительность защищенной RCU хэш-таблицы. 368
10.3.4 Хэш-таблицы с защитой RCU: обсуждение. 372
10.4 Неразделяемые структуры данных. 374
10.4.1 Дизайн хэш-таблицы с изменяемым размером. 374
10.4.2 Реализация хэш-таблицы с изменяемым размером. 376
10.4.3 Хэш-таблицы изменяемого размера: обсуждение. 385
10.4.4 Другие хэш-таблицы с изменяемым размером. 386
10.5 Прочие структуры данных. 390
10.6 Микрооптимизация. 392
10.6.1 Специализация. 392
10.6.2 Биты и байты. 393
10.6.3 Аппаратные соображения. 394
10.7 Резюме. 396
Глава 11. Валидация. 397
11.1 Введение. 398
11.1.1 Откуда берутся ошибки?. 398
11.1.2 Необходимый образ мышления. 400
11.1.3 Когда должна начинаться валидация?. 402
11.1.4 Путь с открытым исходным кодом. 403
11.2 Трассировка. 405
11.3 Утверждения. 406
11.4 Статический анализ. 407
11.5 Рецензирование кода. 408
11.5.1 Инспекция. 408
11.5.2 Пошаговый разбор. 409
11.5.3 Самопроверка. 409
11.6 Вероятности и гейзенбаги. 412
11.6.1 Статистика в дискретном тестировании. 413
11.6.2 Злоупотребление статистикой для дискретного тестирования. 415
11.6.3 Статистика непрерывного тестирования. 416
11.6.4 Охота на гейзенбаги. 418
11.7 Оценка производительности. 424
11.7.1 Эталонные тесты. 425
11.7.2 Профилирование. 425
11.7.3 Дифференциальное профилирование. 426
11.7.4 Микроэталонные тесты. 426
11.7.5 Изоляция. 428
11.7.6 Обнаружение помех. 429
11.8 Резюме. 434
Глава 12. Формальная верификация. 436
12.1 Поиск в пространстве состояний. 436
12.1.1 Promela и Spin. 437
12.1.2 Как использовать Promela. 443
12.1.3 Пример Promela: блокировка. 447
12.1.4 Пример Promela: QRCU.. 450
12.1.5 Promela Parable: dynticks и RCU с вытесняющим выполнением. 461
12.1.6 Проверка RCU с вытесняющим выполнением и dynticks 467
12.2 Поиск в пространстве состояний специального назначения. 496
12.2.1 Анатомия лакмусовой бумажки. 497
12.2.2 Что означает эта лакмусовая бумажка?. 499
12.2.3 Запуск лакмусовой бумажки. 500
12.2.4 Обсуждение PPCMEM.. 501
12.3 Аксиоматические подходы. 503
12.3.1 Аксиоматические подходы и блокировка. 505
12.3.2 Аксиоматические подходы и RCU.. 507
12.4 SAT-решатели. 511
12.5 Средства проверки моделей без сохранения состояния. 513
12.6 Резюме. 514
12.7 Выбор плана проверки. 516
Глава 13. Собираем все вместе. 520
13.1 Головоломки со счетчиками. 520
13.1.1 Подсчет обновлений. 520
13.1.2 Подсчет поисковых запросов. 521
13.2 Вернемся к подсчету ссылок. 521
13.2.1 Реализация категорий подсчета ссылок. 523
13.2.2 Оптимизации счетчика. 530
13.3 Помощники указателя опасности. 530
13.3.1 Масштабируемый счетчик ссылок. 530
13.4 Блокировка последовательности. 531
13.4.1 Дуэльные блокировки последовательности. 531
13.4.2 Коррелированные элементы данных. 532
13.4.3 Атомарное перемещение. 533
13.4.4 Превращение в писателя. 535
13.5 RCU спешит на помощь. 535
13.5.1 RCU и статистические счетчики на основе переменных потока. 535
13.5.2 RCU и счетчики съемных устройств ввода-вывода. 539
13.5.3 Массив и длина. 540
13.5.4 Коррелированные поля. 542
13.5.5 Удобный для обновления обход. 543
13.5.6 Масштабируемый счетчик ссылок 2. 543
13.5.7 Перезапущенные периоды простоя. 544
Глава 14. Продвинутая синхронизация. 548
14.1 Как избежать блокировки. 548
14.2 Неблокирующая синхронизация. 549
14.2.1 Простой NBS. 550
14.2.2 Применимость преимуществ NBS. 554
14.2.3 Обсуждение NBS. 557
14.3 Параллельные вычисления в реальном времени. 558
14.3.1 Что такое вычисления в реальном времени?. 558
14.3.2 Кому нужен режим реального времени?. 565
14.3.3 Кому нужен параллельный режим реального времени?. 566
14.3.4 Реализация параллельных систем реального времени. 567
14.3.5 Реализация параллельных операционных систем реального времени. 569
14.3.6 Реализация параллельных приложений реального времени. 586
14.3.7. Реальное время против реального быстрого: как выбрать?. 591
Глава 15. Продвинутая синхронизация: порядок памяти. 594
15.1 Упорядочение: зачем и как?. 595
15.1.1 Почему аппаратное обеспечение нарушает порядок?. 596
15.1.2 Как принудительно выполнить упорядочение?. 599
15.1.3 Базовые эмпирические правила. 603
15.2 Трюки и ловушки. 605
15.2.1 Переменные с несколькими значениями. 605
15.2.2 Переупорядочивание ссылок на память. 609
15.2.3 Адресные зависимости. 612
15.2.4 Зависимости данных. 615
15.2.5 Зависимости управления. 616
15.2.6 Когерентность кэша. 618
15.2.7 Атомарность множественных копий. 620
15.3 Ужасы времени компиляции. 635
15.3.1 Ограничения по ссылке на память. 636
15.3.2 Проблемы с зависимостями от адреса и от данных. 637
15.3.3. Проблемы с зависимостями управления. 642
15.4 Примитивы более высокого уровня. 648
15.4.1 Выделение памяти. 648
15.4.2 Блокировка. 649
15.4.3 RCU.. 656
15.5 Особенности аппаратного обеспечения. 670
15.5.1 Alpha. 673
15.5.2 Armv7-A/R. 677
15.5.3 Armv8. 678
15.5.4 Itanium.. 679
15.5.5 MIPS. 680
15.5.6 POWER / PowerPC. 681
15.5.7 SPARC TSO.. 683
15.5.8 x86. 684
15.5.9 z Systems 685
15.6 Где требуется упорядочение памяти?. 685
Глава 16. Простота использования. 688
16.1 Что такое «простота»?. 688
16.2 Шкала Расти при проектировании API 689
16.3 Стрижка множества Мандельброта. 690
Глава 17. Противоречивые взгляды на будущее. 693
17.1 Будущее процессорных технологий стало не таким, каким должно было. 693
17.1.1 Однопроцессорность превыше всего. 695
17.1.2 Потокомания. 695
17.1.3 Атака клонов. 696
17.1.4 Краш-тест о стену памяти. 696
17.1.5 Поразительные ускорители. 698
17.2 Транзакционная память. 698
17.2.1 Внешний мир. 699
17.2.2 Модификация процесса. 704
17.2.3 Синхронизация. 710
17.2.4 Обсуждение. 716
17.3 Аппаратная транзакционная память. 719
17.3.1 Преимущества HTM при блокировке WRT. 720
17.3.2 Слабые стороны HTM по сравнению с блокировкой. 722
17.3.3. Слабые стороны HTM по сравнению с блокировкой и не только. 731
17.3.4 Где лучше всего использовать HTM?. 735
17.3.5 Что может повлиять на ситуацию.. 736
17.3.6 Выводы. 740
17.4 Формальное регрессионное тестирование?. 741
17.4.1 Автоматический перевод. 741
17.4.2 Среда. 743
17.4.3 Накладные расходы. 743
17.4.4 Поиск ошибок. 745
17.4.5 Минимальный набор инструментов. 746
17.4.6 Релевантные ошибки. 747
17.4.7 Формальная система оценки регрессии. 748
17.5 Функциональное программирование в параллелизме. 750
17.6 Резюме. 752
Глава 18. Подведем итоги и наметим перспективы.. 753
Приложение А. Важные вопросы.. 757
А.1 Почему параллельные программы не всегда быстрее?. 757
А.2 Почему бы не убрать блокировку?. 758
А.3 Который сейчас час?. 758
А.4 Что значит «после»?. 760
А.5 Сколь сильным должно быть упорядочение?. 764
А.5.1 Где находятся определяющие данные?. 765
А.5.2 Согласованные данные используются последовательно?. 766
А.5.3 Разделяема ли задача?. 766
А.5.4 А если все это неверно?. 766
А.6 В чем разница между «конкурентным» и «параллельным»?. 767
А.7 Почему программа глючит?. 768
Приложение Б. «Игрушечные» реализации RCU.. 769
Б.1 RCU на основе блокировки. 769
Б.2 RCU на основе блокировки потока. 770
Б.3 Простой RCU на основе счетчика. 772
Б.4 RCU без голодания на основе счетчика. 774
Б.5 Масштабируемый RCU на основе счетчиков. 778
Б.6 Масштабируемый RCU на основе счетчиков с общими периодами простоя. 781
Б.7 RCU на основе автономного счетчика. 784
Б.8 RCU с вложенностью на основе автономного счетчика. 787
Б.9 RCU на основе состояний покоя. 790
Б.10 Краткий обзор «игрушечных» реализаций RCU.. 793
Приложение В. Зачем нужны барьеры памяти?. 795
В.1 Структура кэша. 795
В.2 Протоколы когерентности кэша. 798
В.2.1 Состояние MESI 798
В.2.2 Сообщения протокола MESI 799
В.2.3 Диаграмма состояний MESI 800
В.2.4 Пример протокола MESI 802
В.3 Сохранения порождают ненужные простои. 803
В.3.1 Буферы сохранения. 804
В.3.2 Переадресация хранения. 805
В.3.3. Буферы хранения и барьеры памяти. 806
В.4 Последовательности сохранения приводят к ненужным задержкам. 809
В.4.1 Очереди недействительности. 810
В.4.2 Очереди недействительности и подтверждения недействительности. 810
В.4.3 Очереди недействительности и барьеры памяти. 811
В.5 Чтение и запись барьеров памяти. 814
В.6 Примеры последовательностей барьера памяти. 815
В.6.1 Враждебная порядку архитектура. 815
В.6.2 Пример 1. 816
В.6.3 Пример 2. 817
В.6.4 Пример 3. 818
В.7 Барьеры памяти с нами навсегда?. 818
В.8 Советы разработчикам аппаратного обеспечения. 819
Приложение Г. Ответы на быстрые тесты.. 821
Г.1 Как пользоваться этой книгой. 821
Г.2 Введение. 822
Г.3 Аппаратное обеспечение и его привычки. 829
Г.4 Инструментарий. 835
Г.5 Подсчет. 845
Г.6 Разбиение на разделы и синхронизация. 868
Г.7 Блокировка. 877
Г.8 Владение данными. 889
Г.9 Отложенная обработка. 891
Г.10 Структуры данных. 915
Г.11 Проверка. 924
Г.12 Формальная верификация. 935
Г.13 Собираем все вместе. 947
Г.14 Продвинутая синхронизация. 953
Г.15 Продвинутая синхронизация: упорядочение памяти. 956
Г.16 Простота использования. 976
Г.17 Противоречивые взгляды на будущее. 977
Г.18 Важные вопросы. 987
Г.19 «Игрушечные» реализации RCU.. 988
Г.20 Зачем нужны барьеры памяти?. 998
Глоссарий. 1004
Библиография. 1014
Благодарности. 1058
Советник LATEX.. 1058
Рецензенты. 1058
Владельцы машин. 1059
Оригинальные публикации. 1059
Авторство рисунков. 1060
Прочая поддержка. 1061
Акронимы.. 1062
Предметный указатель. 1063
Указатель API 1070
-
Параллельное программирование – так ли это сложно?
2000 ₽
1420 ₽
Пол Маккинни (Paul Mckenney) — профессор, ведущий специалист по поддержке ядра Linux (функционал RCU), член комитета по стандартизации ISO SC22 WG21 (C++), один из авторов действующей в Linux модели памяти. Сфера научных интересов: технологии валидации и надёжная реализация сложных конкурентных вычислений. Более 50 лет занимается программированием, в том числе 30 лет исследует параллельное программирование. Автор более 200 публикаций и обладатель 150 патентов на различные разработки в области информатики. Является активным контрибьютором ядра Linux.