Алгоритм банкира

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

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

Пусть система состоит из трех процессов, которые пронумерованы 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; {признак завершения цикла проверок}

Поиск по сайту: