Concurrencia y Recuperabilidad Paradigma Pesimista

Lic. Gerardo Rossel

2016

Serializabilidad

Recuperabilidad

Recuperabilidad

Control de Concurrencia Pesimista-Optimista-SQL

Serializabilidad

Control de Concurrencia

Serializabilidad

Recuperabilidad

Recuperabilidad

Control de Concurrencia Pesimista-Optimista-SQL

Serializabilidad

Control de Concurrencia

Serializabilidad

Recuperabilidad

Recuperabilidad

Control de Concurrencia Pesimista-Optimista-SQL

Serializabilidad

Control de Concurrencia

Serializabilidad

Recuperabilidad

Recuperabilidad

Control de Concurrencia Pesimista-Optimista-SQL

Serializabilidad

Control de Concurrencia

Serializabilidad

Recuperabilidad

Serializabilidad

Control de Concurrencia

Serializabilidad

Recuperabilidad

Problemas

Lost Update Dirty Read Non-repeatable read / unrepeatable read. Phantom Read.

Control de Concurrencia

Serializabilidad

Recuperabilidad

Control de Concurrencia

Transacciones Definición básica Ti ⊆ wi (X); r1 (X) ∪ {ci , ai } Ti representa la transacción i wi (X) escritura de la transacción i sobre el ítem X ri (X) lectura por la transacción i del ítem X ci representa el commit de la transacción i ai representa el abort de la transacción i ai ∈ Ti ⇐⇒ ci ∈ / Ti Ejemplo T1 = w1 (B); r1 (C); w1 (C); c1 T2 = r2 (D); r2 (B); w2 (C); c2

Serializabilidad

Recuperabilidad

Control de Concurrencia

Historias Definición básica Una historia (schedule) H, para un conjunto de ejecuciones de transacciones, es un orden parcial de las operaciones de las transacciones y que muestra cómo las transacciones son intercaladas (interleaved). Todas las operaciones en las transacciones deben aparecer en el mismo orden en la historia. El concepto de historia provee un mecanismo para expresar y razonar sobre la posible ejecución concurrente de transacciones

Serializabilidad

Recuperabilidad

Control de Concurrencia

Historias Definición básica Una historia (schedule) H, para un conjunto de ejecuciones de transacciones, es un orden parcial de las operaciones de las transacciones y que muestra cómo las transacciones son intercaladas (interleaved). Todas las operaciones en las transacciones deben aparecer en el mismo orden en la historia. El concepto de historia provee un mecanismo para expresar y razonar sobre la posible ejecución concurrente de transacciones Ejemplo H1 = r1 (A); w1 (A); r2 (A); w2 (A); r1 (B); w1 (B); r2 (B); w2 (B)

Serializabilidad

Recuperabilidad

Control de Concurrencia

Equivalencia de Historias

Operaciones Conflictivas Dos operaciones son conflictivas si operan sobre el mismo ítem y al menos una de ellas es una escritura.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Equivalencia de Historias

Operaciones Conflictivas Dos operaciones son conflictivas si operan sobre el mismo ítem y al menos una de ellas es una escritura. Equivalencia Dos historias Hi y Hj son conflicto equivalentes Hi ≡ Hj Están definidas sobre el mismo conjunto de transacciones El orden de las operaciones conflictivas de transacciones no abortadas es el mismo.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Historias Seriales

Definición Una historia completa H es serial si, para todo par de transacciones Ti y TJ que aparecen en H, pasa que todas las operaciones de Ti aparecen antes de las de Tj o viceversa.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Historias Seriales

Definición Una historia completa H es serial si, para todo par de transacciones Ti y TJ que aparecen en H, pasa que todas las operaciones de Ti aparecen antes de las de Tj o viceversa. Ejemplo T1 = w1 (B); r1 (C); w1 (C); T2 = r2 (D); r2 (B); w2 (C); Hserial = w1 (B); r1 (C); w1 (C); c1 ; r2 (D); r2 (B); w2 (C); c2

Serializabilidad

Recuperabilidad

Control de Concurrencia

Historias Serializable

