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.
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.
No hay comentarios.:
Publicar un comentario