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

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

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

Банкирский алгоритм был предложен Эдсгером Дейкстрой в 1965 году в контексте развития операционных систем с разделением времени. В то время компьютеры становились многозадачными, и возникла проблема распределения ограниченных ресурсов (памяти, процессорного времени, устройств ввода-вывода) между конкурирующими процессами. Дейкстра, работавший в компании Burroughs Corporation, искал математически строгий способ гарантировать, что система не войдёт в состояние взаимоблокировки. Название алгоритма связано с аналогией с банковским делом: банк не выдаёт кредит, если это может привести к невозможности вернуть деньги всем вкладчикам.

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

Ресурсы и процессы

В модели банкирского алгоритма операционная система управляет конечным набором ресурсов. Каждый процесс перед началом работы должен объявить максимальное количество ресурсов каждого типа, которое ему может потребоваться. Алгоритм работает с тремя основными структурами данных:

• Доступные ресурсы (Available) — вектор, показывающий, сколько экземпляров каждого ресурса свободно в данный момент.
• Максимальная потребность (Max) — матрица, где каждая строка соответствует процессу, а столбец — типу ресурса, указывающая максимальное количество ресурсов, которое процесс может запросить.
• Выделенные ресурсы (Allocation) — матрица, показывающая, сколько ресурсов каждого типа уже выделено каждому процессу.

Безопасное состояние

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

Алгоритм работы

Проверка запроса на выделение ресурсов

Когда процесс запрашивает ресурсы, операционная система выполняет следующие шаги:

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

Алгоритм проверки безопасности

Проверка безопасности выполняется по следующей процедуре:

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

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

Рассмотрим систему с тремя процессами (P0, P1, P2) и одним типом ресурса (например, 10 экземпляров). Текущее состояние:

• Available: 3 (свободно 3 ресурса)
• Allocation: P0=5, P1=2, P2=2 (всего выделено 9)
• Max: P0=7, P1=4, P2=5
• Need: P0=2, P1=2, P2=3

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

• Доступно 3. P0 требует 2 — можно выполнить. После P0 освобождается 5, доступно становится 8.
• P1 требует 2 — можно выполнить. После P1 освобождается 2, доступно 10.
• P2 требует 3 — можно выполнить. Все процессы завершены. Состояние безопасно.

Если бы P2 запросил дополнительно 1 ресурс (Need стал бы 4), а Available было бы 2, то после выделения P2 состояние стало бы небезопасным, так как ни один процесс не смог бы завершиться.

Преимущества и недостатки

Преимущества

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

Недостатки

• Необходимость априорной информации: Процессы должны заранее объявить максимальную потребность в ресурсах, что не всегда возможно в реальных системах.
• Высокие накладные расходы: Алгоритм требует постоянного пересчёта состояния и проверки безопасности, что снижает производительность.
• Ограниченность модели: Алгоритм предполагает, что ресурсы не могут быть отозваны у процесса, и что процессы не могут изменять свои требования после запуска.
• Масштабируемость: С увеличением числа процессов и типов ресурсов сложность алгоритма растёт, что делает его неприменимым для крупных систем.

Применение

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

• Обнаружение и восстановление: Система позволяет взаимоблокировкам возникать, но затем обнаруживает их и устраняет (например, завершая процессы).
• Игнорирование: Некоторые системы (например, UNIX) просто игнорируют проблему, полагаясь на то, что взаимоблокировки случаются редко.

Однако алгоритм находит применение в специализированных системах:

• Встроенные системы: В системах реального времени с предсказуемыми нагрузками, где важно гарантировать отсутствие deadlock.
• Базы данных: В некоторых СУБД для управления блокировками транзакций.
• Образовательные цели: Алгоритм широко используется в учебных курсах по операционным системам для иллюстрации принципов предотвращения взаимоблокировок.

Критика и альтернативы

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

Альтернативными подходами являются:

• Алгоритм избегания взаимоблокировок на основе графов: Использует графы распределения ресурсов для выявления циклов.
• Протоколы иерархического упорядочения ресурсов: Процессы запрашивают ресурсы в строго определённом порядке, что исключает циклическое ожидание.
• Модели на основе очередей: В некоторых системах применяются очереди с приоритетами для управления доступом к ресурсам.

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

• Банкирский алгоритм был одной из первых формальных моделей управления ресурсами в операционных системах.
• Эдсгер Дейкстра, создатель алгоритма, также известен как автор алгоритма Дейкстры для поиска кратчайших путей в графах и концепции семафоров.
• В 1970-х годах алгоритм был реализован в операционной системе THE (Technische Hogeschool Eindhoven), разработанной Дейкстрой и его коллегами.
• Несмотря на ограничения, банкирский алгоритм остаётся важной теоретической основой для изучения взаимоблокировок в компьютерных науках.

Источники

• Dijkstra, E. W. (1965). "Cooperating Sequential Processes". Technical Report, Technological University Eindhoven.
• Tanenbaum, A. S., & Bos, H. (2015). "Modern Operating Systems" (4th ed.). Pearson.
• Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). "Operating System Concepts" (10th ed.). Wiley.
• Stallings, W. (2017). "Operating Systems: Internals and Design Principles" (9th ed.). Pearson.