Методы обхода тупиков. Алгоритм банкира

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

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

Среди такого рода алгоритмов наиболее известен алгоритм бан­кира, предложенный Дейкстрой, который базируется на так называ­емых безопасных или надёжных состояниях. Безопасное состояние — это такое состояние, для которого имеется по крайней мере одна последовательность событий, которая не приведёт к тупику. Модель алгоритма основана на действиях банкира, который, имея в наличии капитал, выдаёт кредиты.

Суть алгоритма состоит в следующем.

Предположим, что у системы в наличии п свободных устройств, например магнитных лент.

ОС принимает запрос от пользовательского процесса, если его максимальная потребность не превышает п.

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

Текущее состояние системы называется надёжным, если ОС мо­жет обеспечить всем процессам их завершение (выделить необходи­мые ресурсы) в течение конечного времени.

В соответствии с алгоритмом банкира выделение устройств воз­можно, только если состояние системы остаётся надёжным.

Рассмотрим надёжные и ненадёжные состояния на примере. Предположим, что в системе имеется 10 ленточных устройств и ра­ботает 3 процесса. Для завершения работы Процессу 1 потребуется 5 устройств, Процессу 2 — 9 устройств, Процессу 3 — 3 устройства. В какой-то момент времени распределение устройств процессам вы­глядит так, как показано в таблице.

Состояние системы, представленное в таблице, является надёж­ным, поскольку существует такая последовательность выделения ре­сурсов процессам, что с течением времени все потребности процессов в ресурсах будут удовлетворены, и все процессы смогут завершиться в конечное время. Для этого сперва необходимо удовлетворить по­требности Процесса 3, затем (после завершения Процесса 3), Процес­са 1, и лишь затем Процесса 2. При таком порядке удовлетворения запросов на ресурсы система будет проходить только через надёж­ные состояния.

Если же распределять оставшиеся ресурсы в другом порядке, то система перейдёт в ненадёжное состояние.

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

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

1) Число процессов и число ресурсов должно быть фиксировано.

2) Число работающих процессов не должно не увеличиваться. И не должно появляться новых процессов.

3) Алгоритм требует, чтобы клиенты гарантированно возвраща­ли ресурсы.

4) Должны быть заранее указаны максимальные требования про­цессов к ресурсам. Чаще всего данная информация отсутствует.

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