• Author / Uploaded
• Anderson Blacho

Citation preview

Jose Manuel Perez Daniel Futrillé Prof. Ana Aguilera

1 Introducción 2 Concepto de Transacciones 2.1 Propiedades de las transacciones 2.2 Condiciones de terminación de una transacción 2.3 Caracterización de transacciones 2.4 Transacciones y planificadores 2.5 Ejecución concurrente de transacciones 2.5.1 Motivos para la ejecución concurrente 2.5.2 Seriabilidad 2.5.3 Anomalías de Ejecución 2.5.4 Control de concurrencia basado en lock (cerraduras) 2.6 Tipos de Transacciones 2.7 Estructura de transacciones 2.8 Aspectos relacionados al procesamiento de transacciones 3 Conceptos relacionados con el control de concurrencia 3.1 Administración de locks 3.2 Deadlocks prevención y detección 3.3 Técnicas de cerraduras especializadas 3.4 Control de Concurrencia sin locking

Hasta este momento, las primitivas básicas de acceso que se han considerado son las consultas. Sin embargo, no se ha discutido qué pasa cuando, por ejemplo, dos consultas tratan de actualizar el mismo elemento de datos, o si ocurre una falla del sistema durante la ejecución de una consulta. Dada la naturaleza de una consulta, de lectura o actualización, a veces no se puede simplemente reactivar la ejecución de una consulta, puesto que algunos datos pueden haber sido modificados antes de la falla. El no tomar en cuenta esos factores puede conducir a que la información en la base de datos contenga datos incorrectos. El concepto fundamental aquí es la noción de "ejecución consistente" o "procesamiento confiable" asociada con el concepto de una consulta. El concepto de una transacción es usado dentro del dominio de la base de datos como una unidad básica de cómputo consistente y confiable.

Una transacción es una ejecución de un programa de usuario, visto por el DBMS como una serie de operaciones lecturas y escrituras, la cual accede a la base de datos que es compartida por varios usuarios en forma simultánea. Es una colección de acciones que hacen transformaciones de los estados de un sistema preservando la consistencia del mismo. Una base de datos está en un estado consistente si obedece todas las restricciones de integridad definidas sobre ella. Los cambios de estado ocurren debido a actualizaciones, inserciones, y supresiones de información. Por supuesto, se quiere asegurar que la base de datos nunca entra en un estado de inconsistencia. Sin embargo, durante la ejecución de una transacción, la base de datos puede estar temporalmente en un estado inconsistente. El punto importante aquí es asegurar que la base de datos regresa a un estado consistente al fin de la ejecución de una transacción.

La Base de Datos en estado consistente

Inicio de Transacción T1

La Base de Datos temporalmente en un estado inconsistente durante la ejecución de la transacción

Ejecución de la Transacción T1

La Base de Datos en estado consistente

Fin de Transacción T1

Para fines de recuperación el sistema necesita mantenerse al tanto de cuando la transacción se inicia, termina y se confirma o aborta, así el gestor de recuperación se mantiene al tanto de las siguientes operaciones:

• INICIO_DE_TRANSACCIÓN: marca el inicio de la ejecución de la transacción • LEER o ESCRIBIR: especifican operaciones de lectura o escritura de elementos de la base de datos que se efectúan como parte de una transacción. • FIN_DE_TRANSACCIÓN: especifica que las operaciones de leer o escribir han terminado y marca el límite de la ejecución de la transacción. Sin embargo, puede ser necesario verificar si los cambios introducidos por la transacción se pueden aplicar permanentemente a la base de datos (Confirmar) o si debe abortarse porque viola el control de concurrencia o por alguna otra razón. • CONFIRMAR_TRANSACCIÓN: señala que la transacción terminó con éxito y que cualquier actualización ejecutada por ella se puede confirmar sin peligro en la base de datos y no se cancelarán. • ABORTAR: indica que la transacción terminó sin éxito y que cualquier cambio o efecto que pueda ser aplicado a la base de datos debe ser cancelado. Se hacen necesarios mecanismos de control de concurrencia y de recuperación para garantizar estos estados.

Diagrama de Transición de estados para la ejecución de transacciones

Operaciones y Cuerpo de una Transacción: Begin transaction : inicio de la transacción Read a : lectura del objeto a Write a : escritura del objeto a Rollback : anulación de la transacción Commit : fin de la transacción

Begin transaction T O1 O2 . . . On Commit T Oi e conjunto de operaciones

Propiedades de las transacciones: •

•

Atomicidad: Se refiere al hecho de que una transacción se trata como una unidad de operación. Por lo tanto, o todas las acciones de la transacción se realizan o ninguna de ellas se lleva a cabo. La atomicidad requiere que si una transacción se interrumpe por una falla, sus resultados parciales deben ser deshechos. La actividad referente a preservar la atomicidad de transacciones en presencia de abortos debido a errores de entrada, sobrecarga del sistema o interbloqueos se le llama recuperación de transacciones. La actividad de asegurar la atomicidad en presencia de caídas del sistema se le llama recuperación de caídas. Consistencia: La consistencia de una transacción es simplemente su correctitud. En otras palabras, una transacción es un programa correcto que lleva la base de datos de un estado consistente a otro con la misma característica. Debido a esto, las transacciones no violan las restricciones de integridad de una base de datos.

Propiedades de las transacciones: •

Aislamiento: Una transacción en ejecución no puede revelar sus resultados a otras transacciones concurrentes antes de su commit. Más aún, si varias transacciones se ejecutan concurrentemente, los resultados deben ser los mismos que si ellas se hubieran ejecutado de manera secuencial (seriabilidad).

•

Durabilidad: Es la propiedad de las transacciones que asegura que una vez que una transacción hace su commit, sus resultados son permanentes y no pueden ser borrados de la base de datos. Por lo tanto, los DBMS aseguran que los resultados de una transacción sobrevivirán a fallas del sistema. Esta propiedad motiva el aspecto de recuperación de bases de datos, el cual trata sobre como recuperar la base de datos a un estado consistente en donde todas las acciones que han hecho un commit queden reflejadas.

Ejemplo: transferencia de fondos 1. read(A) 2. A := A – 50 3. write(A) 4. read(B) 5. B := B + 50 6. write(B) Transacción para transferir $50 de la cuenta A a la cuenta B

• Consistencia: la suma de A y B no debe cambiar por la ejecución de la transacción • Atomicidad: si la transacción falla entre los pasos 3 y 6, el sistema debe asegurar que los cambios no se reflejen en la BD • Aislamiento: si entre los pasos 3 y 6 se le permite a otra transacción acceder a los datos parcialmente modificados, verá un estado inconsistente de la BD • Durabilidad: una vez que el usuario ha sido notificado que la transacción se realizó, los cambios deben persistir a pesar de fallas

Condiciones de terminación de una transacción: Una transacción siempre termina, aun en la presencia de fallas. Si una transacción termina de manera exitosa se dice que la transacción hace un commit. Si la transacción se detiene sin terminar su tarea, se dice que la transacción aborta. Cuando la transacción es abortada, su ejecución es detenida y todas sus acciones ejecutadas hasta el momento son deshechas (undone) regresando a la base de datos al estado antes de su ejecución. A esta operación también se le conoce como rollback.

Caracterización de transacciones: Las acciones de lectura y escritura se utilizan como base para caracterizar a las transacciones. Los elementos de datos que lee una transacción se dice que constituyen el conjunto de lectura (RS). Similarmente, los elementos de datos que una transacción escribe se les denomina el conjunto de escritura (WS). Note que los conjuntos de lectura y escritura no tienen que ser necesariamente disjuntos. La unión de ambos conjuntos se le conoce como el conjunto base de la transacción (BS = RS U WS). Ejemplo: Los conjuntos de lectura y escritura de la siguiente transacción: RS[Reservación] = { FLIGHT.STSOLD, FLIGHT.CAP } WS[Reservación] = { FLIGHT.STSOLD, FC.FNO, FC.DATE, FC.NAME, FC.SPECIAL }

Transacciones y Planificaciones (Schedules): Hasta ahora conocemos que una transacción es vista por el DBMS como una serie, o lista, de acciones las cuales ejecutan operaciones de lectura y escritura en elementos de la Base de Datos. También sabemos que una transacción debe especificar su acción de finalización como commit (Finalizó exitosamente) o abort (finalizó pero deshizo todas las acciones llevadas a cabo). Ahora, una planificación, es una lista de acciones (lecturas, escrituras, abortos o commit) de un conjunto de transacciones, y el orden que el cual dos acciones de una transacción T aparecen en una Planificación debe ser el mismo orden en el cual aparecen en T. En otras palabras una Planificación representa una secuencia de ejecución actual o potencial el cual describe las acciones de las transacciones así como son vistas por el DBMS.

