Лекция-16:

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

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

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

В классе мягких ресурсов выделено два типа:

• программные

• информационные

Если мягкий ресурс допускает копирование и эффект от использования ресурса-оригинала и ресурса-копии идентичен, то такой ресурс называется программным, в обратном случае – информационным. Мягкие информационные ресурсы либо принципиально не допускают копирования, либо допускают копирование, но оно является функцией времени (сообщения, сигналы, запросы на прерывание и т.д.).

Взаимодействие процессов

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

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

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

begin integer очередь;

очередь := 1;

parbegin

процесс 1: begin

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

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

очередь := 2;

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

goto L1;

end;

parend;

end;

процесс 2: begin

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

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

очередь := 1;

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

goto L2;

end;

Недостатки решения:

• процессы могут входить в критический интервал строго последовательно

• если кто-то из процессов останется в остатке цикла, то он затормозит и второй процесс

Второй способ решения:

begin integer С1,С2;

С1 := 1;

С2 := 1;

parbegin

процесс 1: begin

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

С1 := 1;

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

С1 := 0;

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

goto L1;

end;

parend;

end;

процесс 2: begin

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

С2 := 0;

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

С2 := 1;

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

goto L2;

end;

Недостаток: принципиально при развитии процессов строго синхронно они могут одновременно войти в критический интервал.

Было предложено следующее решение:

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;

parend;

end;

процесс 2: begin

А2: С2 := 0;

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

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

С2 := 1;

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

goto А2;

end;

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

Решение №4.

begin integer С1,С2;

С1 := 1;

С2 := 1;

parbegin

процесс 1: begin

L1: С1 := 0;

if (С2 = 0) then begin

C1 := 0;

goto L1;

end;

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

С1 := 1;

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

goto L1;

end;

parend;

end;

процесс 2: begin

L2: С2 := 0;

if (С1 = 0) then begin

C2 := 0;

goto L2;

end;

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

С2 := 1;

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

goto L2;

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;

parend;

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;

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

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

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

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