Тупик в случае повторно используемых ресурсов
Повторно используемые ресурсы SR (Second hand resource) – это конечное множество одинаковых ресурсов, обладающих следующими свойствами:
* количество единиц ресурсов постоянно;
* каждая единица ресурса или распределена, или доступна только одному процессу;
* процесс может освободить единицу ресурса (или сделать его доступным) при условии, если он ранее получал эту единицу.
Примеры SR-ресурсов: ОП, ВнП, периферийные устройства и, возможно, процессоры, а также такое ПО, как файлы данных, таблицы и "разрешение войти в критическую секцию".
Графы SR. В случае SR-ресурсов граф типа "процесс-ресурс", отображающий состояние OS, называют графом повторно используемых ресурсов. Направленный граф – это пара < N, E >, где N – множество вершин, а E – множество упорядоченных пар (a, b), называемых ребрами, a, bÎN. В случае SR интерпретация графа следующая.
1. Множество N разделено на два непересекающихся класса: P = {p1, p2, ..., pn} – множество вершин для отображения процессов и r = {R1, R2, ..., Rm} – множество вершин для представления ресурсов.
2. Граф является двудольным по отношению к P и r. Каждое ребро e Ì E соединяет вершину из P с вершиной из r. Если e = (pi, Rj), то e – ребро запроса от процесса pi на единицу ресурса Rj. Если же e = (Rj, pi), то e – ребро назначения единицы ресурса Rj процессу pi.
3. Для каждого RiÎr целое неотрицательное число ti, обозначает количество единиц ресурса Ri.
Пусть | (a, b) | – число ребер, направленных от вершины a к вершине b. Тогда система должна работать всегда при следующих ограничениях:
* может быть сделано не более чем ti назначений для Ri, т. е.
* | (Ri, pj) | + | (pj, Ri) | £ ti, для " i, j,
т. е. сумма запросов и распределений для некоторого ресурса не должна превышать количества доступных единиц.
Состояние системы изменяется только в результате запросов, освобождений или приобретений ресурсов одним процессом.
Следует отметить, что процессы являются недетерминированными, так как не существует общего способа узнать заранее, какой ресурс запросит процесс или освободит его в конкретный момент времени.
Чтобы распознать состояние тупика, для каждого процесса необходимо определить, сможет ли он когда-либо снова развиваться. Наиболее благоприятные действия для незаблокированного процесса pi могут представляться сокращением (редукцией) графа SR.
SR-граф сокращается процессом pi через удаление всех ребер, входящих в pi
и выходящих из него. Естественно, процесс pi не должен быть заблокирован и не должен представляться изолированной вершиной в SR-графе. Если процесс интерпретируется как приобретение pi ранее запрошенных ресурсов и затем освобождение всех его ресурсов, тогда pi становится изолированной вершиной.
Граф SR несокращаем, если он не может быть сокращен ни одним процессом. Граф SR полностью сокращаем, если существует последовательность сокращений, которые устраняют все ребра графа. Пример сокращения показан на рис. 7.9.
 |
Теорема. Состояние S есть состояние тупика тогда и только тогда, когда SR-граф в состоянии S не является полностью сокращаемым.
Следствие 1. Если S есть состояние тупика по SR-ресурсам, то по крайней мере два процесса находятся в тупике в S.
Следствие 2. Процесс pi не находится в тупике тогда и только тогда, когда серия сокращений приводит к состоянию, в котором pi
не заблокирован.
