Control de Concurrencia

Actividad: Investigar

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  Martes 13 de Noviembre 

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.

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

ALGORITMOS DE CERRADURA O BASADOS EN CANDADOS

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

En sistemas basados en candados, el despachador es un administrador de candados . 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 el 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.

Se usan cerraduras o candados de lectura o escritura sobre los datos. Para asegurar la secuencialidad se usa un protocolo de dos fases, en la fase de crecimiento de la transacción se establecen los cerrojos y en la fase dedecrecimiento se liberan los cerrojos. Hay que tener en cuenta que se pueden producir ínterbloqueos. En los sistemas distribuidos el nodo que mantiene un dato se encarga normalmente de gestionar los cerrojos sobre el mismo.

             Candados de dos fases :                                                                                                                   En los candados de dos fases una transacción le pone un candado a un objeto antes de usarlo. Cuando un objeto es bloqueado con un candado por otra transacción, la transacción solicitante debe esperar. Cuando una transacción libera un candado, ya no puede solicitar más candados. En la primera fase solicita y adquiere todos los candados sobre los elementos que va a utilizar y en la segunda fase libera los candados obtenidos uno por uno.                                                        

Puede suceder que si una transacción aborta después de liberar un candado, otras transacciones que hayan accesado el mismo elemento de datos aborten también provocando lo que se conoce como abortos en cascada. Para evitar lo anterior, los despachadores para candados de dos fases implementan lo que se conoce como loscandados estrictos de dos fases en los cuales se liberan todos los candados juntos cuando la transacción termina (con compromiso o aborta).

             Candados de dos fases centralizados:                                                                                               En sistemas distribuidos puede que la administración 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 comunicación se presenta entre el administrador de transacciones del nodo en donde se origina la transacción , el administrador de candados en el nodo central y los procesadores de datos  de todos los nodos participantes. Los nodos participantes son todos aquellos en donde la operación se va a llevar a cabo.

Figura E. Comunicación en un administrador centralizado de candados de dos fases.

La crítica más fuerte a los algoritmos centralizados es el "cuello de botella" que se forma alrededor del nodo central reduciendo los tiempos de respuesta de todo el sistema. Su disponibilidad es reducida a cero cuando se presentan fallas en el nodo central.

  Candados de dos fases distribuidos:

En los candados de dos fases distribuidos se presentan despachadores en cada nodo del sistema. Cada despachador maneja las solicitudes de candados para los datos en ese nodo. Una transacción puede leer cualquiera de las copias replicada del elemento x, obteniendo un candado de lectura en cualquiera de las copias de x. La escritura sobre x requiere que se obtengan candados para todas las copias de x. Los mensajes de solicitud de candados se envían a todos los administradores de candados que participan en el sistema. Las operaciones son pasadas a los procesadores de datos por los administradores de candados. Los procesadores de datos envían su mensaje de "fin de operación" al administrador de transacciones coordinador

Figura F. Comunicación en candados de dos fases distribuidos

CONTROL OPTIMISTA DE LA CONCURRENCIA

Los algoritmos de control de concurrencia pesimistas asumen que los conflictos entre transacciones son muy frecuentes y no permiten el acceso a un dato si existe una transacción conflictiva que accesa el mismo dato. Así, la ejecución de cualquier operación de una transacción sigue la secuencia de fases: validación , lectura , cómputo  y escritura  (ver Figura G). Los algoritmos optimistas, por otra parte, retrasan la fase de validación justo antes de la fase de escritura (ver Figura G). De esta manera, una operación sometida a un despachador optimista nunca es retrasada.

Las operaciones de lectura, cómputo y escritura  de cada transacción se procesan libremente sin actualizar la base de datos corriente. Cada transacción inicialmente hace sus cambios en copias locales de los datos. La fase de validación consiste en verificar si esas actualizaciones conservan la consistencia de la base de datos. Si la respuesta es positiva, los cambios se hacen globales (escritos en la base de datos corriente). De otra manera, la transacción es abortada y tiene que reiniciar

Lo que se hace es dejar ejecutar las transacciones y si al terminar se detecta que ha habido conflicto se aborta y se reinicia la transacción.

            Cada transacción tiene tres fases:.

< Fase de lectura:                                                                                                                  Cuerpo de la transacción donde se copian datos desde la base de datos, copias que pueden ser actualizadas pero sin copiar a la base de datos 

                        < Fase de validación:                                                                                                                        Se comprueba que no existan conflictos

                        < Fase de escritura:                                                                                                                           Si no existen conflictos se instalan lo cambios en la base de datos

Conflictos entre operaciones:                                                                                                         Dos operaciones están en conflicto entre si cuando, operan sobre los mismos datos, una de las operaciones es de escritura, o cada operación pertenece a diferentes transacciones.

           Figura G. Fases de la ejecución de una transacción a) pesimista, b) optimista

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.    

                       

