concurrencia
TRANSCRIPT
TÉCNICAS DE CONTROL DE CONCURRENCIA
EJECUCIONES CONCURRENTES Se permite ejecutar concurrentemente varias transacciones en el
sistema. Las ventajas son:• aumento de la utilización del procesador y del disco, conduciendo
a mejorar la productividad de la transacción una transacción puede estar utilizando la CPU, mientras otras está leyendo desde o escribiendo a disco
• reducción del tiempo medio de respuesta de la transacciones: las transacciones pequeñas no tienen necesidad de esperar detrás de las grandes.
Esquemas de control de concurrencia - mecanismos para conseguir aislamiento, es decir, para controlar la interacción entre la transacciones concurrentes a la hora de impedir que destruyan la consistencia de la base de datos
Principales situaciones en las que una transacción (correcta individualmente) puede producir un resultado incorrecto al interferir con otra transacción.
-Problema de la modificación perdida-Problema de la actualización temporal-Problema del resumen incorrecto.
Ejecuciones concurrentes (cont.)Ejecuciones concurrentes (cont.)
La actualización perdida– T1 y T2 que acceden a los mismos datos, tienen sus operaciones intercaladas de modo que hacen incorrecto el valor de algún dato
El problema de la modificación temporal.También se conoce como problema de la lectura sucia. Esta situación ocurre cuando una transacción modifica un ítem y a continuación la transacción falla por alguna razón. El ítem modificado es accedido por otra transacción antes de que el cambio sea desecho y el ítem vuelvaa su valor original-
Técn
icas d
e c
on
trol d
e c
on
cu
rren
cia • El resumen incorrecto
• Otra transacción T3 calcula una función agregada de resumen sobre varios registros (suma las plazas reservadas para todos los vuelos), mientras otras, como T1, actualizan dichos registros: puede que T3 considere unos registros antes de ser actualizados y otros después
Problemas potenciales provocados por la Problemas potenciales provocados por la concurrenciaconcurrencia
T1
leer_elemento(X);X:= X-N;escribir_elemento(X);
leer_elemento(Y);Y:=Y+N;escribir_elemento(Y);
T3suma:=0;leer_elemento(A);suma:= suma+A;………
leer_elemento(X);suma:= suma+X;leer_elemento(Y);suma:= suma+Y;………
T3 lee X después de restar N, pero lee Y antes de sumar N, así que el resultado es un resumen incorrecto (discrepancia de N)
PLANIFICACIONES• Planificaciones – secuencias que indican el orden
cronológico en el que se ejecutan las instrucciones de las transacciones concurrentes• una planificación para un conjunto de transacciones debe
constar de todas las instrucciones de estas transacciones• debe preservar el orden en el que aparecen las
instrucciones en cada transacción individual.
SERIABILIDAD DE LOS PLANES
Suposición básica – Cada transacción preserva la consistencia de la base de datos.
Así, la ejecución secuencial de un conjunto de transacciones preserva la consistencia de la base de datos.
Una (posiblemente concurrente) planificación es serializable si es equivalente a una planificación secuencial. Diferentes formas de equivalencia de planificaciones dan lugar a los conceptos de:1 Equivalencia en cuanto a conflictos2 Equivalencia en cuanto a vistas
SERIABILIDAD EN CUANTO A CONFLICTOS (CONT.)
• La planificación siguiente se puede transformar en la planificación en serie, una planificación en serie donde T2 sigue a T1, mediante conjuntos de intercambios de instrucciones no conflictivas. Por lo tanto, la planificación es serializable en cuanto a conflictos.
Dos operaciones de un plan P están en conflicto si– pertenecen a diferentes transacciones,– tienen acceso al mismo elemento X,– y al menos una de ellas es ESCRIBIR_ELEMENTO(X)
Técn
icas d
e c
on
trol d
e c
on
cu
rren
cia
EL ALGORITMO SIGUIENTE VERIFICA LA SERIALIZABILIDAD DE UN PLAN S
• (1) Para cada transacción Ti participante en el plan S crear un nodo etiquetado Ti en el grafo;
• (2) Para cada caso en S donde Tj ejecuta un Leer_ítem(X) después de que Ti ejecuta un Escribir_ítem(X) crear un arco (Ti → Tj) en el grafo;
• (3) Para cada caso en S donde Tj ejecuta un Escribir_ítem(X) después de que Ti ejecuta un Leer_ítem(X) crear un arco (Ti → Tj) en el grafo;
• (4) Para cada caso en S donde Tj ejecuta un Escribir_ítem(X) después de que Ti ejecuta un Escribir_ítem(X) crear un arco (Ti → Tj) en el grafo;
• (5) El plan S es serializable si y solo si el grafo de precedencias no tiene ciclos;
Si hay un ciclo en el grafo, P no es seriable por conflictos
T1
Lee(x)
Esc(x)
Lee(y)
Esc(y)
T2
Lee(z)
Lee(y)
Esc(y)
Lee(x)
Esc(x)
T3
Lee(y)
Lee(z)
Esc(y)
Lee(z)
SERIABILIDAD EN CUANTO A CONFLICTOS
• La seriabilidad en cuanto a conflictos es demasiado estricta
• Hay planificaciones no serializables respecto a conflictos y que no producen problemas de consistencia
T1 T2
Leer (A)
A=A-50
Escribir (A)
Leer (B)
B=B-10
Escribir (B)
Leer (B)
B=B+50
Escribir (B)
Leer (A)
A=A+10
Escribir (A)
CONTROL DE CONCURRENCIA OPTIMISTA
Se trabaja con la presunción de que los conflictos entre los usuarios son improbables (aunque no imposibles)y se permite a las transacciones ejecutarse sin necesidad de bloquear recursos.
Pesimista: Se bloquean los recursos cuando se requiera
acceder a ellos durante todo el tiempo que dure la transacción.
BLOQUEOS BINARIOS
• Un bloqueo binario puede tener dos estados (o valores): bloqueado (valor=1) y no bloqueado ó
• desbloqueado (valor=0). Un bloqueo diferente se asocia a cada ítem X de la BD. Si el ítem X
• está bloqueado, dicho ítem no puede ser accedido por operaciones de la BD. Si está
• desbloqueado, entonces puede ser accedido. El valor del bloqueo del ítem X lo representaremos
• por Lock(X).
BLOQUEAR ELEMENTO
DESBLOQUEAR ELEMENTO
UTILIZANDO EL BLOQUEO BINARIO, CADA TRANSACCIÓN DEBE OBEDECER LAS
SIGUIENTES REGLAS:• 1. Una transacción T debe realizar una operación
Bloquear_ítem(X) antes que un Leer_Ítem(X) o Escribir_ítem(X).
• 2. Una transacción T debe realizar una operación Desbloquear_ítem(X) después de que todos los Leer_ítem(X) y Escribir_ítem(X) en T se han completado.
• 3. Una transacción T no realizará un Bloquear_ítem(X) si ya posee el bloqueo de X.
• 4. Una transacción T no realizará un Desbloquear_ítem(X) salvo que posea el bloquea de
• X.
BLOQUEOS DE MODO MÚLTIPLE
• El bloqueo binario es muy restrictivo, ya que sería mejor permitir que varias transacciones puedan acceder al mismo ítem X si todas ellas lo requieren sólo con propósitos de lectura.
• SI una transacción pretende escribir un ítem X, entonces debería ser accedido de forma exclusiva.
• Para poder hacer esto, se utilizará un bloqueo de modo múltiple. En este caso hay tres operaciones de bloqueo diferentes:
• Bloquear_para_lectura(X), Bloquear_para_escritura(X) y• Desbloquear_ítem(X).
• Un bloqueo asociado con el ítem X, Lock(X), tendrá tres estados posibles: 'bloqueado para lectura', 'bloqueado para escritura', ó 'desbloqueado'.
Bloqueos
Transacciones
Base de datos
Bloqueo Exclusivo
DB
Transacción ATransacción A
Transacción BTransacción B
Bloqueo Exclusivo o de Escritura
Tupla
Si la transacción A pone un bloqueo exclusivo (X) sobre una tupla, entonces se rechazará una petición de cualquier otra transacción B para un bloqueo de cualquier tipo sobre la tupia
Si la transacción A pone un bloqueo exclusivo (X) sobre una tupla, entonces se rechazará una petición de cualquier otra transacción B para un bloqueo de cualquier tipo sobre la tupia
Bloqueos
Transacciones Base de datos
Tupla
Bloqueo Compartido
DB
Transacción ATransacción A
Transacción BTransacción B
Bloqueo Compartido o de Lectura
Transacción CTransacción CBloqueo
Exclusivo
Si la transacción A pone un bloqueo compartido (S) sobre la tupla entonces:Se rechazará una petición de cualquier otra transacción B para un bloqueo Exclusivo sobre
la tupla.Se otorgará una petición de cualquier otra transacción B para un bloqueo S sobre la tupla
(esto es, ahora también B tendrá un bloqueo S sobre la tupla
Si la transacción A pone un bloqueo compartido (S) sobre la tupla entonces:Se rechazará una petición de cualquier otra transacción B para un bloqueo Exclusivo sobre
la tupla.Se otorgará una petición de cualquier otra transacción B para un bloqueo S sobre la tupla
(esto es, ahora también B tendrá un bloqueo S sobre la tupla
BLOQUEO MORTAL
• El bloqueo mortal (deadlock) o interbloqueo se produce cuando un par de transacciones están
• cada una esperando a que la otra libere un ítem.
PROBLEMAS DE LOS PROTOCOLOS BASADOS EN BLOQUEOS
En la mayoría de los protocolos de bloqueo se puede producir un interbloqueo potencial. En general, los interbloqueos son un mal necesario y manejable.
También es posible que se produzca la inanición si el gestor de control de concurrencia se ha diseñado defectuosamente. Por ejemplo:• Puede que una transacción esté esperando un bloqueo exclusivo
sobre un elemento determinado mientras que una secuencia de transacciones diferentes solicitan y obtienen la autorización de bloqueo compartido sobre el mismo elemento.
• La misma transacción retrocede repetidamente debido a los interbloqueos.
El gestor de control de concurrencia se puede diseñar para impedir que se produzca la inanición.
EL PROTOCOLO DE BLOQUEO DE DOS FASES
Éste es un protocolo que asegura planificaciones secuenciables en cuanto a conflictos.
Fase 1: Fase de crecimiento• las transacciones pueden conseguir bloqueos • las transacciones no pueden liberar bloqueos
Fase 2: Fase de decrecimiento• las transacciones pueden liberar bloqueos • las transacciones no pueden conseguir bloqueos
El protocolo asegura la secuencialidad. Se puede probar que las transacciones se pueden secuenciar en el orden de sus puntos de bloqueo (es decir, el punto de la planificación en el cual la transacción obtiene su bloqueo final).
TRANSACCIONES QUE SIGUEN EL PROTOCOLO B2F
EL PROTOCOLO DE BLOQUEO DE DOS FASES
El protocolo de bloqueo de dos fases NO asegura la ausencia de interbloqueos.
El retroceso en cascada puede ocurrir en el bloqueo de dos fases. Se pueden evitar por medio de una modificación del protocolo denominado protocolo de bloqueo estricto de dos fases. En él una transacción debe mantener todos sus bloqueos exclusivos hasta que se complete o aborte.
El protocolo de bloqueo riguroso de dos fases es incluso más estricto: en él todos los bloqueos se mantienen hasta que se complete o aborte. En este protocolo las transacciones se pueden secuenciar en el orden en que se comprometen.
PROTOCOLOS BASADOS EN LAS MARCAS TEMPORALES
• Cada transacción genera una marca temporal cuando se introduce en el sistema. Si a la transacción Ti se le ha asignado la marca
temporal MT(Ti) y una nueva transacción Tj entra en el sistema,
entonces MT(Ti) < MT(Tj).
• El protocolo maneja la ejecución concurrente de modo que las marcas temporales de las transacciones determinan el orden de secuencia.
• Para asegurar dicho comportamiento, el protocolo mantiene por cada elemento de datos Q dos valores de marca temporal:• marca_temporal-E(Q) denota la mayor marca temporal de todas las
transacciones que ejecutan con éxito escribir(Q).
• marca_temporal-L(Q) denota la mayor marca temporal de todas las transacciones que ejecutan con éxito leer(Q).
PROTOCOLOS BASADOS EN LAS MARCAS TEMPORALES (CONT.)
El protocolo de ordenación por marcas temporales asegura que todas las operaciones leer y escribir conflictivas se ejecutan en el orden de las marcas temporales
Se asegura la seriabilidad en cuanto a conflictos Supóngase que la transacción Ti ejecuta leer(Q) 1. Si MT(Ti) marca_temporal-E(Q) entonces Ti necesita leer
un valor de Q que ya se ha sobrescrito. Por tanto se rechaza la operación leer y Ti se retrocede.
2. Si MT(Ti) marca_temporal-E(Q) entonces la operación leer se ejecuta, y marca_temporal-L(Q) se fija al máximo de marca_temporal-L(Q) y MT(Ti).
PROTOCOLOS BASADOS EN LAS MARCAS TEMPORALES (CONT.)
• Supóngase que la transacción Ti ejecuta escribir(Q).
• Si MT(Ti) < marca_temporal-L(Q) entonces el valor de Q que produce Ti se necesita previamente y el sistema asume que dicho valor no se puede producir nunca. Por tanto, se rechaza la operación escribir y Ti se retrocede.
• Si MT(Ti) < marca_temporal-E(Q) entonces Ti está intentando escribir un valor de Q obsoleto. Por tanto, se rechaza la operación escribir y Ti se retrocede.
• En otro caso se ejecuta la operación escribir y MT(Ti) se asigna a marca_temporal-E(Q).