PRESENTACION ANMADA

http://goanimate.com/videos/0UkhZcA5mMbg?utm_source=linkshare&utm_medium=linkshare&utm_campaign=usercontent

ACTIVIDAD 20 Y 21

PRESENTACION 

https://drive.google.com/file/d/0Bz6Cr7bOrFk7TnF5NVc3TVRyLUk/view?usp=sharing


Actividad #21 • investigar sobre los protocolos REDO/UNDO y el protocolo 2PC de confiabilidad distribuida, así como los puntos de verificación y presentando un ejemplo de su aplicación publicando los resultados en el blog 

Candados de dos fases :                                                                                                                   

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. 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.                                                        

Puede suceder que si una transacción aborta después de liberar un candado, otras transacciones que hayan accesado el mismo elemento de datos aborten también provocando lo que se conoce como abortos en cascada. 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 compromiso o aborta).

Candados de dos fases centralizados:                                                                                               

En sistemas distribuidos puede que la administración de los candados se dedique a un solo nodo del sistema, por lo tanto, se tiene un despachador central el cual recibe todas las solicitudes de candados del sistema. 

Protocolos REDO/UNDO.

El registro de la base de datos contiene información que es utilizada por el proceso de recuperación para restablecer la base de datos a un estado consistente. Esta información puede incluir entre otras cosas:

• el identificador de la transacción,
• el tipo de operación realizada,
• los datos accesados por la transacción para realizar la acción,
• el valor anterior del dato (imagen anterior), y
• el valor nuevo del dato (imagen nueva).

El DBMS inicia la ejecución en el tiempo 0 y en el tiempo t se presenta una falla del sistema. Durante el periodo [0, t] ocurren dos transacciones, T₁ y T₂. T₁ ha sido concluida (ha realizado su commit) pero T₂ no pudo ser concluida.

La propiedad de durabilidad requiere que los efectos de T₁ sean reflejados en la base de datos estable. De forma similar, la propiedad de atomicidad requiere que la base de datos estable no contenga alguno de los efectos de T₂.

Operación REDO.

Por otra parte, es posible que el administrador del buffer haya realizado la escritura en la base de datos estable de algunas de las páginas de la base de datos volátil correspondientes a la transacción T₂.

Así, la información de recuperación debe incluir datos suficientes para permitir deshacer ciertas actualizaciones en el nuevo estado de la base de datos y regrasarla al estado anterior. A esta operación se le conoce como UNDO . La operación UNDO restablece un dato a su imagen anterior utilizando la información del registro de la base de datos.

Operación UNDO.

De forma similar a la base de datos volátil, el registro de la base de datos se mantiene en memoria principal (llamada los buffers de registro) y se escribe al almacenamiento estable (llamadoregistro estable). 

• Las páginas de registro se pueden escribir en el registro estable de dos formas: síncrona o asíncrona. 
• En forma síncrona, también llamada un registro forzado, la adición de cada dato en el registro requiere que la página del registro correspondiente se mueva al almacenamiento estable. 
• De manera asíncrona, las páginas del registro se mueven en forma periódica o cuando los buffers se llenan.

 Puntos de verificación (checkpoints).

Cuando ocurre una falla en el sistema es necesario consultar la bitácora para determinar cuáles son las transacciones que necesitan volver a hacerse y cuando no necesitan hacerse. Estos puntos de verificación nos ayudan para reducir el gasto de tiempo consultando la bitácora. 

El punto de verificación es un registro que se genera en la bitácora para concluir en todo lo que se encuentra antes de ese punto está correcto y verificado.

 Protocolo 2PC de confiabilidad distribuida.

El protocolo 2PC básico un agente (un agente-DTM en el modelo) con un rol especial. Este es llamado el coordinador; todos los demás agentes que deben hacer commit a la vez son llamados participantes.

El coordinador es responsable de tomar la decisión de llevar a cabo un commit o abort finalmente.

 Cada participante corresponde a una subtransacción la cual ha realizado alguna acción de escritura en su base de datos local.

Se puede asumir que cada participante está en un sitio diferente. 

