DBMS - Interbloqueo

En un sistema multiproceso, el interbloqueo es una situación no deseada que surge en un entorno de recursos compartidos, donde un proceso espera indefinidamente un recurso que está retenido por otro proceso.

Por ejemplo, suponga un conjunto de transacciones {T 0 , T 1 , T 2 , ..., T n }. T 0 necesita un recurso X para completar su tarea. El recurso X está en manos de T 1 , y T 1 está esperando un recurso Y, que está en manos de T 2 . T 2 está esperando el recurso Z, que está retenido por T 0 . Por lo tanto, todos los procesos esperan entre sí para liberar recursos. En esta situación, ninguno de los procesos puede finalizar su tarea. Esta situación se conoce como punto muerto.

Los interbloqueos no son saludables para un sistema. En caso de que un sistema se atasque en un punto muerto, las transacciones involucradas en el punto muerto se revierten o se reinician.

Prevención de interbloqueo

Para evitar cualquier situación de punto muerto en el sistema, el DBMS inspecciona agresivamente todas las operaciones, donde las transacciones están a punto de ejecutarse. El DBMS inspecciona las operaciones y analiza si pueden crear una situación de punto muerto. Si encuentra que puede ocurrir una situación de interbloqueo, nunca se permitirá que se ejecute esa transacción.

Existen esquemas de prevención de interbloqueo que utilizan un mecanismo de orden de marca de tiempo de las transacciones para predeterminar una situación de interbloqueo.

Esquema de esperar a morir

En este esquema, si una transacción solicita bloquear un recurso (elemento de datos), que ya está retenido con un bloqueo conflictivo por otra transacción, entonces puede ocurrir una de las dos posibilidades:

  • Si TS (T i ) <TS (T j ), es decir, T i , que solicita un bloqueo en conflicto, es más antiguo que T j , entonces T i puede esperar hasta que el elemento de datos esté disponible.

  • Si TS (T i )> TS (t j ), es decir, T i es más joven que T j , entonces T i muere. T i se reinicia más tarde con un retraso aleatorio pero con la misma marca de tiempo.

Este esquema permite que la transacción más antigua espere pero mata a la más joven.

Esquema de espera de heridas

En este esquema, si una transacción solicita bloquear un recurso (elemento de datos), que ya está retenido con un bloqueo conflictivo por otra transacción, puede ocurrir una de las dos posibilidades:

  • Si TS (T i ) <TS (T j ), entonces T i fuerza a T j a retroceder, es decir, T i hiere a T j . T j se reinicia más tarde con un retraso aleatorio pero con la misma marca de tiempo.

  • Si TS (T i )> TS (T j ), entonces T i se ve obligado a esperar hasta que el recurso esté disponible.

Este esquema permite que la transacción más joven espere; pero cuando una transacción anterior solicita un artículo en poder de uno más joven, la transacción anterior obliga al más joven a abortar y liberar el artículo.

En ambos casos, la transacción que ingresa al sistema en una etapa posterior se cancela.

Evitación de puntos muertos

Abortar una transacción no siempre es un enfoque práctico. En su lugar, se pueden utilizar mecanismos de evitación de interbloqueo para detectar cualquier situación de interbloqueo por adelantado. Están disponibles métodos como "gráfico de espera", pero son adecuados solo para aquellos sistemas donde las transacciones son ligeras y tienen menos instancias de recursos. En un sistema voluminoso, las técnicas de prevención de interbloqueos pueden funcionar bien.

Gráfico de espera

Este es un método simple disponible para rastrear si puede surgir una situación de bloqueo. Por cada transacción que ingresa al sistema, se crea un nodo. Cuando una transacción T i solicita un bloqueo en un artículo, digamos X, que está retenido por alguna otra transacción T j , se crea un borde dirigido de T i a T j . Si T j libera el elemento X, el borde entre ellos se elimina y T i bloquea el elemento de datos.

El sistema mantiene este gráfico de espera para cada transacción en espera de algunos elementos de datos retenidos por otros. El sistema sigue comprobando si hay algún ciclo en el gráfico.

Aquí, podemos usar cualquiera de los dos enfoques siguientes:

  • Primero, no permita ninguna solicitud de un artículo, que ya está bloqueado por otra transacción. Esto no siempre es factible y puede causar inanición, donde una transacción espera indefinidamente un elemento de datos y nunca puede adquirirlo.

  • La segunda opción es revertir una de las transacciones. No siempre es factible revertir la transacción más reciente, ya que puede ser importante que la anterior. Con la ayuda de algún algoritmo relativo, se elige una transacción que debe abortarse. Esta transacción se conoce comovictim y el proceso se conoce como victim selection.