View
17
Download
0
Embed Size (px)
DESCRIPTION
Transacciones y Control de Concurrencia
Citation preview
Bases de Datos -2006
Ejemplos de la aplicacion de
protocolos de control de
concurrencia
Protocolo de bloqueo de dos fases
Ejemplo 1: La siguiente transaccion no obe-dece el protocolo de bloqueos de dos fases:
T1 : lx 1(A); r1(A);w1(A);u1(A); lx 1(B); r1(B);w1(B);u1(B) .
Ejemplo 2: Las siguientes transaccion obe-
decen el protocolo de bloqueos de dos fases:
T1 : lx 1(A); r1(A);w1(A); lx 1(B);u1(A); r1(B);w1(B);u1(B) .
T2 : lx 2(A); r2(A);w2(A); lx 2(B);u2(A); r2(B);w2(B);u2(B) .
1
Ejemplo 3: Usando las transacciones del ejem-
plo 2 la siguiente planificacion es legal con
relacion al protocolo de bloqueos de dos fases:
paso T1 T21 lx 1(A)2 r1(A)3 w1(A)4 lx 1(B)5 u1(A)6 lx 2(A)7 r2(A)8 w2(A)9 lx 2(B) denied10 r1(B)11 w1(B)12 u1(B)13 lx 2(B)14 u2(A)15 r2(B)16 w2(B)17 u2(B)
2
Si a continuacion del paso 7 falla T1 entonces
se deberıa hacer un retroceso en cascada de
las transacciones en lugar de la planificacion
de la figura anterior.
Ejemplo 4: Sean las siguientes transacciones:
T1 : lx 1(A); r1(A);w1(A); lx 1(B);u1(A); r1(B);w1(B);u1(B) .
T2 : lx 2(B); r2(B);w2(B); lx 2(A);u2(B); r2(A);w2(A);u2(A) .
A continuacion se muestra como se puede
llegar a producir un interbloqueo:paso T1 T21 lx 1(A)2 r1(A)3 w1(A)4 lx 2(B)5 r2(B)6 w2(B)7 lx 2(A) denied8 lx 1(B) denied
3
Protocolo de conversion de
bloqueos
Ejemplo 5: Las transacciones:
T1 : lc 1(A); r1(A); subir1(A);w1(A); lx 1(B);
u1(A);w1(B); bajar1(B); r1(B);u1(B) .
T2 : lc 2(A); r2(A); subir2(A), w2(A); lc 2(B);
r2(B); subir2(B);w2(B);u2(B);u2(A) .
Obedecen el protocolo de conversion de blo-
queos. La siguiente planificacion es legal con
relacion al protocolo de conversion de bloqueos.
Observar como se aprovecha la concurrencia al
usar las instrucciones subir y bajar
4
paso T1 T21 lc 1(A)2 r1(A)3 lc 2(A)4 r2(A)5 subir1(A)6 w1(A)7 lx 1(B)8 subir2(A) denied9 u1(A)10 w1(B)11 bajar1(B)12 subir2(A)13 w2(A)14 lc 2(B)15 r2(B)16 r1(B)17 u1(B)18 subir2(B)19 w2(B)20 u2(B)21 u2(A)
5
Protocolo de arbol
Ejemplo 6: Considerar el siguiente arbol (V, T )de raız A:
V = {A, B, C, D, E, F, G} ,
T = {(A, B), (A, C), (B, D), (B, E), (E, F ), (E, G)}) .
Las transacciones:
T1: l1(A);w1(A); l1(C); r1(C); l1(B);u1(A);
u1(C); l1(E); r1(E);u1(B);u1(E)
T2: l2(B); r2(B); l2(E);u2(B); r2(E); l2(F );
u2(E);w2(F );u2(F )
Obedecen el protocolo de arbol. La siguiente
planificacion es legal con relacion al protocolo
de arbol:
6
paso T1 T21 l1(A)2 w1(A)3 l1(C)4 l2(B)5 r2(B)6 l2(E)7 r1(C)8 l1(B) denied9 u2(B)10 r2(E)11 l2(F )12 l1(B)13 u1(A)14 u1(C)15 l1(E) denied16 u2(E)17 w2(F )18 u2(F )19 l1(E)20 r1(E)21 u1(B)22 u1(E)
7
Protocolo de ordenacion por
marcas temporales
Ejemplo 7: Sean las transacciones:
T1 : st1; r1(A);w1(C)
T2 : st2; r2(B);w2(B)
T3 : st3; r3(B); r3(C);w3(A)
sti significa que la transaccion Ti comienza.
Suponemos que tenemos un planificador quecumple con el protocolo de ordenacion por mar-cas temporales.
Las marcas temporales para los elementos dedato inicialmente valen 0.
Ademas de las columnas para las transaccionesvamos a poner columnas adicionales para refle-jar la variacion de las marcas temporales. Unaplanificacion legal es la siguiente:
8
T1 T2 T3 A B C MTL = 0 L = 0 L = 0E = 0 E = 0 E = 0
st1 T1 = 1st3 T3 = 2
st2 T2 = 3r1(A) L = 1
r2(B) L = 3w1(C) E = 1
retr. ¬∃T3
w2(B) E = 3st3 T3 = 4
r3(B) L = 4w3(A) E = 4
Para columna de datos Q: L = X significa que
MTL(Q) = X y E = X significa que MTE(Q) =
X. Para ultima columna Ti = X significa que
MT (Ti) = X.
retr. se usa para decir que se retrocede la
transaccion. T3 se retrocede debido a que no
se puede hacer r3(B). ¬∃T3 quiere decir que
ya no hay una marca temporal para T3.
9
Protocolo basado en validacion
Ejemplo 8: Sean las transacciones:
T1 : st1; r1(A); r1(B);V1;w1(C)
T2 : st2; r2(B); r2(C);V2;w2(A)
T3 : st3; r3(C); r3(D);V3;w3(D)
sti significa que la transaccion Ti comienza.
Ademas Vi significa “Ti intenta validar”. retr.
se usa para decir que se retrocede la transaccion.
La siguiente planificacion es legal con respecto
al protocolo basado en validacion:
10
T1 T2 T3 M1 M2 M3
st1 I = 1r1(A)r1(B)
st2 I = 2r2(B)r2(C)
V1 V = 3st3 I = 4r3(C)r3(D)V3 V = 5retr. ¬∃ S, V
w1(C) F = 6V2 V = 7retr. ¬∃ S, Vst2 I = 8r2(B)r2(C)
st3 I = 9r3(C)r3(D)V3 V = 10
V2 V = 11retr. ¬∃ S, V
w3(D) F = 12st2 I = 13r2(B)r2(C)V2 V = 14w2(A) F = 15
11
Para columna de datos Mi:
• S = X significa que Inicio(Ti) = X
• V = X significa que V alidacion(Ti) = X
• F = X significa que Fin(Ti) = X, y
• ¬∃ S, V significa que debido a que Ti se
retrocedio, dejan de existir Inicio(Ti) y
V alidacion(Ti).
12
Granularidad Multiple
Ejemplo 9: Considerar una base de datos que
contiene dos bloques B1 y B2. El primer bloque
contiene 2 registros R1 y R2, y el segundo
bloque contiene tres registros R3, R4 y R5. La
base de datos, los bloques y los registros for-
man una jerarquıa de elementos bloqueables.
Las siguientes transacciones son obedecen elprotocolo de granularidad multiple:
T1 : lIX 1(BD); lIC 1(B1); lC 1(R1); r1(R1); lIX 1(B2);lX 1(R3);w1(R3);u1(R1);u1(B1);u1(R3);u1(B2);u1(BD)
T2 : lIX 2(BD); lIC 2(B1); lC 2(R1); r2(R1); lX 2(B2);w2(R3);w2(R5);w2(R4);u2(B2);u2(R1);u2(B1);u2(BD)
Asumimos que se tiene un planificador basado
en el protocolo de granularidad multiple. En-
tonces una planificacion legal es la siguiente:
13
T1 T2lIX 1(BD)lIC 1(B1)lC 1(R1)r1(R1)lIX 1(B2)lX 1(R3)w1(R3)
lIX 2(BD)lIC 2(B1)lC 2(R1)r2(R1)lX 2(B2) denied
u1(R1)u1(B1)u1(R3)u1(B2)u1(BD)
lX 2(B2)w2(R3)w2(R5)w2(R4)u2(B2)u2(R1)u2(B1)u2(BD) 14
Ordenacion por marcas temporales
multiversion
Ejemplo 10: Sean las siguientes transacciones:
T1 : st1; r1(A);w1(A);w1(A)
T2 : st2;w2(A); r2(A)
T3 : st3; r3(A);w3(A)
sti significa que la transaccion Ti comienza.
Supongamos que tenemos un planificador ba-
sado en ordenacion por marcas temporales mul-
tiversion.
Inicialmente las marcas temporales de los ele-
mentos de datos valen 0.
La siguiente planificacion es legal con respecto
a este protocolo:
15
T1 T2 T3 A MT VE1 = 0, L1 = 0
st1 T1 = 1st3 T3 = 2
st2 T2 = 3r1(A) L1 = 1 A1
w1(A) E2 = 1, L2 = 1 A1
r3(A) L2 = 2 A2
w2(A) E3 = 3, L3 = 3 A2
w3(A) A2
r2(A) A3
retr. A2
st1 T1 = 4r1(A) L3 = 4 A3
w1(A) E4 = 4, L4 = 4 A3
w1(A) A4
Para columna de datos Q: Li = X significaque MTL(Qi) = X y Ei = X significa queMTE(Qi) = X. Para penultima columna Ti =X significa que MT (Ti) = X. La ultima colum-na se usa para indicar cual es la version de unelemento de datos que se esta considerando enun paso dado.
retr. se usa para decir que se retrocede latransaccion al no poder ejecutarse la operacionde escritura.
16