График ожидания - Wait-for graph

А график ожидания в Информатика это ориентированный граф используется для тупик обнаружение в операционные системы и реляционная база данных системы.

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

Один из таких алгоритмов обнаружения взаимоблокировок использует график ожидания, чтобы отслеживать, какие другие процессы блокируются в данный момент. В графе ожидания процессы представлены как узлы, а ребро от процесса ${\displaystyle P_{i}}$ к ${\displaystyle P_{j}}$ подразумевает ${\displaystyle P_{j}}$ держит ресурс, который ${\displaystyle P_{i}}$ потребности и таким образом ${\displaystyle P_{i}}$ ждет ${\displaystyle P_{j}}$ чтобы снять блокировку с этого ресурса. Если процесс ожидает, пока станет доступным более одного ресурса (тривиальный случай), несколько ребер могут представлять конъюнктивный (и) или дизъюнктивный (или) набор различных ресурсов или определенное количество эквивалентных ресурсов из коллекции. Возможность тупика подразумевает график циклы в конъюнктивном случае и узлы в дизъюнктивном случае. Не существует простого алгоритма обнаружения возможности тупика в конечном случае.^[1]

Схема ожидания графа не применима к системе распределения ресурсов с множеством экземпляров каждого типа ресурса.

Рекомендации

1. Шринивасан, Сельварадж; Раджарам, Раджив (январь 2011 г.). «Децентрализованный алгоритм обнаружения и разрешения тупиковых ситуаций для обобщенной модели в распределенных системах». Тамил Наду: Инженерный колледж RMD. Дои:10.1007 / s10619-011-7078-7. Получено Двадцать первое октября, 2020.

• Зильбершац, Авраам; Гэлвин, Питер; Ганье, Грег (2003). Понятия операционной системы. John Wiley & Sons, Inc., стр.260. ISBN  0-471-25060-0.