Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





Тупики возникают как в аппаратных, так и в программных ресурсах.

Рассмотрим пример. Предположим, что два процесса осуществляют вывод с ленты на принтер. Один из них успел монополизировать ленту и претендует на принтер, а другой наоборот. После этого оба процесса оказываются заблокированными в ожидании второго ресурса (см. рис.)

Рис. 12. Пример тупиковой ситуации.

 

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

Чаще всего тупики связаны с выделенными ресурсами, то есть тупики возникают, когда процессу дается эксклюзивный доступ к устройствам, файлам и другим ресурсам.

Условия возникновения тупиков

Условия возникновения тупиков были сформировыаны Коффманом, Элкином, Шошани в 1970г.

1. Условие взаимоисключения (Mutual exclusion). Каждый ресурс выделен в точности одному процессу или доступен. Процессы требуют предоставления им монопольного управления ресурсами, которые им выделяются.

2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают за собой ресурсы, уже выделенные им, ожидая в то же время выделения дополнительных ресурсов (которые при этом обычно удерживаются другими процессами).

3. Условие неперераспределяемости (No preemtion). Ресурс, данный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.

4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся другим процессам цепи.

Основные направления борьбы с тупиками:

1. Игнорировать проблему в целом

2. Предотвращение тупиков

3. Обнаружение тупиков

4. Восстановление после тупиков

Игнорирование проблемы тупиков

Подход современных ОС (UNIX, Windows) состоит в том, чтобы игнорировать данную проблему в предположении, что маловероятный тупик предпочтительнее, чем нелепые правила, которые заставят пользователя ограничить число процессов, открытых файлов.

Способы предотвращения тупиков.

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

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

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

2. Можно избежать взаимоблокировки, если нарушить условия возникновения тупиков

А) Нарушение условия взаимоисключения

Если в системе отсутствуют выделенные ресурсы, тупиков не будет. Тем не менее, ясно, что обобществление, например, принтера, то есть, разрешение двум процессам писать на один принтер в одно и то же время приведет к хаосу. За счет организации спулинга эту проблему можно решить.

Б) Hарушение условия ожидания дополнительных ресурсов

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

· В первой фазе каждый процесс должен запрашивать все требуемые ему ресурсы сразу, причем не может начать выполняться до тех пор, пока все они не будут ему предоставлены.

· Если же процесс, удерживает определенные ресурсы и получает отказ в выделении ему дополнительных ресурсов, то он должен освободить свои первоначальные ресурсы и, при необходимости, запросить их снова вместе с дополнительными.

в) Нарушение принципа отсутствия перераспределения.

Если можно было отбирать ресурсы у удерживающих их процессов до завершения этих процессов, то можно добиться не выполнения третьего условия возникновения тупиков.

С) Нарушение условия кругового ожидания

Решение этой проблемы – упорядочить ресурсы.

Первый способ - присвоить всем ресурсам уникальные номера и потребовать, чтобы процессы запрашивали ресурсы в порядке возрастания номеров. Тогда круговое ожидание возникнуть не может. Упорядочивание ресурсов в ОС Windows2000 –создание спин – блокировок. Спин–блокировка – способ синхронизации процессов наиболее простой. Спин – блокировка может быть захвачена и освобождена процессом.

Второй способ - каждый процесс может иметь только один ресурс в каждый момент времени. Если нужен второй ресурс - освободи первый.

Обнаружение тупиков.

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

Способы вывода из тупика

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

2. Временно забрать ресурс у текущего владельца и передать его другому процессу.

Возможность забрать ресурс у процесса, дать его другому процессу и затем вернуть его назад без нанесения ущерба сильно зависит от природы ресурса. Подобное восстановление часто трудно, если не невозможно.

3. В ряде систем реализованы средства рестарта с контрольной точки или средства отката (сохранение состояния системы в какой-то момент времени). Там где эти средства не предусмотрены, их должны организовать разработчики прикладных программ. Если проектировщики системы знают, что тупик вероятен, они могут периодически организовывать для процессов контрольные точки.

Когда тупик обнаружен, видно какие ресурсы вовлечены в цикл кругового ожидания. Чтобы осуществить восстановление, процесс, который владеет таким ресурсом, должен быть отброшен к моменту времени, предшествующему его запросу на этот ресурс.

Заключение. Борьба с тупиками слишком дорога, поэтому надо бороться только в тех системах, где игнорирование приведет к катастрофе.







Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.