Gráfico de precedencia para probar la serialización de conflictos en DBMS – Part 1

Requisito previo: serialización de conflictos

El gráfico de precedencia o el gráfico de serialización se usan comúnmente para probar la serialización de conflictos de un cronograma.
Es un Grafo dirigido (V, E) que consta de un conjunto de Nodes V = {T ₁ , T ₂ , T ₃ ……….T _n } y un conjunto de aristas dirigidas E = {e ₁ , e ₂ , e ₃ ………………e _m }.
El gráfico contiene un Node para cada transacción _Ti . Una arista e _i tiene la forma T _j –> T _k donde T _j es el Node inicial de e _i y T _kes el Node final de e _i . Se construye un borde e _i entre los Nodes T _j a T _k si una de las operaciones en T _j aparece en el programa antes de alguna operación conflictiva en T _k .

El algoritmo se puede escribir como:

1. Cree un Node T en el gráfico para cada transacción participante en el cronograma.
2. Para la operación en conflicto leer_elemento(X) y escribir_elemento(X): si una transacción T _j ejecuta un elemento de lectura (X) después de que T _i ejecuta un elemento de escritura (X), dibuje un borde de T _i a T _j en el gráfico.
3. Para la operación conflictiva write_item(X) y read_item(X) – Si una Transacción T _j ejecuta un write_item (X) después de que T _i ejecuta un read_item (X), dibuje un borde de Ti _a T _j en el gráfico.
4. Para la operación conflictiva write_item(X) y write_item(X) – Si una Transacción T _j ejecuta un write_item (X) después de que T _i ejecuta un write_item (X), dibuje un borde de Ti _a T _j en el gráfico.
5. El Schedule S es serializable si no hay un ciclo en el gráfico de precedencia .

Si no hay un ciclo en el gráfico de precedencia, significa que podemos construir un programa en serie S’ que es equivalente en conflicto al programa S.
El programa en serie S’ se puede encontrar mediante clasificación topológica del gráfico de precedencia acíclica. Dichos horarios pueden ser más de 1.

Por ejemplo,
considere el programa S :

 S : r1(x) r1(y) w2(x) w1(x) r2(y) 

Crear gráfico de precedencia:

1. Cree dos Nodes correspondientes a la Transacción T ₁ y T ₂ .
   
2. Para el par en conflicto r1(x) w2(x), donde r1(x) sucede antes que w2(x), dibuje un borde de T ₁ a T ₂ .
   
3. Para el par en conflicto w2(x) w1(x), donde w2(x) sucede antes que w1(x), dibuje un borde de T ₂ a T ₁ .

   

Dado que el gráfico es cíclico, podemos concluir que no es un conflicto serializable a ningún programa de programación serial.
Tratemos de inferir un horario serial a partir de este gráfico utilizando el ordenamiento topológico.
La arista T ₁ –>T ₂ indica que T ₁ debería estar antes de T ₂ en el ordenamiento lineal.
La arista T ₂ –> T ₁ dice que T ₂ debe venir antes que T ₁ en el ordenamiento lineal.
Entonces, no podemos predecir ningún orden en particular (cuando el gráfico es cíclico). Por lo tanto, no se puede obtener un programa de serie de este gráfico.

Considere el otro horario S1:

 S1: r1(x) r3(y) w1(x) w2(y) r3(x) w2(x)

La gráfica de este horario es:

Dado que el gráfico es acíclico, el programa es serializable en conflicto. Realizar la ordenación topológica en este gráfico nos daría un posible programa en serie que es equivalente en conflicto al programa S1.
En Clasificación topológica, primero seleccionamos el Node con grado de entrada 0, que es T1. Esto sería seguido por T3 y T2.
Entonces, S1 es un conflicto serializable ya que es un conflicto equivalente al programa serial T1 T3 T2.

Fuente: Libro de sistemas operativos, Silberschatz, Galvin y Gagne

Este artículo es una contribución de Saloni Baweja . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.