CONTROL DE CONCURRENCIA

ALGORITMO DE ESTAMPAS DE TIEMPO DISTRIBUIDO

 *DESCRIPCIÓN GENERAL

En un sistema distribuido, cada transaccion debe tener una estampilla de tiempo unica para usar en la

decision del orden de serializabilidad. Para la generacion de estampillas unicas, 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 podria generar estampillas de tiempo a mayor

velocidad que otros sitios. En ese caso, las estampillas de tiempo generadas por el sitio mas rapido seran

mayores que las generadas por otros sitios. Esto se evita si cada sitio utiliza un reloj logico,

implementado mediante un contador que se incrementa cada vez que se genera una nueva estampilla de

tiempo local. Para sincronizar los relojes logicos, se requiere que cada sitio Si avance su reloj logico

cuando arriba una nueva transaccion a ese sitio.

A diferencia de los algoritmos basados en candados, los algoritmos basados en estampas de tiempo no

pretenden mantener la seriabilidad por exclusion mutua. En lugar de eso, ellos seleccionan un orden de

serializacion a priori y ejecutan las transacciones de acuerdo a ellas. Para establecer este ordenamiento, el

administrador de transacciones le asigna a cada transaccion

Ti una estampa de tiempo unica ts( Ti )

cuando esta inicia. Una

estampa de tiempo es un identificador simple que sirve para identificar cadatransaccion de manera unica.

*CARACTERÍSTICAS

Existen varias formas en que las estampas de tiempo se pueden asignar. Un metodo es usar un contador

global monotonicamente creciente. Sin embargo, el mantenimiento de contadores globales es un

problema en sistemas distribuidos. Por lo tanto, es preferible que cada nodo asigne de manera autonoma

las estampas de tiempos basandose en un contador local. Para obtener la unicidad, cada nodo le agrega

al contador su propio identificador. Asi, la estampa de tiempo es un par de la forma

<contador local, identificador de nodo>

Note que el identificador de nodo se agrega en la posicion menos significativa, de manera que, este sirve

solo en el caso en que dos nodos diferentes le asignen el mismo contador local a dos transacciones

diferentes.

El administrador de transacciones asigna tambien una estampa de tiempo a todas las operaciones

solicitadas por una transaccion. Mas aun, a cada elemento de datos x se le asigna una estampa de tiempo

de escritura, wts(x), y una estampa de tiempo de lectura, rts(x); sus valores indican la estampa de tiempo

mas grande para cualquier lectura y escritura de x, respectivamente.

Regla TO

: dadas dos operaciones en conflicto, Oij  y Okl, perteneciendo a las transacciones Ti  y Tk, respectivamente,

Oij es ejecutada antes de Okl, si y solamente si, ts  ( Ti  ) < ts  (Tk ). En este caso Ti  se dice ser un transacción más vieja  yTk se dice ser  una              transacciónmás joven .

.

ALGORITMO DE CONTROL DE CONCURRENCIA BASADOS EN EL BLOQUEO.

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

Pruebas de validación optimistas.