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

Банковский алгоритм (англ. 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) проверяет, является ли текущее состояние безопасным:

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

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

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

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

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

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

Процесс	Max (R1,R2)	Allocation (R1,R2)	Need (R1,R2)
P1	(7, 5)	(2, 1)	(5, 4)
P2	(3, 2)	(1, 1)	(2, 1)
P3	(9, 0)	(3, 0)	(6, 0)

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

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) операций, что неприемлемо для систем с большим числом процессов.
Необходимость априорного знания: процессы должны заранее объявить максимальные потребности, что не всегда возможно.
Статичность: алгоритм плохо адаптируется к динамическому появлению и завершению процессов.

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

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

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

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

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

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

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

¶Источники

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

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →