Algoritmos De Control De Concurrencia

Algoritmos De 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. Sin embargo, esto puede afectar grandemente el desempeño de un DDBMS dado que el nivel de concurrencia se reduce al mínimo. El nivel de concurrencia, el número de transacciones activas, es probablemente el parámetro más importante en sistemas distribuidos. Por lo tanto, los mecanismos de control de concurrencia buscan encontrar un balance entre el mantenimiento de la consistencia de la base de datos y el mantenimiento de un alto nivel de concurrencia.

Si no se hace un adecuado control de concurrencia, se pueden presentar dos anomalías. En primer lugar, se pueden perder actualizaciones provocando que los efectos de algunas transacciones no se reflejen en la base de datos. En segundo término, pueden presentarse recuperaciones de información inconsistentes.

En este capítulo se hace la suposición de que el sistema distribuido es completamente confiable y no experimente falla alguna. En el capítulo siguiente, se considerará la presencia de fallas para obtener sistemas confiables.

6.1 Teoría de la seriabilidad

Una calendarización (schedule), también llamado una historia, se define sobre un conjunto de transacciones T = { T1, T2, …, Tn } y especifica un orden entrelazado de la ejecución de las operaciones de las transacciones. La calendarización puede ser especificada como un orden parcial sobre T.

Ejemplo 6.1. Considere las siguientes tres transacciones:

T1: Read( x )

T2: Write( x )

T3: Read( x )

Write( x )

Write( y )

Read( y )

Commit

Read( z )

Read( z )

Commit

Commit

Una calendarización de las acciones de las tres transacciones anteriores puede ser:

H1 = { W2(x), R1(x), R3(x), W1(x), C1, W2(y), R3(y), R2(z), C2, R3(z), C3 }

¨

Dos operaciones Oij(x) y Okl(x) (i y k no necesariamente distintos) que accesan el mismo dato de la base de datos x se dice que están en conflicto si al menos una de ellas es una escritura. De esta manera, las operaciones de lectura no tienen conflictos consigo mismas. Por tanto, existen dos tipos de conflictos read-write (o write-read) y write-write. Las dos operaciones en conflicto pueden pertenecer a la misma transacción o a transacciones diferentes. En el último caso, se dice que las transacciones tienen conflicto. De manera intuitiva, la existencia de un conflicto entre dos operaciones indica que su orden de ejecución es importante. El orden de dos operaciones de lectura es insignificante.

Una calendarización completa define el orden de ejecución de todas las operaciones en su dominio. Formalmente, una calendarización completa STc definido sobre un conjunto de transacciones T = { T1, T2, …, Tn } es un orden parcial STc = { S T, <T } en donde

   1. S T = U i S i , para todos los i = 1, 2, …, n
   2. <T Ê i <i , para todos los i = 1, 2, …, n
   3. Para cualesquiera dos operaciones en conflicto Oij y Okl Î S T, ó Oij <T Okl ó

Okl <T Oij

La primera condición establece simplemente que el dominio de la calendarización es la unión de los dominios de las transacciones individuales. La segunda condición define la relación de ordenamiento como un superconjunto de la relación de ordenamiento de transacciones individuales. Esto mantiene el ordenamiento de las operaciones dentro de cada transacción. La condición final define el orden de ejecución entre dos operaciones en conflicto.

Ejemplo 6.2. Considere las tres transacciones del Ejemplo 6.1, una posible calendarización completa está dada por la siguiente gráfica dirigida acíclica (DAG).

Una calendarización se define como un prefijo de una calendarización completa. Un prefijo de un orden parcial se define como sigue. Dado un orden parcial P = { S , < }, P� = { S �, <� }, es un prefijo de P si

   1. S � Ì S i
   2. “ ei Î S �, e1 <� e2, si y solamente si, e1 < e2, y
   3. “ ei Î S �, si $ ej Î S y ej < ei, entonces, ej Î S �

