Gráfico de espera - Enciclopedia

Un grafo de espera en la ciencia de la computación es un grafo dirigido utilizado para la detección de bucles muertos en sistemas operativos y sistemas de bases de datos relacionales. En la ciencia de la computación, un sistema que permite la operación concurrente de múltiples procesos y el bloqueo de recursos y que no proporciona mecanismos para evitar o prevenir bucles muertos debe soportar un mecanismo para detectar bucles muertos y un algoritmo para recoverse de ellos.

Uno de los algoritmos de detección de bucles muertos utiliza un grafo de espera para rastrear qué otros procesos un proceso está bloqueando en ese momento. En un grafo de espera, los procesos se representan como nodos y una arista desde el proceso




P

i




{\displaystyle P_{i}}

hasta




P

j




{\displaystyle P_{j}}

implica que




P

j




{\displaystyle P_{j}}

posee un recurso que




P

i




{\displaystyle P_{i}}

necesita y, por lo tanto,




P

i




{\displaystyle P_{i}}

está esperando que




P

j




{\displaystyle P_{j}}

libere su bloqueo sobre ese recurso. Si el proceso está esperando más de un recurso para volverse disponible (el caso trivial), pueden representarse múltiples aristas como un conjunto conjuntivo (y) o disyuntivo (o) de diferentes recursos o un cierto número de recursos equivalentes de una colección. La posibilidad de un bucle muerto se implica por ciclos en el caso conjuntivo y por nudos en el caso disyuntivo. No hay un algoritmo simple para detectar la posibilidad de un bucle muerto en el caso final.

Un grafo de espera es un grafo de conflictos bloqueados por locks de ser materializados; también puede definirse como el grafo de conflictos no materializados; los conflictos no materializados no se reflejan en el grafo de precedencia y no afectan la serializabilidad.

El esquema de grafo de espera no es aplicable a un sistema de asignación de recursos con múltiples instancias de cada tipo de recurso.

Una arista desde una transacción T1 a otra transacción T2 representa que T1 espera que T2 libere un lock (es decir, T1 adquirió un lock que es incompatible con un lock previamente adquirido por T2). Un lock es incompatible con otro si están en el mismo objeto, uno es de escritura y provienen de transacciones diferentes.

Un bucle muerto ocurre en un horario si y solo si hay al menos un ciclo en el grafo de espera. No todos los ciclos necesariamente representan una instancia de bucle muerto distinta.

Referencias