Ejemplo de una Planificación : T1

T2

R(A)

Una Planificación completa es aquella que contiene todas las acciones de cada transacción que aparecen en el.

W(A) R(B) W(B) Commit R(C) W(C) Commit

Si las acciones de diferentes transacciones no están entrelazadas (las acciones son ejecutadas de inicio a fin, una por una) la llamamos una Planificación Serial o Secuencial.

Ejecución concurrente de transacciones Conociendo el concepto de planificación, ahora se puede describir ejecuciones entrelazadas o interleaved de transacciones. El DBMS entrelaza las acciones de diferentes transacciones para mejor el rendimiento, en términos de incrementar el promedio de transacciones completadas en un determinado tiempo o mejorar los tiempos de respuestas de las transacciones cortas.

Motivos para ejecución concurrente: La Planificación mostrada en la siguiente figura muestra una ejecución entrelazada de dos transacciones.

Asegurar el aislamiento de las transacciones mientras se permite la ejecución concurrente es difícil, pero es necesario, hay que mejorar el rendimiento.

Seriabilidad: Cualquier ejecución de un conjunto de transacciones es correcta si es libre de interferencias. Una planificación Serializable es una equivalencia de alguna de las ejecuciones seriales de las transacciones. Si cada transacción preserva consistencia, cada planificación serializable preserva consistencia.

Anomalías que surgen con la ejecución entrelazadas La ejecución entrelazadas de transacciones sin control puede resultar en una base de datos inconsistente. Problemas de: – Pérdida de la actualización: Diferentes ejecuciones entrelazadas pueden producir valores finales diferentes. – Lectura inconsistente: Existen ejecuciones entrelazadas que violan RI. – Lectura irreproducible: Existen ejecuciones entrelazadas donde el valor desplegado no es el mismo. -Sobreescribiendo datos inconsistente -Existe una transacción que sobreescribe un valor, el cual había sido modificado por otra transacción mientras esta estaba corriendo.

Conflictos de WR:

T1: T2:

R(A), W(A),

R(A), W(A), C

R(B), W(B), Abort

Conflictos de WR:

T1: T2:

R(A),

R(A), W(A), C

R(A), W(A), C

Conflictos de WW:

T1: T2:

W(A),

W(A), W(B), C

W(B), C

Planificación Invocando a transacciones Abortadas Una transacción siempre termina, aun en la presencia de fallas. Si una transacción termina de manera exitosa se dice que la transacción hace un compromiso. Si la transacción se detiene sin terminar su tarea, se dice que la transacción aborta. Cuando la transacción es abortada, puede ser por distintas razones relacionadas con la naturaleza de la transacción misma, o por conflicto con otras transacciones o por fallo de un proceso o computador, entonces su ejecución es detenida y todas las acciones ejecutadas hasta el momento son deshechas regresando a la base de datos al estado antes de su ejecución. A esta operación también se la conoce como rollback.

Control de Concurrencia Basado en Lock: En los algoritmos basados en candados, las transacciones indican sus intenciones solicitando candados al despachador (llamado el administrador de candados) Los candados son de lectura , también llamados compartidos, o de escritura , también llamados exclusivos. En sistemas basados en candados, el despachador es un administrador de candados . El administrador de transacciones le pasa al administrador de candados la operación sobre la base de datos (lectura o escritura) e información asociada, como por ejemplo el elemento de datos que es accedido y el identificador de la transacción que está enviando la operación a la base de datos.

Tipos de Transacciones: Las transacciones pueden pertenecer a varias clases. Las transacciones pueden ser agrupadas a lo largo de las siguientes dimensiones: Áreas de aplicación. En primer lugar, las transacciones se pueden ejecutar en aplicaciones no distribuidas. Las transacciones que operan en datos distribuidos se les conoce como transacciones distribuidas. Tiempo de duración. Tomando en cuenta el tiempo que transcurre desde que se inicia una transacción hasta que se realiza un commit o se aborta, las transacciones pueden ser de tipo batch o en línea. Estructura. Considerando la estructura que puede tener una transacción se examinan dos aspectos: si una transacción puede contener a su vez subtransacciones o el orden de las acciones de lectura y escritura dentro de una transacción