Las primeras dos condiciones definen a P� como una restricción de P en el dominio S �, en donde las relaciones de ordenamiento en P se mantienen por P�. La última condición indica que para cualquier elemento de S �, todos sus predecesores en S deben ser incluidos también en S �.

Ejemplo 6.3. La siguiente calendarización es un prefijo de la calendarización del Ejemplo 6.2.

Si en una calendarización S, las operaciones de varias transacciones no están entrelazadas, esto es, si las operaciones de una transacción ocurren de manera consecutiva, entonces se dice que la calendarización es serial. Si cada transacción es consistente (obedece las reglas de integridad), entonces la base de datos se garantiza ser consistente al final de la calendarización serial. La historia asociada a este tipo de calendarización se le conoce como serial.

Ejemplo 6.4. La siguiente es una historia serial para el Ejemplo 6.1.

HS = { W2(x), W2(y), R2(z), C2, R1(x), W1(x), C1, R3(x), R3(y), R3(z), C3 }

Las transacciones se ejecutan de manera concurrente, pero el efecto neto de la historia resultante sobre la base de datos es equivalente a alguna historia serial. Bassada en la relación de precedencia introducida por el orden parcial, es posible discutir la equivalencia de diferentes calendarizaciones con respecto a sus efectos sobre la base de datos.

Dos calendarizaciones, S1 y S2, definidas sobre el mismo conjunto de transacciones T, se dice que son equivalentes si para cada par de operaciones en conflicto Oij y Okl (i ¹ k), cada vez que Oij <1 Okl, entonces, Oij <2 Okl. A esta relación se le conoce como equivalencia de conflictos puesto que define la equivalencia de dos calendarizaciones en término del orden de ejecución relativo de las operaciones en conflicto en ellas.

Una calendarización S se dice que es serializable, si y solamente si, es equivalente por conflictos a una calendarización serial.

Ejemplo 6.5. Las siguientes calendarizaciones no son equivalentes por conflicto:

HS = { W2(x), W2(y), R2(z), C2, R1(x), W1(x), C1, R3(x), R3(y), R3(z), C3 }

H1 = { W2(x), R1(x), R3(x), W1(x), C1, W2(y), R3(y), R2(z), C2, R3(z), C3 }

Las siguientes calendarizaciones son equivalentes por conflictos; por lo tanto H2 es serializable:

HS = { W2(x), W2(y), R2(z), C2, R1(x), W1(x), C1, R3(x), R3(y), R3(z), C3 }

H2 = { W2(x), R1(x), W1(x), C1, R3(x), W2(y), R3(y), R2(z), C2, R3(z), C3 }

La función primaria de un controlador de concurrencia es generar una calendarización serializable para la ejecución de todas las transacciones. El problema es, entonces, desarrollar algoritmos que garanticen que únicamente se generan calendarizaciones serializables.

6.2 Seriabilidad en SMBD distribuidos

En bases de datos distribuidas es necesario considerar dos tipos de historia para poder generar calendarizaciones serializables: la calendarización de la ejecución de transacciones en un nodo conocido como calendarización local y la calendarización global de las transacciones en el sistema. Para que las transacciones globales sean serializables se deben satisfacer las siguientes condiciones:

    * cada historia local debe ser serializable, y

    * dos operaciones en conflicto deben estar en el mismo orden relativo en todas las historias locales donde las operaciones aparecen juntas.

La segunda condición simplemente asegura que el orden de serialización sea el mismo en todos los nodos en donde las transacciones en conflicto se ejecutan juntas.

Ejemplo 6.6. Considere las siguientes tres transacciones:

T1: Read( x )

T2: Read( x )

x ¬ x + 5

x ¬ x * 5

Write( x )

Write( x )

Commit

Commit

Las siguientes historias locales son individualmente serializables (de hecho son seriales), pero las dos transacciones no son globalmente serializables.

LH1 = { R1(x), W1(x), C1, R2(x), W2(x), C2 }

LH2 = { R2(x), W2(x), C2, R1(x), W1(x), C1 }

6.3 Taxonomía de los mecanismos de control de concurrencia

