DBMS distribuido - Manejo de interbloqueo
Este capítulo describe los mecanismos de manejo de interbloqueos en los sistemas de bases de datos. Estudiaremos los mecanismos de manejo de interbloqueos en sistemas de bases de datos centralizados y distribuidos.
¿Qué son los interbloqueos?
El punto muerto es un estado de un sistema de base de datos que tiene dos o más transacciones, cuando cada transacción está esperando un elemento de datos que está bloqueado por otra transacción. Un interbloqueo se puede indicar mediante un ciclo en el gráfico de espera. Este es un gráfico dirigido en el que los vértices denotan transacciones y los bordes denotan esperas por elementos de datos.
Por ejemplo, en el siguiente gráfico de espera, la transacción T1 está esperando el elemento de datos X que está bloqueado por T3. T3 está esperando Y que está bloqueado por T2 y T2 está esperando Z que está bloqueado por T1. Por lo tanto, se forma un ciclo de espera y ninguna de las transacciones puede continuar ejecutándose.
Manejo de interbloqueo en sistemas centralizados
Hay tres enfoques clásicos para el manejo de interbloqueos, a saber:
- Prevención de interbloqueo.
- Evitación de puntos muertos.
- Detección y eliminación de interbloqueo.
Los tres enfoques se pueden incorporar tanto en un sistema de base de datos centralizado como en uno distribuido.
Prevención de interbloqueo
El enfoque de prevención de interbloqueos no permite que ninguna transacción adquiera bloqueos que darán lugar a interbloqueos. La convención es que cuando más de una transacción solicitan bloquear el mismo elemento de datos, solo se concede el bloqueo a una de ellas.
Uno de los métodos de prevención de interbloqueo más populares es la adquisición previa de todos los bloqueos. En este método, una transacción adquiere todos los bloqueos antes de comenzar a ejecutarse y retiene los bloqueos durante toda la transacción. Si otra transacción necesita alguno de los bloqueos ya adquiridos, debe esperar hasta que estén disponibles todos los bloqueos que necesita. Con este enfoque, se evita que el sistema se bloquee, ya que ninguna de las transacciones en espera retiene ningún bloqueo.
Evitación de puntos muertos
El enfoque de evitación de puntos muertos maneja los puntos muertos antes de que ocurran. Analiza las transacciones y los bloqueos para determinar si la espera conduce o no a un punto muerto.
El método se puede enunciar brevemente como sigue. Las transacciones comienzan a ejecutarse y solicitan elementos de datos que necesitan bloquear. El administrador de la cerradura comprueba si la cerradura está disponible. Si está disponible, el administrador de bloqueo asigna el elemento de datos y la transacción adquiere el bloqueo. Sin embargo, si el elemento está bloqueado por alguna otra transacción en modo incompatible, el administrador de bloqueo ejecuta un algoritmo para probar si mantener la transacción en estado de espera provocará un interbloqueo o no. En consecuencia, el algoritmo decide si la transacción puede esperar o si una de las transacciones debe abortarse.
Hay dos algoritmos para este propósito, a saber wait-die y wound-wait. Supongamos que hay dos transacciones, T1 y T2, donde T1 intenta bloquear un elemento de datos que ya está bloqueado por T2. Los algoritmos son los siguientes:
Wait-Die- Si T1 es mayor que T2, T1 puede esperar. De lo contrario, si T1 es menor que T2, T1 se cancela y luego se reinicia.
Wound-Wait- Si T1 es mayor que T2, T2 se cancela y luego se reinicia. De lo contrario, si T1 es menor que T2, T1 puede esperar.
Detección y eliminación de interbloqueo
El enfoque de detección y eliminación de interbloqueo ejecuta un algoritmo de detección de interbloqueo periódicamente y elimina el interbloqueo en caso de que haya uno. No comprueba si hay interbloqueo cuando una transacción solicita un bloqueo. Cuando una transacción solicita un bloqueo, el administrador de bloqueo comprueba si está disponible. Si está disponible, la transacción puede bloquear el elemento de datos; de lo contrario, la transacción puede esperar.
Dado que no hay precauciones al otorgar solicitudes de bloqueo, algunas de las transacciones pueden estar bloqueadas. Para detectar interbloqueos, el administrador de cerraduras verifica periódicamente si el gráfico de espera tiene ciclos. Si el sistema está bloqueado, el administrador de bloqueos elige una transacción víctima de cada ciclo. La víctima es abortada y revertida; y luego reiniciado más tarde. Algunos de los métodos utilizados para la selección de víctimas son:
- Elija la transacción más joven.
- Elija la transacción con menos elementos de datos.
- Elija la transacción que ha realizado el menor número de actualizaciones.
- Elija la transacción que tenga menos gastos generales de reinicio.
- Elija la transacción que sea común a dos o más ciclos.
Este enfoque es principalmente adecuado para sistemas que tienen transacciones bajas y donde se necesita una respuesta rápida a las solicitudes de bloqueo.
Manejo de interbloqueo en sistemas distribuidos
El procesamiento de transacciones en un sistema de base de datos distribuido también se distribuye, es decir, la misma transacción puede procesarse en más de un sitio. Los dos principales problemas de manejo de interbloqueos en un sistema de base de datos distribuida que no están presentes en un sistema centralizado sontransaction location y transaction control. Una vez que se abordan estas inquietudes, los interbloqueos se manejan a través de cualquiera de la prevención de interbloqueo, la prevención de interbloqueo o la detección y eliminación de interbloqueo.
Ubicación de la transacción
Las transacciones en un sistema de base de datos distribuida se procesan en varios sitios y utilizan elementos de datos en varios sitios. La cantidad de procesamiento de datos no se distribuye uniformemente entre estos sitios. El período de tiempo de procesamiento también varía. Por lo tanto, la misma transacción puede estar activa en algunos sitios e inactiva en otros. Cuando dos transacciones en conflicto se encuentran en un sitio, puede suceder que una de ellas esté en estado inactivo. Esta condición no surge en un sistema centralizado. Esta preocupación se denomina problema de ubicación de la transacción.
Esta inquietud puede abordarse mediante el modelo Daisy Chain. En este modelo, una transacción lleva ciertos detalles cuando se mueve de un sitio a otro. Algunos de los detalles son la lista de tablas requeridas, la lista de sitios requeridos, la lista de tablas y sitios visitados, la lista de tablas y sitios que aún no se han visitado y la lista de bloqueos adquiridos con tipos. Después de que una transacción finaliza por confirmación o aborto, la información debe enviarse a todos los sitios involucrados.
Control de transacciones
El control de transacciones se ocupa de designar y controlar los sitios necesarios para procesar una transacción en un sistema de base de datos distribuido. Hay muchas opciones con respecto a la elección de dónde procesar la transacción y cómo designar el centro de control, como:
- Se puede seleccionar un servidor como centro de control.
- El centro de control puede viajar de un servidor a otro.
- La responsabilidad de controlar puede ser compartida por varios servidores.
Prevención de interbloqueo distribuido
Al igual que en la prevención de interbloqueo centralizada, en el enfoque de prevención de interbloqueo distribuido, una transacción debe adquirir todos los bloqueos antes de comenzar a ejecutarse. Esto evita los interbloqueos.
El sitio donde ingresa la transacción se designa como sitio de control. El sitio de control envía mensajes a los sitios donde se encuentran los elementos de datos para bloquearlos. Luego espera la confirmación. Cuando todos los sitios han confirmado que han bloqueado los elementos de datos, comienza la transacción. Si falla algún sitio o enlace de comunicación, la transacción debe esperar hasta que se reparen.
Aunque la implementación es simple, este enfoque tiene algunos inconvenientes:
La adquisición previa de cerraduras requiere mucho tiempo para retrasos en la comunicación. Esto aumenta el tiempo requerido para la transacción.
En caso de falla del sitio o del enlace, una transacción debe esperar mucho tiempo para que los sitios se recuperen. Mientras tanto, en los sitios en ejecución, los elementos están bloqueados. Esto puede evitar que se ejecuten otras transacciones.
Si el sitio de control falla, no puede comunicarse con los otros sitios. Estos sitios continúan manteniendo los elementos de datos bloqueados en su estado bloqueado, lo que resulta en un bloqueo.
Evitación de interbloqueo distribuido
Como en el sistema centralizado, la prevención de interbloqueo distribuido maneja el interbloqueo antes de que ocurra. Además, en los sistemas distribuidos, se deben abordar los problemas de ubicación y control de transacciones. Debido a la naturaleza distribuida de la transacción, pueden ocurrir los siguientes conflictos:
- Conflicto entre dos transacciones en el mismo sitio.
- Conflicto entre dos transacciones en sitios diferentes.
En caso de conflicto, una de las transacciones puede abortarse o dejarse esperar según los algoritmos distribuidos esperar-morir o distribuir herida-esperar.
Supongamos que hay dos transacciones, T1 y T2. T1 llega al sitio P e intenta bloquear un elemento de datos que ya está bloqueado por T2 en ese sitio. Por lo tanto, hay un conflicto en el Sitio P. Los algoritmos son los siguientes:
Distributed Wound-Die
Si T1 es mayor que T2, T1 puede esperar. T1 puede reanudar la ejecución después de que el sitio P reciba un mensaje de que T2 se ha comprometido o abortado con éxito en todos los sitios.
Si T1 es menor que T2, T1 se aborta. El control de concurrencia en el sitio P envía un mensaje a todos los sitios donde T1 ha visitado para abortar T1. El sitio de control notifica al usuario cuando T1 ha sido abortado con éxito en todos los sitios.
Distributed Wait-Wait
Si T1 es mayor que T2, T2 debe abortarse. Si T2 está activo en el Sitio P, el Sitio P aborta y revierte T2 y luego transmite este mensaje a otros sitios relevantes. Si T2 ha abandonado el Sitio P pero está activo en el Sitio Q, el Sitio P transmite que T2 ha sido abortado; El sitio L luego aborta y revierte T2 y envía este mensaje a todos los sitios.
Si T1 es menor que T1, T1 puede esperar. T1 puede reanudar la ejecución después de que el Sitio P reciba un mensaje de que T2 ha completado el procesamiento.
Detección de interbloqueo distribuido
Al igual que el enfoque de detección de interbloqueo centralizado, se permite que se produzcan interbloqueos y se eliminan si se detectan. El sistema no realiza ninguna verificación cuando una transacción coloca una solicitud de bloqueo. Para la implementación, se crean gráficos de espera globales. La existencia de un ciclo en el gráfico de espera global indica puntos muertos. Sin embargo, es difícil detectar puntos muertos ya que la transacción espera recursos en la red.
Alternativamente, los algoritmos de detección de interbloqueo pueden utilizar temporizadores. Cada transacción está asociada con un temporizador que se establece en un período de tiempo en el que se espera que finalice una transacción. Si una transacción no finaliza dentro de este período de tiempo, el temporizador se apaga, lo que indica un posible punto muerto.
Otra herramienta utilizada para el manejo de interbloqueos es un detector de interbloqueos. En un sistema centralizado, hay un detector de interbloqueo. En un sistema distribuido, puede haber más de un detector de interbloqueo. Un detector de puntos muertos puede encontrar puntos muertos para los sitios bajo su control. Hay tres alternativas para la detección de interbloqueo en un sistema distribuido, a saber.
Centralized Deadlock Detector - Un sitio está designado como detector central de interbloqueo.
Hierarchical Deadlock Detector - Varios detectores de interbloqueo están organizados en jerarquía.
Distributed Deadlock Detector - Todos los sitios participan en la detección de interbloqueos y su eliminación.