Банковский алгоритм

Банковский алгоритм (англ. Banker’s algorithm) — это метод предотвращения взаимоблокировок (deadlocks) в операционных системах и системах управления ресурсами, основанный на моделировании распределения ресурсов по аналогии с работой банка. Алгоритм был разработан Эдсгером Дейкстрой в 1965 году и назван так из-за сходства с процессом выдачи кредитов банком клиентам. Основная идея заключается в том, что операционная система не выделяет процессу ресурсы, если это может привести к невозможности выполнения всех процессов в будущем, то есть к состоянию взаимоблокировки.

История создания

Банковский алгоритм был предложен нидерландским учёным Эдсгером Дейкстрой в контексте его работы над операционной системой THE (Technische Hogeschool Eindhoven). Дейкстра стремился решить проблему «обедающих философов» — классической задачи синхронизации, иллюстрирующей риск взаимоблокировки при конкурентном доступе к ресурсам. Алгоритм впервые был описан в 1965 году в статье «Решение проблемы взаимоблокировок» и с тех пор стал одним из фундаментальных методов в теории операционных систем.

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

Основные понятия и принципы

Банковский алгоритм оперирует несколькими ключевыми понятиями:

• Процесс — выполняющаяся программа, которая запрашивает и освобождает ресурсы.
• Ресурс — любой объект, необходимый для выполнения процесса (память, процессорное время, устройства ввода-вывода, файлы и т.д.).
• Максимальная потребность — максимальное количество ресурсов каждого типа, которое может запросить процесс за всё время выполнения.
• Выделенные ресурсы — количество ресурсов, уже предоставленных процессу в данный момент.
• Доступные ресурсы — количество свободных ресурсов каждого типа в системе.

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

Классификация состояний

Состояние системы может быть:

• Безопасным — существует последовательность процессов, гарантирующая завершение всех без взаимоблокировки.
• Небезопасным — такой последовательности не существует, и при определённых запросах может возникнуть взаимоблокировка.
• Взаимоблокировка — все процессы заблокированы и не могут продолжить выполнение.

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

Устройство и работа алгоритма

Структуры данных

Алгоритм использует следующие матрицы и векторы:

• Available[m] — вектор доступных ресурсов (m — количество типов ресурсов).
• Max[n][m] — матрица максимальных потребностей процессов (n — количество процессов).
• Allocation[n][m] — матрица выделенных ресурсов.
• Need[n][m] — матрица оставшихся потребностей, вычисляемая как Need[i][j] = Max[i][j] - Allocation[i][j].

Этап 1: Проверка безопасности

Алгоритм безопасности (Safety Algorithm) проверяет, является ли текущее состояние безопасным:

1. Создаются временные копии Work = Available и Finish[i] = false для всех процессов.
2. Ищется процесс i, для которого Finish[i] == false и Need[i] <= Work (по всем ресурсам).
3. Если такой процесс найден, предполагается, что он завершится: Work = Work + Allocation[i], Finish[i] = true.
4. Шаги 2–3 повторяются, пока есть подходящие процессы.
5. Если после цикла все Finish[i] == true, состояние безопасно; иначе — небезопасно.

Этап 2: Выделение ресурсов

Когда процесс i запрашивает ресурсы Request[i]:

1. Проверяется, что Request[i] <= Need[i] (запрос не превышает оставшуюся потребность).
2. Проверяется, что Request[i] <= Available (ресурсы доступны).
3. Временно выделяются ресурсы: Available = Available - Request[i], Allocation[i] = Allocation[i] + Request[i], Need[i] = Need[i] - Request[i].
4. Выполняется проверка безопасности нового состояния.
5. Если состояние безопасно — выделение фиксируется; если небезопасно — запрос отклоняется, и система возвращается к предыдущему состоянию.

Пример работы алгоритма

Рассмотрим систему с тремя процессами (P1, P2, P3) и двумя типами ресурсов (R1, R2). Пусть Available = (3, 2). Матрицы:

Проверка безопасности:

• Work = (3, 2). Процесс P2: Need[2] = (2,1) <= Work → завершается, Work = (3+1, 2+1) = (4, 3).
• Теперь P1: Need[1] = (5,4) > Work = (4,3) — не подходит.
• P3: Need[3] = (6,0) > Work = (4,3) — не подходит.
• Состояние небезопасно, так как ни один процесс не может быть завершён.

Если бы P2 завершился, а затем P1 получил бы ресурсы, состояние могло бы стать безопасным, но в данном примере последовательности не существует.

Применение

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

• Высокая вычислительная сложность: проверка безопасности требует O(n² × m) операций, что неприемлемо для систем с большим числом процессов.
• Необходимость априорного знания: процессы должны заранее объявить максимальные потребности, что не всегда возможно.
• Статичность: алгоритм плохо адаптируется к динамическому появлению и завершению процессов.

Тем не менее, банковский алгоритм остаётся важным теоретическим инструментом для изучения взаимоблокировок и используется в учебных целях в курсах по операционным системам. В некоторых специализированных системах (например, в базах данных с жёсткими требованиями к надёжности) он применяется в модифицированном виде.

Критика и ограничения

Основные недостатки банковского алгоритма:

1. Предположение о фиксированном числе процессов: алгоритм не учитывает динамическое создание и завершение процессов, что характерно для современных многозадачных систем.
2. Требование к точности данных: процессы должны честно указывать максимальные потребности, иначе алгоритм может допустить небезопасное состояние.
3. Ресурсная неэффективность: алгоритм может отказывать в выделении ресурсов, даже если взаимоблокировка маловероятна, что снижает утилизацию ресурсов.
4. Сложность реализации: для каждого типа ресурса требуется вести матрицы и выполнять проверки, что увеличивает накладные расходы.

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

Интересные факты

• Название «банковский» связано с метафорой: банк не выдаёт кредит, если это может привести к невозможности вернуть деньги всем вкладчикам. Аналогично, операционная система не выделяет ресурсы, если это может заблокировать все процессы.
• Алгоритм был предложен Дейкстрой в ответ на проблему «обедающих философов», которая иллюстрирует взаимоблокировку при конкурентном доступе к вилкам (ресурсам).
• В 1973 году Джек Холт (Jack Holt) доказал, что банковский алгоритм является оптимальным в смысле предотвращения взаимоблокировок при заданных предположениях.

Источники

• Дейкстра, Э. «Решение проблемы взаимоблокировок» (1965).
• Таненбаум, Э. «Современные операционные системы» (4-е издание, 2014).
• Сильбершац, А., Гэлвин, П., Гэгн, Г. «Операционные системы: концепции и проектирование» (9-е издание, 2012).
• Холт, Дж. «О некоторых проблемах взаимоблокировок в компьютерных системах» (1973).