stringtranslate.com

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

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

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

Ресурсы

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

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

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

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

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

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

Примечание: Потребность[i,j] = Макс[i,j] - Выделение[i,j]. n=ma.

Пример

Общие системные ресурсы:АБВГД6 5 7 6
Доступные системные ресурсы:АБВГД3 1 1 2
Процессы (выделенные в настоящее время ресурсы): АБВГДП1 1 2 2 1П2 1 0 3 3П3 1 2 1 0
Процессы (максимальные ресурсы): АБВГДП1 3 3 2 2П2 1 2 3 4П3 1 3 5 0
Потребность = максимальные ресурсы - текущие выделенные ресурсыПроцессы (возможно необходимые ресурсы): АБВГДП1 2 1 0 1П2 0 2 0 1П3 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, 1 ресурс 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 в начале удерживает 1 единицу ресурса B.

Запросы

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

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

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

 Пример

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

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


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

  1. Достаточно ресурсов для удовлетворения запроса
  2. Предположим, что запрос удовлетворен.
    • Новое состояние системы будет следующим:
 Доступные системные ресурсы АБВГДБесплатно 3 1 0 2
 Процессы (выделенные в настоящее время ресурсы): АБВГДП1 1 2 2 1П2 1 0 3 3П3 1 2 2 0
 Процессы (максимальные ресурсы): АБВГДП1 3 3 2 2П2 1 2 3 4П3 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. Если предположить, что запрос будет удовлетворен, новое состояние будет следующим:
 Доступные системные ресурсы: АБВГДБесплатно 3 0 1 2
 Процессы (выделенные в настоящее время ресурсы): АБВГДП1 1 2 5 1П2 1 1 3 3П3 1 2 1 0
 Процессы (максимальные ресурсы): АБВГДП1 3 3 2 2П2 1 2 3 4П3 1 3 5 0
  1. Безопасно ли это состояние? Предположим, что P1, P2 и P3 запрашивают больше ресурсов B и C.
    • P1 не может получить достаточно ресурсов B
    • P2 не может получить достаточно ресурсов B
    • P3 не может получить достаточно ресурсов B
    • Ни один процесс не может получить достаточно ресурсов для завершения, поэтому это состояние небезопасно.
  2. Поскольку состояние небезопасное, отклонить запрос
импортировать  numpy  как  npn_processes  =  int ( input ( "Количество процессов? " )) n_resources  =  int ( input ( "Количество ресурсов? " ))available_resources  =  [ int ( x )  for  x  in  input ( "Заявить вектор? " ) . split ( " " )]current_allocated  =  np . array ([  [ int ( x )  for  x  in  input ( f "В настоящее время выделено для процесса { i + 1 } ? " ) . split ( " " )] for i in range ( n_processes ) ])      max_demand  =  np . array ([  [ int ( x )  for  x  in  input ( f "Максимальный спрос от процесса { i + 1 } ? " ) . split ( " " )] for i in range ( n_processes ) ])      total_available  =  available_resources  -  np.sum ( current_allocated , axis = 0 ) running = np.ones ( n_processes ) # Массив с n_processes 1, указывающий, запущен ли еще процесс    while  np.count_nonzero ( running ) > 0 : at_least_one_allocated = False for p in range ( n_processes ): if running [ p ]: if all ( i > = 0 for i in total_available - ( max_demand [ p ] - current_allocated [ p ] )): at_least_one_allocated = True print ( f " { p } is running" ) running [ p ] = 0 total_available += current_allocated [ p ] if not at_least_one_allocated : print ( "Unsafe" ) break # выход else : print ( "Safe" )

Ограничения

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

Ссылки

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

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