Граф распределения ресурсов

Граф распределения ресурсов (англ. Resource Allocation Graph, RAG) — это ориентированный граф, используемый в операционных системах для моделирования и анализа состояния системы в контексте распределения ресурсов между процессами. Он служит инструментом для выявления взаимоблокировок (дедлоков), а также для визуализации текущего состояния занятости и ожидания ресурсов. Граф состоит из двух типов вершин — процессы и ресурсы — и двух типов рёбер, отражающих запросы и предоставления.

Структура и обозначения

Граф распределения ресурсов является двудольным графом, где вершины делятся на два непересекающихся множества:

• Процессы (обозначаются кружками, обычно с номером процесса, например, P1, P2).
• Ресурсы (обозначаются прямоугольниками, внутри которых указывается тип ресурса и количество его экземпляров, например, R1 с тремя экземплярами).

Рёбра графа бывают двух видов:

• Ребро запроса (направлено от процесса к ресурсу) — показывает, что процесс запрашивает один экземпляр данного ресурса. Обозначается линией со стрелкой от процесса к прямоугольнику ресурса.
• Ребро предоставления (направлено от ресурса к процессу) — показывает, что один экземпляр ресурса выделен данному процессу. Обозначается линией со стрелкой от прямоугольника ресурса к процессу.

Если ресурс имеет несколько экземпляров, то внутри прямоугольника точками обозначается каждый экземпляр. Ребро предоставления прикрепляется к конкретному экземпляру (точке), а ребро запроса — к самому прямоугольнику.

Правила построения

При построении графа соблюдаются следующие правила:

• Процесс может иметь несколько рёбер запроса к разным ресурсам.
• Ресурс может быть предоставлен только одному процессу в каждый момент времени (для однопотоковых ресурсов). Для ресурсов с несколькими экземплярами каждый экземпляр предоставляется отдельному процессу.
• Цикл в графе является необходимым, но не достаточным условием взаимоблокировки.

Анализ взаимоблокировок

Основное применение графа распределения ресурсов — обнаружение взаимоблокировок (дедлоков). Взаимоблокировка возникает, когда каждый процесс из множества ожидает ресурс, который удерживается другим процессом из этого же множества.

Условия возникновения взаимоблокировки

Для возникновения взаимоблокировки необходимо одновременное выполнение четырёх условий (условия Коффмана):

1. Взаимное исключение — ресурс не может быть одновременно использован несколькими процессами.
2. Удержание и ожидание — процесс удерживает хотя бы один ресурс и ожидает получения других.
3. Неперераспределяемость — ресурс не может быть принудительно изъят у процесса.
4. Циклическое ожидание — существует циклическая цепочка процессов, каждый из которых ожидает ресурс, удерживаемый следующим.

Алгоритм обнаружения

Для анализа графа используется алгоритм поиска циклов. Если в графе нет циклов, взаимоблокировка отсутствует. Если цикл есть, необходимо проверить, является ли он достаточным условием дедлока:

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

Для точного анализа применяется алгоритм редукции графа:

1. Найти процесс, который не находится в состоянии взаимоблокировки (не ожидает ресурсы или может получить все запрошенные).
2. Удалить все рёбра, связанные с этим процессом (освободить ресурсы).
3. Повторять шаги 1-2, пока возможно.
4. Если после всех шагов остались процессы с рёбрами, они находятся во взаимоблокировке.

Пример графа

Рассмотрим систему с двумя процессами (P1, P2) и двумя ресурсами (R1 с одним экземпляром, R2 с одним экземпляром):

• P1 удерживает R1 и запрашивает R2.
• P2 удерживает R2 и запрашивает R1.

Граф будет содержать цикл: P1 → R2 → P2 → R1 → P1. Так как каждый ресурс имеет один экземпляр, это состояние является взаимоблокировкой.

Если же ресурс R1 имеет два экземпляра, и P1 удерживает один из них, а P2 запрашивает R1, то цикл может не привести к дедлоку, если второй экземпляр R1 свободен.

Применение в операционных системах

Графы распределения ресурсов используются в следующих контекстах:

• Проектирование алгоритмов предотвращения взаимоблокировок — например, алгоритм банкира, который моделирует безопасные последовательности выделения ресурсов.
• Обнаружение взаимоблокировок — операционные системы могут периодически строить граф и выполнять его редукцию для выявления зависших процессов.
• Обучение и моделирование — в учебных курсах по операционным системам графы используются для наглядного объяснения механизмов синхронизации.

Ограничения

Граф распределения ресурсов имеет ряд ограничений:

• Он не учитывает динамику изменения состояний — показывает только мгновенный снимок.
• Не отражает приоритеты процессов или политики планирования.
• Для систем с большим количеством процессов и ресурсов построение и анализ графа может быть вычислительно затратным.
• Не учитывает возможность освобождения ресурсов в будущем или тайм-ауты.

Связанные понятия

• Взаимоблокировка (дедлок) — состояние, при котором процессы бесконечно ожидают друг друга.
• Алгоритм банкира — метод предотвращения взаимоблокировок, основанный на моделировании безопасных состояний.
• Семафоры и мьютексы — примитивы синхронизации, использование которых может приводить к взаимоблокировкам при неправильном применении.
• Состояние гонки — ситуация, когда результат зависит от порядка выполнения процессов, что также может быть проанализировано с помощью графов.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». 4-е издание. — СПб.: Питер, 2015.
• Сильбершатц А., Гэвин П., Гэгн Г. «Операционные системы: внутренняя структура и принципы проектирования». — М.: Вильямс, 2013.
• Столлингс У. «Операционные системы». 6-е издание. — М.: Вильямс, 2007.
• Дейкстра Э. «Взаимодействие последовательных процессов» (оригинальная работа по алгоритму банкира).