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


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


Повторно используемые ресурсы SR (Second hand resource) – это конечное множество одинаковых ресурсов, обладающих следующими свойствами:

*                   количество единиц ресурсов постоянно;

*                   каждая единица ресурса или распределена, или доступна только одному процессу;

*                   процесс может освободить единицу ресурса (или сделать его доступным) при условии, если он ранее получал эту единицу.

Примеры SR-ресурсов: ОП, ВнП, периферийные устройства и, возможно, процессоры, а также такое ПО, как файлы данных, таблицы и "разрешение войти в критическую секцию".

Графы SR. В случае SR-ресурсов граф типа "процесс-ресурс", отображающий состояние OS, называют графом повторно используемых ресурсов. Направленный граф – это пара < N, E >, где N – множество вершин, а E – множество упорядоченных пар (a, b), называемых ребрами, a, bÎN. В случае SR интерпретация графа следующая.

1. Множество N разделено на два непересекающихся класса:= {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. Тогда система должна работать всегда при следующих ограничениях:




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



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