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