Задача взаимного исключения

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

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

Варианты решения:

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);

}

Недостаток: возникает другая проблема – может бесконечно долго решаться вопрос о том, кто первым войдет в критический интервал.