Критическая секция - это участок кода, в котором поток получает доступ к ресурсу, который доступен из других потоков. При параллельном программировании одновременный доступ к общим ресурсам может привести к неожиданному или ошибочному поведению программы, поэтому части программы, в которых имеется доступ к общему ресурсу защищаются специальной секцией. Этот защищенная секция называется критической секцией. Она не может выполняться несколькими процессами. Как правило, критическая секция обращается к общему ресурсу, например, структуре данных, периферийному устройству или сетевому соединению, которые не будут работать корректно в контексте нескольких одновременных доступов.
3.2 Гонки данных
В критической секции код требует монопольного доступа к каким-то общим данным (ресурсам), которые не должен быть одновременно использованы более чем одним потоком исполнения. При нахождении в критической секции более одного процесса возникает состояние «гонки». Состояние гонки возникает тогда, когда несколько потоков многопоточного приложения пытаются одновременно получить доступ к данным, причем хотя бы один поток выполняет запись. Состояния гонки могут давать непредсказуемые результаты, и зачастую их сложно выявить. Причины появления: всевозможные ошибки, от неправильной установки семафоров до ошибок, связанных с относительными приоритетами работы потоков (приоритеты при отладке и в реальной работе могут отличаться); Ошибки оптимизаторов (переупорядочивание инструкций).
Во избежание данной ситуации необходимо выполнение условий:
• При нахождении в критической секции более одного процесса возникает состояние «гонки».
• Два процесса не должны одновременно находиться в критических областях.
• В программе не должно быть предположений о скорости или количестве процессоров.
• Процесс, находящийся вне критической области, не может блокировать другие процессы.
• Невозможна ситуация, в которой процесс вечно ждет попадания в критическую область.
3.3 Примитивы синхронизации
Чтобы избежать гонки данных, существуют примитивы синхронизации:
• Семафоры
• Мьютексы
• Фьютексы
• Спинлоки
• Условные переменные
• Мониторы
• Барьеры
• Неблокирующая синхронизация
3.3.1 Семафор
Семафор - объект, ограничивающий количество потоков, которые могут войти в заданный участок кода. Определение введено Эдсгером Дейкстрой.
Определены следующие операции: инициализация (задать начальное значение счетчика), захват семафора (ждать пока счётчик станет больше 0, после этого уменьшить счётчик на единицу. Соответствует опусканию семафора), освобождение семафора (увеличить счётчик на единицу. Соответствует поднятию семафора). Если семафор закрыт (процессом 1, с помощью операции P(S)), то процесс 2, вызвавший операцию, ждет, пока семафор откроется (процессом 1, с помощью операции V(S)). Выполнение операций, не может быть прервано. Если одной и той же критической секции достигли несколько процессов, то они образуют очередь к семафору.
Простейшим семафором является двоичный семафор, который может принимать лишь два состояния - 0 и 1. Иногда двоичный семафор называют мьютексом (mutex - сокращение от mutual exclusion).
3.3.2 Мьютекс
Мьютекс - аналог одноместного семафора. Мьютекс отличается от семафора тем, что только владеющий им поток может его освободить, т.е. перевести в отмеченное состояние. Они реализованы во многих ОС. Существует множество видов мьютексов, перечислю общие для всех и специфические.
Общие:
· Обычные мьютексы без повторного захвата тем же потоком.
· Мьютексы со счетчиком захватов.
С++ (с 17 стандарта):
· mutex -- нет контроля повторного захвата тем же потоком;
· recursive_mutex -- повторные захваты тем же потоком допустимы, ведётся счётчик таких захватов;
· timed_mutex -- нет контроля повторного захвата тем же потоком, поддерживается захват мьютекса с тайм-аутом;
· recursive_timed_mutex -- повторные захваты тем же потоком допустимы, ведётся счётчик таких захватов, поддерживается захват мьютекса с тайм-аутом.
· shared_mutex - можно захватывать мьютекс для совместного владения несколькими потоками только для чтения данных.
Windows:
· FAST_MUTEX - в Windows называется критической секцией, выполняет те же функции, что и мьютекс. Между мьютексом и критической секцией есть терминологические различия, так процедура, аналогичная захвату мьютекса, называется входом в критическую секцию, снятию блокировки мьютекса -- выходом из критической секции.
Процедура входа и выхода из критических секций обычно занимает меньшее время, нежели аналогичные операции мьютекса, что связано с отсутствием необходимости обращаться к ядру ОС.
Разница между мьютексом и критической секцией в том, что мьютекс является объектом ядра и может быть использован несколькими процессами одновременно, критическая секция же принадлежит процессу и служит для синхронизации только его потоков.
Linux:
· Фьютекс - вариант реализации в Linux.
· PTHREAD_MUTEX_ERRORCHECK -- повторные захваты тем же потоком вызывают немедленную ошибку.
3.3.3 Спинлок
Спинлок - процесс, который достиг критической секции, занятой другим процессом, переходит в состояние спин-блокировки. В это время он непрерывно и с максимальной скоростью опрашивает состояние семафора, т.е. продолжает пытаться захватить ресурс, даже если ресурс блокирован. Таким образом, время ожидания снижается. Это приводит, во-первых, к напрасной трате времени соответствующего процессора, а, во-вторых, накладывает значительную нагрузку на коммуникационную сеть и память, снижая тем самым скорость работы остальных процессоров.
3.3.4 Условные переменные
Условные переменные - примитив синхронизации, обеспечивающий блокирование одного или нескольких потоков до момента поступления сигнала от другого потока о выполнении некоторого условия или до истечения максимального промежутка времени ожидания. Используется при реализации модели Producer-Consumer, где Producer - поток-производитель - выполняет некоторый «заказ» (например, увеличивает переменную до некоторого максимума), сигнализирует потоку потребителю о степени выполнения. Тот в свою очередь блокируется, пока не выполнен «заказ». При получении сигнала о готовности, Consumer потребляет ресурс (например, уменьшает переменную) до определенного минимума.3.3.5 Монитор
Монитор - механизм взаимодействия и синхронизации процессов, обеспечивающий доступ к неразделяемым ресурсам. Подход к синхронизации двух или более компьютерных задач.
Монитор состоит из:
· набора процедур, взаимодействующих с общим ресурсом
· мьютекса
· переменных, связанных с этим ресурсом
· инварианта, который определяет условия, позволяющие избежать состояние гонки
Процедура монитора захватывает мьютекс перед началом работы и держит его или до выхода из процедуры, или до момента ожидания условия (см. ниже). Если каждая процедура гарантирует, что перед освобождением мьютекса инвариант истинен, то никакая задача не может получить ресурс в состоянии, ведущем к гонке.
3.3.6 Барьер
Барьер - метод синхронизации в распределённых вычислениях, при котором выполнение параллельного алгоритма или его части можно разделить на несколько этапов, разделённых барьерами. Барьер для группы потоков (или процессов) в исходном коде означает, что каждый поток (процесс) должен остановиться в этой точке и подождать достижения барьера всеми потоками (процессами) группы. Когда все потоки (процессы) достигли барьера, их выполнение продолжается.
3.3.7 Неблокирующая синхронизация
Однако все перечисленные ранее методы синхронизации являются блокирующими. Ожидание потоков увеличивает время работы программы. Однако существует метод, который не использует подобные примитивы. Неблокирующая синхронизация - подход в параллельном программировании, в котором не используются примитивы блокировки. Разделение доступа между потоками идёт за счёт атомарных операций и специальных, разработанных под конкретную задачу механизмов блокировки. Разделение доступа между потоками идёт за счёт атомарных операций и специальных, разработанных под конкретную задачу механизмов блокировки.
3 уровня синхронизации:
· Без препятствий. Поток не встречает препятствий со стороны потоков во время выполнения задания.
· Без блокировок. Для алгоритмов без блокировок гарантируется системный прогресс по крайней мере одного потока. Например, поток, выполняющий операцию «сравнение с обменом» в цикле, теоретически может выполняться бесконечно, но каждая его итерация означает, что какой-то другой поток совершил прогресс, то есть система в целом совершает прогресс.
· Без ожидания. Алгоритм работает без ожиданий, если каждая операция выполняется за определённое количество шагов, не зависящее от других потоков.
Примеры реализации неблокирующей синхронизации:
· Сравнение с обменом (CAS - compare and swap) - сравнивает значение в памяти с одним из аргументов (старым значением). Если значение равно старому, то записывается новое значение.
· RCU (Read-Copy-Update) - Вместо изменения уже существующих данных, писатель создаёт их копию, меняет её, а затем атомарно обновляет указатель на структуру данных.
4. Технологии параллельных вычислений
Существует возможность вычислять не только на CPU, но и на графических процессорах (GPU).
4.1 CUDA
CUDA - программно-аппаратная архитектура параллельных вычислений, которая позволяет существенно увеличить вычислительную производительность благодаря использованию графических процессоров. Для работы с этой платформой необходимо иметь видеокарту от Nvidia и установить CUDA SDK соответствующей версии. Модель памяти - существует сетка - грид, которая состоит из блоков, содержащие потоки. CUDA Toolkit 3.0 содержит поддержку OpenCL.
4.2 OpenCL
OpenCL - фреймворк для написания компьютерных программ, связанных с параллельными вычислениями на различных графических и центральных процессорах, а также FPGA. Является открытым стандартом (в отличие от CUDA). Цель OpenCL состоит в том, чтобы дополнить открытые отраслевые стандарты для трёхмерной компьютерной графики и звука OpenGL и OpenAL возможностями GPU для высокопроизводительных вычислений.
4.3 OpenACC
OpenACC -- программный стандарт для параллельного программирования, разрабатываемый совместно компаниями Cray, CAPS, Nvidia и PGI. Стандарт описывает набор директив компилятора, предназначенных для упрощения создания гетерогенных параллельных программ, задействующих как центральный, так и графический процессор.
4.4 OpenMP
OpenMP (Open Multi-Processing) -- открытый стандарт для распараллеливания программ. Состоит из набора директив компилятора и библиотечных функций. Позволяет достаточно легко создавать многопоточные приложения на С/С++, Fortran. Поддерживается производителями аппаратуры (Intel, HP, SGI, Sun, IBM), разработчиками компиляторов (Intel, Microsoft, KAI, PGI, PSR, APR, Absoft).
C++ Accelerated Massive Parallelism (сокращенно C++ AMP) -- библиотека, использующая DirectX 11, и открытая спецификация, созданные Microsoft для реализации параллельных программ для гибридных систем на языке C++. Система C++AMP позволяет переносить вычисления на GPU (видеоускорители) без внесения большого количества изменений в программы. Код, который не может запуститься на GPU, например, из-за своей сложности, будет автоматически запущен на центральном процессоре с применением SIMD (SSE) инструкций.
Все представленные технологии поддерживают С, С++, Fortran (Кроме C++AMP).
Заключение
Для эффективного использования высокопроизводительных систем необходимо их эффективно программировать. Одного языка программирования недостаточно для многопроцессорных комплексов, если они выполняют одну программу. Необходимо уметь программировать и обмены данными между процессами одной задачи. Также возникнут вопросы контроля обмена, взаимной синхронизации. Представленная лекция освещает некоторые вопросы параллельных вычислений, особенности реализации программ и современные технологии для вычислений, производимых на графических процессорах (GPU).
Список литературы
1. Распределенные и параллельные вычисления/Введение -- Викиучебник [Электронный ресурс]. - Викиучебник. URL: https://ru.wikibooks.org/wiki/%D0%A0%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B8_%D0%BF%D0%B0%D1%80%D0%B0%D0%BB%D0%BB%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F/%D0%92%D0%B2%D0%B5%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5
2. Типы параллелизма Параллелизм на уровне битов [Электронный ресурс]. - Файловый архив для студентов. StudFiles. URL: https://studfiles.net/preview/4083810/page:15/
3. Processes and Threads - Windows applications [Электронный ресурс]. - Техническая документация, материалы по API и примеры кода. URL: https://docs.microsoft.com/en-us/windows/desktop/procthread/processes-and-threads
4. Таненбаум Эндрю С, Бос Херберт. Современные операционные системы. 4-е изд. . - СПб: Питер, 2015. - 1120 с.: ил.