Definición Una historia H es conflicto serializable (SR) si es conflicto equivalente a alguna historia serial Hs , es decir H ≡ HS

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad Grafo de precedencia Se utiliza el grafo de precedencia SG(H). Es un grafo dirigido con las siguientes características: Un nodo para cada transacción Ti ⊆ H Hay ejes entre Ti y Tj sí y sólo sí hay una operación de Ti que precede en H a una operación de Tj y son operaciones conflictivas. Etiquetamos los ejes del grafo con los nombres de los ítems que los generan.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad Grafo de precedencia Se utiliza el grafo de precedencia SG(H). Es un grafo dirigido con las siguientes características: Un nodo para cada transacción Ti ⊆ H Hay ejes entre Ti y Tj sí y sólo sí hay una operación de Ti que precede en H a una operación de Tj y son operaciones conflictivas. Etiquetamos los ejes del grafo con los nombres de los ítems que los generan. Teorema de la seriabilidad Una historia H es SR sí y solo sí SG(H) es acíclico.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo

Equivalencia serial Si el SG(H) es acíclico entonces los órdenes seriales equivalentes son los diferentes ordenes topológicos del grafo. Ejemplo T1 = r1 (X); w1 (X); r1 (Y ); w1 (Y ) T2 = r2 (Z); r2 (Y ); w2 (Y ); r2 (X); w2 (X) T3 = r3 (Y ); r3 (Z); w3 (Y ); w3 (Z) H = r2 (Z); r2 (Y ); w2 (Y ); r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (X); r1 (Y ); w1 (Y ); w2 (X) ¿Es H serializable?

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo

Dibujarlo en forma columna para visualizar mejor.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo H = r2 (Z); r2 (Y ); w2 (Y ); r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (X); r1 (Y ); w1 (Y ); w2 (X) T1

T2 r2 (Z) r2 (Y ) w2 (Y )

T3

r3 (Y ) r3 (Z) r1 (X) w1 (X) w3 (Y) w3 (Z) r2 (X) r1 (Y ) w1 (Y ) w2 (X)

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo H = r2 (Z); r2 (Y ); w2 (Y ); r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (X); r1 (Y ); w1 (Y ); w2 (X) T1

T2 r2 (Z) r2 (Y ) w2 (Y )

T3

r3 (Y ) r3 (Z)

T1

T2

r1 (X) w1 (X) w3 (Y) w3 (Z) r2 (X) r1 (Y ) w1 (Y ) w2 (X)

T3

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo H = r2 (Z); r2 (Y ); w2 (Y ); r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (X); r1 (Y ); w1 (Y ); w2 (X) T1

T2 r2 (Z) r2 (Y ) w2 (Y )

T3

r3 (Y ) r3 (Z)

T1

T2

r1 (X) w1 (X) w3 (Y) w3 (Z) r2 (X) r1 (Y ) w1 (Y ) w2 (X)

Y, Z T3

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo H = r2 (Z); r2 (Y ); w2 (Y ); r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (X); r1 (Y ); w1 (Y ); w2 (X) T1

T2 r2 (Z) r2 (Y ) w2 (Y )

T3

r3 (Y ) r3 (Z)

T1

T2

r1 (X) w1 (X) w3 (Y) w3 (Z) r2 (X) r1 (Y ) w1 (Y ) w2 (X)

Y

Y, Z T3

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo H = r2 (Z); r2 (Y ); w2 (Y ); r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (X); r1 (Y ); w1 (Y ); w2 (X) T1

T2 r2 (Z) r2 (Y ) w2 (Y )

T3

X r3 (Y ) r3 (Z)

T1

T2

r1 (X) w1 (X) w3 (Y) w3 (Z) r2 (X) r1 (Y ) w1 (Y ) w2 (X)

Y

Y, Z T3

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo H = r2 (Z); r2 (Y ); w2 (Y ); r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (X); r1 (Y ); w1 (Y ); w2 (X) T1

T2 r2 (Z) r2 (Y ) w2 (Y )

T3

X r3 (Y ) r3 (Z)

r1 (X) w1 (X)

T1

T2 Y

Y w3 (Y) w3 (Z) r2 (X)

r1 (Y ) w1 (Y ) w2 (X)

Y, Z T3

