СПИСОК СОКРАЩЕНИЙ
ВС — вычислительная система
КС — критическая секция
МВС — многопроцессорная вычислительная система
ПЭ — процессорный элемент
DSM — distributed shared memory
PGAS — program global address space
RDMA — remote direct memory access
ACID — atomicity, consistency, isolation, durability
ГЛАВА 1. МЕТОДЫ И СРЕДСТВА БЕСКОНФЛИКТНОГО ДОСТУПА МНОГОПОТОЧНЫХ ПРИЛОЖЕНИЙ К ПАМЯТИ
В случае взаимодействия потоков многопоточного приложения посредством передачи сообщений разделяемые данные передаются в сообщении и обеспечения синхронизации по доступу к ним не требуется, т.к. в самом механизме передачи сообщений заложена неявная синхронизация: данные нельзя получить прежде, чем сообщение будет сформировано, отправлено и доставлено получателю. Однако если же потоки взаимодействуют через общую память, то в таком случае необходимы средства бесконфликтного доступа к разделяемым данным, т.к. различие в скорости выполнения потоков на разных процессорных элементах (ПЭ) ВС может привести к возникновению конфликтов по данным или гонок по данным. Можно выделить две группы методов, с помощью которых решают данную проблему: методы, основанные на предотвращении конфликтов; методы, основанные на обнаружении и устранении конфликтов по данным и их последствий. Первая группа методов, в свою очередь, делится на блокирующие (методы взаимного исключения) и неблокирующие. Вторая группа методов основана на понятии транзакции — наборе инструкций, результат выполнения которого наблюдается как неделимое атомарное действие.
Гонки по данным и последствия их возникновения
Наличие гонок в многопоточной программе может привести к недетерминированному и, возможно, некорректному поведению программы с вероятными ошибками времени выполнения.
Можно определить корректность как набор свойств программы, которые характеризуют безошибочность ее работы: будем считать, что алгоритм такой программы не содержит ошибок; при выполнении корректной программы отсутствуют ошибки времени выполнения (такие как “деление на ноль”) и ошибки, связанные с доступом к памяти (например, выход за границы массива); само выполнение корректной программы завершается за конечное число шагов (отсутствуют бесконечные циклы).
Детерминированность — свойство программы, которое характеризует воспроизводимость результатов ее работы: результат работы недетерминированной программы может отличаться от запуска к запуску при одних и тех же входных данных. Детерминированная программа в некоторых случаях может быть некорректной, а недетерминированная — корректной и удовлетворяющей требованиям разработчика. В работе [emrath] авторы охарактеризовали четыре уровня недетерминизма параллельных программ:
1. внутренний детерминизм (англ. internally determinate) — в программе, обладающей данным свойством, для каждого потока последовательность инструкций и значение их операндов всегда детерминированны, т.е. отсутствуют условия гонок, а результат работы программы при запуске с одними и теми же данными всегда одинаков;
2. внешний детерминизм (англ. externally determinate) — программа называется внешне детерминированной, если результат ее работы детерминирован, но она не обладает свойством внутреннего детерминизма. В такой программе могут существовать гонки, однако результат ее работы при запуске с одними и теми же данными всегда одинаков. Наиболее типичный пример внешне детерминированной программы — программа, в которой над общими данными производятся коммутативные и ассоциативные операции;
3. ассоциативный недетерминизм (англ. associatively non-determinate) — в ассоциативно недетерминированной программе существуют гонки между ассоциативными операциями, выполняемыми конкурирующими потоками над операндами с плавающей точкой. В силу конечности разрядной сетки для представления операндов с плавающей точкой результат программы может быть недетерминирован, т.е. такая программа является внешне недетерминированной только из-за возможных ошибок округления;
4. полный недетерминизм (англ. completely non-determinate) — программа, которую нельзя отнести ни к одному из первых трех уровней недетерминизма, является полностью недетерминированной. Результат работы таких программ недетерминирован, и диапазон значений результирующих переменных зависит не от самих операций, выполняемых потоками над общими данными, а от времени их выполнения.
Различают гонки двух видов [netzer]:
1. общие гонки (англ. general races) — являются причиной недетерминированного выполнения разработанной ожидаемо детерминированной программы, что может, но не обязательно, приводить к ошибкам времени выполнения, т.е. некорректному поведению программы;
2. гонки по данным (англ. data races) — возникают в результате нарушения условия неделимости (атомарности) выполнения критических секций (КС) — участков кода, в которых происходит доступ к разделяемым данным, и зачастую являются причиной некорректного выполнения разработанной ожидаемо недетерминированной программы.
Условия гонок, о которых говорится в описанной выше классификации недетерминизма параллельных программ, относятся к типу общих гонок. Однако, учитывая существование другого вида гонок (по данным), можно расширить данную классификацию, разделив класс полностью недетерминированных программ на два подкласса [netzer]: полностью недетерминированные программы с общими гонками; полностью недетерминированные программы с гонками по данным.
Изначально корректная последовательно выполняемая программа при параллельном выполнении ее частей может стать некоректной из-за наличия гонок по данным, которые являются причиной возникновения конфликтов по данным. Гонки возникают при параллельном доступе к памяти нескольких потоков одновременно и на чтение, и на запись. В такой ситуации возможно чтение любым потоком программы значений переменных, не согласованных со значениями других используемых (как правило, ранее считанных) переменных. Можно сказать, что в случае наличия гонок по данным потоки программы могут получить доступ к памяти с несогласованным состоянием или к несогласованному слепку/снапшоту (англ. snapshot) [afek] памяти. Чтение такого состояния памяти называют несогласованным чтением (англ. inconsistent read). К примеру, поток программы может вычислять арифметическое выражение вида 1/(y−x) в предположении, что y никогда не равно x. Тогда при наличии ситуации гонок возможно несогласованное чтение, при котором y будет равен x, что приведет к ошибке времени выполнения, т.е. некорректному выполнению (см. пример на рис. 1.1).
Рис. 1.1. Иллюстрация ситуации несогласованного чтения: а) поток p1 считывает значения y, z из снапшота S1; б) далее p1 считывает значение x из снапшота S2, созданного потоком p2 уже после первого чтения p1
Основной причиной как недетерминизма, так и некорректного выполнения программ, является возможное чередование (англ. interleaving) во времени инструкций, выполняемых несколькими потоками.
Таким образом, наличие условий гонок в паралленой программе P означает наличие двух типов зависимости между двумя любыми наборами I1, I2 этой программы: временной — параллельное выполнение I1 ‖ I2 и зависимости по данным — наличие истинной, выходной или антизависимости [kuck]. Следовательно, чтобы избежать возможности возникновения конфликтов, необходимо устранить чередования (т.е. тем самым упорядочить) зависимых частей или блоков инструкций наборов I1 и I2. Достигается такое упорядочение с помощью методов и средств бесконфликтного доступа к памяти или механизмов синхронизации.
