Банкир алгоритм , который иногда называют в качестве алгоритма обнаружения , является выделение ресурсов и взаимоблокировки избегания алгоритма , разработанный Эдсгер Дейкстрой , что тесты на безопасность, имитируя выделение заранее определенных максимально возможных количеств всех ресурсов , а затем делает «S-состояние» check, чтобы проверить возможные условия взаимоблокировки для всех других ожидающих действий, прежде чем решать, следует ли разрешить продолжение выделения.
Алгоритм был разработан в процессе разработки операционной системы THE и первоначально описан (на голландском языке ) в EWD108. [1] Когда новый процесс входит в систему, он должен объявить максимальное количество экземпляров каждого типа ресурса, которое он может когда-либо требовать; ясно, что это количество не может превышать общее количество ресурсов в системе. Кроме того, когда процесс получает все запрошенные ресурсы, он должен вернуть их за конечный промежуток времени.
Ресурсы
Чтобы алгоритм Банкира работал, ему необходимо знать три вещи:
- Сколько каждого ресурса может запросить каждый процесс [MAX]
- Какая часть каждого ресурса в настоящее время удерживается каждым процессом [ALLOCATED]
- Какая часть каждого ресурса в настоящее время доступна в системе [ДОСТУПНО]
Ресурсы могут быть выделены процессу, только если количество запрошенных ресурсов меньше или равно доступному количеству; в противном случае процесс ждет, пока не станут доступны ресурсы.
Некоторые из ресурсов, которые отслеживаются в реальных системах, - это память , семафоры и доступ к интерфейсу .
Алгоритм Банкира получил свое название от того факта, что этот алгоритм может использоваться в банковской системе, чтобы гарантировать, что у банка не исчерпаются ресурсы, потому что банк никогда не будет размещать свои деньги таким образом, чтобы он больше не мог удовлетворять потребности всех своих клиентов. [2] Используя алгоритм Банкира, банк гарантирует, что, когда клиенты запрашивают деньги, банк никогда не выходит из безопасного состояния. Если запрос клиента не заставляет банк выйти из безопасного состояния, наличные деньги будут распределены, в противном случае клиент должен дождаться, пока какой-либо другой клиент внесет достаточно.
Базовые структуры данных, которые необходимо поддерживать для реализации Банковского алгоритма:
Позволять быть количеством процессов в системе и быть количеством типов ресурсов. Тогда нам потребуются следующие структуры данных:
- Доступно: вектор длины m указывает количество доступных ресурсов каждого типа. Если Available [j] = k, доступно k экземпляров ресурса типа R j .
- Макс: An × матрица определяет максимальную потребность каждого процесса. Если Max [i, j] = k, то P i может запросить не более k экземпляров типа ресурса R j .
- Размещение: An × Матрица определяет количество ресурсов каждого типа, выделенных в данный момент каждому процессу. Если Allocation [i, j] = k, то процессу P i в настоящее время выделяется k экземпляров типа ресурса R j .
- Потребность: An × Матрица указывает оставшиеся потребности в ресурсах каждого процесса. Если Need [i, j] = k, то P i может потребоваться еще k экземпляров типа ресурса R j для выполнения задачи.
Примечание: Need [i, j] = Max [i, j] - Распределение [i, j]. п = ма.
Пример
Общие системные ресурсы:ABCD6 5 7 6
Доступные системные ресурсы:ABCD3 1 1 2
Процессы (выделенные в настоящее время ресурсы): ABCDП1 1 2 2 1П2 1 0 3 3П3 1 2 1 0
Процессы (максимум ресурсов): ABCDП1 3 3 2 2П2 1 2 3 4П3 1 3 5 0
Потребность = максимальные ресурсы - выделенные в настоящее время ресурсыПроцессы (возможно, необходимые ресурсы): ABCDП1 2 1 0 1P2 0 2 0 1П3 0 1 4 0
Безопасные и небезопасные состояния
Состояние (как в приведенном выше примере) считается безопасным, если все процессы могут завершить выполнение (завершить). Поскольку система не может знать, когда процесс будет завершен или сколько ресурсов он запросит к тому времени, система предполагает, что все процессы в конечном итоге попытаются получить заявленные максимальные ресурсы и вскоре после этого завершатся. В большинстве случаев это разумное предположение, поскольку система не особенно заботится о том, как долго выполняется каждый процесс (по крайней мере, с точки зрения предотвращения тупиковых ситуаций). Кроме того, если процесс завершается без получения максимального ресурса, это только упрощает его работу в системе. Безопасное состояние считается принимающим решение, если оно будет обрабатывать очередь готовности.
Учитывая это предположение, алгоритм определяет, является ли состояние безопасным , пытаясь найти гипотетический набор запросов от процессов, которые позволили бы каждому получить свои максимальные ресурсы, а затем завершить работу (возвращая свои ресурсы в систему). Любое состояние, в котором такого набора нет, считается небезопасным .
Мы можем показать, что состояние, приведенное в предыдущем примере, является безопасным, показав, что каждый процесс может получить свои максимальные ресурсы, а затем завершиться.
- 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.
- 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.
- 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.
- 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.
- Поскольку все процессы могли завершиться, это состояние безопасно.
В качестве примера небезопасного состояния рассмотрим, что произошло бы, если бы процесс 2 вначале содержал 2 единицы ресурса B.
Запросы
Когда система получает запрос на ресурсы, она запускает алгоритм банкира, чтобы определить, безопасно ли удовлетворить запрос. Алгоритм становится довольно простым, если понимать различие между безопасным и небезопасным состояниями.
- Можно ли удовлетворить запрос?
- В противном случае запрос невозможен и должен быть либо отклонен, либо помещен в список ожидания.
- Предположим, что запрос удовлетворен
- Безопасно ли новое государство?
- Если да, удовлетворите запрос
- Если нет, либо отклоните запрос, либо поместите его в список ожидания.
Решение о том, отклоняет ли система невозможный или небезопасный запрос или откладывает его, зависит от операционной системы.
Пример
Начиная с того же состояния, что и в предыдущем примере, предположим, что процесс 1 запрашивает 2 единицы ресурса C.
- Недостаточно ресурса C для удовлетворения запроса
- Запрос отклонен
С другой стороны, предположим, что процесс 3 запрашивает 1 единицу ресурса C.
- Ресурсов достаточно для удовлетворения запроса
- Предположим, запрос удовлетворен
- Новое состояние системы будет:
Доступные системные ресурсы ABCDБесплатно 3 1 0 2
Процессы (выделенные в настоящее время ресурсы): ABCDП1 1 2 2 1П2 1 0 3 3П3 1 2 2 0
Процессы (максимум ресурсов): ABCDП1 3 3 2 2П2 1 2 3 4П3 1 3 5 0
- Определите, безопасно ли это новое состояние
- P1 может получить 2 ресурса A, 1 B и 1 D и завершить работу
- Затем P2 может получить ресурсы 2 B и 1 D и завершить работу.
- Наконец, P3 может получить ресурсы 1 B и 3 C и завершить работу.
- Следовательно, это новое состояние безопасно
- Поскольку новое состояние безопасно, удовлетворить запрос
Последний пример: из состояния, в котором мы начали, предположим, что процесс 2 запрашивает 1 единицу ресурса B.
- Ресурсов достаточно
- Предполагая, что запрос удовлетворен, новое состояние будет:
Доступные системные ресурсы: ABCDБесплатно 3 0 1 2
Процессы (выделенные в настоящее время ресурсы): ABCDП1 1 2 5 1П2 1 1 3 3П3 1 2 1 0
Процессы (максимум ресурсов): ABCDП1 3 3 2 2П2 1 2 3 4П3 1 3 5 0
- Это состояние безопасно? Предполагая, что P1, P2 и P3 запрашивают больше ресурсов B и C.
- P1 не может получить достаточно ресурсов B
- P2 не может получить достаточно ресурсов B
- P3 не может получить достаточно ресурсов B
- Ни один процесс не может получить достаточно ресурсов для завершения, поэтому это состояние небезопасно.
- Поскольку состояние небезопасно, отклоните запрос
импортировать numpy как npn_processes = int ( input ( 'Количество процессов?' )) n_resources = int ( input ( 'Количество ресурсов?' ))available_resources = [ int ( x ) для x во входных данных ( 'Вектор утверждения?' ) . разделить ( "" )]current_allocated = np . array ([[ int ( x ) для x на входе ( 'В настоящее время выделено для процесса' + str ( i + 1 ) + '?' ) . split ( '' )] для i в диапазоне ( n_processes )]) max_demand = np . array ([[ int ( x ) для x на входе ( 'Максимальный спрос от процесса' + str ( i + 1 ) + '?' ) . split ( '' )] для i в диапазоне ( n_processes )])total_available = available_resources - np . сумма ( текущее_распределение , ось = 0 )работает = np . ones ( n_processes ) # Массив с n_processes 1, чтобы указать, что процесс еще не запущенпока нп . count_nonzero ( работает ) > 0 : at_least_one_allocated = Ложные для р в диапазоне ( n_processes ): если работает [ р ]: если все ( я > = 0 для I в total_available - ( max_demand [ р ] - currently_allocated [ р ])): at_least_one_allocated = Истинная печать ( ул ( р ) + 'работает' ) работает [ р ] = 0 total_available + = currently_allocated [ р ] , если не at_least_one_allocated : печать ( 'небезопасных' ) выход () print ( 'Безопасный' )
Ограничения
Как и другие алгоритмы, алгоритм Банкира имеет некоторые ограничения при реализации. В частности, ему необходимо знать, какой объем каждого ресурса может запросить процесс. В большинстве систем эта информация недоступна, что делает невозможным реализацию алгоритма Банкира. Кроме того, нереально предполагать, что количество процессов статично, поскольку в большинстве систем количество процессов изменяется динамически. Более того, требование о том, что процесс в конечном итоге освободит все свои ресурсы (когда процесс завершится), достаточно для правильности алгоритма, однако этого недостаточно для практической системы. Ожидание высвобождения ресурсов часами (или даже днями) обычно неприемлемо.
Рекомендации
- ^ Дейкстра, Эдсгер В. Een algorithme тер voorkoming ван де dodelijke omarming (EWD-108) (PDF) . EW Dijkstra Archive. Центр американской истории Техасского университета в Остине .( транскрипция ) (на голландском языке; алгоритм предотвращения смертельного объятия )
- ^ Зильбершатц, Гальвин и Гань (2013). Понятия операционной системы, 9-е издание . Вайли. п. 330. ISBN 978-1-118-06333-0.CS1 maint: несколько имен: список авторов ( ссылка )
дальнейшее чтение
- « Концепции операционных систем » Зильбершаца, Гальвина и Гагна (страницы 259–261 7-го издания)
- « Концепции операционных систем » Зильбершаца, Гальвина и Гагна (страницы 298–300 8-го издания)
- Дейкстра, Эдсгер В. Математика алгоритма банкира (EWD-623) (PDF) . EW Dijkstra Archive. Центр американской истории Техасского университета в Остине .( транскрипция ) (1977), опубликовано на страницах 308–312 книги Эдсгер В. Дейкстра, Избранные труды по вычислениям: личная перспектива , Springer-Verlag, 1982. ISBN 0-387-90652-5