Tiene ciclos, ej: T2 → T3 → T1 → T2

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo 2 H = r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (Z); r1 (Y ); w1 (Y ); r2 (Y ); w2 (Y ); r2 (X); w2 (X) T1 T2 T3 r3 (Y ) X, Y r3 (Z) r1 (X) T1 T2 w1 (X) w3 (Y) w3 (Z) Y, Z Y r2 (Z) r1 (Y ) T3 w1 (Y ) r2 (Y ) w2 (y) r2 (X) w2 (X)

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo 2 H = r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (Z); r1 (Y ); w1 (Y ); r2 (Y ); w2 (Y ); r2 (X); w2 (X) T1 T2 T3 r3 (Y ) X, Y r3 (Z) r1 (X) T1 T2 w1 (X) w3 (Y) w3 (Z) Y, Z Y r2 (Z) r1 (Y ) T3 w1 (Y ) r2 (Y ) w2 (y) r2 (X) w2 (X)

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo 2 H = r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (Z); r1 (Y ); w1 (Y ); r2 (Y ); w2 (Y ); r2 (X); w2 (X) T1 T2 T3 r3 (Y ) X, Y r3 (Z) r1 (X) T1 T2 w1 (X) w3 (Y) w3 (Z) Y, Z Y r2 (Z) r1 (Y ) T3 w1 (Y ) r2 (Y ) w2 (y) r2 (X) w2 (X)

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo 2 H = r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (Z); r1 (Y ); w1 (Y ); r2 (Y ); w2 (Y ); r2 (X); w2 (X) T1 T2 T3 r3 (Y ) X, Y r3 (Z) r1 (X) T1 T2 w1 (X) w3 (Y) Y, Z w3 (Z) Y r2 (Z) r1 (Y ) T3 w1 (Y ) r2 (Y ) w2 (y) r2 (X) Orden Serial: w2 (X)

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo 2 H = r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (Z); r1 (Y ); w1 (Y ); r2 (Y ); w2 (Y ); r2 (X); w2 (X) T1 T2 T3 r3 (Y ) X, Y r3 (Z) r1 (X) T1 T2 w1 (X) w3 (Y) Y, Z w3 (Z) Y r2 (Z) r1 (Y ) T3 w1 (Y ) r2 (Y ) w2 (y) r2 (X) Orden Serial: T3 w2 (X)

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo 2 H = r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (Z); r1 (Y ); w1 (Y ); r2 (Y ); w2 (Y ); r2 (X); w2 (X) T1 T2 T3 r3 (Y ) X, Y r3 (Z) r1 (X) T1 T2 w1 (X) w3 (Y) Y, Z w3 (Z) Y r2 (Z) r1 (Y ) T3 w1 (Y ) r2 (Y ) w2 (y) r2 (X) Orden Serial: T3 → T1 w2 (X)

Serializabilidad

Recuperabilidad

Control de Concurrencia

Testeo de Serializabilidad - Ejemplo 2 H = r3 (Y ); r3 (Z); r1 (X); w1 (X); w3 (Y ); w3 (Z); r2 (Z); r1 (Y ); w1 (Y ); r2 (Y ); w2 (Y ); r2 (X); w2 (X) T1 T2 T3 r3 (Y ) X, Y r3 (Z) r1 (X) T1 T2 w1 (X) w3 (Y) Y, Z w3 (Z) Y r2 (Z) r1 (Y ) T3 w1 (Y ) r2 (Y ) w2 (y) r2 (X) Orden Serial: T3 → T1 → T2 w2 (X)

Serializabilidad

Recuperabilidad

Control de Concurrencia

View Equivalence y View Serializability View Equivalence Dos historias H y H0 son view equivalentes si: 1

H y H’ tienen el mismo conjunto de transacciones y operaciones

2

Para cualquier operación ri (X) de Ti ⊆ H si el valor de X fue escrito por wj (X) de Tj o es el valor original de X antes de que comience H, la misma condición debe cumplirse para la operación ri (X) de H0

3

Si la operación wk (X) de Tk es la última operación de escritura del ítem X en H, entonces wk (X) debe ser también la última operación de escritura del ítem X en H0

. View Serializability Una historia H es view serializable si es view equivalente con una historia H0 serial.

Serializabilidad

Recuperabilidad

Recuperabilidad

Control de Concurrencia

Serializabilidad

Recuperabilidad

Control de Concurrencia

Problemas de recuperabilidad Recuperción Se puede asumir que el Abort se implementa recuperando imágenes anteriores de los ítems.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Problemas de recuperabilidad Recuperción Se puede asumir que el Abort se implementa recuperando imágenes anteriores de los ítems. Ejemplos H1 = w1 (X, 2); r2 (X); w2 (Y , 3); c2 . Si T1 aborta deberíamos abortar T2 (violaríamos la semántica del commit)

H1 = w1 (X); r2 (X); w2 (Y ); a1 . Aborts en cascada

H1 = w1 (X); w2 (X); a1 ; a2 . Problema para recuperar imagen w1 (X, 2) significa que la transacción 1 escribe el valor 2 en X

Serializabilidad

Recuperabilidad

Control de Concurrencia

Lectura entre transacciones

Dadas dos transacciones Ti y Tj decimos que Ti lee X de Tj si Ti lee X y Tj fue la última transacción que escribió X y no abortó antes de que Ti lo leyera. 1

wj (X) < ri (X)

2

aj ≮ ri (X)

3

Si hay algún wk (X) tal que wj (X) < wk (X) < ri (X) entonces ak < ri (X)

Serializabilidad

Recuperabilidad

Control de Concurrencia

Niveles de recuperabilidad Historia Recuperable RC Una historia H es RC si siempre que una transacción Ti lee de Tj con i 6= j en H y ci ∈ H entonces cj < ci . Intuitivamente una historia es recuperable si una transacción realiza commit sólo después de que hicieron commit todas las transacciones de las cuales lee.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Niveles de recuperabilidad Historia Recuperable RC Una historia H es RC si siempre que una transacción Ti lee de Tj con i 6= j en H y ci ∈ H entonces cj < ci . Intuitivamente una historia es recuperable si una transacción realiza commit sólo después de que hicieron commit todas las transacciones de las cuales lee. Avoids Cascading Aborts ACA Una historia H es ACA si siempre que una transacción Ti lee X de Tj con i 6= j en H entonces cj < ri [X]. Lee sólo valores de transacciones que ya hicieron commit

Serializabilidad

Recuperabilidad

Control de Concurrencia

Niveles de recuperabilidad Historia Recuperable RC Una historia H es RC si siempre que una transacción Ti lee de Tj con i 6= j en H y ci ∈ H entonces cj < ci . Intuitivamente una historia es recuperable si una transacción realiza commit sólo después de que hicieron commit todas las transacciones de las cuales lee. Avoids Cascading Aborts ACA Una historia H es ACA si siempre que una transacción Ti lee X de Tj con i 6= j en H entonces cj < ri [X]. Lee sólo valores de transacciones que ya hicieron commit Stricta ST Una historia H es ST si siempre que wj (X) < oi (X) con i 6= j entonces aj < oi (X) o cj < oi (A) siendo oi (X) igual a ri (X) o a wi (X) Es decir no se puede leer ni escribir un ítem hasta que la transacción que lo escribió previamente haya hecho commit o abort.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Teorema de la recuperabilidad

Teorema ST ⊂ ACA ⊂ RC Ortogonalidad SR intersecta a todos los conjuntos RC, ACA y ST. Son conceptos ortogonales. Es fácil ver que una historia serial es también ST.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Relación entre recuperabilidad y serializabilidad SR RC ACA ST

Seriales

Serializabilidad

Recuperabilidad

Control de Concurrencia

Control de Concurrencia

Serializabilidad

Recuperabilidad

Control de Concurrencia

Utilización de locks

Lock Un lock es una variable asociada con un ítem de datos que describe el estado de ese ítem con respecto a posibles operaciones que pueden aplicarse a él. Problemas Deadlock Livelocks

Serializabilidad

Recuperabilidad

Control de Concurrencia

Lock Binario

Lock o Bloqueo Binario

