Взаимодействие процессов Задача взаимного исключения

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

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

Первый подход к решению задачи взаимного исключения:

begin

Integer очередь;

oчередь : = 1;

parbegin

процесс1: begin

L1 : if(очередь=2)then goto L1;

критический интервал 1;

очередь : = 2;

остаток цикла 1;

goto L1;

end;

процесс2: begin

L2 : if(очередь=1)then goto L2;

критический интервал 2;

очередь : = 1;

остаток цикла 2;

goto L2;

end;

parend;

end.

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

Недостатки такой организации взаимодействия:

- строгая очерёдность вхождения в критический интервал;

- остановка любого из процессов в остатке цикла приводит к остановке и другого процесса.

Был предложен второй способ решения:

begin integer С1,С2;

С1 := 1;С2 := 1;

parbegin

процесс 1: begin

L1: if (С2 = 0) then goto L1;

С1 := 0;

критический интервал 1;

С1 := 1;

остаток цикла 1;

goto L1;

end;

процесс 2: begin

L2: if (С1 = 1) then goto L2;

С2 := 0;

критический интервал 2;

С2 := 1;

остаток цикла 2;

goto L2;

end;

parend;

end;

Здесь используются две целочисленные переменные С1 и С2 соответственно для 1-го и 2-го процессов. Если какая-то из переменных равна нулю, значит, соответствующий процесс находится в своём критическом интервале, иначе – вне критического интервала.

Недостаток:

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

Предложен третий вариант:

begin integer С1,С2;

С1 := 1;С2 := 1;

parbegin

процесс 1: begin

А1: С1 := 0;

L1: if (С2 = 0) then goto L1;

критический интервал 1;

С1 := 1;

остаток цикла 1;

goto А1;

end;

процесс 2: begin

А2: С2 := 0;

L2: if (С1 = 0) then goto L2;

критический интервал 2;

С2 := 1;

остаток цикла 2;

goto А2;

end;

parend;

end;

В данном варианте возможна ситуация, когда при одновременном начале работы процессы не смогут войти в критический интервал. Решение вопроса о том, кому первому войти в интервал, откладывается до бесконечности.

4-ый вариант:

begin integer С1,С2;

С1 := 1;С2 := 1;

parbegin

процесс 1:

begin

L1: С1 := 0;

if (С2 = 0) then

begin

C1 := 1;

goto L1;

end;

критический интервал 1;

С1 := 1;

остаток цикла 1;

goto L1;

end;

процесс 2:

begin

L2: С2 := 0;

if (С1 = 0) then

begin

C2 := 1;

goto L2;

end;

критический интервал 2;

С2 := 1;

остаток цикла 2;

goto L2;

end;

parend;

end;

Наиболее корректный вариант №5.

begin integer С1,С2,очередь;

С1 := 1; С2 := 1; очередь := 1;

parbegin

процесс 1:

begin

А1: С1 := 0;

L1: if (С2 = 0) then

begin

if (очередь = 1) then goto L1;

C1 := 1;

B1: if (очередь = 2) then goto B1;

goto А1;

end;

критический интервал 1;

очередь := 2;

С1 := 1;

остаток цикла 1;

goto А1;

end;

процесс 2:

begin

А2: С2 := 0;

L2: if (С1 = 0) then

begin

if (очередь = 2) then goto L2;

C2 := 1;

B2: if (очередь = 1) then goto B2;

goto А2;

end;

критический интервал 2;

очередь := 1;

С2 := 1;

остаток цикла 2;

goto А2;

end;

parend;

end;

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

Для проверки корректности решения задачи взаимного исключения необходимо доказать три положения:

1. Решение безопасно в том смысле, что два процесса никогда не могут одновременно оказаться в своих критических интервалах;

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

3. Остановка какого-либо из процессов вне критического интервала (в остатке цикла) не вызывает блокировки другого процесса.