Процессы называются параллельными, если они существуют одновременно. Параллельные процессы могут работать совершенно независимо друг от друга или они могут быть асинхронными – им необходимо периодически синхронизироваться или взаимодействовать.
Ag a
Par begin
Оператор1; оператор2; …; операторN;
Par end.
X:=(–b+(b^2–4*a*c)^0,5)/(2*a)
Par begin
R1:= –b;
R2:=b^2;
R3:=4*a;
R4:=2*a;
Par end
R5:=R3*c;
R5:=R2–R5;
R5:=R5^0,5;
R5:=R1+R5;
X:=R5/R4;
При параллельном вычислении процессам приходится обращаться к общим данным (ресурсам). Ситуации, при которых конечный результат одновременной работы с общими данными зависит оттого, кто из них был первым, называются состояниями состязания. Подобные ситуации необходимо исключать путем введения определенных правил обращения к разделяемым данным.
Если во время обращения одного процесса к совместно-используемым данным всем другим процессам это запрещается, то такой способ взаимодействия называется взаимным исключением.
Если процесс обращается к разделяемым данным, то говорят, что он находится в своем критическом участке, а часть программы, в которой есть обращение к разделяемым данным, называется критической секцией или областью. Впервые программа реализации взаимного исключения была разработана Деккером. Свойства этого алгоритма:
Var N: integer;
Procedure Процесс1;
Begin
While true do
Begin
While N=2 do;
КритическийУчасток1;
N:=2;
ПрочиеОператоры1;
end;
end;
procedure Процесс2;
begin
while true do
begin
while N=1 do;
КритическийУчасток2;
N:=1;
ПрочиеОператоры2;
End; end;
BEGIN
N:=1;
Par begin
Процесс1; Процесс2;
Par end
END.
Примитив «вход взаимного исключения» реализуется как один цикл while, который повторяется до тех пор, пока переменная «номер процесса» не станет равной номеру данного процесса. Примитив «выход» реализуется как одна команда, который устанавливает для переменной N значение, равное номеру другого процесса. Алгоритм Деккера реализует взаимного исключения для двух процессов.
1981 год – алгоритм Петерсона.
Кроме программных, существуют и аппаратные способы решения проблемы взаимоисключения. Кроме алгоритмов существуют семафоры.