Los problemas de concurrencia son comunes en una base de datos. El bloqueo y el estampado son dos técnicas para evitarlos. A continuación se muestran ejercicios corregidos sobre este tema.
Preámbulo
Expresión de restricciones
—————————
0. Preámbulo de PL/SQL
SQL:
– Declarativo por lo tanto sin estructuras de control (bucles, condiciones, etc.)
– Operaciones de conjunto de datos
=> Pocas aplicaciones se pueden lograr mediante una simple secuencia de consultas SQL; necesidad de enriquecer SQL con capacidades procesales.
3 posibilidades
– SQL incorporado (PRO*C…)
– API de comunicación (SQL-CLI…)
– Lenguaje dedicado (PL/SQL…)
Ventaja de los lenguajes dedicados: Procedimientos ejecutados en el lado del servidor -> Sólo los resultados se devuelven al cliente -> Intercambios de red mínimos
P0. Procedimientos PL/SQL
P0.1
CREAR O REEMPLAZAR EL PROCEDIMIENTO D
(noc EN CUENTAS.Numero%TYPE,
crédito EN NÚMERO )
ES
COMENZAR
ACTUALIZAR CUENTAS ESTABLECER SALDO = SALDO – débito
DONDE Número = noc;
FIN;
/
P0.2
CREAR O REEMPLAZAR EL PROCEDIMIENTO C
(noc EN CUENTAS.Numero%TYPE,
crédito EN CUENTAS.Saldo%TYPE)
ES
COMENZAR
ACTUALIZAR CUENTAS ESTABLECER SALDO = SALDO + crédito
DONDE Número = noc;
FIN;
/
P0.3
CREAR O REEMPLAZAR EL PROCEDIMIENTO S
(noc EN CUENTAS.Número%TYPE)
ES
elSaldo CUENTAS.Saldo%TYPE;
COMENZAR
SELECCIONE el saldo EN theBalance
DE CUENTAS
DONDE Número = noc;
DBMS_OUTPUT.PUT_LINE(elSaldo);
FIN;
/
P0.4
CREAR O REEMPLAZAR EL PROCEDIMIENTO V
(no de EN CUENTAS.Numero%TYPE,
noto EN CUENTAS.Numero%TYPE,
trans EN CUENTAS.Saldo%TYPE)
ES
COMENZAR
D (no de, trans);
C (noto, trans);
FIN;
/
P0.5
CREAR O REEMPLAZAR FUNCIÓN comprobar
(noc EN CUENTAS.Numero%TYPE,
importe EN CUENTAS.Saldo%TYPE)
VOLVER BOOLEANO
ES
es Solvente BOOLEAN;
elSaldo CUENTAS.Saldo%TYPE;
COMENZAR
SELECCIONE el saldo EN theBalance
DE CUENTAS
DONDE Número = noc;
SI Saldo >= monto ENTONCES
essolvente := VERDADERO;
DEMÁS
esDisolvente := FALSO;
TERMINARA SI;
RETORNO es Solvente;
Comprobación FINAL;
Ejercicio 1
Pregunta 1
Para evitar posibles problemas de concurrencia, el administrador opta por ejecutar las transacciones en serie. Consideramos el caso de dos transacciones simultáneas en la cuenta X, cuyo saldo inicial es de 1000 euros. Ambos son débitos, el primero son 400 euros, el segundo son 800 euros.
En el preciso momento en que T1 inicia su flujo, comienza T2.
Qué esta pasando ?
¿Cómo podemos acelerar la ejecución de estas transacciones?
Pregunta 2
Seis administradores de cuentas bancarias realizan cada uno, en una transacción y simultáneamente, operaciones en 4 cuentas A, B, C y D. Sea Ei(A) una operación de escritura en la cuenta A por parte del administrador i, y Li( A) a operación de lectura de la cuenta A por parte del administrador i. Considere la siguiente secuencia de operación: E2(A), L2(B), L6(D), E5(C), E3(A), L5(A), L1(C), L2(D), L3(C) , E4(C), E3(D), L4(B), L1(B).
- Constrúyelo grafico precedencia de estas transacciones.
- ¿Qué problemas de ejecución podrían surgir?
- ¿Esta ejecución es serializable?
Ejercicio 2
Pregunta 3
Nos situamos en el caso del bloqueo, con gránulo de nivel tupla.
Demuestre que el algoritmo de bloqueo “detecta” el problema de esta ejecución. ¿Cuál sería el algoritmo de resolución de conflictos más adecuado para esta ejecución?
Ejercicio 3
Pregunta 4
Sugerir un algoritmo algoritmo de lectura y escritura con estampación. ¿Estamos seguros de que esta ejecución sea serializable con el sistema de estampado? Demuestre que esto es cierto para cualquier ejecución no serializable.
Pregunta 5
Compare las dos familias de técnicas vistas anteriormente (bloqueo y estampado). ¿El algoritmo de estampado simple es más adecuado para esta ejecución que el bloqueo?
P4. Gráfico de precedencia
El mecanismo de control de la competencia debe proporcionar a cada transacción la ilusión de que es la única que se ejecuta en la BD, es decir, la ejecución efectiva (por lo tanto entrelazada) de las transacciones debe ser equivalente a una ejecución en serie de éstas (ejecución: secuencia ordenada de lecturas). /operaciones de escritura).
Las ejecuciones equivalentes a una ejecución en serie se denominan serializables. El mecanismo de concurrencia debe garantizar que solo genere ejecuciones serializables.
Ejecución: secuencia ordenada de operaciones de lectura/escritura por diferentes transacciones.
Ejecución en serie: Las operaciones de diferentes transacciones no se entrelazan.
¿Es posible reordenar la ejecución para que sea serial?
No, porque es imposible intercambiar entradas con cualquier otra operación -> Induce una relación de precedencia entre transacciones.
Más formalmente:
Ti precede a Tj (“Ti < Tj”) si Ai ocurre antes
Aj en la ejecución Ai y Aj implican el mismo objeto del BD
Ai o Aj es una acción de escritura.
Esta relación de precedencia genera el gráfico de precedencia, en el que un vértice es una transacción y una arista dirigida es una relación de precedencia.
Por ejemplo: Ti -> Tj significa que Ti precede a Tj
Vista por objeto de operaciones (más simple que la vista global, pero pierde el orden de las operaciones dentro de una transacción):
A: E2(A) E3(A) L5(A)
B: L2(B) L4(B) L1(B)
C: E5(C) L1(C) L3(C) E4(C)
D: L6(D) L2(D) E3(D)
Gráfico de precedencia:
T2 -> T3 <-> T5 -> T1 -> T4
T6 ->|
Propiedad del gráfico de precedencia:
Ejecución serializable si no hay ciclo (por ejemplo, arriba, T3 debe realizarse antes que T5, que debe realizarse antes de T3)
Problema: la detección de ciclos es NP completa (no determinista, polinómica, difícil)
Observó:
Propiedad de aislamiento = Las transacciones deben ejecutarse AS si estuvieran solas en la base de datos. La serialización garantiza que el resultado de una ejecución intercalada sea el mismo que el de una ejecución en serie. Pero la serialización no es una condición suficiente para garantizar que las transacciones se ejecuten de forma aislada.
Ejemplo de ejecución serializable no aislada (ABORTO en cascada):
T1 < T2 < … < Tn
P5. Mecanismo de aislamiento más utilizado: bloquear y desbloquear
Protocolo de bloqueo más utilizado: Bloqueo bifásico
Fase 1: se adquieren todos los bloqueos, no se realiza ningún desbloqueo
Fase 2: se completan todos los desbloqueos, no se adquieren bloqueos
Propiedad: Garantiza la serialización de la ejecución de un cronograma legal (es decir, lock1(X) no puede ir seguido de lock2(X) sino de unlock1(X))
Cuatro tipos de bloqueos: compartido VS exclusivo/corto VS largo (consulte la matriz de compatibilidad indicada)
Dos tipos de operación: Lectura y Escritura.
Diferentes grados de aislamiento:
* Grado 0 (Leer no comprometido):
Instalación de bloqueos exclusivos de escritura corta.
-> Lee incluso objetos modificados por transacciones que no se han comprometido
* Grado 1 (Lectura comprometida):
Instalación de bloqueos exclusivos de escritura larga.
Establecer bloqueos de lectura compartidos breves
-> Solo leer objetos modificados por transacciones confirmadas
* Grado 2 (Lectura Repetible):
Grado 1 + Instalación de bloqueos de lectura compartidos largos
-> Lectura repetible
* Grado 3 (Serializable):
Nivel 2 + Elimina fantasmas
El bloqueo “detecta” el problema de serialización: puntos muertos
Varias formas de gestionar los puntos muertos
* TimeOut: elimina las transacciones que tardan más de x segundos en ejecutarse
* Detección: Gráfico de espera
T5 <-> T3
<- T1
<- T4
Gráfico construido a medida que avanza la ejecución
Revertir cualquier transacción que pueda causar que aparezca un ciclo en el gráfico de espera
Ejemplo: 1. T5 -> T3 2. T1 -> T5 -> T3 3. T1 -> T5 <-> T3 ==> Reversión de T3
Problema: La detección del ciclo siempre es NP completa; puede ser largo si el gráfico es ancho
* Prevención: Marcas de tiempo
Da prioridad a las transacciones antiguas para evitar que se produzcan bloqueos.
Marca de tiempo asociada a cada transacción.
T1 quiere adquirir un bloqueo sobre un objeto bloqueado por T2.
Solución 1: esperar y morir
si T1 es mayor que T2, T1 espera
de lo contrario, T1 Rollback (y se reinicia con la misma marca de tiempo)
Solución 2: Wound-Wait (espera transacciones antiguas)
si T1 es anterior a T2, T2 debe abandonar el bloqueo y revertir
de lo contrario, T1 espera
-> Nunca interbloquear: T1 acabará siendo el más antiguo y por tanto se ejecutará con prioridad.
Esperar-morir VS Herir-esperar:
Candados adquiridos al inicio de una transacción -> Es más probable que las transacciones antiguas tengan sus candados antes que las nuevas
-> Espera de herida: causa poca reversión porque ver suposición
Esperar-morir provoca una gran cantidad de retroceso porque se supone que es así; pero cada vez al comienzo de transacciones jóvenes
Sellos:
T2:1 T6:2T5:3T3:4T1:5T4:6
Espera-muere:
Sellos:
T2:1 T6:2T5:3T3:4T1:5T4:6
Espera de herida:
P5.b.
Bloqueo altruista: una transacción libera sus bloqueos cuando ya no los necesita.
+: Efectivo
– : (i) Problema de lectura sucia; (ii) Ejecución a priori no 2PL, por lo tanto a priori no serializable.
P6.
Sistema de estampado: Asigna un sello a cada transacción (generalmente la marca de tiempo de su creación), impide el acceso a objetos contrarios al orden de los sellos -> Prioridad a transacciones jóvenes. Las transacciones que llegan tarde se revierten y se reinician con una nueva marca de tiempo. Parte de la familia de protocolos optimistas, es decir, un método eficaz cuando hay pocos conflictos debido a pocos gastos generales, pero potencialmente mucha reversión.
Dos reglas:
Leer demasiado tarde: una transacción solo puede leer datos si es más reciente que el último escritor
Escribir demasiado tarde: una transacción solo puede escribir datos si es más joven que el último lector y escritor.
Algoritmo básico:
– Colocar sello en cada transacción.
– Cada objeto conserva el sello del último lector así como el del último escritor
– Cuando Ti quiere leer el objeto O:
Si el sello < O.LastWriter: Leer demasiado tarde -> Ti ROLLBACK luego se reinicia con un nuevo sello
De lo contrario está bien
– Cuando Ti quiere escribir el objeto O:
Si Ti.stamp < O.LastReader || Ti.stamp < O.LastWriter: Escribir demasiado tarde -> Ti ROLLBACK luego se reinicia con un nuevo sello
De lo contrario está bien
Ejemplo:
Sellos:
T2: 1-8 T6: 2T5: 3-7T3: 4T1: 5T4: 6
Objetos:
A (L: ; E: 1) A (L: ; E: 4)
segundo (l: 1; mi: )
C (L: 5; E: 3-6) C (L: 5; E: 6)
D (L: 2; E: 4)
Los gráficos de precedencia de ejecuciones de estampado nunca tienen un ciclo.
Prueba por absurdo:
Considere el gráfico de precedencia cíclica de una ejecución obtenida mediante estampación:
T1 -> … -> Ti <-> Tj -> … -> Tn => Ti < Tj < Ti
<=> yo < j < yo
Contradicción
P8.
Estampar bien cuando hay pocos conflictos (sin esperas); malo cuando hay muchos conflictos (muchas reversiones).
Buen bloqueo cuando hay muchos conflictos (menos retroceso que estampado); malo cuando hay pocos conflictos (esperas innecesarias, gastos generales de administración de bloqueos).
Los sistemas comerciales intentan combinar las ventajas de ambos: estampado multiversión (una variación del estampado único discutido anteriormente) para transacciones de solo lectura y bloqueo 2PL para transacciones de lectura/escritura. (ver pág. 978 de “DB Systems: el libro completo” de Widom y Ullmann)
ES 
FR 
EN