El criterio de clasificación más común de los algoritmos de control de concurrencia es el tipo de primitiva de sincronización. Esto resulta en dos clases: aquellos algoritmos que están basados en acceso mutuamente exclusivo a datos compartidos (candados) y aquellos que intentar ordenar la ejecución de las transacciones de acuerdo a un conjunto de reglas (protocolos). Sin embargo, esas primitivas se pueden usar en algoritmos con dos puntos de vista diferentes: el punto de vista pesimista que considera que muchas transacciones tienen conflictos con otras, o el punto de vista optimista que supone que no se presentan muchos conflictos entre transacciones.

Los algoritmos pesimistas sincronican la ejecución concurrente de las transacciones en su etapa inicial de su ciclo de ejecución. Los algoritmos optimistas retrasan la sincronización de las transacciones hasta su terminación. El grupo de algoritmos pesimistas consiste de algoritmos basados en candados, algoritmos basados en ordenamiento por estampas de tiempo y algoritmos híbridos. El grupo de los algoritmos optimistas se clasifican por basados en candados y basados en estampas de tiempo (Ver. Figura 6.1).

Figura 6.1. Clasificación de los algoritmos de control de concurrencia.

6.4 Algoritmos 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 (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.

Candados de dos fases (2PL)

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. Así una transacción que utiliza candados de dos fases se comporta como en la Figura 6.2. 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.

La importancia de los candados de dos fases es que se ha demostrado de manera teórica que todos las calendarizaciones generadas por algoritmos de control de concurrencia que obedecen a los candados de dos fases son serializables.

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 los candados estrictos de dos fases en los cuales se liberan todos los candados juntos cuando la transacción termina (con commit o aborta). El comportamiento anterior se muestra en la Figura 6.3.

Figura 6.2. Gráfica del uso de los candados de dos fases.

Figura 6.3. Comportamiento de los candados de dos fases estrictos.

6.4.1 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. En la Figura 6.4 se presenta la estructura de la comunicación de un administrador centralizado de candados de dos fases. La comunicación se presenta entre el administrador de transacciones del nodo en donde se origina la transacción (llamado el coordinador TM), el administrador de candados en el nodo central y los procesadores de datos (DP) de todos los nodos participantes. Los nodos participantes

son todos aquellos en donde la operación se va a llevar a cabo.

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

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. Más aún, su disponibilidad es reducida a cero cuando se presentan fallas en el nodo central.

6.4.2 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. La comunicación entre los nodos que cooperan para ejecutar una transacción de acuerdo al protocolo de candados distribuidos de dos fases se presenta en la Figura 6.5. 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ía su mensaje de “fin de operación” al administrador de transacciones coordinador.

6.5 Algoritmos basados en estampas de tiempo

A diferencia de los algoritmos basados en candados, los algoritmos basados en estampas de tiempo no pretenden mantener la seriabilidad por exclusión mutua. En lugar de eso, ellos seleccionan un orden de serialización a priori y ejecutan las transacciones de acuerdo a ellas. Para establecer este ordenamiento, el administrador de transacciones le asigna a cada transacción Ti una estampa de tiempo única ts( Ti ) cuando ésta inicia. Una estampa de tiempo es un identificador simple que sirve para identificar cada transacción de manera única. Otra propiedad de las estampas de tiempo es la monoticidad, esto es, dos estampas de tiempo generadas por el mismo administrador de transacciones deben ser monotonicamente crecientes. Así, las estampas de tiempo son valores derivados de un dominio totalmente ordenado.

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

Existen varias formas en que las estampas de tiempo se pueden asignar. Un método 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 autónoma las estampas de tiempos basándose en un contador local. Para obtener la unicidad, cada nodo le agrega al contador su propio identificador. Así, 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 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. Más aún, 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 más grande para cualquier lectura y escritura de x, respectivamente.

El ordenamiento de estampas de tiempo (TO) se realiza mediante la siguiente regla:

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 y Tk se dice ser una transacción más joven.

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

La acción de rechazar una operación, significa que la transacción que la envió necesita reiniciarse para obtener la estampa de tiempo más reciente del dato e intentar hacer nuevamente la operación sobre el dato.

Ordenamiento conservador por estampas de tiempo

El ordenamiento básico 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. El ordenamiento conservador de estampas de tiempo retrasa cada operación hasta que exista la seguridad de que no será reiniciada. La forma de asegurar lo anterior es sabiendo que ninguna otra operación con una estampa de tiempo menor puede llegar al despachador. Un problema que se puede presentar al retrasar las operaciones es que ésto puede inducir la creación de interbloqueos (deadlocks).

Ordenamiento por estampas de tiempo múltiples

Para prevenir la formación de interbloqueos se puede seguir la estrategia siguiente. Al hacer una operación de escritura, no se modifican los valores actuales sino se crean nuevos valores. Así, puede haber copias múltiples de un dato. Para crear copias únicas se siguen las siguientes estrategias 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, tal que, ts(xv) es la estampa de tiempo más grande que tiene un valor menor a ts(Ti).

   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), tal que,

