Неделимые действия и операторы ожидания

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

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 с условием В. Такое действие не может быть выполнено, пока условие в не станет истинным. Если в ложно, оно может стать истинным только в результате действий других процессов. Таким образом, процесс, ожидающий выполне­ния условного неделимого действия, может оказаться задержанным непредсказуемо долго.


Содержание раздела

---