Interbloqueo se produce cuando cada transacción T en un programa de dos o más transacciones en espera de algún elemento bloqueado por alguna otra transacción T ‘ en el conjunto. Por lo tanto, ambos terminan en una situación de punto muerto, esperando que el otro libere el bloqueo del artículo. Los interbloqueos son un problema común y hemos introducido el problema al resolver el control de concurrencia mediante la introducción de bloqueos . Evitar interbloqueos es un problema importante y se sugirieron algunos protocolos para evitarlos, como los protocolos Conservative 2-PL y Graph Based, pero aún existen algunos inconvenientes.
Aquí, discutiremos un nuevo concepto de Transaction Timestamp TS(T i ) . Una marca de tiempo es un identificador único creado por el DBMS para identificar una transacción. Por lo general, se asignan en el orden en que se envían al sistema, por lo que se puede pensar en una marca de tiempo como la hora de inicio de la transacción.
Puede haber diferentes formas de generar marcas de tiempo, como
- Un contador simple que se incrementa cada vez que se asigna su valor a una transacción. Pueden estar numerados 1, 2, 3… . Aunque tendremos que resetear el contador de vez en cuando para evitar desbordamientos.
- Usando la fecha/hora actual del reloj del sistema. Simplemente asegurándonos de que no se dé el mismo valor a dos transacciones en el mismo tic del reloj, siempre obtendremos una marca de tiempo única. Este método es ampliamente utilizado.
Esquemas de prevención de bloqueos mutuos basados en sellos de tiempo…
Como se discutió, las marcas de tiempo son identificadores únicos asignados a cada transacción. Se basan en el orden en que se inician las Transacciones. Digamos que si T 1 comienza antes de T 2 entonces TS(T 1 ) será menor que (<) TS(T 2 ) .
Hay dos esquemas para evitar el interbloqueo llamados herida-espera y espera-muerte . Digamos que hay dos transacciones Ti y Tj , ahora digamos que Ti intenta bloquear un elemento X pero el elemento X ya está bloqueado por algún Tj , ahora en una situación tan conflictiva, los dos esquemas evitan el punto muerto. Usaremos este contexto en breve.
- Wait_Die: se permite que una transacción más antigua espere una transacción más joven, mientras que una transacción más joven que solicita un elemento en poder de una transacción anterior se aborta y se reinicia.
Del contexto anterior, si TS(T i ) < TS(T j ) , entonces (T i mayor que T j ) T i puede esperar; de lo contrario , aborte T i (T i más joven que T j ) y reinícielo más tarde con la misma marca de tiempo. - Wound_Wait: Es justo lo contrario de la técnica Wait_Die. Aquí, una transacción más joven puede esperar a una más antigua, mientras que si una transacción más antigua solicita un artículo en poder de la transacción más joven, nos adelantamos a la transacción más joven anulándola.
Del contexto anterior, si TS(T i ) < TS(T j ) , entonces (T i mayor que T j ) T j se aborta (es decir, Ti hiere a T j ) y lo reinicia más tarde con la misma marca de tiempo; de lo contrario (T i más joven que T j ) se permite que T i espere.
Por lo tanto, ambos esquemas terminan abortando la más joven de las dos transacciones que pueden estar involucradas en un punto muerto. Se hace sobre la base de la suposición de que abortar la transacción más joven desperdiciará menos procesamiento, lo cual es lógico. En tal caso no puede haber un ciclo ya que estamos esperando linealmente en ambos casos.
Para GATE, la teoría de estos dos métodos es suficiente, para obtener más información al respecto, puede consultar aquí .
Otro grupo de protocolos que evita el interbloqueo pero no requiere marcas de tiempo . Se discuten a continuación:
- Algoritmo sin espera: sigue un enfoque simple, si una transacción no puede obtener un bloqueo, se aborta inmediatamente y luego se reinicia después de un cierto retraso de tiempo sin verificar si se producirá un punto muerto o no. Aquí, ninguna transacción espera nunca, por lo que no hay posibilidad de punto muerto.
Este método no es algo práctico. Puede hacer que la transacción se cancele y se reinicie innecesariamente. - Espera cautelosa: si T i intenta bloquear un elemento X pero no puede hacerlo porque X está bloqueado por algún T j . En tal conflicto, si Tj no está esperando algún otro elemento bloqueado, entonces se permite que Ti espere, de lo contrario abortar Ti .
Otro enfoque, para lidiar con interbloqueos es la detección de interbloqueos, podemos usar Wait-for-Graph . Esto utiliza un enfoque similar cuando solíamos verificar los ciclos mientras verificamos la serialización.
Inanición: un problema que puede ocurrir cuando usamos el bloqueo es la inanición, que ocurre cuando una transacción no puede continuar durante un período de tiempo indefinido mientras que otras transacciones en el sistema continúan normalmente. Esto puede ocurrir si el esquema de espera para los artículos bloqueados es injusto, dando prioridad a algunas transacciones sobre otras. Es posible que tengamos algunas soluciones para Inanición. Uno está usando una cola por orden de llegada ; las transacciones están habilitadas para bloquear un artículo en el orden en que originalmente solicitaron el bloqueo. Este es un mecanismo ampliamente utilizado para reducir la inanición. Nuestro Gerente de Control de Concurrencia es el encargado de programar las transacciones, por lo que emplea diferentes métodos para superarlas. Puede consultar esto para obtener una explicación detallada.
Pruebe esta pregunta: PUERTA | GATE-CS-2017 (Conjunto 1) | Pregunta 46
A continuación, analizaremos el famoso Protocolo de ordenación de marcas de tiempo y la regla de escritura de Thomas. Hasta entonces ¡Feliz aprendizaje!
Referencia: Conceptos de sistemas de bases de datos, Quinta edición [Silberschatz, Korth, Sudarshan], Capítulo 16.