Dos transacciones T 1 y T 2 se dan como:
T1: r1(X)w1(X)r1(Y)w1(Y) T2 : r2(Y)w2(Y)r2(Z)w2(Z)
donde r i (V) denota una operación de lectura por transacción T i en una variable V y w i (V) denota una operación de escritura por transacción T i en una variable V. El número total de horarios serializables en conflicto que pueden ser formados por T1 y T2 es ______
Nota: Esta pregunta apareció como tipo de respuesta numérica.
(A) 54
(B) 55
(C) 56
(D) 57
Respuesta: (A)
Explicación: Para que los horarios sean serializables en conflicto, deben estar libres de conflictos RW, WW, WR.
En el cronograma serializable de conflicto, debemos ver que las operaciones en ambas transacciones que ocurren en el mismo elemento de datos no deben entrar en conflicto. El elemento de datos y se comparte entre las dos transacciones, por lo que las operaciones de lectura y escritura en T1 en el elemento de datos y pueden producir un conflicto RW, WR, WW con las operaciones de lectura y escritura de la transacción T2 en el elemento de datos y.
Otra restricción es que se debe mantener el orden de las operaciones de cada transacción. No podemos cambiar el orden de la operación en la transacción. Supongamos que si read(x) es anterior a write(x) en T1, entonces debería estar en el mismo orden en el calendario serializable de conflicto resultante.
En T1 tenemos dos operaciones en conflicto r1(y) y w1(y)
En T2 tenemos dos operaciones en conflicto r2(y) y w2(y)
Tanto la lectura como la escritura de T1 en y deben realizarse juntas antes de la lectura y escritura par de T2 o después del par de lectura y escritura en T2 porque intercalarlos resultará en inconsistencias porque ambas transacciones están realizando operaciones en el mismo objeto.
Solo hay una forma de tener un calendario serializable (en conflicto) como T1->T2, porque la última operación de T1 y la primera operación de T2 entran en conflicto entre sí.
Ahora vea cuántos horarios son serializables en conflicto a T2->T1.
T1- r1(x) w1(x) r1(y) w1(y)
Ahora vea T2 desde la derecha, si vemos T2 desde la derecha, vea la primera operación en conflicto
w2(z) y r2(z) no tienen ningún conflicto con ninguna operación, pero w(y) tiene conflicto
Elija W2(y) y ver, en cuántos lugares puede estar allí.
Case1: w2(y) r1(x) w1(x) r1(y) w1(y) Case2: r1(x) w2(y) w1(x) r1(y) w1(y) Case3: r1(x) w1(x) w2(y) r1(y) w1(y)
Elija cada caso y vea cuántas posiciones puede tomar otra operación de T2.
Caso 1: w2(y) r1(x) w1(x) r1(y) w1(y)
¿Cuántas posiciones pueden tomar w2(z) y r2(z)?
(Tenga en cuenta que estos w2 (z) y r2 (z) no pueden venir antes de w2 (y) )
que es 5C1 + 5C2 = 15 (o ambos pueden ocupar el mismo espacio o dos espacios diferentes)
Ahora vea, para cada una de estas 15 posiciones, ¿Cuántos puede tomar r2(y)?
Obviamente, r2(y) no puede venir antes de w2(y), por lo tanto, una posición.
15×1 = 15 horarios posibles totales del caso 1.
Caso 2: r1(x) w1(y) w1(x) r1(y) w1(y)
¿Cuántas posiciones pueden tomar w2(z) y r2(z)?
eso es 4C1 + 4C2 = 10 (o ambos pueden tomar el mismo espacio o dos espacios diferentes)
Ahora vea, para cada una de estas 10 posiciones, ¿cuántas puede tomar r2(y)?
Solo 2 posiciones, porque tiene que venir antes de w1(y) .
10×2 = 20 horarios posibles totales del caso 2.
Caso 3: r1(x) w1(x) w2(y) r1(y) w1(y)
¿Cuántas posiciones pueden tomar w2(z) y r2(x)?
eso es 3C1 + 3C2 = 6
Ahora mira, para cada una de estas 6 posiciones, ¿cuántas puede tomar r2(y)?
Solo 3 posiciones, porque tiene que venir antes de w2(y) .
6×3 = 18 programaciones posibles totales del caso 3.
programaciones totales que son serializables en conflicto como T2->T1 = 15+20+18 = 53.
programaciones totales que son serializables en conflicto como T1->T2 = 1.
programaciones totales que son conflicto serializable como T2->T1 o T1->T2 = 53+1 = 54.
Esta solución es aportada por Parul Sharma.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA