Существует четыре основных стратегии работы с тупиками.
1. Полное игнорирование проблемы ("алгоритм страуса"). В большинстве своем реальные операционные системы не осуществляют борьбу с тупиками, поскольку ресурсов и так достаточно много.
2. Предотвращение тупиков (prevention) — подход, цель которого обеспечение условий, исключающих возможность возникновения тупиковой ситуации. Чтобы предотвратить тупик, достаточно нарушить хотя бы одно необходимое условие.
· Первое условие (взаимоисключение) вполне естественно (например, для такого устройства, как накопитель на магнитной ленте).
· Нарушая второе условие (ожидание), процесс должен сразу запросить все ресурсы. Эффективность системы при этом может значительно ухудшиться. В качестве компромиссного решения можно предложить разделять процесс на шаги.
· Нарушить третье условие (нераспределяемость) можно следующим образом. Процесс, удерживающий ресурсы и получивший отказ на другие ресурсы, должен освободить все взятые ресурсы, и через некоторое время запросить их заново. При этом процесс может потерять большую часть проделанной работы.
· Нарушая четвертое условие (кругового ожидания), следует ввести линейную упорядоченность ресурсов, пронумеровав их, и выдавать их в порядке, не допускающим возникновение кругового ожидания. Данный подход требует значительных накладных расходов на хранение информации, связанной с типами ресурсов и упорядоченностью экземпляров ресурсов.
3. Обход тупиков (avoidance)— подход, который обеспечивает рациональное распределение ресурсов по рациональным правилам. Он вводит менее жесткие ограничения, чем предыдущий подход. Наиболее известным методом обхода тупиков является алгоритм банкира:
· Алгоритм банкира имитирует действия банкира, располагающего определенным источником капитала, выдающего ссуды и принимающего платежи. Алгоритм был предложен Дейкстрой.
· Состояние системы будем называть надежным, если операционная система может обеспечить всем пользователям завершение их задач в течение конечного промежутка времени. Суть алгоритма в том, что система удовлетворяет только те запросы, при которых ее состояние остается надежным. Остальные запросы откладываются.
· Существуют два основных ограничения этого подхода: каждый процесс заранее должен указать максимальное количество ресурсов, которое ему понадобится и в каждый момент процесс должен захватывать только один ресурс. Данный алгоритм на практике неприменим из-за его неэффективности, т. к. необходимость в пересчете возникает непрерывно, при каждом поступлении процесса в систему и его удалении для каждой разновидности ресурсов.
4. Обнаружение тупиков (detection) — подход, который допускает возникновение тупиков, определяет процессы и ресурсы, которые вовлечены в тупиковую ситуацию, и пытается вывести систему из нее.
Для анализа свойств асинхронных процессов (в частности, для обнаружения тупиков) используются графические модели, которые мы сейчас рассмотрим.
Дата добавления: 2020-03-21; просмотров: 558;