![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Существует четыре основных стратегии работы с тупиками.
1. Полное игнорирование проблемы (" алгоритм страуса"). В большинстве своем реальные операционные системы не осуществляют борьбу с тупиками, поскольку ресурсов и так достаточно много. 2. Предотвращение тупиков (prevention) — подход, цель которого обеспечение условий, исключающих возможность возникновения тупиковой ситуации. Чтобы предотвратить тупик, достаточно нарушить хотя бы одно необходимое условие. · Первое условие (взаимоисключение) вполне естественно (например, для такого устройства, как накопитель на магнитной ленте). · Нарушая второе условие (ожидание), процесс должен сразу запросить все ресурсы. Эффективность системы при этом может значительно ухудшиться. В качестве компромиссного решения можно предложить разделять процесс на шаги. · Нарушить третье условие (нераспределяемость) можно следующим образом. Процесс, удерживающий ресурсы и получивший отказ на другие ресурсы, должен освободить все взятые ресурсы, и через некоторое время запросить их заново. При этом процесс может потерять большую часть проделанной работы. · Нарушая четвертое условие (кругового ожидания), следует ввести линейную упорядоченность ресурсов, пронумеровав их, и выдавать их в порядке, не допускающим возникновение кругового ожидания. Данный подход требует значительных накладных расходов на хранение информации, связанной с типами ресурсов и упорядоченностью экземпляров ресурсов. 3. Обход тупиков (avoidance) — подход, который обеспечивает рациональное распределение ресурсов по рациональным правилам. Он вводит менее жесткие ограничения, чем предыдущий подход. Наиболее известным методом обхода тупиков является алгоритм банкира: · Алгоритм банкира имитирует действия банкира, располагающего определенным источником капитала, выдающего ссуды и принимающего платежи. Алгоритм был предложен Дейкстрой. · Состояние системы будем называть надежным, если операционная система может обеспечить всем пользователям завершение их задач в течение конечного промежутка времени. Суть алгоритма в том, что система удовлетворяет только те запросы, при которых ее состояние остается надежным. Остальные запросы откладываются. · Существуют два основных ограничения этого подхода: каждый процесс заранее должен указать максимальное количество ресурсов, которое ему понадобится и в каждый момент процесс должен захватывать только один ресурс. Данный алгоритм на практике неприменим из-за его неэффективности, т. к. необходимость в пересчете возникает непрерывно, при каждом поступлении процесса в систему и его удалении для каждой разновидности ресурсов. 4. Обнаружение тупиков (detection) — подход, который допускает возникновение тупиков, определяет процессы и ресурсы, которые вовлечены в тупиковую ситуацию, и пытается вывести систему из нее. Для анализа свойств асинхронных процессов (в частности, для обнаружения тупиков) используются графические модели, которые мы сейчас рассмотрим.
|