3 El Problema de Control de Concurrencia
Cuando dos o más transacciones se ejecutan concurrentemente, sus
operaciones se ejecutan en un modelo intercalado. Esto significa
que las operaciones de un programa se ejecutan entre dos
operaciones de otro programa. Esta intercalación puede causar
que los programas no funcionen correctamente, o
interfieran, y de esta manera, dejaría inconsistente a
la base de datos. Esta interferencia se debe completamente a la
intercalación de las operaciones, puesto que puede ocurrir a
pesar de que cada programa funciona correctamente cuando se
ejecuta de forma individual y no se presenta falla alguna en el
sistema. El objetivo del control de concurrencia es evitar la
interferencia y, por ende, los errores.
Veamos algunos ejemplos para entender cómo es que los programas
pueden interferir con otros. Volviendo al ejemplo del banco,
supongamos que tenemos un programa llamado Depositar, el cual
deposita dinero en una cuenta.
Procedure Depositar(Cuenta, Monto)
begin
Start;
temp := Leer(Cuentas[Cuenta]);
temp := temp + Monto;
Escribir(Cuentas[Cuenta],temp);
Commit;
end
Supongamos que la cuenta 7 tiene un saldo de US$1000 y que el
cliente 1 deposita US$100 en la cuenta 7 en el mismo
instante en el que el cliente 2 deposita US$100000 en la
cuenta 7. Cada uno de los clientes llama al procedimiento
Depositar de tal manera que se crea una transacción para
realizar su actualización. La ejecución concurrente de éstos
depósitos produce una secuencia de lecturas y escrituras en la
base de datos, tales como
Leer1(Cuentas[7]) devuelve el valor de US$1000
Leer2(Cuentas[7]) devuelve el valor de US$1000
Escribir2(Cuentas[7], US$101000
Commit2
Escribir1(Cuentas[7], US$1100)
Commit1
El resultado de esta ejecución es que la Cuenta[7] contiene
US$1100. A pesar que el depósito del cliente 2 concluyó
satisfactoriamente, la interferencia con la ejecución de
Depósito del cliente 1 causó que el depósito del cliente
2 se pierda. Este fenónemo de actualización perdida
ocurre cuando dos transacciones, mientras intentan modificar un
dato, ambas leen el valor antiguo del elemento antes que ninguna
haya modificado su valor.
Otro problema del control de concurrencia se ilustra con el
siguiente programa, llamado ImprimirSuma, el cual imprime la suma
de los saldos de dos cuentas.
Procedure ImprimirSuma(Cuenta1, Cuenta2)
begin
Start;
temp1 := Leer(Cuentas[Cuenta1]);
output(temp1);
temp2 := Leer(Cuentas[Cuenta2]);
output(temp2);
temp1 := temp1 $+$ temp2;
output(temp1);
Commit;
end
Supongamos que las cuentas 8 y 9 tiene un saldo de US$200
cada una, y que el cliente 3 imprime los saldos de las cuentas
8 y 9 (utilizando ImprimirSuma) en el mismo instante en el que
el cliente 4 transfiere US$100 de la cuenta 8 a la cuenta
9 (utilizando Transferir). La ejecución concurrente de estas
dos transacciones puede originar la siguiente ejecución de
operaciones de la base de datos.
Leer4(Cuentas[8]) devuelve el valor de US$200
Escribir4(Cuentas[8], US$100)
Leer3 (Cuentas[8]) devuelve el valor de US$100
Leer3 (Cuentas[9]) devuelve el valor de US$200
Leer4 (Cuentas[9]) devuelve el valor de US$200
Escribir4 (Cuentas[9], US$300)
Commit4
Commit3
El procedimiento Transferir interfiere con ImprimirSuma en esta
ejecución, causando que ImprimirSuma imprima el valor de
US$300, la cual no es la suma correcta de los saldos de las
cuentas 8 y 9. El procedimiento ImprimirSuma no capturó los
US$100 en tránsito de la cuenta 8 a la cuenta 9. Es
importante recalcar que, a pesar de la interferencia, Transferir
todavíia asigna los valores correctos en la base de datos.
Este tipo de interferencia se denomina análisis
inconsistente que ocurre cuando una transacción lee un dato
antes que otra transacción lo actualice y lea otro dato
después que la misma transacción lo ha actualizado. Es decir,
la extracción (lectura) de los datos sólo percibe algunos de
los resultados de la transacción de actualización.
Para conseguir el objetivo del control de concurrencia se utiliza
un sincronizador. Un sincronizador es un programa (o una
colección de ellos) que controla la ejecución concurrente de
las transacciones; su función radica en ordenar las operaciones
que forman parte de las transacciones que se requieren ejecutar
concurrentemente, de tal manera que la ejecución resultante sea
correcta. Usando tres operaciones básicas (ejecución, rechazo
y retraso de una operación) el sincronizador puede controlar el
orden en el cual las operaciones son ejecutadas por el
Administrador de Datos (DM). Cuando éste recibe una operación
de la transacción (mediante el TM), usualmente trata de pasarla
al DM inmediatamente, si no produce alguna ejecución incorrecta.
Si el sincronizador decide que la ejecución de la operación
puede producir resultados incorrectos, puede o retrasarla (en caso
de que pueda procesar correctamente la operación más adelante)
o rechazarla (si no es posible procesarla en el futuro de tal
manera que produzca resultados correctos).
Por ejemplo, retomemos la ejecución concurrente de dos
transacciones Depositar, que depositan US$100 y US$100,000
en la cuenta 7
Leer1 (Cuentas[7]) devuelve el valor de US$1000
Leer2 (Cuentas[7]) devuelve el valor de US$1000
Escribir2 (Cuentas[7], US$101000)
Commit2
Escribir1(Cuentas[7], US$1100)
Commit1
Para evitar esta ejecución incorrecta, un sincronizador debe
decidir rechazar Escribir1 provocando que la transacción T1 sea
cancelada. En este caso, el usuario o el Administrador de
Transacciones puede reenviar T1 , la cual ahora se puede ejecutar
sin interferir con T2. Como otra alternativa, el sincronizador
puede prevenir la ejecución anterior retrasando Leer2 hasta que
reciba y procese Escribir1 y de esta forma evitando que se rechace
Escribir1 más adelante.
Por lo tanto, un DBMS que controla la ejecución concurrente de
sus transacciones tiene una estructura como la siguiente :
Fig. 2. Estructura Esquemáica de un DBMS
4 Teoria 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 transacción 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
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;
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
T1 = r1[x] -› w1[x] -› c1
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
|
