Введение в архитектуру компьютеров


Тупик в случае повторно используемых ресурсов - часть 2


*                   может быть сделано не более чем ti назначений для Ri, т. е.

 для всех i;

*                   | (Ri, pj) | + | (pj, Ri) | £ ti, для " i, j,

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

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

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

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

SR-граф сокращается процессом pi через удаление всех ребер, входящих в pi

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

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


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

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

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

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

не заблокирован.




Начало  Назад  Вперед



Книжный магазин