Операционные системы, среды и оболочки

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

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

Обнаружение тупика посредством редукции графа повторно используемых ресурсов:
? Граф повторно используемых ресурсов сокращается процессом Рi, который не является ни заблокированной, ни изолированной вершиной, путем удаления всех ребер, входящих в вершину Рi и выходящих из Рi.
? Граф повторно используемых ресурсов несокращаем, если он не может быть сокращен ни одним процессом.
? Граф ресурсов типа SR является полностью сокращаемым, если существует последовательность сокращений, которая удаляет все дуги графа.
Лемма: для ресурсов типа SR порядок сокращений дуг графа повторно используемых ресурсов несуществен; все последовательности ведут к одному и тому же несокращаемому графу.
Теорема о тупике: Состояние S есть состояние тупика тогда и только тогда, когда граф повторно используемых ресурсов в состоянии S не является полностью сокращаемым.
Первое следствие: процесс не находится в тупике тогда и только тогда, когда серия сокращений приводит к состоянию, в котором он не заблокирован.
Второе следствие: если S есть состояние тупика (по ресурсам типа SR), то по крайней мере два процесса находятся в тупике в S.
? Из теоремы о тупике следует и алгоритм обнаружения тупиков. Нужно попытаться сократить граф; если граф полностью не сокращается, то начальное состояние было состоянием тупика для тех процессов, вершины которых остались в несокращенном графе.
? Лемма позволяет предложить алгоритмы обнаружения тупика. Например, можно представить систему посредством графа повторно используемых ресурсов и попробовать выполнить его редукцию.
Методы обнаружения тупика по наличию замкнутой цепочки запросов
? Первая теорема: цикл в графе повторно используемых ресурсов является необходимым условием тупика.
? Вторая теорема: тупик может быть вызван только при запросе, который не удовлетворен немедленно. Т.е. проверка на тупиковое состояние может быть выполнена боле эффективно, если она проводится непрерывно (по мере развития процессов).
? Состояние называется фиксированным, если каждый процесс, выдавший запрос, заблокирован.
? Третья теорема: если состояние системы фиксированное (все процессы, имеющие запросы, удовлетворены), то наличие узла в соответствующем графе повторно используемых ресурсов — достаточное условие тупика.
? Четвертая теорема: граф повторно используемых ресурсов с единичной емкостью указывает на состояние тупика тогда и только тогда, когда он содержит цикл.
Алгоритм обнаружения тупика по наличию замкнутой цепочки запросов