Gráfico de espera

El gráfico de espera (o gráfico de espera de transacción ) es una herramienta que se utiliza en el desarrollo de DBMS y sistemas de subprocesos múltiples y se utiliza, en particular, para determinar la situación de interbloqueo . De hecho, el gráfico de espera de transacción es un gráfico bipartito dirigido que contiene dos tipos de vértices:

vértices de tipo correspondientes a transacciones o hilos en ejecución. Forman la primera parte del gráfico. $T$
vértices de tipo correspondientes a recursos y objetos que pueden ser capturados por transacciones. Forman la segunda parte del gráfico. $R$

Los arcos del gráfico de espera también tienen un doble significado:

los arcos que van del nodo de transacción al nodo de recurso indican que este recurso ya ha sido capturado por la transacción ${\ estilo de visualización (T, R)}$ $T$ $R$
los arcos que van desde el nodo de recursos hasta el nodo de transacción indican que la transacción está esperando a que se libere el recurso. ${\ estilo de visualización (R, T)}$ $R$ $T$ $R$

Las propiedades más simples

Un recurso que no tiene arcos entrantes es gratuito.
Si un vértice de transacción tiene un cierto número distinto de cero de arcos entrantes, entonces el proceso correspondiente (la transacción en sí) está en estado de espera, es decir, está suspendido y no se puede ejecutar en el momento actual.
Si hay una ruta entre dos transacciones , entonces la transacción debe ejecutarse (completarse) antes de que comience la ejecución , ya que esta última requiere la liberación de algunos recursos capturados por la transacción . $T_{1}\rightarrow T_{2}$ $T_{1}$ $T_{2}$ $T_{1}$

De la última propiedad se sigue obviamente que la situación de interbloqueo corresponde a un ciclo en el gráfico de espera.

Fuentes

Callejones sin salida, reconocimiento y destrucción Archivado el 2 de marzo de 2007 en Wayback Machine .