Evaluacion 4 Unidad

Actividad # 21

Protocolos 

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, T1 y T2. T1 ha sido concluida (ha realizado su commit) pero T2 no pudo ser concluida.

La propiedad de durabilidad requiere que los efectos de T1 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 T2.

Ejemplo de una falla del sistema

A pesar que T1 haya sido terminada, puede suceder que el buffer correspondiente a la página de la base de datos modificada no haya sido escrito a la base de datos estable. Así, para este caso la recuperación tiene que volver a realizar los cambios hechos por T1. A esta operación se le conoce como REDO.

La operación de REDO utiliza la información del registro de la base de datos y realiza de nuevo las acciones que pudieron haber sido realizadas antes de la falla. La operación REDO genera una nueva imagen.

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

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 y se muestra en la Figura de abajo. 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 # 20

Conceptos básicos de confiabilidad en un ambiente distribuido

Confiabilidad

La confiabilidad es otro requerimiento indiscutible y probablemente el mas importante. Una base de datos no confiable es simplemente inutilizable. Para la mayoria de las aplicaciones empotradas, en especial las empleadas en sistemas de tiempo real, la confiabilidad es una propiedad no negociable que debe tener todos los componentes.

Un siste de manejo de bases de datos confiable es aquel que puede continuar procesando las solicitudes de un usuario aun cuando el sistema soble el que opera no es confiable. En otras palabras aun cuando los componentes de un sistema distribuido falle, un DDBMS confiable debe seguir ejecutando las solicitudes de usuario sin violar la consistencia de la base de datos.

Conceptos basicos de confiabilidad

La confiabilidad engloba varias actividades y una de ellas es el planteamiento de modelos de confiabilidad, esto es fundamentalmente la probabilidad de supervivencia del sistema.

Se expresa como una funcion de las confiabilidades de los componentes o subsistemas, que generalmente, estos modelos se encuentran dependiendo del tiempo.

Candado de dos fases:

En los candados de dos fases una transaccion le pone un candado a un objeto antes de usarlo. Cuando un objeto es bloqueado con un candado por otra transaccion, la transaccion solicitante debe esperar. Cuando una transaccion libera un candado, ya no puede solicitar que va a utilizar y en la segunda fase libera los candados obtenidos uno por uno.

Puede suceder que si una transaccion aborta despues de liberar un candado, otras transacciones que hayan accesado el mismo elemento de datos aborten tambien provocando lo que se conoce como aborto en cascada. Para evitar lo anterior, los despachadoes para candados en 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 transaccion termina (con compromiso o aborta).

Candado de dos fases centralizados:

En sistemas distribuidos puede que la administracion 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. La comunicacion se presenta entre el administrador de transacciones del nodo en donde se origina la transaccion, el administrador de candados en el nodo central y los proesoadores de datos de todos los nodos participantes. 

Actividad # 19

Disciplinas del Interbloqueo

Un interbloqueo se produce cuando dos o más tareas se bloquean entre sí permanentemente teniendo cada tarea un bloqueo en un recurso que las otras tareas intentan bloquear.

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

Por ejemplo:

• La transacción A tiene un bloqueo compartido de la fila 1.
• La transacción B tiene un bloqueo compartido de la fila 2.
• La transacción A ahora solicita un bloqueo exclusivo de la fila 2 y se bloquea hasta que la transacción B finalice y libere el bloqueo compartido que tiene de la fila 2.
• La transacción B ahora solicita un bloqueo exclusivo de la fila 1 y se bloquea hasta que la transacción A finalice y libere el bloqueo compartido que tiene de la fila 1.

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.

      Condicionar un sistema para quitar cualquier posibilidad de ocurrencia de interbloqueo. 

Que no se cumpla una condición necesaria

• “Exclusión mutua” y “sin expropiación” no se pueden relajar. Dependen de carácter intrínseco del recurso.

• Las otras dos condiciones son más prometedoras.

  
  
  
  Deteccion Interbloqueo 
  
  
  Existen diversos algoritmos para ello en la detención de ciclos en el grafo de esperas, entre ellos:
  

  • Algoritmo 1: Comprueba la existencia de ciclos mediante la eliminación de nodos terminales.
  • Algoritmo 2: Comprueba posibles ciclos desde la ultima transacción bloqueada y marcando los nodos por lo que pasa. Si pasa dos veces por el mismo nodo a detectado un ciclo.

  
  

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.

Si éste se encuentra actualizando un archivo, cortarlo a la mitad de la operación puede ocasionar que el archivo quede en un mal estado.

Si se utiliza el método de terminación parcial, entonces, dado un conjunto de procesos bloqueados, debemos determinar cuál proceso o procesos debe terminarse para intentar romper el interbloqueo. Se trata sobre todo de una cuestión económica, debemos abortar los procesos que nos representen el menor costo posible.

Actividad # 18

Algoritmos de Control de Concurrencia

 

CONTROL DE CONCURRENCIA

El control de concurrencia trata con los problemas de aislamiento yconsistencia del procesamiento de transacciones.El control de concurrencia distribuido de una DDBMS asegura que laconsistencia de la base de datos se mantiene en un ambiente distribuidomultiusuario.Si las transacciones son internamente consistentes, la manera más simple delograr este objetivo es ejecutar cada transacción sola, una después de otra.

El criterio de clasificación más común de los algoritmos de control deconcurrencia es el tipo de primitiva de sincronización. Esto resulta en dos clases:

