2015-08-21
499
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);
}
Решение задачи взаимного исключения. Алгоритм Деккера.
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;
|
|
|
int flag[2], turn;
void P0()
{
while (1)
{
flag[0]=1;
while (flag[1]);
{
if (turn==1)
{
flag[0]=0;
while (turn==1);
flag[0]=1;
}
}
критический интервал 1;
turn=1;
flag[0]=0;
….
}
}
void P1()
{
while (1)
{
flag[1]=1;
while (flag[0]);
{
if (turn==0)
{
flag[1]=0;
while (turn==0);
flag[1]=1;
}
}
критический интервал 2;
turn=0;
flag[1]=0;
….
}
}
void main()
{
flag[0]=0;
flag[1]=0;
turn=1;
parbegin(P0,P1);}
Решение задачи взаимного исключения. Алгоритм Пэтерсона..
int flag[2], turn;
void P0()
{
while (1)
{
flag[0]=1; turn=1;
while (flag[1] && (turn==1));
критический интервал 1;
flag[0]=0;
….
}
}
void P1()
{
while (1)
{
flag[1]=1; turn=0;
while (flag[0] && (turn==0));
критический интервал 2;
flag[1]=0;
….
}
}
void main()
{
flag[0]=0;
flag[1]=0;
parbegin(P0,P1);
}
Для доказательства корректности задачи взаимного исключения необходимо проверить три положения.
1. Решение безопасно в том смысле, что два процесса не могут одновременно оказаться в своих критических интервалах
2. В случае сомнения, кому из двух процессов первому войти в критический интервал, выяснение этого вопроса не откладывается до бесконечности
3. Остановка какого-либо из процессов в остатке цикла не вызывает блокировки другого процесса.
Обобщенная задача взаимного исключения
Даны N процессов, каждый со своим критическим интервалом. Необходимо организовать их функционирование так, чтобы в любой момент самое большее один процесс находился в критическом интервале. Для проверки правильности решения проверяем три условия.
begin integer array b, c [0..N];
integer очередь;
for очередь = 1 step 1 until N do begin
b [очередь]:= 1;
c [очередь]:= 1;
end;
очередь:= 0;
parbegin
процесс 1: begin … end;
процесс 2: begin … end;
…
процесс N: begin … end;
parend;
end;
процесс i: begin integer j, k;
Ai: b [i]:= 0;
Li: if (очередь <> i) then begin
|
|
|
С[i] = 1;
k = очередь;
if (b [k] = 1) then очередь:= i;
goto Li;
end;
C[i]:= 0;
for j:= 1 step 1 until N do
if ((j <> i) and (C[j] = 0)) then goto Li;
Критический интервал i;
очередь:= 0;
C[i]:= 1;
b[i]:= 1;
Oстаток цикла i;
goto Ai;
end;
