Правильное поведение параллельных программ

Вышеприведенный пример демонстрирует типичную неочевидную ошибку, которая может возникнуть в параллельной программе. Сложность здесь восходит к присваиванию переменным, разделяемым между различными процессами. Мы уже знаем, что при работе с set! требуется осторожность, потому что результаты вычислений зависят от порядка, в котором происходят присваива-ния.37 При наличии параллелизма нужно быть острожным вдвойне, поскольку не всегда можно управлять порядком, в котором присваивания происходят в разных процессах. Если несколько таких изменений могут происходить одновременно (как в случае с двумя вкладчиками, имеющими доступ к общему счету), нам требуется способ обеспечить правильную работу системы. Например, в случае со снятием денег с общего счета, мы должны сделать так, чтобы общее количество денег оставалось неизменным. Чтобы заставить параллельные программы работать корректно, иногда требуется наложить некоторые ограничения на одновременное исполнение.

Одно из возможных ограничений на параллелизм может состоять в том, что никакие две операции, способные изменить разделяемые переменные состояния, не могут исполняться одновременно. Это очень серьезное ограничение. Для распределенной банковской системы это означало бы, что проектировщик системы должен сделать так, что в каждый момент происходит не более одной транзакции. Это требование чрезмерно консервативное и ведет к неэффективности. На рисунке 3.30 показан случай с совместным счетом Петра и Павла, причем у Павла есть еще и собственный счет. Диаграмма показывает две операции снятия денег с совместного счета (одну проводит Петр, одну Павел), а также занесение Павлом денег на личный счет.38 Два снятия денег с одного счета не должны происходить одновременно (поскольку оба работают с одним счетом), и Павел не может одновременно снять деньги и занести их в банк (поскольку и та, и другая операция касаются кошелька Павла). Однако не должно быть препятствий, мешающих Павлу заносить деньги на личный счет в то время, как Петр берет деньги с общего счета.

Менее драконовское ограничение на параллелизм могло бы состоять в том, чтобы параллельная система выдавала такие же результаты, как если бы процессы происходили последовательно. У этого ограничения две важных стороны. Во-первых, от процессов на самом деле не требуется последовательного исполнения, а только результаты, совпадающие с теми, которые получались бы, если бы они работали один за другим. В примере на рис. 3.30, проектировщик банковской системы спокойно может разрешить одновременное занесение денег Павлом и снятие их Петром, поскольку общий результат будет таков, как будто бы они шли последовательно. Во-вторых, у параллельной программы может быть более одного «правильного» результата, потому что мы требуем только, чтобы он совпадал с результатом при каком-нибудь последовательном порядке. Например, предположим, что общий счет Петра и Павла вначале равен 100 долларам, Петр кладет на него 40 долларов, а Павел снимает половину имеющихся там денег. При этом последовательное исполнение может привести к

37 Программа подсчета факториала из раздела 3.1.3 демонстрирует это в рамках одного последовательного процесса.

38Столбцы показывают содержимое кошелька Петра, общий счет (в Банке 1), кошелек Павла и личный счет Павла (в Банке 2), до и после каждого снятия (W) и занесения денег на счет (D). Петр берет 10 долларов из Банка 1; Павел кладет 5 долларов в Банк 2, затем берет 25 долларов из Банка 1.

Петр

Банк1

Павел

Банк2

время

Рис. 3.30: Одновременные операции при работе с совместным счетом в Банке1 и личным счетом в Банке2.

значению на счету либо в 70, либо в 90 долларов (см. упражнение 3.38).39

Можно найти и еще более слабые требования для корректного выполнения параллельных программ. Программа, имитирующая диффузию (например, поток тепла в объекте), может состоять из большого числа процессов, каждый из которых изображает маленький участок пространства, и которые параллельно обновляют свои значения. Каждый процесс в цикле изменяет свое значение на среднее между своим собственным значением и значениями соседей. Этот алгоритм сходится к правильному ответу независимо от порядка, в котором выполняются операции; нет никакой нужды в ограничениях на параллельное использование разделяемых значений.

Упражнение 3.38.

Пусть Петр, Павел и Мария имеют общий счет, на котором вначале лежит 100 долларов. Петр кладет на счет 10 долларов, одновременно с этим Павел берет 20, а Мария берет половину денег со счета. При этом они выполняют следующие операции:

Петр: (set! balance (+ balance 10)) Павел: (set! balance (- balance 20)) Мария: (set! balance (- balance (/ balance 2)))

a. Перечислите возможные значения balance после завершения операций, предполагая, что банковская система требует от транзакций исполняться последовательно в каком-то порядке.

39Более формально это утверждение можно выразить, сказав, что поведение параллельных программ - недетерминированное (nondeterministic). То есть, они описываются не функциями с одним значением, а функциями, чьи результаты являются множествами возможных значений. В разделе 4.3 мы рассмотрим язык для выражения недетерминистских вычислений.

b. Назовите какие-нибудь другие значения, которые могли бы получиться, если бы система разрешала операциям чередоваться. Нарисуйте временные диаграммы, подобные рис. 3.29, чтобы объяснить, как возникают такие результаты.

3.4.2 Механизмы управления параллелизмом

Мы убедились, что сложность работы с параллельными процессами происходит из необходимости учитывать порядок чередования событий в различных процессах. Предположим, к примеру, что у нас есть два процесса, один с упорядоченными событиями (a,b,с), а другой с упорядоченными событиями (x,y,z). Если эти два процесса исполняются параллельно, без каких-либо дополнительных ограничений на чередование событий, то возможно 20 различных порядков событий, соблюдающих упорядочение их внутри каждого из процессов:

(a, b, с, x, y, z) (a, b, x, c, y, z) (a, b, x, y, с, z) (a, b, x, y, z, с) (a, x, b, с, y, z)

( a, x, b, y, с, z) ( a, x, b, y, z, с) ( a, x, y, b, с, z) ( a, x, y, b, z, с) ( a, x, y, z, b, с)

( x, a, b, с, y, z) ( x, a, b, y, с, z) ( x, a, b, y, z, с) ( x, a, y, b, с, z) ( x, a, y, b, z, с)

(x, a, y, z, b, с) (x, y, a, b, с, z) (x, y, a, b, z, с)

( x, y, a, x, b, с) ( x, y, x, a, b, с)

При разработке этой системы нам как программистам пришлось бы рассматривать результаты каждого из этих 20 упорядочений и проверять, что каждое из них допустимо. С ростом числа процессов и событий такой подход быстро становится нереалистичным.

Более практичный подход к проектированию параллельных систем состоит в том, чтобы придумать общие механизмы, которые бы ограничивали чередование событий в параллельных процессах и тем самым давали нам уверенность, что поведение программы верно. Для этой цели было разработано большое количество механизмов. В этом разделе мы опишем один из них - сериализатор (serializer).

Сериализация доступа к разделяемой памяти

Идея сериализации заключается в следующем: процессы выполняются параллельно, но при этом существуют определенные группы процедур, которые не могут выполняться одновременно. Выражаясь точнее, сериализация порождает выделенные множества процедур, такие, что в каждом сериализованном множестве в любой момент может происходить выполнение только одной процедуры из множества. Если какая-то процедура из множества уже выполняется, то процесс, который пытается выполнить любую процедуру из множества, будет приостановлен до тех пор, пока не закончится текущее вычисление процедуры.

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