• Author / Uploaded
• John Velasquez Villanueva

Citation preview

PROBLEMAS DE CONTROL DE CONCURRENCIA 1. El problema de la actualización perdida. Cuando dos transacciones que tienen acceso a los mismos elementos de la base de datos tienen sus operaciones intercaladas de modo que hacen incorrecto el valor de algún elemento. Esto ocurre si una transacción sobrescribe el valor de un elemento, que ya ha sido modificado previamente por otra transacción que aún está en ejecución, ocasionando la pérdida de la modificación previa. Ej: Valor inicial de X es 10. Valor final de X es 20 y no 30

Transacción A Leer_elemento(X) X:=X+10

Tiempo T1 T2

Escribir_elemento(X)

T3

T4

Transacción B

Leer_elemento(X) X:=X+10 Escribir_elemento(X)

PROBLEMAS DE CONTROL DE CONCURRENCIA 2. El problema de la actualización temporal (dependencia no comprometida). Esto ocurre cuando una transacción actualiza un elemento de la base de datos y luego la transacción falla. Otra transacción tiene acceso al elemento actualizado antes de que se restaure su valor original. Ej: Valor inicial de X es 10 Transacción A Tiempo Transacción B T1 Escribir_elemento(X) (X se modifica a 20) Leer_elemento(X)

T2

T3

Abortar (X se restaura a 10) Observación: La transacción A lee una modificación no comprometida (lectura sucia) en el tiempo T2, que se deshace en el tiempo T3. Como resultado, la transacción A puede producir resultados incorrectos.

PROBLEMAS DE CONTROL DE CONCURRENCIA 2. El problema de la actualización temporal (dependencia no comprometida). Ej: Valor inicial de X es 10 Observación: La transacción A actualiza una modificación no comprometida en el tiempo T2, y pierde esa actualización en el tiempo T3 (otra versión de la actualización perdida)

eTransacción A

Tiempo T1

Transacción B Escribir_elemento(X) (X se modifica a 20) esa actualización en el tiempo T3. Escribir_elemento(X) T2 (X se modifica a 30) T3 Abortar (X se restaura a 10)

PROBLEMAS DE CONTROL DE CONCURRENCIA 3. El problema del resumen incorrecto (análisis inconsistente). Si una transacción está calculando una función agregada de resumen sobre varios registros mientras otras transacciones están actualizando algunos de ellos, puede ser que la función agregada calcule algunos valores antes de que se actualicen y otros después de actualizarse.

3. El problema del resumen incorrecto (análisis inconsistente). Ej: Sean los valores iniciales de A:=40, B:=50 y C:=30 Transacción A Leer_elemento(A) Suma:=Suma+A Leer_elemento(B) Suma:=Suma+B

Tiempo T1

Transacción B

T2 T3 T4 T5

Leer_elemento(C) C:=C-10 Escribir_elemento(C) Leer_elemento(A) A:=A+10 Escribir_elemento(A) Confirmar

T6 T7 Leer_elemento(C) T8 Suma:=Suma+C (Observación: Suma es 110, no 120)

PROBLEMAS DE CONTROL DE CONCURRENCIA 4. Lectura repetible. Ocurre cuando una transacción lee un elemento dos veces y otra transacción modifica el elemento entre las dos lecturas. Así la primera transacción recibe diferentes valores en sus dos lecturas del mismo elemento Ej: si el valor inicial de X es 10 Transacción A Tiempo Transacción B Leer_elemento(X) T1 T2 Leer_elemento(X)

T3

Escribir_elemento(X) (X se modifica a 20)

TÉCNICAS DE CONTROL DE CONCURRENCIA BLOQUEO La noción básica del bloqueo consiste en que cuando una transacción requiere la seguridad de que algún objeto (casi siempre un registro de la base de datos) no cambiará de alguna manera no predecible, adquiere un bloqueo sobre ese objeto. El efecto del bloqueo es “bloquear el acceso de otras transacciones” al objeto, y en particular evitar que lo modifiquen Funcionamiento del bloqueo: 1. Primero, suponemos la existencia de dos tipos de bloqueo: Bloqueos exclusivos (bloqueos X) y bloqueos compartidos (bloqueos S). 2. Si la transacción A tiene bloqueo exclusivo (X) sobre el registro R, una solicitud por parte de la transacción B de cualquier tipo de bloqueo sobre R hará que B entre en un estado de espera. B esperará hasta que se libere el bloqueo de A.

