Алгоритм предотвращения тупиковых ситуаций.

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

Рассмотрим пример:

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

Представим фрагмент двух програм:

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

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

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

На рисунке а) изображено некоторое состояние системы:

Допустим, процесс С запросил еще два устройства и его удовлетворили, то если один из процессов запросит то количество устройств, которое ему положено максимально или больше 1 для завершения, будет дедлок. Поэтому удовлетворять запрос С – опасно.

Для определения, ведет ли удовлетворение запроса к опасному состоянию, существуют специальные алгоритмы.

Один из них носит название “Алгоритм Банкира”.

Каждому процессу поставлено в соответствие целое число i (1£ i £N). Процессу i соответствуют его максимальная потребность в устройствах МАКС(i), количество устройств, выделенных ему в данный момент ВЫДЕЛУСТР(i), полагающийся ему остаток – ОСТАТОК(i) и признак МОЖЕТ НЕ ЗАКОНЧИТЬ(i).

Системы заводят глобальную переменную ОБЩУТР, обозначающую общее число имеющихся в системе устройств.

В начале работы неизвестно, может ли какой либо процесс окончиться МОЖЕТ НЕ ЗАКОНЧИТЬ(i) true для всех i.

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

Если состояние системы становится небезопасным, то она не удовлетворяет соответствующий запрос.

..........

СВОБУСТР:=ОБЩУСТР;

for i:=1 step 1 until N do

Begin

СВОБУСТР:=СВОБУСТР-ВЫДЕЛУСТР(i);

МОЖЕТНЕЗАКОНЧИТЬ(i):=True;

ОСТАТОК(i):=МАКС(i)-ВЫДЕЛУСТР(i);

end;

ПРИЗНАК:=Ture;

do while (ПРИЗНАК);

ПРИЗНАК:=False;

for i:=1 step 1 until N do

Begin

if МОЖЕТНЕЗАКОНЧИТЬ(i) and ОСТАТОК(i) <= СВОБУСТР;

СВОБУСТР:=СВОБУСТР+ВЫДЕЛУСТР(i);

ПРИЗНАК:=True;

end;end;end;end;

if СВОБУСТР=ОБЩУСТР then Состояние системы безопасное

else Состояние системы не безопасное

..........