Lock Binario Un lock binario es el modelo más simple. No es utilizado en las BD reales, pero es útil para comenzar y luego pasar a modelos más realistas. Locks binarios pueden tener uno de dos estados: locked o unlocked Notación li (A) Lock. La transacción i realiza un bloqueo o lock sobre el ítem A. ui (A) UnLock. La transacción i libera los bloqueos o locks previos sobre el ítem A. Usado en todos los modelos, se asume que libera todos los locks tomados.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Lock Binario

Lock o Bloqueo Binario Lock binario El lock binario fuerza exclusión mutua sobre un ítem X. Las transacciones pueden ser vistas como una secuencia de locks y unlocks Historias Legales Consistencia de Transacciones: 1

Una Ti puede leer o escribir un ítem X si previamente realizó un lock sobre X y no lo ha liberado

2

Si una transacción Ti realiza un lock sobre un elemento debe posteriormente liberarlo.

Legalidad: Una Ti que desea obtener un lock sobre X que ha sido lockeado por Tj en un modo que conflictua, debe esperar hasta que Tj haga unlock de X.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Lock Binario

Grafo de precedencia para lock binario Se asume H legal. Para hacer el SG(H) se siguen los siguientes pasos: 1

Hacer un nodo por cada Ti ⊆ H

2

Si Ti realiza un li (X) para algún ítem X y luego Tj con i 6= j realiza un li (X) hacer un arco Ti → Tj

Serializabilidad

Recuperabilidad

Control de Concurrencia

Lock Binario

Grafo de precedencia para lock binario Se asume H legal. Para hacer el SG(H) se siguen los siguientes pasos: 1

Hacer un nodo por cada Ti ⊆ H

2

Si Ti realiza un li (X) para algún ítem X y luego Tj con i 6= j realiza un li (X) hacer un arco Ti → Tj

Ejemplo: H = l2 (A); u2 (A); l3 (A); u3 (A); l1 (B); u1 (B); l2 (B); u2 (B) T1

T2

T3

Serializabilidad

Recuperabilidad

Control de Concurrencia

Lock Binario

Grafo de precedencia para lock binario Se asume H legal. Para hacer el SG(H) se siguen los siguientes pasos: 1

Hacer un nodo por cada Ti ⊆ H

2

Si Ti realiza un li (X) para algún ítem X y luego Tj con i 6= j realiza un li (X) hacer un arco Ti → Tj

Ejemplo: H = l2 (A); u2 (A); l3 (A); u3 (A); l1 (B); u1 (B); l2 (B); u2 (B) B T1

T2

T3

Serializabilidad

Recuperabilidad

Control de Concurrencia

Lock Binario

Grafo de precedencia para lock binario Se asume H legal. Para hacer el SG(H) se siguen los siguientes pasos: 1

Hacer un nodo por cada Ti ⊆ H

2

Si Ti realiza un li (X) para algún ítem X y luego Tj con i 6= j realiza un li (X) hacer un arco Ti → Tj

Ejemplo: H = l2 (A); u2 (A); l3 (A); u3 (A); l1 (B); u1 (B); l2 (B); u2 (B) B T1

T2

A T3

Serializabilidad

Recuperabilidad

Control de Concurrencia

Lock Binario

Grafo de precedencia para lock binario Se asume H legal. Para hacer el SG(H) se siguen los siguientes pasos: 1

Hacer un nodo por cada Ti ⊆ H

2

Si Ti realiza un li (X) para algún ítem X y luego Tj con i 6= j realiza un li (X) hacer un arco Ti → Tj

Ejemplo: H = l2 (A); u2 (A); l3 (A); u3 (A); l1 (B); u1 (B); l2 (B); u2 (B) B T1

T2

A T3

H es SR y la Historia Serial Equivalente es T1 , T2 , T3

Serializabilidad

Recuperabilidad

Control de Concurrencia

Locks con varios modos

Lock Ternario Motivación Debido a que operaciones de lectura de diferentes transacciones sobre el mismo ítem no son conflictivas se puede permitir que accedan sólo para lectura. Atención Sin embargo si una transacción desea escribir debe tener acceso exclusivo al ítem. 2 tipos de locks rli (A) Lock de lectura o compartido. La transacción i realiza un bloqueo o lock de lectura sobre el ítem A. wli (A) Lock de escritura o exclusivo. La transacción i realiza un lock exclusivo o de escritura sobre el ítem A.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Locks con varios modos