TÉCNICAS DE CONTROL DE CONCURRENCIA Funcionamiento del bloqueo: 3. Si una transacción A tiene un bloqueo compartido (S) sobre el registro R: a) una solicitud por parte de la transacción B de bloqueo X sobre R hará que B entre en un estado de espera (B esperará hasta que se libere el bloqueo de A. b) una solicitud por parte de la transacción B de un bloqueo S sobre R será concedida (es decir, B tendrá también ahora un bloqueo S sobre R). Las tres características anteriores pueden resumirse en una matriz de compatibilidad de tipos de bloqueo X

S

-

X

N

N

S

Guión = no hay bloqueo

S

N

S

S

N indica un conflicto

-

S

S

S

S indica compatibilidad

TÉCNICAS DE CONTROL DE CONCURRENCIA Funcionamiento del bloqueo: 4. Las solicitudes de bloqueo sobre registros por parte de las transacciones son implícitas. Cuando se quiere leer un registro, se solicita implícitamente un bloqueo compartido (S) sobre el registro. Cuando se quiere escribir un registro, se solicita implícitamente un bloqueo exclusivo (X) sobre el registro. Se permite la promoción de bloqueo S a bloqueo X dentro de una misma transacción. 5. Los bloqueos X se mantienen hasta el término exitoso o no de la transacción. Lo normal es que los bloqueos S se mantengan también hasta ese momento. Así, el bloqueo garantiza planes seriables y estrictos. DESVENTAJAS: Bloqueo mutuo, Limitación del grado de concurrencia, Espera indefinida (si una transacción no puede continuar durante un período indeterminado, mientras otras transacciones continúan con normalidad. como sucedería si el esquema de espera es injusto y confiera a algunas transacciones mayor prioridad que otras), Inanición debido a los algoritmos que resuelven el bloqueo mortal.

Solución al problema de la actualización perdida utilizando la técnica del bloqueo Transacción A Leer_elemento(X)

Tiempo

Transacción B

(X:=10)

T1

(Adquiere bloqueo S) X:=X+10 T2

Leer_elemento(X)

(Adquiere bloqueo S) X:=X+10 Escribir_elemento(X)

T3

Espera T4

Escribir_elemento(X) Espera (Bloqueo Mutuo)

Solución al problema de la actualización temporal utilizando la técnica del bloqueo Transacción A

Tiempo T1

Leer_elemento(X) Espera

T2

T3

Continuar: Leer_elemento(X) (Adquiere bloqueo S)

Transacción B (X:=10) Escribir_elemento(X) (Adquiere bloqueo X) (X se modifica a 20)

T4

Abortar (X se restaura a 10) (libera el bloqueo X)

Solución al problema de la actualización temporal utilizando la técnica del bloqueo Transacción A

Escribir_elemento(X) Espera

Tiempo T1

Transacción B (X:=10) Escribir_elemento(X) (Adquiere bloqueo X) (X se modifica a 20)

T2

T3

Continuar: Escribir_elemento(X) T4 (Adquiere bloqueo X)

Abortar (X se restaura a 10) (libera el bloqueo X)

Solución al problema del resumen incorrecto utilizando el bloqueo Transacción A Leer_elemento(A) (Adquiere bloqueo S sobre A) Suma:=Suma+A Leer_elemento(B) (Adquiere bloqueo S sobre B) Suma:=Suma+B

Tiempo T1

T2

T3

T4 T5

T6 Leer_elemento(C) Espera

Transacción B (A:=40, B:=50,C:=30)

T7 (Bloqueo Mutuo)