Estructuras de las Transacciones: Las transacciones planas consisten de una secuencia de operaciones primitivas encerradas entre las palabras clave begin y end. Por ejemplo, Begin_transaction Reservación ... end. En las transacciones anidadas las operaciones de una transacción pueden ser así mismo transacciones. Por ejemplo, Begin_transaction Reservación ... Begin_transaction Vuelo ... end. {Vuelo} ... Begin_transaction Hotel ... end. ... end.

Aspectos relacionados al procesamiento de transacciones: •

Modelo de estructura de transacciones: considerar si las transacciones son planas o pueden estar anidadas.

•

Consistencia de la base de datos interna: Los algoritmos de control de datos semántico tienen que satisfacer siempre las restricciones de integridad cuando una transacción pretende hacer un commit.

•

Algoritmos de control de concurrencia: Los algoritmos de control de concurrencia deben sincronizar la ejecución de transacciones concurrentes bajo el criterio de correctitud. La consistencia entre transacciones se garantiza mediante el aislamiento de las mismas.

•

Protocolos de control de réplicas: El control de réplicas se refiere a cómo garantizar la consistencia mutua de datos replicados. Por ejemplo se puede seguir la estrategia read-one-write-all (ROWA).

Conceptos relacionados con el control de concurrencia: Planificación serial: recordamos el concepto antes visto; para cada transacción T participando en el Planificación, todas las operaciones de T se ejecutan consecutivamente en la Planificación; sino, T es no serial. Planificaciones Equivalentes: Para que dos Planificaciones sean equivalentes, las operaciones aplicadas a cada dato afectado por las planificaciones deben ser aplicadas en ambas planificaciones en el mismo orden Planificación serializable: equivalente a alguna Planificación serial

T1 read (A) A := A-50 write (A)

T2

read (A); temp := A * 0.1 A := A – temp write (A) read (B) B := B+50 write (B) Commit

read (B) B:=B+temp write (B) Commit

Plan Serializable

Conceptos relacionados con el control de concurrencia: Serializabilidad: Un plan serializable implica que el plan es correcto • Deja la base de datos en un estado consistente • El intercalamiento es apropiado y resultará en un estado como si las transacciones fueran ejecutadas secuencialmente, pero será eficiente debido a la ejecución concurrente. La serializabilidad es difícil de verificar • El intercalamiento de las operaciones ocurre en el sistema operativo a través de un planificador • Difícil determinar de antemano como las operaciones serán intercaladas Enfoque práctico: Protocolos asegurando la serializabilidad a través del uso de Candados (locks)

Propósito del Control de Concurrencia: En general, reforzar el aislamiento (a través de la exclusión mutua) entre transacciones conflictivas. En particular, evitar los problemas de: • Actualización perdida • Actualización temporal • Suma incorrecta

Problema de la Actualización Perdida: Ocurre cuando dos transacciones que acceden los mismos datos tienen sus operaciones intercaladas de forma que hacen que el valor de un dato sea incorrecto. T1 read_item (X) X := X-N

T2 read_item (X) X := X+M

write_item (X) read_item (Y) Y:= Y+N write_item (Y) Commit

write_item (X) Commit

X tiene un valor incorrecto porque la actualización de T1 se pierde

Problema de la de la actualización temporal: Ocurre cuando una transacción actualiza un dato y después falla. El dato actualizado es accedido por otra transacción antes de cambiar su valor al original. T1 read_item (X) X := X-N write_item (X)

T2

read_item (X) X := X+M write_item (X) Commit read_item (Y) Abort

T1 falla y debe regresar el valor modificado de X al original; T2 leyó temporalmente el valor incorrecto de X.

Problema de la suma incorrecta: Si una transacción está calculando una función matemática sobre un conjunto de tuplas mientras que otras transacciones están actualizándolas, el resultado puede ser incorrecto. T1

T3 sum :=0 read_item(A) sum := sum+A

read_item (X) X := X-N write_item (X)

read_item(Y) Y := Y+N write_item(Y) Commit

read_item(X) sum:=sum+X read_item(Y) sum :=sum+Y Commit

T3 lee X después de sustraer N y lee Y antes de sumar N: el resultado es incorrecto

Protocolos basados en candados (Locks): Es un conjunto de reglas seguidas por todas las transacciones para solicitar y liberar candados. Un candado es un mecanismo de control de acceso concurrente a un dato Los datos pueden tener candados en dos modos: • Modo exclusivo (X). El dato puede ser leído y escrito. Un candado en este modo se solicita con la instrucción lock-X • Modo compartido (S). El dato solo puede ser leído. Un candado en este modo se solicita con la instrucción lock-S. Las transacciones indican sus intenciones solicitando candados al despachador (llamado el administrador de candados). La transacción puede proceder solo después de que una solicitud es otorgada.

