Teoría de Seriabilidad
En los ejemplos anteriores, los errores fueron causados por la ejecución intercalada de operaciones de transacciones diferentes. Los ejemplos no muestran todas las posibles formas en las que la ejecución de dos transacciones pueden interferir, pero sí ilustran dos de los problemas que surgen con frecuencia debido a la intercalación. Para evitar estos problemas, se deben controlar las intercalaciones entre transacciones.
Una forma de evitar los problemas de interferencia es no permitir que las transacciones se intercalen. Una ejecución en la cual ninguna de dos transacciones se intercala se conoce como serial. Para ser más precisos, una ejecución se dice que es serial si, para todo par de transacciones, todas las operaciones de una transacción se ejecutan antes de cualquier operación de la otra transacción. Desde el punto de vista del usuario, en una ejecución serial se ve como si las transacciones fueran operaciones que el DBS procesa atómicamente. Las transacciones seriales son correctas dado que cada transacción es correcta individualmente, y las transacciones que se ejecutan serialmente no pueden interferir con otra.
Si el DBS procesara transacciones serialmente, significaría que no podría ejecutar transacciones concurrentemente, si entendemos concurrencia como ejecuciones intercaladas. Sin dicha concurrencia, el sistema usaría sus recursos en un nivel relativamente pobre y podría ser sumamente ineficiente.
Una solución puede ser ampliar el rango de ejecuciones permisibles para incluir aquellas que tienen los mismos efectos que las seriales. Dichas ejecuciones se conocen como serializables. Entonces, una ejecución es serializable si produce el mismo resultado y tiene el mismo efecto sobre la base de datos que alguna ejecución serial de las mismas transacciones. Puesto que las transacciones seriales son correctas, y dado que cada ejecución serializable tiene el mismo efecto que una ejecución serial, las ejecuciones serializables también son correctas.
Las ejecuciones que ilustran la actualización perdida y el análisis inconsistente no son serializables. Por ejemplo, ejecutando las dos transacciones de Depositar serialmente, en cualquier orden, da un resultado diferente al de la ejecución intercalada que pierde una actualización, por lo tanto, la ejecución intercalada no es serializable. Similarmente, la ejecución intercalada de Transferir e ImprimirSuma tiene un efecto diferente a los de cada ejecución serial de las dos transacciones, y por ello no es serializable.
Aunque éstas dos ejecuciones intercaladas no son serializables, muchas otras sí lo son. Por ejemplo, consideremos la siguiente ejecución intercalada de Transferir e ImprimirSuma. Esta ejecución tiene el mismo efecto que la ejecución serial de Transferir seguida de ImprimirSuma por lo tanto es serializable.
Una forma de evitar los problemas de interferencia es no permitir que las transacciones se intercalen. Una ejecución en la cual ninguna de dos transacciones se intercala se conoce como serial. Para ser más precisos, una ejecución se dice que es serial si, para todo par de transacciones, todas las operaciones de una transacción se ejecutan antes de cualquier operación de la otra transacción. Desde el punto de vista del usuario, en una ejecución serial se ve como si las transacciones fueran operaciones que el DBS procesa atómicamente. Las transacciones seriales son correctas dado que cada transacción es correcta individualmente, y las transacciones que se ejecutan serialmente no pueden interferir con otra.
Si el DBS procesara transacciones serialmente, significaría que no podría ejecutar transacciones concurrentemente, si entendemos concurrencia como ejecuciones intercaladas. Sin dicha concurrencia, el sistema usaría sus recursos en un nivel relativamente pobre y podría ser sumamente ineficiente.
Una solución puede ser ampliar el rango de ejecuciones permisibles para incluir aquellas que tienen los mismos efectos que las seriales. Dichas ejecuciones se conocen como serializables. Entonces, una ejecución es serializable si produce el mismo resultado y tiene el mismo efecto sobre la base de datos que alguna ejecución serial de las mismas transacciones. Puesto que las transacciones seriales son correctas, y dado que cada ejecución serializable tiene el mismo efecto que una ejecución serial, las ejecuciones serializables también son correctas.
Las ejecuciones que ilustran la actualización perdida y el análisis inconsistente no son serializables. Por ejemplo, ejecutando las dos transacciones de Depositar serialmente, en cualquier orden, da un resultado diferente al de la ejecución intercalada que pierde una actualización, por lo tanto, la ejecución intercalada no es serializable. Similarmente, la ejecución intercalada de Transferir e ImprimirSuma tiene un efecto diferente a los de cada ejecución serial de las dos transacciones, y por ello no es serializable.
Aunque éstas dos ejecuciones intercaladas no son serializables, muchas otras sí lo son. Por ejemplo, consideremos la siguiente ejecución intercalada de Transferir e ImprimirSuma. Esta ejecución tiene el mismo efecto que la ejecución serial de Transferir seguida de ImprimirSuma por lo tanto es serializable.
Leer4 (Cuentas[8]) devuelve el valor de US$200
Escribir4 (Cuentas[8], US$100)
Leer3 (Cuentas[8]) devuelve el valor de US$100
Leer4 (Cuentas[9]) devuelve el valor de US$200$
Escribir4 (Cuentas[9], US$300)
Commit4
Leer3 (Cuentas[9]) devuelve el valor de US$300
Commit3
Escribir4 (Cuentas[8], US$100)
Leer3 (Cuentas[8]) devuelve el valor de US$100
Leer4 (Cuentas[9]) devuelve el valor de US$200$
Escribir4 (Cuentas[9], US$300)
Commit4
Leer3 (Cuentas[9]) devuelve el valor de US$300
Commit3
La teoría de Seriabilidad es una herramienta matemática que permite probar si un sincronizador trabaja o no correctamente. Desde el punto de vista de la teoría de Seriabilidad, una transacción es una representación de una ejecución de operaciones de lectura y escritura y que indica el orden en el que se deben ejecutar estas operaciones. Además, la transacción contiene un Commit o un Abort como la última operación para indicar si la ejecución que representa terminó con éxito o no. Por ejemplo, la ejecución del siguiente programa
Procedure P
begin
Start;
temp := Leer(x);
temp := temp + 1;
Escribir(x, temp);
Commit;
temp := Leer(x);
temp := temp + 1;
Escribir(x, temp);
Commit;
end
puede ser presentado como r1[x] -› w1[x] -› c1. Los subíndices identifican esta transacción particular y la distinguen de cualquier otra transacción que acceda al mismo dato. En general, usaremos r1[x] (o w1[x] para denotar la ejecución de Leer (o Escribir) ejecutado por la transacción T1 sobre el dato x.
Cuando se ejecuta concurrentemente un conjunto de transacciones, sus operaciones deben estar intercaladas. La manera de modelar esto es usando una estructura llamada historia. Una historia indica el orden en el que se deben ejecutar las operaciones de las transacciones en relación a otras. Si una transacción Ti especifica el orden de dos de sus operaciones, estas dos operaciones deben aparecer en ese mismo orden en cualquier historia que incluya a Ti. Además, es necesario que una historia especifique el orden de todas las operaciones conflictivas que aparezcan en ella.
Se dice que dos operaciones están en conflicto si ambas operan sobre el mismo dato y al menos una de ellas es una operación de escritura (Escribir). Por lo tanto, Leer(x) está en conflicto con Escribir(x), mientras que Escribir(x) está en conflicto tanto con Leer(x) como con Escribir(x). Si dos operaciones están en conflicto, es muy importante su orden de ejecución. Consideremos las siguientes transacciones
Cuando se ejecuta concurrentemente un conjunto de transacciones, sus operaciones deben estar intercaladas. La manera de modelar esto es usando una estructura llamada historia. Una historia indica el orden en el que se deben ejecutar las operaciones de las transacciones en relación a otras. Si una transacción Ti especifica el orden de dos de sus operaciones, estas dos operaciones deben aparecer en ese mismo orden en cualquier historia que incluya a Ti. Además, es necesario que una historia especifique el orden de todas las operaciones conflictivas que aparezcan en ella.
Se dice que dos operaciones están en conflicto si ambas operan sobre el mismo dato y al menos una de ellas es una operación de escritura (Escribir). Por lo tanto, Leer(x) está en conflicto con Escribir(x), mientras que Escribir(x) está en conflicto tanto con Leer(x) como con Escribir(x). Si dos operaciones están en conflicto, es muy importante su orden de ejecución. Consideremos las siguientes transacciones
T1 = r1[x] -› w1[x] -› c1
T3 = r3[x] -› w3[y] -› w3[x] -› c3
T4 = r4[y] -› w4[x] -› w4[y] -› w4[z] -› c4
T3 = r3[x] -› w3[y] -› w3[x] -› c3
T4 = r4[y] -› w4[x] -› w4[y] -› w4[z] -› c4
Una historia completa sobre T1, T3, T4 es
H1 = r4[y] r1[x] w1[x] c1 w4[x] r3[x] w4[y] w3[y] w4[z] w3[x] c4 c3
No hay comentarios:
Publicar un comentario