Aun si un participante y el coordinador se encuentran en el mismo sitio, se sigue el protocolo como si estuvieran en distintos sitios.

La idea básica del 2PC es determinar una decisión única para todos los participantes con respecto a hacer commit o abort en todas las subtransacciones locales.

El protocolo consiste en dos fases:

• La primera fase tiene como objetivo alcanzar una decisión común,

• La meta de la segunda fase es implementar esta decisión.

El protocolo procede como sigue:

Fase uno:

• El coordinador escribe “prepare” en la bitácora y envía un mensaje donde pregunta a todos los participantes si preparan el commit (PREPARE).

• Cada participante escribe “ready” (y registra las subtransacciones) en su propia bitácora si está listo o “abort” de lo contrario.

• Cada participante responde con un mensaje READY o ABORT al coordinador.

• El coordinador decide el commit o abort en la transacción como un resultado de las respuestas que ha recibido de los participantes. Si todos respondieron READY, decide hacer un commit. Si alguno ha respondido ABORT o no ha respondido en un intervalo de tiempo determinado se aborta la transacción.

Fase dos:

• El coordinador registra la decisión tomada en almacenamiento estable; es decir, escribe “global_commit” o “global_abort” en la bitácora.

• El coordinador envía mensaje de COMMIT o ABORT según sea el caso para su ejecución.

• Todos los participantes escriben un commit o abort en la bitácora basados en el mensaje recibido del coordinador (desde este momento el procedimiento de recuperación es capaz de asegurar que el efecto de la subtransacción no será perdido).

Finalmente:

• Todos los participantes envían un mensaje de acuse de recibo (ACK) al coordinador, y ejecutan las acciones requeridas para terminar (commit) o abortar (abort) la subtransacción.
• Cuando el coordinador ha recibido un mensaje ACK de todos los participantes, escribe un nuevo tipo de registro en la bitácora, llamado un registro “completo”.
  
  

ACTIVIDAD 19

Actividad #19 Investigar las disciplinas del Interbloqueo: prevención, detección, eliminación y recuperación. Publicando los resultados en el blog.


Un interbloqueo es una condición que se puede dar en cualquier sistema con varios subprocesos, no sólo en un sistema de administración de bases de datos relacionales, y puede producirse para recursos distintos a los bloqueos en objetos de base de datos

Prevención del interbloqueo.

Objetivo: conseguir que sea imposible la aparición de situaciones de interbloqueo.

Impedir que se produzca una de las cuatro condiciones necesarias para producirlo: Exclusión mutua, Retención y espera, No expropiación, y Espera circular.

Recuperación de Interbloqueo.

Limpiar un sistema de interbloqueos, una vez que fueron detectados. 

Cuando se ha detectado que existe un interbloqueo, podemos actuar de varias formas. Una posibilidad es informar al operador que ha ocurrido un interbloqueo y dejar que el operador se ocupe de él manualmente. La otra posibilidad es dejar que el sistema se recupere automáticamente del interbloqueo. Dentro de esta recuperación automática tenemos dos opciones para romper el interbloqueo: Una consiste en abortar uno o más procesos hasta romper la espera circular, y la segunda es apropiar algunos recursos de uno o más de los procesos bloqueados.

Eliminar interbloqueos.

Para eliminar interbloqueos abortando un proceso, tenemos dos métodos; en ambos, el sistema recupera todos los recursos asignados a los procesos terminados.

1. Abortar todos los procesos interbloqueados. Esta es una de las soluciones más comunes, adoptada por Sistemas Operativos. Este método romperá definitivamente el ciclo de interbloqueo pero con un costo muy elevado, ya que estos procesos efectuaron cálculos durante mucho tiempo y habrá que descartar los resultados de estos cálculos parciales, para quizá tener que volver a calcularlos más tarde.
2. Abortar un proceso en cada ocasión hasta eliminar el ciclo de interbloqueo. El orden en que se seleccionan los procesos para abortarlos debe basarse en algún criterio de costo mínimo. Después de cada aborto, debe solicitarse de nuevo el algoritmo de detección, para ver si todavía existe el interbloqueo. Este método cae en mucho tiempo de procesamiento adicional.
   
   