- Aquellos algoritmos que están basados en acceso mutuamente exclusivo adatos compartidos (candados o bloqueos).

- Aquellos que intentar ordenar la ejecución de las transacciones de acuerdo a un conjunto de reglas (protocolos).

Es la actividad de controlar accesos concurrentes a la base de datos, es decir, es la forma en que el DBMS maneja las ejecuciones paralelas en la BD.

Asegura que transacciones multiples sometidas por usuarios diferentes no interfieran unas con otras de forma que se produscan resultados incorrectos.

El control de concurrencia en base de datos distribuidas es mas compleja que en sistemas centralizados. Un aspecto interesante dl control de concurrencia es el manejo de interbloqueos, el sistema no debe permitir que dos o mas transacciones se bloqueen entre ellas. 

El control de concurrencia trata con dos problemas principales:

1)Aislamiento de transacciones:

Define el grado en que se debe aislar una transaccion de las modificaciones de recursos o datos realizadas por otras transacciones. Los niveles de aislamiento se describen en funcion de los efectos secundarios de la simultaneidad que se permiten, como las lecturas de datos sucios o las lecturas fantasmas.

2)Consistencia del procesamiento  de transacciones: 

La consistencia de una transaccion es simplemente su correctitud. Podria definirse como la coherencia entre todos los datos de la base de datos. La consistencia entre transacciones se garantiza mediante el aislamiento de las mismas. 

Basados en 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 manejadores de transacciones y el calendarizador. 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 n 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.

Bloqueo Mortal

 En aiatemas operativo, el bloqueo mutuo (también conocido como interbloqueo, traba mortal, deadlock, abrazo mortal) es el bloqueo permanente de un conjunto de procesos o hilos de ejecucion en un sistema concurrente que compiten por recursos del sistema o bien se comunican entre ellos. A diferencia de otros problemas de concurrencia de procesos, no existe una solución general para los interbloqueos.

Todos los interbloqueos surgen de necesidades que no pueden ser satisfechas, por parte de dos o más procesos. En la vida real, un ejemplo puede ser el de dos niños que intentan jugar al arco y flecha, uno toma el arco, el otro la flecha. Ninguno puede jugar hasta que alguno libere lo que tomó.

En el siguiente ejemplo, dos procesos compiten por dos recursos que necesitan para funcionar, que sólo pueden ser utilizados por un proceso a la vez. El primer proceso obtiene el permiso de utilizar uno de los recursos (adquiere el lock  sobre ese recurso). El segundo proceso toma el lock del otro recurso, y luego intenta utilizar el recurso ya utilizado por el primer proceso, por lo tanto queda en espera. Cuando el primer proceso a su vez intenta utilizar el otro recurso, se produce un interbloqueo, donde los dos procesos esperan la liberación del recurso que utiliza el otro proceso.

Basados en estampas 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.

  A diferencia de los algoritmos basados en candados, los algoritmos basados en marcas de tiempono pretenden mantener la seriabilidad por la exclusión mutua. En su lugar eligen un orden deserializacion en primera instancia y ejecutan las transacciones de acuerdo a ese orden. Enestos algoritmos cada transacción lleva asociada una marca de tiempo. Cada dato lleva asociadodos marcas de tiempo: uno de lectura y otro de escritura, que reflejan la marca de tiempo de latransacció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 latransacción, sino se aborta. Estatécnica esta libre de Ínterbloqueos pero puede darse que halla que repetir varias veces latransacción. En los sistemas distribuidos se puede usar un mecanismo como, los relojes deLamport para asignar marcas de tiempo.El conjunto de algoritmos pesimistas esta formado por algoritmos basados en candados,algoritmos basados en ordenamiento por estampas de tiempo y algoritmos híbridos. Los algoritmosoptimistas se componen por los algoritmos basados en candados y algoritmos basados enestampas de tiempo.

Control de concurrencia en sistemas de archivos distibudos

Hasta aquí se a hablado sobre el modelo transaccional haciendo hincapié en lo referido a base de datos distribuidas. En adelante se desarrollara como se emplea el control de concurrencia en sistemas distribuidos de archivos Los sistemas de archivos que forman parte de una red de computadoras tienen múltiples clientes de los que encargarse. Si dos o mas clientes, accidentalmente o no, deciden acceder al mismo archivo al mismo tiempo pueden producirse conflictos. La solución utilizada es permitir a los usuarios el uso de bloqueos sobre los archivos de trabajo. La idea es sencilla, mientras un usuario esta trabajando sobre una parte de los datos, otros no podrán hacerlo de manera que las distintas actualizaciones se efectuaran en forma sucesiva y ordenada sin interferencias. Se utilizan dos clases de bloqueos: Los bloqueos compartidos que por lo general se usan para lectura , y los bloqueos exclusivos que normalmente se usan para escritura. La granularidad del bloqueo es otra consideración importante. Es posible bloquear archivos enteros, pero también es posible bloquear archivos enteros o subárboles, cuanto menor sea la unidad lógica bloqueada mayor será la concurrencia admisible. El concepto de bloqueo introduce varios problemas de contrapartida. Primero, si un cliente necesita acceder a varios archivos, como ocurre de forma común cuando se efectúan transferencias de dinero en aplicaciones bancarias, hay una posibilidad de abrazo mortal. 

Pruebas de validacion optimistas 

Algoritmos optimistas: retrasan la fase de validacion justo antes de la fase de escritura. De esta manera, una operacion sometida a un despachador optimista nunca es retrasada.