Многопроцессорные вычислительные системы

Основы вычислительных систем

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

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

Чтобы распознать состояние тупика, для каждого процесса необходимо определить, сможет ли он когда-либо снова развиваться. Наиболее благоприятные действия для незаблокированного процесса p_i могут представляться сокращением (редукцией) графа SR.

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

Граф SR несокращаем, если он не может быть сокращен ни одним процессом. Граф SR полностью сокращаем, если существует последовательность сокращений, которые устраняют все ребра графа. Пример сокращения показан на рис. 5.9.

Рис. 5.9. Последовательность сокращений графа

Теорема. Состояние S есть состояние тупика тогда и только тогда, когда SR-граф в состоянии S не является полностью сокращаемым.

Следствие 1. Если S есть состояние тупика по SR-ресурсам, то по крайней мере два процесса находятся в тупике в S.

Следствие 2. Процесс p_i не находится в тупике тогда и только тогда, когда серия сокращений приводит к состоянию, в котором p_i не заблокирован.