Операционные системы. Курс лекций
Тупики. - часть 4
Для обнаружения тупиков нужно составить матрицу.
Алгоритм обнаружения взаимоблокировки основан на обнаружении векторов. Пусть в исходном положении все процессы не маркированы. По мере продвижения алгоритма на процессы будет ставиться отметка служащая признаком того что они могут закончить свою работу т.е. они не находятся в тупике.
После завершения алгоритма известно, что любой, не маркированный процесс, находится в тупике.
Алгоритм обнаружения тупиков состоит из шагов:
1. Ищем не маркированный процесс,
2. Если такой процесс найден, то прибавляем i-ю строку матрицы текущего распределения С к вектору А, маркируем процесс и возвращаемся к шагу 1;
3. Если таких процессов не существует, то работа алгоритма завершается.
Завершение алгоритма означает, что все, не маркированные процессы, находятся в тупике.
На первом шаге алгоритм ищет процесс, который может доработать до конца, такой процесс характеризуется тем, что все требуемые для него должны находится среди доступных в данный момент ресурсов. Тогда выбираемый процесс проработает до своего завершения и после этого вернет ресурсы, которые он занимал в общий фонд доступных ресурсов. Если окажется, что все процессы могут работать, тогда не один из них в данный момент не заблокирован и может быть выбран для работы. Если некоторые из процессов никогда не смогут запуститься, значит, они попали в тупик.
Восстановление при помощи принудительной выгрузки ресурса. Иногда можно временно отобрать ресурс у его текущего ресурса и отдать его другому владельцу. Возможность забирать ресурс у процесса в значительной мере зависит от свойств ресурса. Большинство процессов владеющие ресурсом не могут отдать его другому процессу.
Восстановление через откат. Если разработчики системы знают о вероятности появления взаимоблокировки, то они могут организовать работу так что бы процессы периодически создавали контрольные точки, т.е.