Leer_elemento(C) (Adquiere bloqueo S sobre C) C:=C-10 Escribir_elemento(C) (Adquiere bloqueoX sobre C (se promueve)) Leer_elemento(A) (Adquiere bloqueo S sobre A) A:=A+10 Escribir_elemento(A) Espera

BLOQUEO MUTUO (DEADLOCK, ABRAZO MORTAL) Es una situación en la cual dos o más transacciones están en un estado de espera simultáneo, y cada una espera la liberación de un bloqueo por parte de otra para poder continuar. En la práctica los bloqueos mutuos casi nunca implican más de dos transacciones. PREVENCIÓN DEL BLOQUEO MUTUO Algunas esquemas que evitan el bloqueo mutuo aplican el concepto de marca de tiempo de la transacción MT(T). Las marcas de tiempo se ordenan con base en el orden en que se inician las transacciones (la transacción más antigua tiene la más alta prioridad). Dos esquemas son esperar-morir y herir-esperar. Supongamos que la transacción Ti solicita un bloqueo sobre el elemento X, pero X está bloqueado por otra transacción Tj , con un bloqueo en conflicto. Esperar-morir (Wait-die): Si MT(Ti) < MT(Tj) (Ti es más antigua que Tj) entonces Ti espera; de lo contrario se aborta Ti y se le reinicia posteriormente con la misma marca de tiempo.

BLOQUEO MUTUO (DEADLOCK, ABRAZO MORTAL, BLOQUEO MORTAL) PREVENCIÓN DEL BLOQUEO MUTUO Herir-esperar (Wound-wait): Si MT(Ti) < MT(Tj) (Ti es más antigua que Tj) entonces se aborta Tj (Ti hiere a Tj) y se le reinicia posteriormente con la misma marca de tiempo; de lo contrario Ti espera. Ambos esquemas hacen que aborte una transacción más reciente que podrían intervenir en un bloqueo mutuo, a pesar de que tal vez nunca provoquen un bloqueo mutuo. Estas dos técnicas evitan el bloqueo mutuo. El Protocolo de bloqueo de dos fases conservador también puede prevenir bloqueos mutuos, requiere que toda transacción bloquee por adelantado todos los elementos que vaya a necesitar, si no es posible obtener algunos de los elementos, no se bloqueará ninguno de ellos, y la transacción tendrá que esperar hasta que todos los bloqueos se hagan disponibles. Limita la concurrencia, la transacción adquiere todos los bloqueos desde el inicio.

BLOQUEO MUTUO (DEADLOCK, ABRAZO MORTAL, BLOQUEO MORTAL) DETECCIÓN DE BLOQUEO MUTUO La detección de un bloqueo muto implica la detección de un ciclo en la GRÁFICA DE ESPERA, donde se indica “quién está esperando a quién”. Algunos sistemas se limitan a utilizar un mecanismo de tiempos de espera y suponen que una transacción que no ha realizado trabajo alguno durante algún periodo especificado está en bloqueo mutuo. Algunos sistemas seleccionan como víctima, al proceso con el menor tiempo de uso de CPU. La transacción elegida como víctima es cancelada, y algunos sistemas la reinician de manera automática. Otros sistemas se limitan a enviar un código de retorno “víctima de bloqueo mutuo” de vuelta a la aplicación. El algoritmo de selección de víctimas puede conferir prioridades más altas a las transacciones que se han abortado varias veces, a fin de que no se escojan como víctimas una y otra vez.

PROTOCOLO DE BLOQUEO DE DOS FASES BÁSICO Se dice que una transacción sigue el protocolo bloqueo de dos fases si todas las operaciones de bloqueo (bloquear_lectura, bloquear_escritura) preceden a la primera operación de desbloqueo en la transacción. Una transacción así puede dividirse en dos fases: FASE DE EXPANSIÓN: (o de crecimiento) durante la cual se pueden adquirir nuevos candados sobre elementos, pero no se puede liberar ninguno.

