Control de Concurrencia
Carlos A. Olarte ([email protected])BDII
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Contenido
1 Introduccion
2 Protocolos basados en Bloqueos
3 Protocolos basados en Grafos
4 Protocolos de Marcas temporales
5 Esquemas Multiversion
6 Granularidad Multiple
7 Interbloqueos
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Control de Concurrencia
Mecanismo para asegurar la propiedad de aislamiento
Protocolo de Bloqueo: Reglas acerca de como se debenacceder los recursos para generar planificaciones secuenciales(vistas o conflictos)
Que se debe tener en cuenta (prevenir)?
Inanicion: Cuando una transaccion debe esperar por siempre(∞)Interbloqueos: (dead locks)Perder la concurrencia (Todo secuencial)Largas esperas
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Protocolos basados en Bloqueos
Modos de Bloqueo: Compartido o Exclusivo
Conflicto: Modos de bloqueo incompatibles
Una planificacion es legal para un protocolo de bloqueo sidicha planificacion es posible para un conjunto detransacciones que siguen las reglas del protocolo de bloqueo
Matriz de Compatibilidad: Indica cuando dos modos debloqueo son compatibles.
X C
X F F
C F V
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Protocolo de Bloqueo de 2 Fases
Consta de una fase de Crecimiento en la que se adquierenbloqueos (no se pueden liberar) y una fase de Decrecimientocuando se liberan bloqueos (y no se pueden obtener)
Punto de Bloqueo donde se obtiene el ultimo bloqueo
No asegura la aparicion de interbloqueos ni de retrocesos encascada
Las transacciones se pueden secuenciar a partir de su punto debloqueo generando planificaciones SECC (demostrar)
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Continuacion
Variantes del PB. 2 Fases
Protocolo Estricto de 2 fases: Todos los bloqueos en modoexclusivo deben mantenerse hasta el final de la transaccion
Protocolo Riguroso de 2 fases: Todos los bloqueos debenmantenerse hasta el compromiso de la transaccion
Protocolo Refinado de 2 fases: Dos nuevas operaciones:
Subir: Pasar de modo C a modo X (solo en fase decrecimiento)Bajar: Pasar de modo X a modo C (solo en fase dedecrecimiento)
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Protocolo del Arbol
Requiere un orden parcial → del conjunto de elementos de datos(di → dj si para acceder a di y a dj se requiere primero acceder adi .Todos los bloqueos se realizan en modo X . Las reglas delprotocolo:
El primer bloqueo puede ser sobre cualquier elemento
Ti puede bloquear un elemento Q solamente si posee unbloqueo sobre el padre de Q
Se pueden desbloquear elemento en cualquier orden
Ti no puede bloquear elementos que previamente hadesbloqueado
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Continuacion
Ventajas: Previene los interbloqueos y se permitendesbloquear recursos antes del compromiso (aumento deconcurrencia)
Desventajas: Tener que bloquear el padre. Establecer el ordenparcial (→) no siempre es posible
Existiran planificaciones que sean legales bajo el P2F y no bajo elP.Arbol? y viceversa?
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Protocolo de Marcas Temporales
Cada transaccion cuenta con una marca temporal M(Ti )
Las planificaciones generadas deben ser equivalentes alordenamiento secuencial (cronologico) de las marcas
Sobre cada recurso Q se cuenta con MTE (Q) (ultimatransaccion –MT– que escribio Q) y MTL(Q) (ultimatransaccion –MT– que leyo Q)
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Continuacion
Protocolo de ordenacion
Para operaciones de lectura en Ti
1 Si MT (Ti ) < MTE (Q) se rechaza Ti puesto que se estaleyendo un valor sobre-escrito.
2 Si MT (Ti ) ≥ MTE (Q) se acepta la operacion y se actualizaMTL(Q) por MT (Ti ).
Para operaciones de escritura de Ti
1 Si MT (Ti ) < MTL(Q) se rechaza la escritura puesto que elvalor producido no fue el leido
2 Si MT (Ti ) < MTE (Q) se rechaza puesto que se estaescribiendo algo obsoleto
3 Se acepta la escritura y se actualiza MTE (Q) por MT (Ti )
Al retroceder la transaccion se le asigna un nuevo MT (Ti ) y vuelvea empezar (no hay interbloqueos)
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Regla de Escritura de Thomas
Se modifica la segunda regla de escritura del protocolo deordenacion de M.T para ignorar la escritura
Asegura secuencialidad en cuanto a vistas
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Esquemas Multiversion
Cada escritura de Q genera una nueva version de Q
Se debe asegurar que las lecturas seleccionen la version de Qapropiada
Cada version de Q (Qk) se le asigna: contenido,MTE (Qk) = MT (Ti ) y MTL(Qk) (ultima transaccion queleyo la version Qk).
Se mantiene la secuencialidad mediante las siguientes reglas:
1 Si Ti ejecuta L(Q) el valor retornado es el valor de Qk
2 Si Ti ejecuta E (Q) :1 Si MT (Ti ) < MTL(Qk) se retrocede Ti
2 Si MT (Ti ) = MTE (Qk) se sobreescribe Qk
3 En otro caso aparece una nueva version de Q
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Continuacion
Ventaja: Asegura que las lecturas nunca fallan
Desventaja: Conflictos resueltos con retrocesos
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Granularidad Multiple
Jerarquıa de Granularidad
Matriz de Compatibilidad
IC IX C IXC XIC V V V V FIX V V F F FC V F V F F
IXC V F F F FX F F F F F
Si se bloquea el padre (Bloqueo Explicito) se bloquean susdescendientes (Bloqueos Implıcitos)
Aparecen tres nuevos modos: Intencional Exclusivo (IX ), I.Compartido (IC ) e I. Compartido-Exclusivo(ICX )
Los bloqueos se realizan de arriba hacia abajo y losdesbloqueos en orden inverso
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Reglas del Protocolo
Ti puede bloquear Q si:
1 Se observa la matriz de compatibilidad
2 La raız se bloquea en cualquier modo
3 Ti puede bloquear Q en modo C o IC solo si Ti estaactualmente bloqueando el padre de Q en modo IX o IC
4 Ti puede bloquear Q en modo X ,ICX o IX solo si Ti estaactualmente bloqueando el padre de Q en modo IX o ICX
5 Ti debe ser de dos fases
6 Ti no puede desbloquear Q si algun descendiente de Q estaactualmente bloqueado
Por que son necesarios los bloqueos intencionales?
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Interbloqueos (Dead Locks)
Un sistema de encuentra en un Interbloqueo cuando existe unconjunto de transacciones {T1,T2, ...,Tn} tal que para todoi ∈ [1..n − 1], Ti espera por Ti+1 y Tn espera por T1.
Como se tratan los interbloqueos?
Esquemas Preventivos: Nunca ocurre el interbloqueoEsquemas de Deteccion y Recuperacion
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Esquemas Preventivos
Por lımite de tiempo: Despues de cierto tiempo se retrocedela transaccion (facil de implementar aunque no siempre queun recurso se encuentre ocupado por mucho tiempo implica laexistencia de un interbloqueo)
El protocolo de bloqueo asegura la no aparicion puesto queexige un orden para adquirir bloqueos como en el protocolodel arbol
Expropiar y retroceder:
Esperar Morir: Si Ti solicita un recurso ocupado por Tj esperasolamente si MT (Ti ) < MT (Tj) de lo contrario Ti seretrocede (Muere). En este caso no hay expropiacionHerir-Esperar: Como el caso anterior con la diferencia que esTj quien se retrocede
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Deteccion y Recuperacion
Se requiere un esquema que:
Mantenga la informacion necesaria los bloqueos: Construir ungrafo de espera (〈ti , tj〉 ∈ A si ti espera por un recurso de tj)
Ejecute un algoritmo de deteccion: En este caso deteccion deciclos en el grafo de espera
Ejecute un mecanismo de recuperacion en caso de sernecesario:
Seleccionar una transaccion (preferiblemente la de menorcosto)Retroceder de la transaccion escogida
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Operaciones de Insercion y Eliminacion
Para eliminar un recurso se presentan los conflictos similares quepara una escritura. Por tanto:
En el protocolo de 2 fases, se debe solicitar un bloqueo enmodo exclusivo sobre Q antes de eliminarlo
En el protocolo de marcas temporales se adicionan reglassimilares a las reglas de escritura
Fenomeno Fantasma: Suponga que Ti efectua select count(*)from x y Tj insert into x.... Si Ti no utiliza la nueva tupla, laplanificacion secuencial que se debe obtener es 〈ti , tj〉. Como lasdos transacciones estan en conflicto por una tupla que no tienen encomun este fenomeno se conoce como fenomeno fantasma
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Algunos Ejemplos Practicos
Commit / Rollback
Bloqueos (Esperas hasta comprometer o retroceder)
Versiones (lecturas antes de comprometer)
Deteccion de Interbloqueos
Granularidad a nivel de registro (no a nivel de columna)
SELECT ... FOR UPDATE
Fenomeno Fantasma
Cambios del nivel de Consistencia
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia
Niveles Debiles de Consistencia
La norma SQL-92 define niveles de consistencia que no siempregarantizan secuencialidad:
Secuenciable
Lectura Repetible: Solo se pueden leer registroscomprometidos. Entre dos lecturas del mismo recurso,ninguna otra transaccion puede modificar dicho recurso
Compromiso de Lectura: Solo se puede leer registroscomprometidos pero no se asegura la lectura repetible
Sin compromiso de Lectura: Se permite leer registros nocomprometidos
Carlos A. Olarte ([email protected]) BDII Control de Concurrencia