Matriz de Compatibilidad

Lock Sostenido por Tj

Lock solicitado

por Ti

rl wl

rl Si No

wl No No

Serializabilidad

Recuperabilidad

Control de Concurrencia

Locks con varios modos

Legalidad y Consistencia

Consistencia (a) Una accion ri (X) ser precedida por un lri (X) o un wli (X), sin que intervenga un ui (X) (b) Un accion wi (X) debe ser precedida por una wli (X) sin que intervenga un ui (X) (c) Todos los locks deben ser seguidos de un unlock del mismo elemento Legalidad de las Historias (a) Si wli (X) aparece en una historia, entonces no puede haber luego un wlj (X) o rlj (X) para j 6= i sin que haya primero un ui (X) (b) Si rli (X) aparece en una historia no puede haber luego un wlj (X) para j 6= i sin que haya primero un ui (X)

Serializabilidad

Recuperabilidad

Control de Concurrencia

Locks con varios modos

Grafo de precedencia para Locking ternario

1

Hacer un nodo por cada Ti

2

Si Ti hace un rli (X) o wli (X) y luego Tj con j 6= i hace un wlj (X) en H hacer un arco Ti → Tj

3

Si Ti hace un wli (X) y Tj con j 6= i hace un rlj (X) en H entonces hacer un arco Ti → Tj

Básicamente dice que si dos transacciones realizan un lock sobre el mismo ítem y al menos uno de ellas es un write lock se debe dibujar un eje desde la primera a la segunda.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Locks con varios modos

Conversión o Upgrading/Downgrading Lock

Conversión Una transacción que tiene un lock sobre un ítem X tiene permitido bajo ciertas condiciones convertir dicho lock en otro tipo de lock. La forma más común es el upgrading lock, es decir pasar de un lock de escritura o compartido a un lock exclusivo o de escritura.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Locks con varios modos

Update Lock y update lock Deadlock al usar updgrade lock Supongamos T1 y T2 , y se presente la siguiente historia donde cada una quiere realizar un upgrade lock. Ambos son denegados: H = rl1 (X); rl2 (X); w1 (X); w2 (X) Upgrade lock Se puede evitar el problema del deadlock si agregamos otro modo de lock llamado update lock. Un update lock sobre un ítem X que denotamos uli (X) da a la transacción Ti privilegio de lectura sobre X pero no de escritura. Como ventaja el update lock pasa a ser el único que puede ser upgraded a write lock

Serializabilidad

Recuperabilidad

Control de Concurrencia

Locks con varios modos

Matriz de compatibilidad Lock

Matriz de compatibilidad Update Block rl wl ul

rl Si No No

wl No No No

ul Si No No

Uso de update lock H = rl1 (X); rl2 (X); w1 (X); w2 (X) Deadlock T1 = ul1 (A); wl1 (X); u1 (A) T2 = ul2 (A); wl2 (X); u2 (A) H = ul1 (A); ul2 (A); wl1 (X); u1 (A); ul2 (A); wl2 (X); u2 (A)

Serializabilidad

Recuperabilidad

Control de Concurrencia

Locks con varios modos

Loking Y Serializabilidad

Atención El mecanismo de locking por si solo no garantiza serializabilidad. Se necesita utilizar un protocolo para posicionar los locks y unlocks.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Locks con varios modos

Loking Y Serializabilidad

Atención El mecanismo de locking por si solo no garantiza serializabilidad. Se necesita utilizar un protocolo para posicionar los locks y unlocks.

T1 = rl1 (X); u1 (X); wl1 (Y ); u1 (Y ); c1 T2 = wl2 (X); wl2 (Y ); u2 (X); u2 (Y ); c2 H = rl1 (X); u1 (X); wl2 (X); wl2 (Y ); u2 (X); u2 (Y ); c2 ; wl1 (Y ); u1 (Y ), c1

Serializabilidad

Recuperabilidad

Control de Concurrencia

Locks con varios modos

Loking Y Serializabilidad