ACTIVIDAD 18

Actividad #18 
Investigar, Analizar y comprobar los algoritmos de control de concurrencia, tales como: los basados en bloqueo,los basados en estampas de tiempo y las pruebas de validación optimistas. Presentando sus resultados en clase y publicados en el blog

Algoritmos de Control de Concurrencia

En un sistema distribuido, cada transacción debe tener una estampilla de tiempo unica para usar en la decisión del orden de desestabilizad. 

Para la generación de estampillas únicas, en el modelo distribuido: cada transaccion tiene una estampilla de tiempo que surge de concatenar la estampilla de tiempo local con el identificador de sitio.

El problema del modelo distribuido es que un sitio podría generar estampillas de tiempo a mayor velocidad que otros sitios. En ese caso, las estampillas de tiempo generadas por el sitio mas rápido serán mayores que las generadas por otros sitios.

 Esto se evita si cada sitio utiliza un reloj lógico, implementado mediante un contador que se incrementa cada vez que se genera una nueva estampilla de tiempo local.

 Para sincronizar los relojes lógicos, se requiere que cada sitio Si avance su reloj logico   cuando arriba una nueva transacción a ese sitio.

1. Existen varias formas en que las estampas de tiempo se pueden asignar. Un metodo es usar un contador global monotonicamente creciente
2. El administrador de transacciones asigna tambien una estampa de tiempo a todas las operaciones
   solicitadas por una transaccion
   
   
   
   
   
   
   
   
   
   
   
   

   BLOQUEOS

   Un bloqueo en general es cuando una acción que debe ser realizada está esperando a un evento. Para manejar los bloqueos hay distintos acercamientos: prevención, detección, y recuperación. También es necesario considerar factores como que hay sistemas en los que permitir un bloqueo es inaceptable y catastrófico, y sistemas en los que la detección del bloqueo es demasiado costosa.
   
   En el caso específico de las bases de datos distribuidas usar bloqueo de recursos, peticiones para probar, establecer o liberar bloqueos requiere mensajes entre los maneja dores de transacciones y el calenda rizador  Para esto existen dos formas básicas:
   

   • Autónoma: cada nodo es responsable por sus propios bloqueos de recursos.
     • Una transacción sobre un elemento con n replicas requiere 5n mensajes
     • Petición del recurso
     • Aprobación de la petición
     • Mensaje de la transacción
     • Reconocimientos de transacción exitosa
     • Peticiones de liberación de recursos
   • Copia Primaria: un nodo primario es responsable para todos los bloqueos de recursos
     • Una transacción sobre un elemento con n copias requiere 2n+3 mensajes
     • Una petición del recurso
     • Una aprobación de la petición
     • n mensajes de la transacción
     • n reconocimientos de transacción exitosa
     • Una petición de liberación de recurso

   Podemos definir que dos operaciones entran en conflicto que debe ser resuelto si ambas acceden a la misma data, y una de ellas es de escritura y si fueron realizadas por transacciones distintas.
   
   
   
   
   
   
   
   
   
   
   
   

   ALGORITMOS BASADOS EN MARCAS DE TIEMPO

   A diferencia de los algoritmos basados en candados, los algoritmos basados en marcas de tiempo no pretenden mantener la seriabilidad por la exclusión mutua. 

   
   

   En su lugar eligen un orden de serializacion en primera instancia y ejecutan las transacciones de acuerdo a ese orden.       En estos algoritmos cada transacción lleva asociada una marca de tiempo. Cada dato lleva asociado dos marcas de tiempo: uno de lectura y otro de escritura, que reflejan la marca de tiempo de la transacción que hizo la ultima operación de ese tipo sobre el dato.                         

   
   

       Para leer la marca de tiempo de escritura del dato, debe ser menor que el de la transacción, si no aborta. Para escribir las marcas de tiempo de escritura y lectura del dato, deben ser menores que el de la transacción, sino se aborta.                                                                                        Esta técnica esta libre de Ínterbloqueos pero puede darse que halla que repetir varias veces la transacción. En los sistemas distribuidos se puede usar un mecanismo como, los relojes de Lamport para asignar marcas de tiempo.    

   
   

   
   

   
   

   
   

   Los algoritmos basados en estampas de tiempo no pretenden mantener la seriabilidad por exclusión mutua. En lugar de eso, ellos seleccionan un ordende serialización a prioridad y ejecutan las transacciones, de acuerdo a ellas. Para establecer este ordenamiento, el administrador de transacciones le asigna a cada transacción T1 una estampa de tiempo única t1 (T1) cuando ésta inicia.Una estampa de tiempo es un identificador simple que sirve para identificar cada transacción de manera única.

   
   

   
   

   Pruebas de validación optimistas

   
   

   

   
   

   
   

   
   

   
   

   
   

   
   

   

   
   

   
   

   
   

   
   

   
   

   
   

   
   

   
   

                          

