Страница: 15/18
В некоторых случаях, когда тупиковая ситуация образована многими процессами, использующими много ресурсов, распознавание тупика является нетривиальной задачей. Существуют формальные, программно - реализованные методы распознавания тупиков, основанные на ведении таблиц распределения ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки.
Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения все заблокированные процессы. Можно снять только часть из них, при этом освобождаются ресурсы, ожидаемые остальными процессами, можно вернуть некоторые процессы в область свопинга, можно совершить "откат" некоторых процессов до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в местах, после которых возможно возникновение тупика. Из всего вышесказанного ясно, что использовать семафоры нужно очень осторожно, так как одна незначительная ошибка может привести к останову системы. Для того чтобы облегчить написание корректных программ, было предложено высокоуровневое средство синхронизации, называемое монитором. Монитор - это набор процедур, переменных и структур данных. Процессы могут вызывать процедуры монитора, но не имеют доступа к внутренним данным монитора. Мониторы имеют важное свойство, которое делает их полезными для достижения взаимного исключения: только один процесс может быть активным по отношению к монитору. Компилятор обрабатывает вызовы процедур монитора особым образом. Обычно, когда процесс вызывает процедуру монитора, то первые несколько инструкций этой процедуры проверяют, не активен ли какой-либо другой процесс по отношению к этому монитору. Если да, то вызывающий процесс приостанавливается, пока другой процесс не освободит монитор. Таким образом, исключение входа нескольких процессов в монитор реализуется не программистом, а компилятором, что делает ошибки менее вероятными.
В распределенных системах, состоящих из нескольких процессоров, каждый из которых имеет собственную оперативную память, семафоры и мониторы оказываются непригодными. В таких системах синхронизация может быть реализована только с помощью обмена сообщениями.
3.5 Предотвращение тупиковых ситуаций
Для предотвращения тупика необходимо использовать ресурсы таким способом, при котором мы не можем войти в тупик. В реальной жизни аналог такого решения это “левые повороты слишком опасны, так что мы делаем только правые повороты”. Это требует больше времени, чтобы добраться до места назначения, но такой метод работает. В терминах тупиков, мы можем удерживать использование ресурсов так, чтобы не волноваться о возможности возникновения тупиков. Здесь мы рассмотрим эту идею на нескольких примерах.
3.5.1 Линейное упорядочение ресурсов
Пусть все ресурсы полностью упорядочены от 1 до r. Мы можем наложить следующее ограничение: процесс не может запрашивать ресурс Rk, если он удерживает ресурс Rh и при этом k < h.
Просто видеть, что, используя это правило, мы никогда не будем входить в тупики. (Для доказательства применим метод доказательства от противного).
Приведем пример того, как применяется это правило. Пусть есть процесс, который использует ресурсы, упорядоченные как A, B, C, D, E, следующим способом:
|
|
Тогда процесс может делать следующее:
захватить (A); захватить (B); захватить (C);
использовать C;
использовать A, C;
использовать A, B, C;
освободить (A); освободить (B); захватить (E);
использовать C и E;
освободить (C); освободить (E); захватить (D);
использовать D;
освободить (D);
Стратегия этого типа может использоваться, когда мы имеем несколько ресурсов. Эту стратегию просто применять, при этом степень параллелизма уменьшается не слишком сильно.
3.5.2 Иерархическое упорядочение ресурсов
Реферат опубликован: 6/09/2006