Un gráfico de espera en informática es un gráfico dirigido que se utiliza para la detección de bloqueos 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 bloqueos debe soportar un mecanismo para detectar bloqueos y un algoritmo para recuperarse de ellos.
Un algoritmo de detección de interbloqueos de este tipo utiliza un gráfico de espera para rastrear qué otros procesos están bloqueando actualmente un proceso. En un gráfico de espera, los procesos se representan como nodos y una arista del proceso a implica que tiene un recurso que necesita y, por lo tanto, está esperando para liberar su bloqueo en ese recurso. Si el proceso está esperando que haya más de un recurso 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 interbloqueo 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 interbloqueo en el caso final. [1]
Un gráfico de espera es un gráfico de conflictos bloqueados por bloqueos que no se materializan; también se puede definir como el gráfico de conflictos no materializados; los conflictos no materializados no se reflejan en el gráfico de precedencia y no afectan la serializabilidad.
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 desde 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 adquirido previamente de T2). Un bloqueo es incompatible con otro si están en el mismo objeto, uno es una escritura y son de transacciones diferentes.
Se produce un bloqueo en una programación si y solo si hay al menos un ciclo en el gráfico de espera. No todos los ciclos representan necesariamente una instancia de bloqueo distinta.
