Алгоритм банкиров - Википедия - Bankers algorithm

В Банкирский алгоритм, иногда называемый алгоритм обнаружения, это распределение ресурсов и тупик избегание алгоритм разработан Эдсгер Дейкстра проверяет безопасность путем моделирования распределения заранее определенных максимально возможных количеств всех Ресурсы, а затем выполняет проверку «s-состояния» для проверки возможных условий взаимоблокировки для всех других ожидающих действий, прежде чем решить, следует ли разрешить продолжение выделения.

Алгоритм был разработан в процессе проектирования для THE Операционная система и первоначально описано (в нидерландский язык ) в EWD108.[1] Когда новый процесс входит в систему, он должен объявить максимальное количество экземпляров каждого типа ресурса, которое он может когда-либо требовать; ясно, что это количество не может превышать общее количество ресурсов в системе. Кроме того, когда процесс получает все запрошенные ресурсы, он должен вернуть их за конечный промежуток времени.

Ресурсы

Чтобы алгоритм Банкира работал, ему необходимо знать три вещи:

  • Сколько каждого ресурса каждый процесс может запросить [MAX]
  • Какая часть каждого ресурса в настоящее время удерживается каждым процессом [ALLOCATED]
  • Какая часть каждого ресурса в настоящее время доступна в системе [ДОСТУПНО]

Ресурсы могут быть выделены процессу, только если количество запрошенных ресурсов меньше или равно доступному количеству; в противном случае процесс ждет, пока не станут доступны ресурсы.

Некоторые ресурсы, отслеживаемые в реальных системах, объем памяти, семафоры и интерфейс доступ.

Алгоритм Банкира получил свое название от того факта, что этот алгоритм может использоваться в банковской системе, чтобы гарантировать, что у банка не исчерпаются ресурсы, потому что банк никогда не будет распределять свои деньги таким образом, чтобы он больше не мог удовлетворять потребности всех своих клиентов.[2] Используя алгоритм Банкира, банк гарантирует, что, когда клиенты запрашивают деньги, банк никогда не выходит из безопасного состояния. Если запрос клиента не заставляет банк выйти из безопасного состояния, деньги будут распределены, в противном случае клиент должен дождаться, пока какой-либо другой клиент внесет достаточно.

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

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

  • Доступно: вектор длины m указывает количество доступных ресурсов каждого типа. Если Available [j] = k, имеется k экземпляров ресурса типа Rj имеется в наличии.
  • Макс: An × матрица определяет максимальную потребность каждого процесса. Если Max [i, j] = k, то Pя может запрашивать не более k экземпляров ресурса типа Rj.
  • Размещение: An × Матрица определяет количество ресурсов каждого типа, выделенных в данный момент каждому процессу. Если Allocation [i, j] = k, то обработать Pя в настоящее время выделено k экземпляров типа ресурса Rj.
  • Потребность: An × Матрица указывает оставшуюся потребность в ресурсах каждого процесса. Если Need [i, j] = k, то Pя может потребоваться еще k экземпляров ресурса типа Rj для выполнения задачи.

Примечание: Need [i, j] = Max [i, j] - Распределение [i, j] .n = m-a.

Пример

Общие системные ресурсы: A B C D6 5 7 6
Доступные системные ресурсы: A B C D3 1 1 2
Процессы (выделенные в настоящее время ресурсы): A B C DP1 1 2 2 1P2 1 0 3 3P3 1 2 1 0
Процессы (максимальные ресурсы): A B C DP1 3 3 2 2P2 1 2 3 4P3 1 3 5 0
Потребность = максимальные ресурсы - выделенные в данный момент ресурсы Процессы (возможно, необходимые ресурсы): A B C DP1 2 1 0 1P2 0 2 0 1P3 0 1 4 0

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

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

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


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

  1. P1 требуется на 2 A, 1 B и 1 D больше ресурсов, чтобы достичь максимума
    • [доступный ресурс: <3 1 1 2> - <2 1 0 1> = <1 0 1 1>]
    • Теперь в системе все еще есть 1 A, нет ресурсов B, 1 C и 1 D.
  2. P1 завершает работу, возвращая системе ресурсы 3 A, 3 B, 2 C и 2 D
    • [доступный ресурс: <1 0 1 1> + <3 3 2 2> = <4 3 3 3>]
    • Теперь в системе доступно 4 ресурса A, 3 B, 3 C и 3 D.
  3. P2 получает 2 дополнительных ресурса B и 1 D, затем завершает работу, возвращая все свои ресурсы
    • [доступный ресурс: <4 3 3 3> - <0 2 0 1> + <1 2 3 4> = <5 3 6 6>]
    • В системе теперь есть 5 ресурсов A, 3 B, 6 C и 6 D.
  4. P3 получает ресурсы 1 B и 4 C и завершает работу.
    • [доступный ресурс: <5 3 6 6> - <0 1 4 0> + <1 3 5 0> = <6 5 7 6>]
    • Теперь в системе есть все ресурсы: 6 A, 5 B, 7 C и 6 D.
  5. Поскольку все процессы могли завершиться, это состояние безопасно

В качестве примера небезопасного состояния рассмотрим, что произошло бы, если бы процесс 2 вначале содержал 2 единицы ресурса B.