PROTOCOLO DE BLOQUEO DE DOS FASES BÁSICO FASE DE CONTRACCIÓN: durante la cual se pueden liberar los candados existentes, pero no se pueden adquirir nuevos candados. Si se permite promover candados (esto es, que una transacción emita una operación bloquear_lectura(X) y más adelante emita una operación bloquear_escritura (X)), esta definición no cambia. Pero si también se permite la degradación de candados (esto es, que una transacción emita una operación bloquear_escritura(X) y más adelante emita una operación bloquear_lectura (X), la definición debe alterarse ligeramente.

Todas las degradaciones deben efectuarse en la fase de contracción. Así, una operación bloquear_lectura(X) que degrada un candado de escritura que ya se tenía sobre X sólo puede aparecer en la fase de contracción de la transacción. VENTAJAS: Garantiza planes seriables. DESVENTAJAS: Los planes no evitan la reversión en cascada, Bloqueo mutuo, Limitación del grado de concurrencia, Espera indefinida (si una transacción no puede continuar durante un período indeterminado, mientras otras transacciones continúan con normalidad. como sucedería si el esquema de espera es injusto y confiera a algunas transacciones mayor prioridad que otras), Inanición debido a los algoritmos que resuelven el bloqueo mortal.

PROTOCOLO DE BLOQUEO DE DOS FASES BÁSICO Ejemplo:

T1 bloquear_lectura(Y) leer_elemento(Y) bloquear_escritura(X) desbloquear(Y) leer_elemento(X) X := X + Y escribir_elemento(X) desbloquear(X)

CONTROL DE CONCURRENCIA BASADO EN ORDENAMIENTO POR MARCA DE TIEMPO (BÁSICO) En las técnicas de bloqueo el orden de las transacciones en el plan en serie equivalente se basa en el orden en que las transacciones en ejecución bloquean los elementos que requieren. Un enfoque distinto implica el uso de marcas de tiempo de las transacciones para ordenar la ejecución de las transacciones según un plan en serie equivalente. MARCA DE TIEMPO: es un identificador único dado por el sistema para identificar una transacción. Los valores se asignan en el orden en que las transacciones se introducen en el sistema, se le puede considerar como el tiempo de inicio de una transacción T como MT(T).

ALGORITMO DE ORDENAMIENTO POR MARCA DE TIEMPO: Se basa en ordenar las transacciones con base en sus marcas de tiempo. El plan será seriable, y el plan en serie equivalente tendrá las transacciones en orden según sus valores de marca de tiempo. Para evitar que el orden en que se tiene acceso a un elemento por más de una transacción no viole la seriabilidad del plan, el algoritmo asocia a cada elemento X de la base de datos, dos valores de marca de tiempo: 1. MT_lectura(X); esta es la más grande de todas las marcas de tiempo de las transacciones que han leído con éxito el elemento X. 2. MT_escritura(X); esta es la más grande de todas las marcas de tiempo de las transacciones que han escrito con éxito el elemento X.

El algoritmo debe verificar si se viola el ordenamiento por marca de tiempo de las transacciones en estos dos casos: 1. La transacción T emite una operación escribir_elemento(X): a. Si MT_lectura(X) > MT(T) o MT_escritura(X) > MT(T) entonces T aborta y se rechaza la operación, se vuelve a introducir T con nueva marca de tiempo; b. De otro modo, se ejecuta la operación y se asigna MT_escritura(X) := MT(T) 2. La transacción T emite una operación leer_elemento (X): a. Si MT_escritura(X) > MT(T) se debe abortar T y rechazar la operación, se vuelve a introducir T con una nueva marca de tiempo. b. Si MT_escritura  MT(T) se ejecuta la operación y MT_lectura(X) := mayor { MT(T), MT_lectura(X) }

CONTROL DE CONCURRENCIA BASADO EN ORDENAMIENTO POR MARCA DE TIEMPO (BÁSICO) VENTAJAS: Garantiza planes seriables, No hay bloqueo mortal DESVENTAJAS: No garantiza que los planes sean recuperables, No evitan la reversión en cascada, Puede ocurrir la INANICION si una transacción se aborta y reinicia continuamente.

TÉCNICAS PARA EL CONTROL DE CONCURRENCIA DE MULTIVERSIÓN Los protocolos para controlar la concurrencia que conservan los valores antiguos de un elemento de información cuando éste se actualiza se conocen como técnicas de control de concurrencia multiversión, porque se mantienen varias versiones (valores) de un elemento. Cuando una transacción requiere acceso a un elemento, se elige una versión apropiada para mantener la seriabilidad del plan que se está ejecutando, si es posible. La idea consiste en que algunas operaciones de lectura que serían rechazadas si se usarán otras técnicas se pueden aceptar leyendo una versión anterior del elemento a fin de mantener la seriabilidad. Cuando una transacción escribe, escribe una nueva versión y se conserva la versión anterior de dicho elemento. La desventaja es que se requiere más almacenamiento para mantener múltiples versiones de los elementos de la base de datos.

GRANULARIDAD DE LOS DATOS Un elemento de la base de datos manejado por las técnicas de control de concurrencia puede ser: Un registro de la base de datos, Un valor de campo de un registro de la base de datos, Un bloque de disco, Un archivo completo, La base de datos completa. Cuanto mayor sea el tamaño del elemento, menor será el grado de concurrencia permitido. Cuanto menor sea el tamaño del elemento, el sistema tendrá una mayor cantidad de elementos por gestionar, además requerirá mas espacio de almacenamiento. En general, el tamaño es uniforme, pero para las técnicas que permiten tamaños variables, el tamaño ad-hoc dependerá del tipo de las transacciones implicadas.

OPERACIONES DE INSERCIÓN Y ELIMINACIÓN Se ha centrado la atención en las operaciones leer y escribir, las cuales accesan a elementos de datos ya existentes. Sin embargo las transacciones también necesitan de las operaciones que permitan crear y borrar elementos de datos. INSERTAR(X): inserta en la base de datos el nuevo elemento de datos X y le asigna un valor inicial. En un entorno de bloqueo, se da a T un bloqueo de escritura (exclusivo) para el elemento X. En el protocolo de ordenación por marcas de tiempo, se fijan los valores MT_lectura(X) y MT_escritura(X) a MT(T).

OPERACIONES DE INSERCIÓN Y ELIMINACIÓN ELIMINAR(X): elimina de la base de datos el elemento de datos X. En un entorno de bloqueo, también se da a T un bloqueo de escritura (exclusivo) para el elemento X. En el protocolo de ordenación por marcas de tiempo, Si MT_lectura(X) > MT(T) o MT_escritura(X) > MT(T) entonces abortar y revertir T y rechazar la operación; de lo contrario ejecutar la operación eliminar(X).

REGISTROS FANTASMAS PROBLEMA DEL FANTASMA: ocurre cuando un registro que está siendo insertado por alguna transacción T satisface una condición que deberá satisfacer un conjunto de registros a los que tenga acceso otra transacción T’. Aun cuando las transacciones están en conflicto desde un punto lógico, no hay realmente ningún registro en común entre las dos transacciones, ya que T’ puede haber bloqueado el conjunto de registros antes de que T insertara el nuevo registro. El registro que causa el conflicto es un registro fantasma que ha aparecido repentinamente en la base de datos al ser insertado.

REGISTROS FANTASMAS Una solución al problema del fantasma es el llamado bloqueo de índice. (Un índice incluye entradas que tienen un valor de atributo, más un conjunto de apuntadores a todos los registros del archivo que tienen ese valor). Toda transacción que inserte un registro en una tabla debe insertar información en cada uno de los índices que se mantengan en la tabla. Si la entrada del índice correspondiente se bloquea antes de que se pueda tener acceso al registro mismo será posible detectar el conflicto por el registro fantasma: La razón es que la transacción T’ solicitaría un candado de lectura para la entrada de índice correspondiente y T solicitaría un candado de escritura para esa misma entrada. Puesto que los bloqueos del índice están en conflicto, el problema del fantasma se detectaría.