Atención El mecanismo de locking por si solo no garantiza serializabilidad. Se necesita utilizar un protocolo para posicionar los locks y unlocks.

T1 = rl1 (X); u1 (X); wl1 (Y ); u1 (Y ); c1 T2 = wl2 (X); wl2 (Y ); u2 (X); u2 (Y ); c2 H = rl1 (X); u1 (X); wl2 (X); wl2 (Y ); u2 (X); u2 (Y ); c2 ; wl1 (Y ); u1 (Y ), c1

X T1

T2 Y

Serializabilidad

Recuperabilidad

Control de Concurrencia

2PL

Two Phase Locking - 2PL Two Phase Locking - Definición Una transacción respeta el protocolo de bloqueo en dos fases (2PL) si todas las operaciones de bloqueo (lock) preceden a la primer operación de desbloqueo (unock) en la transacción. Una transacción que cumple con el protocolo se dice que es una transacción 2PL Fase de crecimiento: toma los locks Fase de contracción: libera los locks Serializabilidad con 2PL Dado T = T1 , T2 , ..., Tn , si toda Ti en T es 2PL, entonces todo H legal sobre T es SR.

Serializabilidad

Recuperabilidad

Control de Concurrencia

2PL

Variantes de 2PL 2PL Estricto (2PLE) Una transacción cumple con 2PL Estricto si es 2PL y no libera ninguno de sus locks de escritura hasta después de realizar el commit o el abort. Serializabilidad con 2PL Estricto 2PLE garantiza que la historia es ST. No es libre de deadlock. 2PL Riguroso (2PLR) Una transacción cumple con 2PL Riguroso si es 2PL y no libera ninguno de sus locks de escritura o lectura hasta después de realizar el commit o el abort.

Serializabilidad

Recuperabilidad

Control de Concurrencia

Administración de Deadlocks

Deadlocks

Definición Deadlock es un estado en el cual cada miembro de un grupo de transacciones está esperando que algún otro miembro libere un lock. ¿Cómo tratar con Deadlocks? Prevención Detección

Serializabilidad

Recuperabilidad

Control de Concurrencia

Administración de Deadlocks

Detección usando Wait-for Graph Un nodo por cada transacción que tiene un lock o espera por uno. Un eje entre dos nodos (Ti y Tj ) si Ti está esperando que Tj libere un lock que sobre un ítem que Ti necesita bloquear. Considerar la siguiente historia parcial: l1 (A); l2 (B); l1 (B); l3 (C); l2 (C); l4 (B); l3 (A)

Serializabilidad

Recuperabilidad

Control de Concurrencia

Administración de Deadlocks

Detección usando Wait-for Graph Un nodo por cada transacción que tiene un lock o espera por uno. Un eje entre dos nodos (Ti y Tj ) si Ti está esperando que Tj libere un lock que sobre un ítem que Ti necesita bloquear. Considerar la siguiente historia parcial: l1 (A); l2 (B); l1 (B); l3 (C); l2 (C); l4 (B); l3 (A) T1

Serializabilidad

Recuperabilidad

Control de Concurrencia

Administración de Deadlocks

Detección usando Wait-for Graph Un nodo por cada transacción que tiene un lock o espera por uno. Un eje entre dos nodos (Ti y Tj ) si Ti está esperando que Tj libere un lock que sobre un ítem que Ti necesita bloquear. Considerar la siguiente historia parcial: l1 (A); l2 (B); l1 (B); l3 (C); l2 (C); l4 (B); l3 (A) T1

T2

Serializabilidad

Recuperabilidad

Control de Concurrencia

Administración de Deadlocks

Detección usando Wait-for Graph Un nodo por cada transacción que tiene un lock o espera por uno. Un eje entre dos nodos (Ti y Tj ) si Ti está esperando que Tj libere un lock que sobre un ítem que Ti necesita bloquear. Considerar la siguiente historia parcial: l1 (A); l2 (B); l1 (B); l3 (C); l2 (C); l4 (B); l3 (A) T1

T2

Serializabilidad

Recuperabilidad

Control de Concurrencia

Administración de Deadlocks

