Асинхронные параллельные процессы. Пример параллельных процессов

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

Пример параллельных процессов

Предположим нам необходимо вычислить один корень квадратного уравнения по формуле:

X:=( -B + (B**2 - 4*A*C)**.5)/(2*A)

Этот оператор присваивания можно вычислить при помощи последовательного процессора следующим образом:

1 B**2

2 4*A

3 (4*A)*C

4 (B**2)-(4*A*C)

5 (B**2-4*A*C)**.5

6 -B

7 (-B)+((B**2-4*A*C)**.5)

8 2*A

9 (-B+(B**2-4*A*C)**.5)/(2*A)

Здесь каждая из девяти указанных операций выполняется в последовательности, определяемой принятыми в системе правилами предшествования операторов.

А в системе, предусматривающей параллельную обработку, данное выражение может быть вычислено с использованием парных операторов параллелизма следующим образом:

1 ParBegin

temp1:= -b;   temp2:= b**2; temp3:= 4*a; temp4:= 2*a;

ParEnd

2 temp5:=temp3 * c;

3 temp5:=temp2 - temp5;

4 temp5:= temp5 ** .5;

5 temp5:=temp1 + temp5;

6 x:= temp5 / temp4;

Здесь четыре операции, входящие в конструкцию ParBegin/ParEnd, выполняются параллельно, а остальные пять операций по-прежнему приходистя выполнять последовательно. Параллельное выполнение вычислений дает возможность значительно уменьшить реальное время решения задачи.

Взаимоисключение

Рассмотрим систему, обслуживающую в режиме разделения времени много терминалов, от которых периодически поступают сообщения. Учет этих сообщений ведется при помощи отдельного процесса для каждого терминала а также с помощью глобальной переменной ПРИНЯТО_СООБЩЕНИЙ. Рассмотрим, что произойдет, если два процесса попытаются одновременно увеличить на 1 значение этой переменной.

Допустим, что каждый процесс увеличивает на 1 значение переменной ПРИНЯТО_СООБЩЕНИЙ при помощи собственного участка кода следующего вида:

LOAD   ПРИНЯТО_СООБЩЕНИЙ

ADD     1

STORE ПРИНЯТО_СООБЩЕНИЙ

Пусть в данный момент переменная ПРИНЯТО_СООБЩЕНИЙ имеет значение 5. Предположим теперь, что первый процесс выполняет команды LOAD и ADD, после чего в регистре оказывается значение 6. Затем этот процесс ввиду истечения кванта времени уступает процессор другому процессу. Второй процесс выполняет все три команды, устанавливая значение переменной ПРИНЯТО_СООБЩЕНИЙ в 6. Затем второй процесс возвращает управление первому процессу, который продолжает свое выполнение и также помещает значение 6 в переменную ПРИНЯТО_СООБЩЕНИЙ. Система в сущности теряет одно сообщение - правильная общая сумма должна быть равна 7. Эту задачу можно решить, если каждому процессу предоставлять монопольное, исключительное право доступа к этой переменной. Когда один процесс увеличивает эту разделяемую переменную, всем остальным процессам, которым нужно было бы также произвести приращение в то же самое время, придется ждать, а когда данный процесс закончит свое обращение к переменной, будет разрешено продолжить работу одному из процессов, находящихся в состоянии ожидания. Таким образом, каждый процесс, обращающийся к разделяемым данным, исключает для всех других процессов возможность одновременного с ним обращения к этим данным. Это называется взаимоисключением.

Критические участки

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

Очевидно, что в случае, если один процесс находится в своем критическом участке, необходимо исключить возможность вхождения для всех других процессов (по крайней мере для тех, которые обращаются к тем же самым разделяемым данным) в их критические участки.

Обеспечение взаимоисключения является одной из ключевых проблем параллельного программмирования. Было предложено много способов решения этой проблемы - программные и аппаратные; частные, низкоуровневые и глобальные, высокоуровневые; одни из предложенных способов предусматривают свободное взаимодействие между процессами, а другие требуют строгого соблюдения жестких протоколов.

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

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

Примитивы исключения

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

Реализация примитивов взаимоисключения

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

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