Запросы

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

  1. Можно ли удовлетворить запрос?
    • В противном случае запрос невозможен и должен быть либо отклонен, либо помещен в список ожидания.
  2. Предположим, что запрос удовлетворен
  3. Безопасно ли новое государство?
    • Если да, удовлетворить запрос
    • Если нет, либо отклоните запрос, либо поместите его в список ожидания.

Решение о том, отклоняет или откладывает система невозможный или небезопасный запрос, зависит от операционной системы.

Пример

Начиная с того же состояния, что и в предыдущем примере, предположим, что процесс 3 запрашивает 2 единицы ресурса C.

  1. Недостаточно ресурса C для удовлетворения запроса
  2. Запрос отклонен


С другой стороны, предположим, что процесс 3 запрашивает 1 единицу ресурса C.

  1. Ресурсов достаточно для удовлетворения запроса
  2. Предположим, запрос удовлетворен
    • Новое состояние системы будет:
    Доступные системные ресурсы A B C D Бесплатно 3 1 0 2
    Процессы (выделенные в настоящее время ресурсы): A B C DP1 1 2 2 1P2 1 0 3 3P3 1 2 2 0
    Процессы (максимальные ресурсы): A B C DP1 3 3 2 2P2 1 2 3 4P3 1 3 5 0
  1. Определите, безопасно ли это новое состояние
    1. P1 может получить 2 ресурса A, 1 B и 1 D и завершить работу
    2. Затем P2 может получить ресурсы 2 B и 1 D и завершить
    3. Наконец, P3 может получить ресурсы 1 B и 3 C и завершить
    4. Следовательно, это новое состояние безопасно
  2. Поскольку новое состояние безопасно, удовлетворим запрос


Последний пример: из состояния, в котором мы начали, предположим, что процесс 2 запрашивает 1 единицу ресурса B.

  1. Ресурсов достаточно
  2. Предполагая, что запрос удовлетворен, новое состояние будет:
    Доступные системные ресурсы: A B C D Бесплатно 3 0 1 2
    Процессы (выделенные в настоящее время ресурсы): A B C DP1 1 2 5 1P2 1 1 3 3P3 1 2 1 0
    Процессы (максимальные ресурсы): A B C DP1 3 3 2 2P2 1 2 3 4P3 1 3 5 0
  1. Это состояние безопасно? Предполагая, что P1, P2 и P3 запрашивают больше ресурсов B и C.
    • P1 не может получить достаточно ресурсов B
    • P2 не может получить достаточно ресурсов B
    • P3 не может получить достаточно ресурсов B
    • Ни один процесс не может получить достаточно ресурсов для завершения, поэтому это состояние небезопасно
  2. Поскольку состояние небезопасно, отклоните запрос
импорт тупой в качестве нпn_processes = int(Вход('Количество процессов? '))n_resources = int(Вход(«Количество ресурсов? '))доступные ресурсы = [int(Икс) за Икс в Вход('Заявить вектор? ').расколоть(' ')]Current_allocated = нп.множество([[int(Икс) за Икс в Вход(«В настоящее время выделено для обработки» + ул(я + 1) + '? ').расколоть(' ')] за я в классифицировать(n_processes)])max_demand = нп.множество([[int(Икс) за Икс в Вход(«Максимальный спрос от процесса» + ул(я + 1) + '? ').расколоть(' ')] за я в классифицировать(n_processes)])total_available = доступные ресурсы - нп.сумма(Current_allocated, ось=0)Бег = нп.те(n_processes)  # Массив с n_processes 1, чтобы указать, что процесс еще не запущенпока нп.count_nonzero(Бег) > 0:    at_least_one_allocated = Ложь    за п в классифицировать(n_processes):        если Бег[п]:            если все(я >= 0 за я в total_available - (max_demand[п] - Current_allocated[п])):                at_least_one_allocated = Истинный                Распечатать(ул(п) + ' бежит')                Бег[п] = 0                total_available += Current_allocated[п]    если нет at_least_one_allocated:        Распечатать("Небезопасно")        выход()                Распечатать('Безопасный')

Ограничения

Как и другие алгоритмы, алгоритм Банкира имеет некоторые ограничения при реализации. В частности, ему необходимо знать, какой объем каждого ресурса может запросить процесс. В большинстве систем эта информация недоступна, что делает невозможным реализацию алгоритма Банкира. Кроме того, нереалистично предположить, что количество процессов статично, поскольку в большинстве систем количество процессов изменяется динамически. Более того, требование, чтобы процесс в конечном итоге освободил все свои ресурсы (когда процесс завершается), достаточно для правильности алгоритма, однако этого недостаточно для практической системы. Ожидание высвобождения ресурсов в течение нескольких часов (или даже дней) обычно неприемлемо.

Рекомендации

  1. ^ Дейкстра, Эдсгер В. Een алгоритмы термообработки ван де доделийке омарминг (EWD-108) (PDF). Архив Э.В. Дейкстры. Центр американской истории, Техасский университет в Остине. (транскрипция ) (на голландском; Алгоритм предотвращения смертельные объятия )
  2. ^ Зильбершатц, Гальвин и Ганье (2013). Основные понятия операционной системы, 9-е издание. Вайли. п. 330. ISBN  978-1-118-06333-0.CS1 maint: несколько имен: список авторов (связь)

дальнейшее чтение