actividad 17

Un SGBD se dice transaccional, si es capaz de mantener la integridad de los datos, haciendo que estas transacciones no puedan finalizar en un estado intermedio.

 Cuando por alguna causa el sistema debe cancelar la transacción, empieza a deshacer las órdenes ejecutadas hasta dejar la base de datos en su estado inicial (llamado punto de integridad), como si la orden de la transacción nunca se hubiese realizado.

Para esto, el lenguaje de consulta de datos SQL (Structured Query Language), provee los mecanismos para especificar que un conjunto de acciones deben constituir una transacción.

• BEGIN TRAN: Especifica que va a empezar una transacción.
• COMMIT TRAN: Le indica al motor que puede considerar la transacción completada con éxito.
• ROLLBACK TRAN: Indica que se ha alcanzado un fallo y que debe restablecer la base al punto de integridad.

En un sistema ideal, las transacciones deberían garantizar todas las propiedades ACID; en la práctica, a veces alguna de estas propiedades se simplifica o debilita con vistas a obtener un mejor rendimiento.

Transacciones planas: Consisten en una secuencia de operaciones primitivas encerradas entre las palabras clave BEGIN  y END

Transacciones Anidadas: Consiste en tener transacciones que dependen de otras, estas transacciones están incluidas dentro de otras de un nivel superior y se las conoce como subtransacciones. La transacción de nivel superior puede producir hijos (subtransacciones) que hagan más fácil la programación del sistema y mejoras del desempeño.

Estados de una Transacción

• Transacción Activa: se encuentra en este estado justo después de iniciar su ejecución.
• Transacción Parcialmente Confirmada: en este punto, se efectúan diferentes operaciones de verificación para asegurar que la transacción no interfiera con otras transacciones en ejecución.
• Transacción Confirmada: Ha concluido su ejecución con éxito.
• Transacción Fallida: En este caso, es posible que la transacción deba ser cancelada.
• Transacción Terminada: indica que la transacción a abandonado el sistema.

Planificaciones

• Conservar el orden de la transacción.
• P1 y P2 son secuénciales.
• N! Plantaciones válidas para N transacciones.
• No consistencia
• Dejar concurrencia al SO.
• Se puede asegurar la consistencia.
• Secuencialidad
• El sistema debe controlar la ejecución concurrente de las transacciones para asegurar que el estado de la base sigue siendo consistente.

Planificaciones que aseguran consistencia

• Se debe tener en cuenta:
• No se verifican todas las instrucciones, sólo las operaciones de lectura y de escritura de la base de datos.
• Cuando se poseen operaciones secuenciales de lectura y de escritura en el mismo punto de la base de datos entonces la planificación puede generar inconsistencias.
• La mejor forma de asegurar planificaciones correctas es asegurando las equivalencias de planificación y esto se logra con dos posibles técnicas: Secuencialidad en cuanto a conflictos y Secuencialidad en cuanto a vistas.

PRESENTACION

https://drive.google.com/file/d/0Bz6Cr7bOrFk7aTMxaFBsVlpraXc/view?usp=sharing