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.