Actividad #18

Algoritmos de Control de Concurrencia

CONTROL DE CONCURRENCIA

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

Algoritmos de control de concurrencia

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

Basados en Bloqueos

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 (rl), también llamados compartidos, o de escritura (wl), también llamados exclusivos. 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.

	rl	wl
rl	Si	No
Wl	No	No

En sistemas basados en candados, el despachador es un administrador de candados (LM). 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 accesado y el identificador de la transacción que está enviando la operación a la base de datos. El administrador de candados verifica si el elemento de datos que se quiere accesar ya ha sido bloqueado por un candado. Si candado solicitado es incompatible con el candado con que el dato está bloqueado, entonces, la transacción solicitante es retrasada. De otra forma, el candado se define sobre el dato en el modo deseado y la operación a la base de datos es transferida al procesador de datos. El administrador de transacciones es informado luego sobre el resultado de la operación. La terminación de una transacción libera todos los candados y se puede iniciar otra transacción que estaba esperando el acceso al mismo dato.

Basado en Estampas de Tiempo

Protocolo de marcas de tiempo (timestamp protocols) Su objetivo es ordenar las transacciones globalmente de manera que transacciones con una marca de tiempo menor, obtengan la prioridad en el caso de conflicto.

Estampas de tiempo: son valores derivados de un dominio totalmente ordenado.

Identificador de nodo: se agrega en la posición menos significativa, de manera que, éste 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 también una estampa de tiempo a todas las operaciones solicitadas por una transacción.

Dado este orden, un conflicto entre operaciones se puede resolver de la siguiente forma:

for Ri(x) do begin if ts(Ti) < wts( x ) then reject Ri(x) else accept Ri(x) rts(x) ¬ ts(Ti) end for Wi(x) do begin if ts(Ti) < rts(x) and ts(Ti) < wts(x) then reject Wi(x) else accept Wi(x) wts(x) ¬ ts(Ti) end Ordenamiento básico (conservador) por estampas de tiempo: trata de ejecutar una operación tan pronto como se recibe una operación. Así, la ejecución de las operaciones es progresiva pero pueden presentar muchos reinicios de transacciones.

Ordenamiento conservador de estampas de tiempo: retrasa cada operación hasta que exista la seguridad de que no será reiniciada.

Ordenamiento por estampas de tiempo múltiples

Estrategias para prevenir la formación de interbloqueos: Al hacer una operación de escritura, no se modifican los valores actuales sino se crean nuevos valores.

Estrategias Para crear copias únicas de acuerdo al tipo de operación de que se trate:

1.Una operación de lectura Ri(x): se traduce a una operación de lectura de x de una sola versión encontrando la versión de x, digamos xv.

2. Una operación de escritura: Wi(x) se traduce en una sola version, Wi(xw), y es aceptada si el despachador no ha procesado cualquier lectura Rj(xr).

Pruebas de Validación Optimistas

Los Algoritmos de control de concurrencia discutidos antes son por naturaleza pesimistas.

Algoritmos optimistas: 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.