Алгоритм предотвращения тупиковых ситуаций.
Рассмотрим систему, в которой процессы конкурируют из-за лентопротяжных устройств если процессу предоставить все требуемые устройства, которые ему нужны, он будет работать в течении конечного отрезка времени, после чего он возвращает все затребованные устройства.
Рассмотрим пример:
Пусть двум процессам, выполняющимся в режиме мультипрограммирования для выполнения работы нужно два ресурса, например, принтер и последовательный порт. Такая ситуация может возникнуть, например, во время распечатки информации, поступающей по модемной связи.
Представим фрагмент двух програм:
В зависимости от соотношения скоростей процессов, они могут либо взаимно блокировать друг друга (дедлок a), либо образовывать очереди к разделяемым ресурсам, либо совершенно независимо использовать разделяемые ресурсы (С).
Программа должна удовлетворять запросы таким образом, чтобы процессы могли закончиться, и не возникло тупиков.
Пусть система состоит из трех процессов и десяти устройств. Каждому процессу соответствует его максимальная потребность в устройствах, количество их, выделенное процессу в данный момент и количество, которое он еще имеет право потребовать.
На рисунке а) изображено некоторое состояние системы:
Имя процесса | Максимальная потребность | Выделено | Остаток | |
a) | A | |||
B | ||||
C |
Имя процесса | Максимальная потребность | Выделено | Остаток | |
б) | A | |||
B | ||||
C |
Допустим, процесс С запросил еще два устройства и его удовлетворили, то если один из процессов запросит то количество устройств, которое ему положено максимально или больше 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 Состояние системы не безопасное
..........
Дата добавления: 2016-06-15; просмотров: 2080;