control de concurrencia lic. bárbara da silva sistemas de bases de datos distribuidas - ucv
TRANSCRIPT
Control de Concurrencia
Lic. Bárbara da Silva
Sistemas de Bases de Datos Distribuidas - UCV
Esquema de la Clase
• Caracterización de una Transacción• Formalización del concepto de transacción• Discusión Tarea
• Control de Concurrencia• Teoría de la Seriabilidad
– Seriabilidad en BD Centralizadas– Seriabilidad en BDD Distribuidas
• Mecanismos de Control de Concurrencia• Algoritmos• Manejo de Abrazo Mortal
Caracterización de una Transacción
Una transacción lee y escribe data.
Entonces:
RS = Conjunto de elementos de datos de la BD leidos por una transacción.WS = Conjunto de elementos de datos escritos por una transacción.
Por tanto el conjunto base de una transacción es:BS = RS U WS
Formalización del Concepto de Transacción
Oij(x) = Una operación Oj de la transacción Ti que opera sobre la entidad x de la BD. Donde Oij Є {R(x), W(x)}
El conjunto de todas las operaciones en Ti se puede definir como:
Osi = UjOij
Ni = La condición de terminación para Ti. Ni Є {abort, commit}
Una transacción Ti es un orden parcial sobre las operaciones y la condición de terminación. Ese orden parcial se denota como:Ti = {∑i, <i}
‹ Indica el orden de ejecución (precede a)
Formalización del Concepto de Transacción
1. ∑i = Osi U {Ni}
2. Para dos operaciones cualesquiera Oij, Oik Є Osi siOij = {R(x) ó W(x)} y Oik = W(x) Para cualquier x, EntoncesOij < Oik ó Oik < Oij
3. Oij Є Osi Oij <i Ni
Formalización del Concepto de Transacción
T = { ∑, <}
∑ = {R(x), R(y), W(y), C}
< = {(R(x), W(y)), (R(y), W(y)), (R(x), C), (R(y), C), (W(y), C)}
= {R(x), R(y), W(y), C}
BEGIN_TRANSACTION
Read(x)
Read(y)
y = y * x;
Write(y)
Commit
END_TRANSACTION
Grafo Dirigido Acíclico (DAG) de T
R(x) W(y) C
R(y)
Control de Concurrencia
El Mecanismo de Control de Concurrencia de un DDBMS asegura que se mantiene la consistencia de la base de datos en un ambiente distribuido multiusuario.
Sino se hace un adecuado control de concurrencia, se pueden presentar dos anomalías:
Se pueden perder actualizaciones provocando que los efectos de algunas transacciones no se reflejen en la base de datos
Pueden presentarse recuperaciones de información inconsistentes.
Teoría de la Seriabilidad
Establece que un algoritmo de control de concurrencia es correcto cuando sus resultados son los mismos que si se hubiese procesado secuencialmente.
BEGIN_TRANSACTION
X = 0;
X = X + 1;
END_TRANSACTION
BEGIN_TRANSACTION
X = 0;
X = X + 2;
END_TRANSACTION
BEGIN_TRANSACTION
X = 0;
X = X + 3;
END_TRANSACTIONSchedule 1
x = 0; x = x+1; x = 0; x = x+2; x = 0; x = x+3; Si
Schedule 2
x = 0; x = 0; x = x + 1; x = x + 2; x = 0; x = x+3;
Si
Schedule 3
x = 0; x = 0; x = x+1; x = 0; x = x+2; x = x+3; No
Seriabilidad en BD Centralizadas
Sean las transaccionesTi = Ri(x) Wi(y)Tj = Rj(x) Wj(x)
Tk = Rk(y)
Por definición la ejecución serial de Ti Tj Tk es correcta
Si tenemos una historia de ejecución S1 = Ri(x) Rj(x) Wi(y) Rk(y) Wj(x)
Queremos saber si es correcta
Seriabilidad en BD Centralizadas
Dos transacciones Ti y Tj se ejecutan serialmente en una historia S si la última operación de Ti precede la primera operación de Tj en S o viceversa, en otro caso ellas se ejecutan concurrentemente.
Seriabilidad: Una historia es correcta si ésta es serializable, esto es, ella es equivalente a una historia serial.
Operaciones en Conflicto: Dos operaciones Oi y Oj están en conflicto si 1. Son emitidas por transacciones diferentes 2. Operan sobre el mismo dato y una de ellas es una escritura.
Ejemplo: (Ri(x) Wj(x)) y (Wi(x) Wj(x)) son operaciones en conflicto.
Seriabilidad en BD Centralizadas
Condición suficiente para equivalencia
Dos historias S1 y S2 son equivalentes si para cada par de operaciones en conflicto Oi y Oj se tiene que:
Si Oi precede a Oj en S1 => Oi precede a Oj en S2
Ejemplo:S1 = Ri(x) Rj(x) Wj(y) Wi(x)S2 = Rj(x) Wj(y) Ri(x) Wi(x) -> Es una historia serial: Tj Ti
Las operaciones en conflicto son Rj(x) con Wi(x)Rj(x) precede a Wi(x) en S1 y en S2
S1 S2, Por tanto S1 es una historia correcta
Seriabilidad en BDD
Se dispone de:
- n transacciones distribuidas T1, T2,..., Tn sobre m nodos- Un conjunto local de historias S1, S2,..., Sm
La seriabilidad de historias locales no es suficiente para asegurar la correctitud de ejecución de un conjunto de transacciones distribuidas.
Seriabilidad en BDD
Ejemplo:S1 (nodo 1) = Ri(x) Wi(x) Rj(y) Wk(x)S2 (nodo 2) = Wj(z) Wi(z) S3 (nodo 3) = Wj(z) Rk(z)
Las tres historias son serializables:S1 = Ti Tj Tk S2 = Tj Ti S3 = Tj Tk
Sin embargo no existe una secuencia global de ejecución de las transacciones ya que
Ti < Tj en S1 y Tj < Ti en S2.
Condición de Seriabilidad en BDD
La ejecución de transacciones T1, T2,...,Tn es correcta si:
1. Cada historia local Sk es serializable.
2. Existe un ordenamiento total de T1, T2, ... ,Tn tal que si Ti < Tj en el ordenamiento total, entonces existe una historial serial Sk’ tal que Sk es equivalente a SK’ y Ti < Tj en Serial(Sk’) para cada nodo k donde ambas transacciones son ejecutadas.
Condición de Seriabilidad en BDD
Ejemplo:S1 (nodo 1) = Ri(x) Wi(y) Rj(y) Wk(x) S2 (nodo 2) = Wi(y) Wj(z)S3 (nodo 3) = Wj(z) Rk(z)
Las tres historias son serializables:S1 = Ti Tj Tk S2 = Ti Tj S3 = Tj Tk
En el nodo 1 Ti < Tj y Tj < TkEn el nodo 2 Ti < Tj En el nodo 3 Tj < Tk Entonces:
Ti Tj Tk es un orden total que satisface la condición de seriabilidad
Condición de Seriabilidad en BDD
Proposición:
Sean T = {T1, T2, ..., Tn} un conjunto de transaccionesE = {S1, S2,..., Sm} una ejecución de T
E es serializable si existe un ordenamiento total de las transacciones tal que para cada par de operaciones en conflicto Oi y Oj de las transacciones Ti y Tj respectivamente
Oi < Oj en cualquier historia de E si y solo si Ti < Tj en el ordenamiento total.
Un mecanismo de control de concurrencia es correcto si éste sólo permite ejecuciones correctas
de transacciones distribuidas