ts(Ti) < ts(xr) < ts(Tj)

6.6 Control de concurrencia optimista

Los algoritmos de control de concurrencia discutidos antes son por naturaleza pesimistas. En otras palabras, ellos 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 (V), lectura ®, cómputo © y escritura (W) (ver Figura 6.6a). Los algoritmos optimistas, por otra parte, retrasan la fase de validación justo antes de la fase de escritura (ver Figura 6.6b). De esta manera, una operación sometida a un despachador optimista nunca es retrasada.

Las operaciones de lectura, cómputo y escrita 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

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

Los mecanismos optimistas para control de concurrencia fueron propuestos originalmente con el uso de estampas de tiempo. Sin embargo, en este tipo de mecanismos las estampas de tiempo se asocian únicamente con las transacciones, no con los datos. Más aún, las estampas de tiempo no se asignan al inicio de una transacción sino justamente al inicio de su fase de validación. Esto se debe a que las estampas se requieren únicamente durante la fase de validación.

Cada transacción Ti se subdivide en varias subtransacciones, cada una de las cuales se puede ejecutar en nodos diferentes. Sea Tij una subtransacción de Ti que se ejecuta en el nodo j. Supongamos que las transacciones se ejecutan de manera independiente y ellas alcanzan el fin de sus fases de lectura. A todas las subtransacciones se les asigna una estampa de tiempo al final de su fase de lectura. Durante la fase de validación se realiza una prueba de validación, si una transacción falla, todas las transacciones se rechazan.

La prueba de validación se realiza con una de las siguientes reglas:

   1. Si todas las transacciones Tk, tales que, ts( Tk ) < ts( Tij ), han terminado su fase de escritura antes que Tij ha iniciado su fase de lectura entonces la validación tiene éxito. En este caso la ejecución de las transacciones es completamente serial como se muestra en la Figura 6.7a.

   2. Si existe alguna transacción Tk, tal que, ts( Tk ) < ts( Tij ) y la cual completa su fase de escritura mientras Tij está en su fase de lectura, entonces, la validación tiene éxito si WS(Tk ) Ç RS(Tij ) = Æ . En este caso, las fases de lectura y escritura se traslapan, como se muestra en la Figura 6.7b, pero Tij no lee datos queson escritos por Tk.

   3. Si existe alguna transacción Tk, tal que, ts( Tk ) < ts( Tij ) y la cual completa su fase de lectura antes que Tij termine su fase de lectura, entonces, la validación tiene éxito si WS(Tk ) Ç RS(Tij ) = Æ y WS(Tk ) Ç WS(Tij ) = Æ . En este caso, las fases de lectura se traslapan, como se muestra en la Figura 6.7c, pero las transacciones no accesan datos comunes.

Figura 6.7. Casos diferentes de las pruebas de validación para control de concurrencia optimista.


Mis sitios nuevos:
Emprendedores
Politica de Privacidad