Решение задачи взаимного исключения. Алгоритм Деккера
Взаимодействие процессов
Задача взаимного исключения
Если двум или более процессам необходимо взаимодействовать друг с другом, то они должны быть связаны, то есть иметь средства для обмена информацией. Предполагается, что процессы связаны слабо. Под этим подразумевается, что кроме достаточно редких моментов явной связи эти процессы рассматриваются как совершенно независимые друг от друга. В частности, не допускаются какие либо предположения об относительных скоростях различных процессов.
В качестве примера рассматривается два последовательных процесса, которые удобно считать циклическими. В каждом цикле выполнения процесса существует критический интервал. Это означает, что в любой момент времени только один процесс может находиться внутри своего критического интервала. Чтобы осуществить такое взаимное исключение, оба процесса имеют доступ к некоторому числу общих переменных. Операции проверки текущего значения такой общей переменной и присваивание нового значения общей переменной рассматриваются как неделимые. То есть, если два процесса осуществляют присваивание новое значение одной и той же общей переменной одновременно, то присваивание происходит друг за другом и окончательное значение переменной одному из присвоенных значений, но никак не их смеси. Если процесс поверяет значение переменной одновременно с присваиванием ей значения другим процессом, то первый процесс обнаруживает либо старое, либо новое значение, но никак не их смесь.
Первый вариант решения задачи взаимного исключения
Begin integer очередь;
очередь := 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;
***************************
int turn=1;
Void P0()
{
While (1)
{
while(turn!=0)
Критический интервал 1;
turn=1;
….
}
}
Void P1()
{
While (1)
{
while(turn!=1)
Критический интервал 2;
turn=0;
….
}
}
Void main()
{
Parbegin(P0,P1);
}
Недостатки решения:
1. Процессы могут входить в критический интервал строго последовательно. Темп развития процессов определяется медленным процессом.
2. Если какой-то из процессов остановится в остатке цикла, то это приведет к остановке и второго процесса.
Второйвариант решения задачи взаимного исключения
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 = 0) then goto L2;
С2 := 0;
Критический интервал 2;
С2 := 1;
Остаток цикла 2;
Goto L2;
End;
Parend;
End;
int flag[2];
Void P0()
{
While (1)
{
while (flag[1]);
flag[0]=1;
Критический интервал 1;
flag[0]=0;
….
}
}
Void P1()
{
While (1)
{
while (flag[0]);
flag[1]=1;
Критический интервал 2;
flag[1]=0;
….
}
}
Void main()
{
flag[0]=0;
flag[1]=0;
Parbegin(P0,P1);
}
Недостаток. При развитии процессов строго синхронно они могут одновременно войти в критический интервал.
Было предложено следующее решение (вариант 3)::
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;
int flag[2];
Void P0()
{
While (1)
{
flag[0]=1;
while (flag[1]);
Критический интервал 1;
flag[0]=0;
….
}
}
Void P1()
{
While (1)
{
flag[1]=1;
while (flag[0]);
Критический интервал 2;
flag[1]=0;
….
}
}
Void main()
{
flag[0]=0;
flag[1]=0;
Parbegin(P0,P1);
}
Недостаток. Бесконечно долго решается вопрос о том, кто первым войдет в критический интервал.
Решение 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;
int flag[2];
Void P0()
{
While (1)
{
flag[0]=1;
while (flag[1]);
{
flag[0]=0;
Задержка;
flag[0]=1;
}
Критический интервал 1;
flag[0]=0;
….
}
}
Void P1()
{
While (1)
{
flag[1]=1;
while (flag[0]);
{
flag[1]=0;
Задержка;
flag[1]=1;
}
Критический интервал 2;
flag[1]=0;
….
}
}
Void main()
{
flag[0]=0;
flag[1]=0;
Parbegin(P0,P1);
}
Недостаток. Бесконечно долго решается вопрос о том, кто первым войдет в критический интервал.
Решение задачи взаимного исключения. Алгоритм Деккера.