Los protocolos basados en gráficos son otra forma de implementar protocolos basados en bloqueos .
Como sabemos, los problemas principales con el Protocolo basado en bloqueo han sido evitar interbloqueos y garantizar un cronograma estricto. Hemos visto que los Horarios estrictos son posibles con el seguimiento de 2-PL estricto o riguroso . Incluso hemos visto que se pueden evitar interbloqueos si seguimos Conservative 2-PL, pero el problema con este protocolo es que no se puede usar en la práctica. Los protocolos basados en gráficos se utilizan como alternativa a 2-PL. Los protocolos basados en árboles son una implementación sencilla del protocolo basado en gráficos .
Un requisito previo de este protocolo es que conozcamos el orden para acceder a un elemento de la base de datos. Para ello implementamos un Ordenamiento Parcial sobre un conjunto de Elementos de la Base de Datos (D) {d 1 , d 2 , d 3 , ….., d n } . El protocolo que sigue a la implementación de la ordenación parcial se establece como-
- Si d i –> d j entonces cualquier transacción que acceda tanto a d i como a d j debe acceder a d i antes de acceder a d j .
- Implica que el conjunto D ahora puede verse como un gráfico acíclico dirigido (DAG), llamado gráfico de base de datos .
Protocolo basado en árbol –
- El orden parcial en los elementos de la base de datos determina una estructura similar a un árbol.
- Solo se permiten bloqueos exclusivos.
- El primer bloqueo por Ti puede estar en cualquier elemento de datos. Posteriormente, un dato Q puede ser bloqueado por Ti solo si el padre de Q está actualmente bloqueado por Ti .
- Los elementos de datos se pueden desbloquear en cualquier momento.
Seguir el protocolo basado en árbol garantiza la capacidad de serialización de conflictos y el cronograma libre de interbloqueos. No necesitamos esperar a desbloquear un elemento de datos como lo hicimos en el protocolo 2-PL, aumentando así la concurrencia.
Ahora, veamos un ejemplo, el siguiente es un gráfico de base de datos que se utilizará como referencia para bloquear los elementos posteriormente.
Imagen: gráfico de base
de datos Veamos un ejemplo basado en el gráfico de base de datos anterior. Tenemos tres Transacciones en este cronograma y este es un ejemplo básico, es decir, solo veremos cómo funciona el Bloqueo y Desbloqueo, mantengamos esto simple y no lo compliquemos agregando operaciones en los datos.
| T 1 | T 2 | T 3 | |
|---|---|---|---|
| 1 | Bloqueo-X(A) | ||
| 2 | Bloqueo-X(B) | ||
| 3 | Bloquear-X(D) | ||
| 4 | Bloqueo-X(H) | ||
| 5 | Desbloquear-X(D) | ||
| 6 | Bloquear-X(E) | ||
| 7 | Bloquear-X(D) | ||
| 8 | Desbloquear-X(B) | ||
| 9 | Desbloquear-X(E) | ||
| 10 | Bloqueo-X(B) | ||
| 11 | Bloquear-X(E) | ||
| 12 | Desbloquear-X(H) | ||
| 13 | Bloqueo-X(B) | ||
| 14 | Bloqueo-X (G) | ||
| 15 | Desbloquear-X(D) | ||
| dieciséis | Desbloquear-X(E) | ||
| 17 | Desbloquear-X(B) | ||
| 18 | Desbloquear-X(G) |
En el ejemplo anterior, primero vea que el cronograma es serializable en conflicto. La serialización de los bloqueos se puede escribir como T 2 –> T 1 –> T 3 .
Los elementos de datos bloqueados y desbloqueados siguen la misma regla que se indicó anteriormente y siguen el gráfico de la base de datos.
Por lo tanto, revisemos una vez más cuáles son los puntos clave de los protocolos basados en gráficos.
Ventaja –
- Garantiza el calendario serializable de conflictos.
- Garantiza un cronograma libre de interbloqueos
- El desbloqueo se puede hacer en cualquier momento
Con algunas ventajas también vienen algunas desventajas.
Desventaja –
- A veces pueden ocurrir sobrecargas de bloqueo innecesarias, por ejemplo, si queremos tanto D como E, al menos tenemos que bloquear B para seguir el protocolo.
- Cascading Rollbacks sigue siendo un problema. No seguimos una regla de cuándo puede ocurrir la operación de desbloqueo, por lo que este problema persiste para este protocolo. En general, este protocolo se conoce y utiliza principalmente por su forma única de implementar Deadlock Freedom. Referencias: Conceptos de sistemas de bases de datos, Quinta edición [Silberschatz, Korth, Sudarshan], Capítulo 16.