Un gráfico de espera en informática es un gráfico dirigido que se utiliza para la detección de interbloqueos en sistemas operativos y sistemas de bases de datos relacionales .
En informática, un sistema que permite la operación simultánea de múltiples procesos y el bloqueo de recursos y que no proporciona mecanismos para evitar o prevenir el bloqueo debe admitir un mecanismo para detectar bloqueos y un algoritmo para recuperarse de ellos.
Uno de esos algoritmos de detección de interbloqueos utiliza un gráfico de espera para rastrear qué otros procesos está bloqueando actualmente un proceso. En un gráfico de espera, los procesos se representan como nodos, y una ventaja desde el proceso hasta lo implica retiene un recurso que necesita y, por lo tanto, está esperando que se libere su bloqueo sobre ese recurso. Si el proceso está esperando que más de un recurso esté disponible (el caso trivial), múltiples aristas pueden representar un conjunto conjuntivo (y) o disyuntivo (o) de diferentes recursos o una cierta cantidad de recursos equivalentes de una colección. La posibilidad de un punto muerto está implícita en los ciclos del gráfico en el caso conjuntivo y en los nudos en el caso disyuntivo. No existe un algoritmo simple para detectar la posibilidad de un punto muerto en el caso final. [1]
Un gráfico de espera es un gráfico de conflictos bloqueados por bloqueos para que no se materialicen; también puede definirse como el gráfico de los conflictos no materializados; Los conflictos no materializados no se reflejan en el gráfico de precedencia y no afectan la serialización.
El esquema de espera de gráfico no es aplicable a un sistema de asignación de recursos con múltiples instancias de cada tipo de recurso.
Un arco de una transacción T1 a otra transacción T2 representa que T1 espera a que T2 libere un bloqueo (es decir, T1 adquirió un bloqueo que es incompatible con un bloqueo previamente adquirido de T2). Un bloqueo es incompatible con otro si están en el mismo objeto, uno es de escritura y son de transacciones diferentes.
Se produce un punto muerto en una programación si y sólo si hay al menos un ciclo en el gráfico de espera. No cada ciclo representa necesariamente un caso distinto de punto muerto.
