Неделимые действия и операторы ожидания
Как упоминалось выше, выполнение параллельной программы можно представить как чередование неделимых действий, выполняемых отдельными процессами. При взаимодействии процессов не все чередования допустимы. Цель синхронизации — предотвратить нежелательные чередования. Это осуществляется путем объединения мелкомодульных неделимых операций в крупномодульные (составные) действия или задержки выполнения процесса до достижения программой состояния, удовлетворяющего некоторому предикату. Первая форма синхронизации называется взаимным исключением; вторая — условной синхронизацией. В данном разделе рассмотрены аспекты неделимых действий и представлена нотация для определения синхронизации.
2.4.1. Мелкомодульная неделимость
Напомним, что неделимое действие выполняет неделимое преобразование состояния. Это значит, что любое промежуточное состояние, которое может возникнуть при выполнении этого действия, не должно быть видимым для других процессов. Мелкомодульное недели-
Глава 2. Процессы и синхронизация 57
мое действие — это действие, реализуемое непосредственно аппаратным обеспечением, на котором выполняется программа.
В последовательной программе неделимыми оказываются операторы присваивания, поскольку при их выполнении нет промежуточных состояний, видимых программе (за исключением, возможно, случаев, когда происходит ошибка, определяемая аппаратным обеспечением). Однако в параллельных программах оператор присваивания не является неделимым действием, поскольку он может быть реализован в виде последовательности мелкомодульных машинных инструкций. В качестве примера рассмотрим следующую программу и предположим, что мелкомодульные неделимые действия — это чтение и запись переменных.
int у = 0, z = 0;
со х = y+z; // у = 1; z = 2; ос;
Если выражение х = y+z реализовано загрузкой значения у в регистр и последующим прибавлением значения z, то конечными значениями переменной х могут быть 0,1,2 или 3.
Это про исходит потому, что мы можем получить как начальные значения у и z, так и их конечные значения или некоторую комбинацию, в зависимости от степени выполнения второго процесса. Еще одна особенность приведенной программы в том, что конечным значением х может быть и 2, хотя невозможно остановить программу и увидеть состояние, в котором сумма y+z имеет значение 2. Предполагается, что машины обладают следующими характеристиками.
• Значения базовых типов (например int) хранятся в элементах памяти (например словах), которые считываются и записываются неделимыми операциями.
• Значения обрабатываются так: их помещают в регистры, там к ним применяют операции и затем записывают результаты обратно в память.
• Каждый процесс имеет собственный набор регистров. Это реализуется или путем предоставления каждому процессу отдельного набора регистров, или путем сохранения и восстановления значений регистров при выполнении различных процессов. (Это называется переключением контекста, поскольку регистры образуют контекст выполнения процесса.)
• Любые промежуточные результаты, появляющиеся при вычислении сложных выражений, сохраняются в регистрах или областях памяти, принадлежащих исполняемому процессу, например, в его стеке.
В этой модели машины, если выражение е в одном процессе не обращается к переменной, измененной другим процессом, вычисление выражения всегда будет неделимой операцией, даже если для этого необходимо выполнить несколько мелкомодульных действий. Это происходит потому, что при вычислении выражения е ни одно значение, от которого зависит е, не изменяет своего значения, и ни один процесс не может видеть временные значения, которые создаются при вычислении выражения. Аналогично, если присваивание х = е в одном процессе не ссылается на переменные, изменяемые другим процессом (например, ссылается только на локальные переменные), то выполнение присваивания будет неделимой операцией.
К сожалению, многие операторы в параллельных программах, ссылающиеся на разделяемые переменные, не удовлетворяют этим условиям непересекаемости.
Однако часто выполняются более мягкие условия.
(2.2) Условие "не больше одного". Критической ссылкой в выражении называется ссылка на переменную, изменяемую другим процессом. Предположим, что любая критическая ссылка — это ссылка на простую переменную, которая хранится в элементе памяти и может быть считана и записана автоматически. Оператор присваивания х = е удовлетворяет условию "не больше одного", если либо выражение е содержит не больше одной критической ссылки, а переменная х не считывается другим процессом, либо выражение е не содержит критических ссылок, а другие процессы могут считывать переменную х.
58 Часть 1 Программирование с разделяемыми переменными
Это условие называется "не больше одного", поскольку в таком случае возможна только одна разделяемая переменная, и на нее ссылаются не более одного раза. Аналогичное определение применяется к выражениям, которые не являются операторами присваивания. Такое выражение удовлетворяет условию "не больше одного", если содержит не более одной критической ссылки.
Если оператор присваивания удовлетворяет требованиям условия "не больше одного", то выполнение оператора присваивания будет казаться неделимой операцией, поскольку одна-единственная разделяемая переменная в выражении будет записываться или считываться только один раз. Например, если выражение е не содержит критических ссылок, а переменная х — простая переменная, читаемая другими процессами, то они не могут распознать, вычисляется ли выражение неделимым образом. Аналогично, если е содержит одну критическую ссылку, то процесс, выполняющий присваивание, не сможет различить, каким образом изменяется значение переменной; он увидит только некоторое конечное значение.
Чтобы пояснить определение условия "не больше одного", приведем несколько примеров. В следующей программе оба присваивания удовлетворяют этому условию. int х = О, у = 0; со х = х+1; // у = у+1; ос;
Здесь нет критических ссылок ни в один процесс, поэтому конечным значением и х, и у будет 1. Оба присваивания в следующей программе также удовлетворяют условию. int х = 0, у = 0; со х = у+1; // у = у+1; ос;
•Первый процесс ссылается на у (одна критическая ссылка), но переменная х не читается вторым процессом, и во втором процессе нет критических ссылок. Конечным значением переменной х будет или 1, или 2, а конечным значением у — 1. Первый процесс увидит переменную у или перед ее увеличением, или после, но в параллельной программе он никогда не знает, какое из значений он видит, поскольку порядок выполнения программы недетерминирован.
В следующем примере ни одно присваивание не соответствует требованию "не больше одного".
int х = 0, у = 0;
со х = у+1; // у = х+1; ос;
Выражение в каждом процессе содержит критическую ссылку, и каждый процесс присваивает значение переменной, считываемой другим процессом. Действительно, конечными значениями переменных х и у могут быть 1 и 2, 2 и 1, или даже 1 и 1 (если процессы считывают значения переменных х и у до присвоения им значений). Однако, поскольку каждое присваивание ссылается только один раз и только на одну переменную, изменяемую другим процессом, конечными будут те значения, которые действительно существовали в некотором состоянии. Это отличается от примера, приведенного ранее, в котором выражение y+z ссылалось на две переменные, изменяемые другим процессом.
2.4.2. Задание синхронизации: оператор ожидания
Возможно, выражение или оператор присваивания не удовлетворяет условию "не больше одного", однако необходимо выполнить его как неделимое. В более общем случае в одном неделимом действии необходимо выполнить последовательность операторов. В любом случае нужен механизм синхронизации, позволяющий задать крупномодульное неделимое действие, — последовательность мелкомодульных неделимых операций, которая выглядит как неделимая.
В качестве конкретного примера представим, что база данных содержит два значения х и у, которые всегда должны быть одинаковы в том смысле, что ни один процесс, использующий базу данных, не должен видеть состояния, в котором х и у различаются. Следовательно, если процесс изменяет х, он должен изменить и у в том же самом неделимом действии.
Еще один пример: пусть один процесс вставляет элементы в очередь, представленную связанным списком. Другой процесс удаляет элементы из списка при условии, что они там есть.
Глава 2. Процессы и синхронизация 59
Одна переменная указывает на начало списка, а другая — на его конец. Вставка и удаление элементов требуют обработки двух значений. Например, для вставки элемента нужно изменить ссылку в предыдущем элементе и указатель конца списка так, чтобы они указывали на новый элемент. Если в списке содержится только один элемент, одновременные вставка и удаление могут вызвать конфликт и привести список к непригодному для использования состоянию. Таким образом, вставка и удаление элемента должны быть неделимыми действиями. К тому же, если список пуст, необходимо отложить выполнение операции удаления до того, как в список будет вставлен элемент.
Неделимые действия задаются с помощью угловых скобок (и}. Например, <е) указывает, что выражение е должно быть вычислено неделимым образом.
Синхронизация определяется с помощью оператора await:
(2.3) (await (В) S;>
Булево выражение В задает условие задержки (delay condition), as— это список последовательных операторов, завершение которых гарантированно (например, последовательность операторов присваивания). Оператор await заключен в угловые скобки для указания, что он выполняется как неделимое действие. В частности, выражение В гарантированно имеет значение "истина"6, когда начинается выполнение S, и ни одно.промежуточное состояние в s не видно другим процессам.
Например, выполнение кода
(await (s > 0) s = s-1;)
откладывается до момента, когда значение s станет положительным, а затем оно уменьшается на 1. Гарантируется, что перед вычитанием значение s положительно.
Оператор await является очень мощным, поскольку может быть использован для определения любых крупномодульных неделимых действий. Это делает его удобным для выражения синхронизации, поэтому будем использовать оператор await для разработки первоначальных решений задач синхронизации. Вместе с тем, выразительная мощность оператора await делает очень дорогой его реализацию в общей форме. Однако, как показано в этой и нескольких последующих главах, существует множество частных случаев оператора await, допускающих эффективную реализацию. Например, последний приведенный выше оператор await является частным случаем операции Р над семафором s (см. главу 4).
Общая форма оператора await определяет как взаимное исключение, так и синхронизацию по условию. Для определения только взаимного исключения можно использовать сокращенную форму оператора await:
<S;>
Например, в следующем операторе значения х и у увеличиваются в неделимом действии: (х = х+1; у * у+1;>
Промежуточное состояние, в котором х была увеличена на единицу, а у — еще нет, по определению не будет видимым для других процессов, ссылающихся на переменные х или у. Если последовательность s — это одиночный оператор присваивания, удовлетворяющий условию (2.2) "не больше одного", или если последовательность s реализована одной машинной инструкцией, то s будет выполнена как неделимая; таким образом, (S;) имеет тот же эффект, что и S. Для задания только условной синхронизации сократим оператор await так:
(await (B);>
Например, следующим оператором выполнение процесса откладывается до момента, когда значение переменной count станет положительным.
(await (count > 0);) 6 Условие задержки лучше было бы называть условием окончания задержки. — Прим.
ред.
60 Часть 1. Программирование с разделяемыми переменными
Если выражение в удовлетворяет условию "не больше одного", как в данном примере, то выражение (await (В) ;) может быть реализовано как
while (not В);
Это пример так называемого цикла ожидания (spin loop). Тело оператора while пусто, поэтому он просто зацикливается до тех пор, когда значением в станет "ложь".
Безусловное неделимое действие — это действие, которое не содержит в теле условия задержки в. Такое действие может быть выполнено немедленно, конечно, в соответствии с требованием неделимости его выполнения. Аппаратно реализуемые (мелкомодульные) действия, выражения в угловых скобках и операторы await, в которых условие опущено или является константой "истина", являются безусловными неделимыми действиями.
Условное неделимое действие — это оператор await с условием В. Такое действие не может быть выполнено, пока условие в не станет истинным. Если в ложно, оно может стать истинным только в результате действий других процессов. Таким образом, процесс, ожидающий выполнения условного неделимого действия, может оказаться задержанным непредсказуемо долго.