CONTROL DE CONCURRENCIA EN SISTEMAS DE ARCHIVOS  DISTRIBUIDOS

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.

Abrazos mortales:

Principalmente, existen dos métodos para manejar el problema de los abrazos mortales. Podemos usar algún protocolo para asegurar que el sistema nunca entrará en un estado de abrazo mortal. Alternativamente, podemos permitir que el sistema entre en un estado de abrazo mortal y después recuperarnos. El recuperarse de un abrazo mortal puede ser muy difícil y muy caro. Por ello, primeramente consideraremos los métodos para asegurar que no ocurran los abrazos mortales. Comúnmente, existen dos métodos. El de PREVENCIÓN de abrazos mortales y el de EVASIÓN de abrazos mortales. Un conjunto de procesos está en un abrazo mortal cuando todos los procesos en ese conjunto están esperando un evento que sólo puede ser causado por otro proceso en el conjunto. Los eventos a los cuales nos estamos refiriendo son
concernientes con la asignación y liberación de recursos principalmente. Sin embargo,  pueden llevar a la
existencia de abrazos mortales.

Para ejemplificar un estado de abrazo mortal, se considerara un sistema con tres unidades de disco. Supongamos que existen tres procesos, cada uno de ellos tiene asignada una de las unidades de disco. Si ahora cada proceso pide otra unidad de disco, los tres procesos se encuentran ahora en un estado de abrazo mortal. Cada uno esta esperando el evento "unidad de disco liberada", lo cual solo puede ser causada por alguno de los otros procesos en espera. Este ejemplo ilustra un abrazo mortal involucrando procesos compitiendo por el mismo tipo de recurso. Los abrazos mortales pueden también involucrar diferentes tipos de recursos. Por ejemplo, consideremos un sistema con una impresora y una unidad de disco. Supongamos que el proceso A tiene asignada la unidad de disco y que el proceso B tiene asignada la impresora. Ahora, si A pide la impresora y B pide la unidad de disco, ocurre un abrazo mortal.

  

Ejemplo de un abrazo mortal.

Es obvio que un abrazo mortal es una condición indeseable. En un abrazo mortal, los procesos nunca terminan de ejecutarse y los recursos del sistema están amarrados, evitando que otros procesos puedan siquiera empezar.  

 Condiciones Necesarias . Una situación de abrazo mortal puede surgir sí y solo sí las siguientes cuatro condiciones ocurren simultáneamente en un sistema:  

Exclusión Mutua. Cada recurso se asigna por lo regular exactamente a un proceso o bien esta disponible. Al menos un recurso es mantenido en un modo no-compartible;

esto es, sólo un proceso a la vez puede usar el recurso. Si otro proceso solicita ese recurso, tiene que ser retardado hasta que el recurso haya sido liberado.

Retener y Esperar. Los procesos que regularmente contienen recursos otorgados antes pueden solicitar nuevos recursos. Debe existir un proceso que retenga al menos un recurso y esté esperando para adquirir recursos adicionales que están siendo retenidos por otros procesos.

No existe el derecho de desasignar : Los recursos previamente otorgados no pueden extraerse por la fuerza de un proceso. Deben ser liberados explícitamente por el proceso que los contiene. Los recursos no pueden ser desasignados ; esto es, un recurso sólo puede ser liberado voluntariamente por el proceso que lo retiene, después de que el proceso ha terminado su tarea.

Espera Circular. Debe haber una cadena de dos o más procesos, cada uno de los cuales esté esperando un recurso contenido en el siguiente miembro de la cadena. Debe existir un conjunto {p0, p1, ...,pn} de procesos en espera tal que p0 esté esperando por un recurso que está siendo retenido por p1, p1 está esperando por un recurso que está siendo retenido por p2, ..., pn-1 está esperando por un recurso que está siendo retenido por pn y pn está esperando por un recurso que está siendo retenido por p0.

            Se remarca que las cuatro condiciones deben de cumplirse para que pueda ocurrir un abrazo mortal. La condición de espera circular implica la condición de retener y esperar, de tal manera que las cuatro condiciones no son totalmente independientes. Sin embargo, puede ser útil el considerar cada condición por separado.

Una forma de modelar estas condiciones es usando un grafo de recursos: los círculos representan procesos, los cuadrados recursos. Una arista desde un recurso a un proceso indica que el recurso ha sido asignado al proceso. Una arista desde un proceso a un recurso indica que el proceso ha solicitado el recurso, y está bloqueado esperándolo. Entonces, si hacemos el grafo con todos lo procesos y todos los recursos del sistema y encontramos un ciclo, los procesos en el ciclo están bajo bloqueo mutuo.