<<
>>

Способы предотвращения тупиков путем тщательного распределения ресурсов. Алгоритм банкира

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

наиболее известен алгоритм банкира, предложенный Дейкстрой, который базируется на так называемых безопасных или надежных состояниях (safe state).

Безопасное состояние — это такое состояние, для которого имеется по крайней мере одна последовательность событий, которая не приведет к взаимоблокировке. Модель алгоритма основана на действиях банкира, который, имея в наличии капитал, выдает кредиты.

Суть алгоритма состоит в следующем:

• Предположим, что у системы в наличии п устройств, например, лент.

• ОС принимает запрос от пользовательского процесса, если его максимальная потребность не превышает п.

• Пользователь гарантирует, что если ОС в состоянии удовлетворить его запрос, то все устройства будут возвращены системе в течение конечного времени.

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

• В соответствии с алгоритмом банкира выделение устройств возможно, только если состояние системы остается надежным.

Рассмотрим пример надежного состояния для системы с 3 пользователями и 11 устройствами, где 9 устройств задействовано, а 2 имеется в резерве. Пусть текущая ситуация такова:

Таблица 7.1

Данное состояние надежно. Последующие действия системы могут быть таковы. Вначале удовлетворить запросы третьего пользователя, затем дождаться, когда он закончит работу и освободит свои три устройства. Затем можно обслужить первого и второго пользователей. То есть система удовлетворяет только те запросы, которые оставляют ее в надежном состоянии, и отклоняет остальные.

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

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

• Число пользователей и число ресурсов фиксировано.

• Число работающих пользователей должно оставаться постоянным.

• Алгоритм требует, чтобы клиенты гарантированно возвращали ресурсы.

• Должны быть заранее указаны максимальные требования процессов

к ресурсам. Чаще всего данная информация отсутствует.

Наличие таких жестких и зачастую неприемлемых требований может склонить разработчиков к выбору других решений проблемы взаимоблокировки.

<< | >>
Источник: В.Е. Карпов К.А. Коньков. Основы операционных систем. 2005

Еще по теме Способы предотвращения тупиков путем тщательного распределения ресурсов. Алгоритм банкира:

  1. Статья 209-1. Умышленное нарушение требований законодательства о предотвращении и противодействии легализации (Отмыванию) доходов, полученных преступным путем, или финансирования терроризма
  2. Статья 409. Уклонение от военной службы путем самокалечения или иным способом
  3. Статья 188. Похищение путем демонтажа и иным способом электрических сетей, кабельных линий связи и их оборудования - Статья 188 исключена на основании Закона N 270-VI от 15.04.2008
  4. 1 . Следите за его весом столь же тщательно, как и за своим.
  5. Статья 325. Нарушение санитарных правил и норм по предотвращения инфекционных заболеваний и массовых отравлением
  6. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  7. Статья 27. Предотвращение ограничения способности физического лица иметь гражданские права и обязанности
  8. АЛГОРИТМ
  9. АЛГОРИТМ УДАЧИ
  10. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  11. 1. "Тупик"
  12. Алгоритм исцеления:
  13. Способ мышления определяет способ взаимоотношений с окружающим миром.
  14. Прием преодоления умственных тупиков.
  15. Прием преодоления умственных тупиков.