Protocolos basados en candados: Como se aprecia en la tabla siguiente, los candados de lectura presentan conflictos con los candados de escritura, dado que las operaciones de lectura y escritura son incompatibles. • Un candado es otorgado si el candado solicitado es compatible con otros candados previamente otorgados. • Se pueden tener varios candados compartidos sobre un dato, pero sólo un candado exclusivo. • Si un candado no puede ser concedido, la transacción que lo solicita debe esperar a que todos los candados incompatibles sean El poner candados no es suficiente liberados. para garantizar serializabilidad

Protocolo de candado en dos fases (2PL): Asegura planificaciones serializables. Fase 1: Crecimiento • Una transacción puede solicitar/obtener candados • Una transacción no puede liberar candados Fase 2: reducción • Una transacción puede liberar candados • Una transacción no puede obtener candados En los candados de dos fases una transacción le pone un candado a un objeto antes de usarlo. Cuando un objeto es bloqueado con un candado por otra transacción, la transacción solicitante debe esperar. Cuando una transacción libera un candado, ya no puede solicitar más candados.

Protocolo de candado en dos fases (2PL): Una transacción que utiliza candados de dos fases se comporta como en la siguiente figura. En la primera fase solicita y adquiere todos los candados sobre los elementos que va a utilizar y en la segunda fase libera los candados obtenidos uno por uno.

Protocolo de candado en dos fases (2PL): La importancia de los candados de dos fases es que se ha demostrado de manera teórica que todos los planificadores generados por algoritmos de control de concurrencia que obedecen a los candados de dos fases son serializables. Abortos en Cascada: Puede suceder si una transacción aborta después de liberar un candado, otras transacciones que hayan accedido el mismo elemento de datos aborten también. Para evitar lo anterior, los despachadores para candados de dos fases implementan lo que se conoce como los candados estrictos de dos fases en los cuales se liberan todos los candados juntos cuando la transacción termina (con commit o aborta). Ver la siguiente figura.

Protocolo de candado en dos fases (2PL):

Problemas de los protocolos basados en candados: abrazo mortal: Abrazo mortal: dos transacciones esperan mutuamente a que la otra libere un candado. Prevención: una transacción pone un candado a todos los datos a los que se refiere antes de comenzar su ejecución. Evitar: si una transacción intenta crear un ciclo, entonces se echa para atrás (roll back) esa transacción.

Problemas de los protocolos basados en candados: inanición: Ocurre cuando una transacción en particular consistentemente espera o es reinicializada y nunca tiene la posibilidad de seguir adelante. Esta limitación es característica de todos los mecanismos de planificación basados en prioridades (estampillas de tiempo).

Tecnicas de cerraduras Especializadas Lecturas fantasma Una transacción vuelve a ejecutar una consulta, devolviendo un conjunto de filas que satisfacen una condición de búsqueda y encuentra que otras filas que satisfacen la condición que han sido insertadas por otra transacción cursada.

Control de Concurrencia sin locking Control de concurrencia optimista Los algoritmos de control de concurrencia discutidos antes son por naturaleza pesimistas. En otras palabras, ellos asumen que los conflictos entre transacciones son muy frecuentes y no permiten el acceso a un dato si existe una transacción conflictiva que acceda al mismo dato. Así, la ejecución de cualquier operación de una transacción sigue la secuencia de fases: validación (V), lectura (R), cómputo (C) y escritura (W). Los algoritmos optimistas, por otra parte, retrasan la fase de validación justo antes de la fase de escritura. De esta manera, una operación sometida a un despachador optimista nunca es retrasada.

• Database Management, Ramakrishnan Gehrke • Sistema de bases de datos, Elmasri Navathe • http://www.utm.mx/~caff/perso/index.html • http://www.cs.princeton.edu/courses/archive/spr00/cs425/slides/ • https://dpt-info.u-strasbg.fr/doc/oracle/server.102/b14220/transact.htm • www.cs.ust.hk/~dimitris • codex.cs.yale.edu/avi/db-book • http://www.cs.cinvestav.mx/SC/prof_personal/adiaz/Disdb/Cap_5.html • http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/MonogSO/ TRANS02.htm • http://es.tldp.org/Postgresql-es/web/navegable/user/x3589.html