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