Concurrencia

Question 1

Anomalías de la ejecución concurrente

Answer 1

• La anomalía de la lectura sucia (dirty read) se presenta cuando una transacción T 2 lee un ítem que ha sido modificado por otra transacción T 1 . Si luego T 1 se deshace, la lectura que hizo T 2 no es válida en el sentido de que la ejecución resultante puede no ser equivalente a una ejecución serial de las transacciones. También se lo conoce con el nombre de “Temporary update” ó “Read uncommitted data”. Es un conflicto de tipo WR: W T 1 (X )…R T 2 (X )…(a T 1 ó c T 1 ).
• La anomalía de la actualización perdida (lost update) ocurre cuando una transacción modifica un ítem que fue leído anteriormente por una primera transacción que aún no terminó. En este caso, si la primera transacción luego modifica y escribe el ítem que leyó, el valor escrito por la segunda se perderá. Si en cambio la primera transacción volviera a leer el ítem luego de que la segunda lo escribiera, se encontraría con un valor distinto. En este caso se lo conoce como lectura no repetible (unrepeatable read). Ambas situaciones presentan un conficto de tipo RW (read-write), seguido por otro de tipo WW ó WR, respectivamente. Caracterización: R T 1 (X )…W T 2 (X )…(a T 1 ó c T 1 ).
• La anomalía de la escritura sucia (dirty write) ocurre cuando una transacción T 2 escribe un ítem que ya había sido escrito por otra transacción T 1 que luego se deshace. El problema se dará si los mecanismos de recuperación vuelven al ítem a su valor inicial, deshaciendo la modificación realizada por T 2 . También se conoce con el nombre de overwrite uncommitted. Es un conficto de tipo WW (write-write): W T 1 (X )…W T 2 (X )…(a T 1 ó c T 1 ).
• La anomalía del fantasma (phantom) se produce cuando una transacción T 1 observa un conjunto de ítems que cumplen determinada condición, y luego dicho conjunto cambia porque algunos de sus items son modificados/creados/eliminados por otra transacción T 2 . Si está modificación se hace mientras T 1 aún se está ejecutando, T 1 podría encontrarse con que el conjunto de ítems que cumplen la condición cambió. Esta anomalía atenta contra la serializabilidad.

Question 2

Ejecucion serial

Answer 2

Dado un conjunto de transacciones T 1 , T 2 , …, T n una ejecución serial es aquella en que las transacciones se ejecutan por completo una detrás de otra, en base a algún orden T i 1 , T i 2 , …, T i n .

Question 3

nociones de equivalencia entre órdenes de ejecución de transacciones

Answer 3

Equivalencia de resultados: Cuando, dado un estado inicial particular, ambos órdenes de ejecución dejan a la base de datos en el mismo estado.
Equivalencia de conflictos: Cuando ambos órdenes de ejecución poseen los mismos conflictos entre instrucciones. Esta noción es particularmente interesante porque no depende del estado inicial de la base de datos. Es la más fuerte de las tres.
Equivalencia de vistas: Cuando en cada órden de ejecución, cada lectura R T i (X ) lee el valor escrito por la misma transacción j, W T j (X ). Además se pide que en ambos órdenes la última modificación de cada ítem X haya sido hecha por la misma transacción.

Equivalencia de conflictos: Dado un orden de ejecución tenemos un conflicto cuando dos transacciones distintas ejecutan instrucciones sobre un mismo ítem X , y al menos una de las dos instrucciones es una escritura.
Note from geeksforgeeks.com: If a schedule is conflict serializable then it is also view serializable schedule.

Question 4

Grafo de precedencias

Answer 4

La serializabilidad por conflictos puede ser evaluada a través del grafo de precedencias.

1. Se crea un nodo por cada transacción T 1 , T 2 , …, T n .
2. Se agrega un arco entre los nodos T i y T j (con i 6 = j) si y sólo si existe algún conflicto de la forma RW, WR o WW .

Question 5

Control de concurrencia

Answer 5

• Enfoque pesimista: Busca garantizar que no se produzcan conflictos. Control de concurrencia basado en locks.
• Enfoque optimista: Consiste en “dejar hacer” a las transacciones, y deshacer (rollback) una de ellas si en fase de validación se descubre un conflicto. Conveniente cuando la probabilidad de conflicto es baja.
  • Control de concurrencia basado en timestamps.
  • Snapshot Isolation.
  • Control de concurrencia multiversión (MVCC).

Question 6

Control de concurrencia basado en locks

Answer 6

Protocolo de lock de dos fases (2PL): Una transacción no puede adquirir un lock luego de haber liberado un lock que había adquirido.
La regla divide naturalmente en dos fases a la ejecución de la transacción: Una fase de adquisición de locks, en la que la cantidad de locks adquiridos crece. Una fase de liberación de locks, en que la cantidad de locks adquiridos decrece. El cumplimiento de este protocolo es condición suficiente para garantizar que cualquier orden de ejecución de un conjunto de transacciones sea serializable. (Prueba en [GM09 18.3.4] )
Sin embargo, la utilización de locks introduce otros dos problemas potenciales que antes no teníamos:
deadlock
livelock

Question 7

Control de concurrencia basado en locks

Answer 7

Protocolo de lock de dos fases (2PL): Una transacción no puede adquirir un lock luego de haber liberado un lock que había adquirido.
La regla divide naturalmente en dos fases a la ejecución de la transacción: Una fase de adquisición de locks, en la que la cantidad de locks adquiridos crece. Una fase de liberación de locks, en que la cantidad de locks adquiridos decrece. El cumplimiento de este protocolo es condición suficiente para garantizar que cualquier orden de ejecución de un conjunto de transacciones sea serializable. (Prueba en [GM09 18.3.4] )
Sin embargo, la utilización de locks introduce otros dos problemas potenciales que antes no teníamos:
deadlock
livelock