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