Обход тупиков avoidance. Алгоритм банкира.

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

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

Пусть система состоит из трех процессов, которые пронумерованы I=1..N, где N=3 и десяти устройств вывода, кол=10.

Каждому процессу соответствует:

· максимальная потребность в устройствах, макс[I], где I номер процесса;

· количество устройств, выделенных процессу в данный момент выд[I];

· оставшееся количество, которое процесс может еще потребовать ост[I].

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

Таблица 1

Таблица 2

Алгоритм, предложенный Дейкстрой - алгоритм банкира как раз и предназначен для выяснения ведет ли удовлетворение некоторого запроса к опасному состоянию. Заметим, что новое состояние безопасно тогда и только тогда, когда каждый процесс все же может завершиться (обозначим это таким образом: может_не_завершиться [I]=false для каждого I-го процесса).

const кол=10;N=3{общее количество устройств вывода и процессов,

соответственно}

var I : 1..N;{текущий номер процесса}

макс, выд, ост : array [1..N] of integer;{ соответственно,

максимальное, выделенное, оставшееся количество устройств, определенное каждому процессу в текущий момент времени, }

своб : 1..N;{общее количество свободных устройств в текущий

момент времени}

приз : boolean;

может_не_завершиться: array [1..N] of boolean;

. . .

{здесь мы не рассматриваем процесс заполнения массивов МАКС и ВЫД в каждый момент времени, согласно данным, например таб. 1,2}

begin

своб:=кол;

for I:=1 to N do

begin

своб:= своб-выд[I];

может_не_завершиться [I]:=true;{в начале работы неизвестно может ли завершиться каждый процесс, поэтому начальное значение этого признака устанавливаем true }

ост[I]:=макс[I] - выд[I] {расчет оставшихся устройств для каждого процесса}

end;

приз:=true;{признак завершения цикла проверок}

while (приз) do

begin

приз:=false;

for I:=1 to N do

begin

if (может_не_завершиться [I]) and (ост[I]<=своб) then

begin

может_не_завершиться [I]:=false;

своб:=своб+выд[I];

приз:=true

end

end

end

end;

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

Кроме того, он имеет ряд существенных недостатков:

· исходит из фиксированного числа распределяемых ресурсов

· требует, чтобы число процессов оставалось постоянным

· требует, чтобы процессы гарантированно возвращали выделенные им ресурсы в течение некоторого конечного времени

· требует, чтобы пользователи заранее указывали свои максимальные потребности в ресурсах

Уклонение от взаимоблокировок

При рассмотрении вопроса обнаружения взаимоблокировок мы предположили, что когда процесс запрашивает ресурсы, просит их все сразу (матрица R на рис. 6.4). Но в большинстве систем ресурсы запрашиваются по одному. Система должна уметь принимать решения о том представляет выделение ресурса опасность или нет, и вы­делять его только в том случае, если это безопасно.

Траектории ресурса

Основные алгоритмы уклонения от взаимоблокировок основаны на концепции безопасных состояний.

На рис. 6.6 представлена модель для системы с двумя процессами и двумя ре­сурсами, например принтером и плоттером. На горизонтальной оси отображены номера команд, выполняемых процессом А. На вертикальной оси отображены номера команд, выполняемых процессом В. В команде I₁ процесс А запрашивает принтер, в команде I₂ он запрашивает плоттер. Принтер и плоттер высвобождают­ся командами I₃ и I₄ соответственно. Процессу В нужен плоттер с команды I₅ по команду I₇ и принтер с команды I₆ по команду I₈.

Каждая точка на графике представляет совместное состояние двух процессов. Изначально система находится в точке р, когда ни один процесс еще не выпол­нил ни одной инструкции. Если планировщик запустит процесс А первым, мы попадем в точку q, в которой процесс А выполнил какое-то количество команд, а процесс В еще ничего не сделал. В точке q траектория становится вертикальной, показывая, что планировщик решил запустить в работу процесс В. При наличии одного процессора все отрезки траектории могут быть только вертикальными или горизонтальными, но не диагональными. Кроме того, движение всегда происходит вверх и вправо.

Когда процесс А пересекает прямую I₁, на пути из Г в s, он запрашивает, а затем получает в свое распоряжение принтер. Когда процесс В достигает точки t, он за­прашивает плоттер.

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

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

Если система войдет в прямоугольник, ограниченный по бокам прямыми I₁ и I₂ а сверху и снизу прямыми I₅ и I₆, то она в конце концов доберется до пересечения линий I₂ и I₆, и возникнет взаимоблокировка. В этот момент процесс А запрашивает плоттер, а процесс В запрашивает принтер, но оба ресурса будут уже выделены. По­лучается, что небезопасным является весь прямоугольник, и в него входить нельзя. В точке t единственным безопасным действием будет работа процесса до тех пор, пока он не дойдет до команды I₄. После нее для того, чтобы добраться до точки и, подойдет любая траектория.

Важный для понимания момент заключается в том, что в точке t процесс В запрашивает ресурс. Система должна принять решение: предоставлять его или нет. Если ресурс предоставляется, система попадает в небезопасную область и со временем входит в состояние взаимоблокировки. Чтобы предупредить взаимобло­кировку, нужно приостановить процесс В до тех пор, пока процесс А не запросит и не высвободит плоттер.