PUERTA | GATE-CS-2014-(Conjunto-3) | Pregunta 65 – Part 7

Considere las transacciones T1, T2 y T3 y los programas S1 y S2 que se dan a continuación.

T1: r1(X); r1(Z); w1(X); w1(Z)
T2: r2(Y); r2(Z); w2(Z)
T3: r3(Y); r3(X); w3(Y)
S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z);
    w3(Y); w2(Z); r1(Z); w1(X); w1(Z)
S2: r1(X); r3(Y); r2(Y); r3(X); r1(Z);
    r2(Z); w3(Y); w1(X); w2(Z); w1(Z) 

¿Cuál de las siguientes afirmaciones sobre los horarios es VERDADERA?
(A) Solo S1 es serializable en conflicto.
(B) Solo S2 es serializable en conflicto.
(C) Tanto S1 como S2 son serializables en conflicto.
(D) Ni S1 ni S2 son serializables por conflicto.

Respuesta: (A)
Explicación: Para la serialización de conflictos de un programa (que da el mismo efecto que un programa en serie), debemos verificar las operaciones de conflicto, que son Lectura-Escritura, Escritura-Lectura y Escritura-Escritura entre cada par de transacciones, y en base a esos conflictos hacemos un grafo de precedencia, si el grafo contiene un ciclo, no es un calendario serializable de conflicto.

Para hacer un gráfico de precedencia: si Leer (X) en Ti seguido de Escribir (X) en Tj (por lo tanto, un conflicto), entonces dibujamos un borde de Ti a Tj (Ti -> Tj)

Si hacemos un gráfico de precedencia para S1 y S2, obtendríamos aristas dirigidas para S1 como T2->T1, T2->T3, T3->T1, y para S2 como T2->T1, T2->T3, T3- >T1, T1->T2. En S1 no hay ciclo, pero S2 tiene un ciclo. Por lo tanto, solo S1 es un conflicto serializable.

Nota: el orden de serie para S1 es T2 -> T3 -> T1.

Cuestionario de esta pregunta