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

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

История и происхождение

Алгоритм банкира был впервые описан Эдсгером Дейкстрой в его статье «Cooperating Sequential Processes» (1965). Дейкстра работал над проблемой синхронизации процессов и управления ресурсами в многозадачных системах. Идея алгоритма возникла из наблюдения за работой банковской системы: банк не может выдать кредит, если это приведёт к невозможности удовлетворить все обязательства перед вкладчиками. Аналогично, операционная система не должна выделять ресурсы процессу, если это может привести к невозможности завершения всех активных процессов.

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

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

Для понимания работы алгоритма необходимо определить несколько ключевых понятий:

• Процесс (P) — программа в состоянии выполнения, которая запрашивает и использует ресурсы.
• Ресурс (R) — любой объект, который может быть выделен процессу (например, память, процессорное время, файлы, устройства ввода-вывода). Ресурсы считаются однотипными (например, 5 одинаковых принтеров).
• Выделенный ресурс (Allocated) — количество ресурсов каждого типа, уже предоставленных процессу.
• Максимальная потребность (Max) — максимальное количество ресурсов каждого типа, которое процесс может запросить в ходе своего выполнения. Это значение должно быть объявлено процессом заранее.
• Доступные ресурсы (Available) — количество свободных ресурсов каждого типа в системе на данный момент.
• Потребность (Need) — количество ресурсов каждого типа, которое процессу ещё требуется для завершения. Рассчитывается как Need = Max - Allocated.
• Безопасное состояние (Safe State) — состояние системы, при котором существует последовательность выполнения процессов (безопасная последовательность), в которой каждый процесс может получить все необходимые ему ресурсы и завершиться, не вызывая дедлока.
• Безопасная последовательность — порядок, в котором процессы могут быть выполнены без возникновения взаимоблокировки.

Принцип работы алгоритма

Алгоритм банкира работает по принципу «предварительной проверки». Когда процесс запрашивает ресурсы, система не выделяет их сразу, а сначала проверяет, не приведёт ли это выделение к небезопасному состоянию. Если выделение ресурсов переведёт систему в небезопасное состояние, запрос отклоняется, и процесс должен подождать.

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

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

1. Создаются временные копии векторов Available, Allocated и Need.
2. Ищется процесс, чья Need меньше или равна Available (по всем типам ресурсов). Если такой процесс найден, он считается завершённым: все его ресурсы освобождаются и добавляются к Available.
3. Шаг 2 повторяется до тех пор, пока:

• Все процессы не будут завершены — состояние безопасно.
• Не останется ни одного процесса, чья Need меньше или равна Available — состояние небезопасно (потенциальный дедлок).

Алгоритм запроса ресурсов

Когда процесс Pi запрашивает вектор ресурсов Request:

1. Проверяется, что Request <= Need[i]. Если нет, запрос считается ошибочным (процесс запрашивает больше, чем объявил).
2. Проверяется, что Request <= Available. Если нет, процесс должен ждать.
3. Система временно выделяет ресурсы, обновляя векторы:

• Available = Available - Request
• Allocated[i] = Allocated[i] + Request
• Need[i] = Need[i] - Request

1. Выполняется проверка на безопасное состояние для нового состояния.
2. Если новое состояние безопасно — ресурсы выделяются окончательно. Если нет — запрос отклоняется, и система возвращается к предыдущему состоянию.

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

Рассмотрим систему с 3 процессами (P1, P2, P3) и 2 типами ресурсов (R1 и R2). Пусть в системе доступно 10 единиц R1 и 5 единиц R2.

Доступные ресурсы (Available): (10 - 0 - 2 - 3, 5 - 1 - 0 - 0) = (5, 4).

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

1. Ищем процесс, чья Need <= Available:

• P1: (7,4) <= (5,4)? Нет.
• P2: (1,2) <= (5,4)? Да. Завершаем P2. Available становится (5+2, 4+0) = (7,4).

1. Ищем следующий процесс:

• P1: (7,4) <= (7,4)? Да. Завершаем P1. Available становится (7+0, 4+1) = (7,5).

1. Ищем следующий процесс:

• P3: (6,0) <= (7,5)? Да. Завершаем P3.

Все процессы завершены. Состояние безопасно. Безопасная последовательность: P2, P1, P3.

Теперь предположим, что процесс P1 запрашивает (1, 1). Временно выделяем:

• Available = (5-1, 4-1) = (4, 3)
• Allocated[P1] = (0+1, 1+1) = (1, 2)
• Need[P1] = (7-1, 4-1) = (6, 3)

Проверка на безопасное состояние для нового состояния:

1. Ищем процесс, чья Need <= Available:

• P1: (6,3) <= (4,3)? Нет.
• P2: (1,2) <= (4,3)? Да. Завершаем P2. Available = (4+2, 3+0) = (6, 3).

1. Ищем следующий процесс:

• P1: (6,3) <= (6,3)? Да. Завершаем P1. Available = (6+1, 3+2) = (7, 5).

1. Ищем следующий процесс:

• P3: (6,0) <= (7,5)? Да. Завершаем P3.

Новое состояние безопасно. Запрос P1 на (1, 1) удовлетворяется.

Достоинства и недостатки

Достоинства

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

Недостатки

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

Применение на практике

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

• Игнорирование дедлоков: наиболее распространённая стратегия. Система не предпринимает никаких мер для предотвращения или обнаружения дедлоков, полагаясь на то, что они случаются редко. Если дедлок всё же возникает, система перезагружается или «убивает» один из процессов.
• Обнаружение и восстановление: система периодически проверяет наличие дедлоков (например, с помощью графа ожидания) и, если находит, предпринимает действия по их устранению (например, принудительное завершение одного из процессов).
• Предотвращение дедлоков на этапе проектирования: используются протоколы, исключающие одно из четырёх необходимых условий возникновения дедлока (взаимное исключение, удержание и ожидание, отсутствие приоритетного захвата, циклическое ожидание). Например, протокол «все или ничего» или упорядоченное выделение ресурсов.

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

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

• Название алгоритма связано с тем, что Дейкстра впервые описал его на примере банковской системы, где банк имеет ограниченный капитал, а клиенты берут кредиты.
• Алгоритм банкира является частным случаем более общего алгоритма «избегания дедлоков» (deadlock avoidance), который отличается от «предотвращения» (deadlock prevention) тем, что не накладывает жёстких ограничений на порядок запросов.
• Существуют модификации алгоритма, которые позволяют работать с динамически изменяющимся множеством процессов, но они значительно сложнее.

Источники

• Дейкстра, Э. «Cooperating Sequential Processes» (1965).
• Таненбаум, Э., Бос, Х. «Современные операционные системы» (4-е издание).
• Сильбершац, А., Гэлвин, П., Гэгн, Г. «Операционные системы: концепции и проектирование» (9-е издание).
• Столлингс, У. «Операционные системы: внутренняя структура и принципы проектирования» (9-е издание).