Экзаменационные билеты. MPI теория

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

V-операция выполняет увеличение значения семафора на единицу.

Данные операции рассматриваются как неделимые.

Если семафор может принимать значения 0 или 1, то он называется двоичным, иначе – общим.

Пример использования семафоров для циклических процессов с критической секцией:

Begin

Semaphore free:=1;

Parbegin

Pi:Li: begin

P(free);

{ do something critical };

V(free);

{ do some };

goto Li;

end;

parend;

end.

Вопрос 14 Понятие дедлока. Необходимые условия дедлока. Привести пример сети Петри, допускающей дедлок.

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

Необходимые условия дедлока.

1. Наличие неразделённого ресурса

2. дозахват ресурса

3. не допускается временное освобождение ресурса

Пример сети, допускающей дедлок.

Ситуация дедлока возникает при следующей последовательности срабатываний переходов сети: t₁, t₄, t₂,t₅. И в этом состоянии имеем дедлок: ни один переход не может сработать. Однако сеть будет нормально функционировать, если в месте  p₁ оставить одну фишку, т.е. разрешить выполняться либо процессу  A либо процессу B, но не обоим одновременно.

№15 Понятие дедлока. Необходимые условия дедлока. Два подхода в борьбе с дедлоками. Привести пример сети Петри, допускающей дедлок.

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

Это может быть нормальный останов сети, а может быть и следствием конкуренции за ресурсы

Необходимые условия дедлока.

1.  Наличие неразделенного ресурса.

2.  Дозахват ресурса.

3.  Не допускается временное освобождение ресурса.

4.  Циклическое ожидание

Подходы в борьбе с дедлоками.

1. Предотвращение. (Строим алгоритм, чтобы не было хотя бы 1 необход. условия.)
2. Преодоление. (Создаем свой алгоритм, распознающий дедлоки)

1.  Строим разделяемые ресурсы.

2.  Требование сразу всех необходимых ресурсов – процессу разрешается дозахват ресурсов, если он освободил ранее захваченные.

3.  Д.Б. алгоритмы для освобождения ресурсов. Можно заменить один ресурс другим – spooling.

4.  Необходимо знание запрашиваемых переменных, т.е.

1.  Перенумерация ресурсов и запрос осуществлять по возрастанию номеров.

2.  Использовать алгоритм банкира: если есть n типов ресурса, ti – количество i – го ресурса и есть Pj, j –1..m процессов, то сумма K^j_i < t_j (суммарный запрос всех процессов не превышает количество имеющихся ресурсов)

Существуют системы, системы дедлок: при циклическом ожидании просто уничтожается 1 из процессов.

Пример сети, допускающей дедлок:

Ситуация дедлока возникает при следующей последовательности срабатываний переходов сети: t₁, t₄, t₂, t₅. И в этом состоянии имеем дедлок: ни один переход не может сработать. Однако сеть будет нормально функционировать, если в месте p₁ оставить одну фишку, т.е. разрешить выполняться либо процессу A либо процессу B, но не обоим одновременно.

Билет №16

Механизм «Условных критических интервалов Хансена».

Пример решения задачи (читатели-писатели) с помощью этого механизма.

Идея: переменные из программы привязать к общим ресурсам. В условных критических интервалах общие ресурсы представлены переменными (разделяемые переменные).

Например: var x: shared real;

Разделяемые переменные доступны только внутри оператора: region x do S.

Только один процесс может исполнять оператор region с переменной x в качестве параметра. Т.о., пока исполняется оператор S, никакой другой процесс не может начать исполнение оператора region x.

Задача:

begin var v,w: shared record: rr,aw: integer

reader: begin   region v when aw=0 do rr:=rr+1;

read;

region v do rr:=rr+1;

end;

writer: begin   region v do dw:=aw+1 do wait rr:=0;

region w do write       ;

region v do aw:=aw-1;

end;

end.

P1: region x do (region y do S1);

P2: region y do (region x do S2);

Очевидна возможность дедлока, когда два процесса P1 и P2 одновременно начнут выполнять свои вложенные операторы region.

Билет №17

Монитор Хоара. Пример.

Основная идея: классические типы данных и операторы над ними должны храниться вместе.

1.  monitor create;

2.  var n: integer;

3.  procedure Вверх; begin n:=n+1; end;

4.  procedure Вниз; begin when n>0 do begin n:=n-1; end;

5.  function Приземление: boolean; begin Приземление:=