Операционные системы. Курс лекций




Тупики. - часть 4


Для обнаружения тупиков нужно составить матрицу.

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

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

Алгоритм обнаружения тупиков состоит из шагов:

1.    Ищем не маркированный процесс,

 для которого i-ая строка матрицы запросов R<= A (вектора доступных ресурсов);

2.    Если такой процесс найден, то прибавляем i-ю строку матрицы текущего распределения С к вектору А, маркируем процесс и возвращаемся к шагу 1;

3.    Если таких процессов не существует, то работа алгоритма завершается.

Завершение алгоритма означает, что все, не маркированные процессы, находятся в тупике.

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

 

Восстановление при помощи принудительной выгрузки ресурса. Иногда можно временно отобрать ресурс у его текущего ресурса и отдать его другому владельцу. Возможность забирать ресурс у процесса в значительной мере зависит от свойств ресурса. Большинство процессов владеющие ресурсом не могут отдать его другому процессу.

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


Содержание  Назад  Вперед