Detección usando Wait-for Graph Un nodo por cada transacción que tiene un lock o espera por uno. Un eje entre dos nodos (Ti y Tj ) si Ti está esperando que Tj libere un lock que sobre un ítem que Ti necesita bloquear. Considerar la siguiente historia parcial: l1 (A); l2 (B); l1 (B); l3 (C); l2 (C); l4 (B); l3 (A) T1

T2

T3

Serializabilidad

Recuperabilidad

Control de Concurrencia

Administración de Deadlocks

Detección usando Wait-for Graph Un nodo por cada transacción que tiene un lock o espera por uno. Un eje entre dos nodos (Ti y Tj ) si Ti está esperando que Tj libere un lock que sobre un ítem que Ti necesita bloquear. Considerar la siguiente historia parcial: l1 (A); l2 (B); l1 (B); l3 (C); l2 (C); l4 (B); l3 (A) T1

T2

T3

Serializabilidad

Recuperabilidad

Control de Concurrencia

Administración de Deadlocks

Detección usando Wait-for Graph Un nodo por cada transacción que tiene un lock o espera por uno. Un eje entre dos nodos (Ti y Tj ) si Ti está esperando que Tj libere un lock que sobre un ítem que Ti necesita bloquear. Considerar la siguiente historia parcial: l1 (A); l2 (B); l1 (B); l3 (C); l2 (C); l4 (B); l3 (A) T1

T2

T4

T3

Serializabilidad

Recuperabilidad

Control de Concurrencia

Administración de Deadlocks

Detección usando Wait-for Graph Un nodo por cada transacción que tiene un lock o espera por uno. Un eje entre dos nodos (Ti y Tj ) si Ti está esperando que Tj libere un lock que sobre un ítem que Ti necesita bloquear. Considerar la siguiente historia parcial: l1 (A); l2 (B); l1 (B); l3 (C); l2 (C); l4 (B); l3 (A) T1

T2

T4

T3

Serializabilidad

Recuperabilidad

Control de Concurrencia

Administración de Deadlocks

Elección de víctima. Cuanto tiempo la transacción ha estado ejecutándose. Sería mejor abortar una transacción más joven que una que ha estado ejecutándose por más tiempo Cuantos ítems de datos han sido actualizados por la transacción. Sería mejor abortar una transacción que hizo pocas modificaciones a la base de datos. Es decir que tiene la menor cantidad de registros de log. Cuantos ítems de datos le faltan actualizar. Aunque esto puede ser algo que el DBMS no necesariamente sepa. El número de ciclos que contiene la transacción. Mientras más ciclos tenga mejor es. Configurable En Microsoft SQL Server, una transacción puede configurarse como: “SET DEADLOCK_PRIORITY LOW” or “SET DEADLOCK_PRIORITY NORMAL.”

Serializabilidad

Recuperabilidad

Control de Concurrencia

Administración de Deadlocks

Prevención usando TimeStamp

TimeStamp Cada transacción Ti recibe un timestamp TS(Ti ). Es un identificador único basado en el orden en el cual cada transacción comienza. Si TS(Ti ) < TS(Tj ) sigifica que Ti es más vieja que Tj

Serializabilidad

Recuperabilidad

Control de Concurrencia

Administración de Deadlocks

Prevención usando TimeStamp Si Ti intenta realizar un lock sobre in ítem y no puede porque Tj ya tiene un lock previo entonces hay dos estrategias: Wait-Die Si TS(Ti ) < TS(Tj ) (Ti más viejo que Tj ), entonces Ti se lo pone en espera, Si TS(Ti ) > TS(Tj )(Ti más joven que Tj ),entonces se aborta Ti (Ti dies) y se recomienza mas tarde con el mismo timestamp.

Wound-Wait Si TS(Ti ) < TS(Tj ) (Ti más viejo que Tj ), entonces, abortar Tj (Ti wounds Tj ) y recomienza más tarde con el mismo timestamp. Si TS(Ti ) > TS(Tj )(Ti más joven que Tj ),entonces, Ti se pone en espera.

Serializabilidad

Recuperabilidad

Administración de Deadlocks

Otros esquemas

Timeout No waiting (NW) Cautious waiting (CW)

Control de Concurrencia