metodos de control de concurrencia

Salvador Jesús Romero Castellano

Métodos de Control de Concurrencia en Bases de DatosSalvador Jesús Romero Castellano

14 de Enero de 2005

ResumenEl objetivo de los métodos de control de concurrencia es garantizar la no inferencia o la

propiedad de aislamiento de transacciones que se ejecutan de manera concurrente. Los distintosobjetivos atacan el problema garantizando que las transacciones se ejecuten en un plan que seaserializable, es decir, que el resultado sea equivalente a el resultante de ejecutar un plan en serie.

Este documento analiza los tres grandes grupos de métodos y protocolos (de bloqueo, demarcas de tiempo y optimistas), haciendo especial énfasis en las ventajas e inconvenientes de usarunos u otros.

Contenidos1. Protocolos basados en técnicas de bloqueo

1. Bloqueos binarios1. Usando bloqueos binarios

2. Bloqueos de lectura/escritura3. Protocolo de bloqueo en dos fases

1. Bloqueo en dos fases básico, conservador, estricto y riguroso1. Conservador o estático2. Estricto3. Riguroso

2. Problemas del bloqueo en dos fases: Interbloqueo y espera indefinida1. Protocolos de prevención de interbloqueo2. Detección del interbloqueo3. Espera indefinida

2. Protocolos de ordenación por marcas de tiempos1. Ordenación básica2. Regla de escritura de Thomas3. Ordenamiento estricto o conservador

3. Protocolos de control multiversión1. Protocolo de ordenación por marcas de tiempo multiversión2. Protocolo de bloqueo en dos fases multiversión

4. Protocolos de control optimistas

1

Métodos de control de concurrencia

Protocolos basados en técnicas de bloqueo

Cabe destacar antes de comenzar el estudio de los protocolos basados en bloqueos que sonlos más utilizados por los SGBD comerciales. Los demás tienen una alcance más teórico quepráctico.

Un bloqueo es una variable asociada a un elemento de datos de la base de datos, usada pararestringir las operaciones que se pueden aplicar sobre él. Existen varios tipos de bloqueo: binarios(de propiedades limitadas), compartidos, exclusivos (usados en la práctica), y bloqueos decertificación.

Las operaciones sobre bloqueos se deben implementar como secciones críticas, es decir, deforma indivisible; el SGBD no deberá alternar sus instrucciones con otras.

Bloqueos binariosSe caracterizan por tener dos valores posibles; bloqueado y desbloqueado. Cada elemento de

la base de datos tiene un bloqueo distinto. El bloqueo señala si una transacción está operando sobreel elemento o está libre para que se pueda operar con él. De esta manera se impide que dos o mástransacciones estén operando sobre un mismo elemento al mismo tiempo.

La implementación de un bloqueo binario es simple; basta con un vector de la siguienteforma: <referencia al dato bloqueado, booleano, referencia a la transacción que lo bloquea> dondeel booleano es en sí el indicador del bloqueo.

Usando bloqueos binariosCuando se usan bloqueos, una transacción ha de usarlos mediante las funciones

bloquear_elemento y desbloquear_elemento, cumpliendo las siguientes reglas:

1. Una transacción T debe emitir la operación bloquear_elemento(x) antes de que se realicecualquier operación leer_elemento(X) i escribir_elemento(x)

1. Una transacción T debe emitir la operación desbloquear_elemento(X) después de habercompletado todas las operaciones leer_elemento(X) y escribir_elemento(X) en T.

1. Una transacción T no emitirá una operación bloquear_elemento(X) si ya posee el bloqueo delelemento X.

1. Una transacción T no emitirá una operación desbloquear_elemento(X) a menos que ya poseael bloqueo del elemento X.

Bloqueos de lectura/escrituraSon una ampliación de los bloqueos binarios. Tenemos que el bloqueo puede tener tres

posibles posiciones: libre, bloqueado para lectura, y bloqueado para escritura. De esta forma, más deuna transacción puede tener un mismo elemento de datos bloqueado para lectura, pero sólo una paraescritura. Si una transacción quiere escribir en ese elemento, habrá de esperar a que el bloqueoquede libre (cualquiera que sea el tipo de bloqueo), y a continuación, bloquearlo para escritura. Siquiere leer, sólo tendrá que esperar si el elemento está bloqueado para escritura. Se dice por tanto,que el bloqueo de lectura es compartido y el de escritura exclusivo. Tendremos por tanto tresoperaciones; bloquear_escritura(X), bloquear_lectura(X) y desbloquear(X).

2


El sistema debe hacer cumplir las siguientes reglas para usar los bloqueos delectura/escritura:

1. Una transacción T debe emitir la operación bloquear_lectura(x) o bloquear_escritura(X) antesde que se realice cualquier operación leer_elemento(X) de T.

1. Una transacción T debe emitir la operación bloquear_escritura(X) antes de que realicecualquier operación escribir_elemento(X) de T.

1. Una transacción T debe emitir la operación desbloquear(X) una vez que se hayan completadotodas las operaciones leer_elemento(X) y escribir_elemento(X) de T.

1. Una transacción T no emitirá una operación bloquear_lectura(X) si ya posee un bloqueo delectura (compartido) o de escritura (exclusivo) para el elemento X.

1. Una transacción T no emitirá una operación bloquear_escritura(X) si ya posee un bloqueo delectura (compartido) o de escritura (exclusivo) para el elemento X.

1. Una transacción T no emitirá una operación desbloquear(X) a menos que ya posea algún tipode bloqueo sobre el elemento X.

Las reglas 4 y 5 se pueden relajar, admitiendo que una transacción que tenga bloqueado unelemento en modo lectura, lo pueda bloquear en modo escritura, si no existe ninguna otratransacción que lo tenga bloqueado. Así mismo, si lo tiene bloqueado en escritura, puede relajar elbloqueo a lectura.

Protocolo de bloqueo en dos fasesEn él, todas las operaciones de bloqueo preceden a la primera operación de desbloqueo de la

transacción. El proceso se puede así dividir en dos fases; la fase de bloqueo y de desbloqueo. Si sepermite la conversión entre bloqueos, las conversiones de bloqueos de lectura a bloqueos deescritura son en la primera fase y las de bloqueos de escritura a lectura en la segunda.

Su principal ventaja es que garantiza la seriabilidad, lo que no se consigue usandosimplemente bloqueos.

Como inconvenientes podemos citar varios:• Bloquea los elementos que podrían ser desbloqueados tras su uso ocupados hasta la segunda fase,

impidiendo que otras transacciones que los necesiten los utilicen. Esto hace que el rendimientode este protocolo se degrade conforme aumenta el grado de concurrencia;

• No permite todos los planes serializables posibles.• La implementación de este este bloqueo depende del programador, que puede no realizar su tarea

convenientemente.

Bloqueo en dos fases básico, conservador, estricto y rigurosoSon variaciones del bloqueo en dos fases. Se detallan a continuación:

Conservador o estáticoRequiere que una transacción bloquee todos los elementos a los que tendrá acceso antes de

3


comenzar a ejecutarse. Una vez bloqueados, no habrá conversión de bloqueos de lectura a escritura.Si no es posible bloquearlos todos, la transacción no bloqueará nada y esperará a poder bloqueartodos los elementos necesarios en su totalidad.

Su principal ventaja es que no sólo garantiza la seriabilidad, sino que evita el interbloqueode transacciones.

Como principal inconveniente señalaremos que, en la práctica, es muy difícil saber quéelementos serán necesarios durante la transacción antes de que esta comience, si no imposible.

También es interesante destacar que, al tener que esperar a poder bloquear todos loselementos que la transacción necesite, este protocolo reduce la concurrencia.

EstrictoLa transacción no libera ninguno de sus bloqueos de escritura antes de confirmarse o

abortar.Este tipo de bloqueo garantiza planes estrictos en cuanto a recuperabilidad (recuperable es

un plan que, una vez confirmada la transacción, no será necesaria deshacerla). Sin embargo, puedesufrir interbloqueos.

RigurosoEs una versión más restrictiva del estricto. Similar al anterior, pero además tampoco libera

los bloqueos de lectura. Es más fácil de implementar.

Problemas del bloqueo en dos fases: interbloqueo y espera indefinidaEl interbloqueo se produce cuando cada transacción T en un conjunto de dos o más

transacciones está esperando a algún elemento que está bloqueado por alguna otra transacción T' dedicho conjunto. En este estado, cada transacción está parada en espera a que otra transacción libereel recurso. Las condiciones para que se produzca en interbloqueo son las siguientes:

1. Exclusión mutua. Cada elemento está bloqueado por una transacción, o está libre.2. Retención y espera: Una transacción que ya tiene elementos bloqueados puede solicitar un

elemento adicional, y esperar que se le asigne, sin devolver previamente ninguno de losanteriores.

3. No apropiación: Sólo puede liberar un elemento la transacción que lo tiene asignado; no se lopuede quitar otra transacción que tenga mayor prioridad, ni el SGBD.

4. Espera circular: Existe una cadena circular, compuesta por dos transacciones o más, y otrostantos elementos intercalados, de manera que cada proceso está esperando que se le asigne unelemento, el cual, a su vez, está asignado al siguiente proceso de la cadena.

El tratamiento del interbloqueo está orientado bien a prevenirlo, bien a detectarlo y evitarlo.

Protocolos de prevención de interbloqueoEstos protocolos no se emplean en la práctica, ya sea debido a suposiciones poco realistas, o

una posible sobrecarga del sistema. Esto no sólo es válido para las bases de datos; en los sistemasoperativos el coste de la detección en los casos de los sistemas para PC o similares y el de la

4


prevención en casi todos, hace que no se haga nada para tratarlo, circunstancia con la que tenemosque enfrentarnos a menudo, y que solemos resolver matando un programa.

El primer protocolo, el bloqueo en dos fases conservador, ya lo hemos visto y comentado.Un segundo protocolo, que también limita la concurrencia, consiste en ordenar todos los elementosde la base de datos y asegurarse de que una transacción que necesite varios elementos los bloquearásegún ese orden. Su inconveniente es que obliga al programador a conocer la manera en que estánordenados estos elementos.

Otros métodos para evitar el interbloqueo se basan en una 'marca de tiempo detransacción', que es un identificador único asignado a la transacción que ayuda a ordenar lastransacciones temporalmente, según el orden en que han sido iniciadas. Mediante estas marcas sedecide si una transacción que se encuentre en posible situación de interbloqueo debe esperar,abortar, o hacer que otra transacción aborte.

Hay dos enfoques, conocidos como esperar-morir y herir-esperar. Suponiendo que unatransacción A intenta bloquear una elemento X bloqueado por una transacción B, en el primerenfoque, si A es más antigua que B espera a que B libere X. En caso contrario, A aborta y vuelve areiniciar con la misma marca de tiempo. En el enfoque herir-esperar si A es más antigua que Bentonces B aborta. En caso contrario, A espera a que B acabe. Estos algoritmos tienen la virtud deevitar la espera indefinida (comentada más adelante).

El algoritmo de no-espera consiste en que si una transacción no consigue un bloqueo, abortay se reinicia tras un lapso de tiempo, aunque no fuera a haber interbloqueo. Las desventajas de estemétodo son evidentes. Para mejorarlo se propone la espera cautelosa, que reduce el número deabortos innecesarios. Supongamos como antes que A trata de bloquear un elemento X ya bloqueadopor B. Si B no está en espera de otro bloqueo, A espera a que B libere X. En caso contrario se abortaA. Este método trata de evitar el interbloqueo atacando a su condición de espera circular.

Otros algoritmos diseñados para evitar bloqueos en espera de recursos compartidosmúltiples, como el algoritmo del banquero, pueden ser aplicados también en este contexto.

Detección del interbloqueoEste enfoque es más práctico, y más interesante si esperamos que haya poca interferencia

entre transacciones. La forma más sencilla y conocida es mediante el grafo de espera detransacciones/elementos. Se tiene que existe interbloqueo si el grafo de espera tiene un ciclo. Elsistema revisa periódicamente este grafo, y si encuentra un ciclo, elige una transacción víctima paraabortarla y así romper el anterior. El inconveniente de este sistema es decidir una política adecuadapara la frecuencia de la comprobación y la selección de víctimas.

Otra solución más sencilla es el uso de tiempos limitados, que presupone que una transacción quelleve en espera un tiempo superior a un tiempo predefinido se encuentra bloqueada, y se procede asu eliminación.

Espera indefinidaEste problema tiene lugar cuando una transacción no puede continuar durante un periodo

indeterminado mientras otras transacciones del sistema continúan con normalidad. La solución a

5


este problema pasa por tener una planificación justa, que impida que algunas de las transacciones'mueran de inanición'.

Protocolos de ordenación por por marcas de tiempoUna marca de tiempo es un identificador único que el SGBD crea para identificar una

transacción, basada en la mayoría de los casos en el momento en que se inician. Se pueden, portanto, ordenar las transacciones cronológicamente según su marca de tiempo.

Este método se basa en marcas de tiempo para ordenar las transacciones. El plan resultantede esta ordenación será equivalente a un plan en serie con las transacciones ordenadas según suspropias marcas de tiempo.

Esto es una diferencia fundamental conforme a los métodos anteriores, en los que los planesserializables lo eran a algún plan serial que se pueda construir con los protocolos de bloqueo (¡queno eran todos los planes seriales posibles!). En este caso sabemos a qué plan serial secorrespondería el plan serializable resultante de aplicar ordenación por marcas de tiempo.

Este sistema asocia a cada elemento un par de variables; marca_lectura y marca_escritura,en las que se escribirá el valor de la marca de tiempo de una transacción que las consulte. De estamanera, la marca_lectura(X) será igual a la marca de tiempo de la última transacción que haya leídocon éxito el elemento X. Ídem para marca_lectura(X).

El método consiste en dejar al sistema organizar las operaciones libremente (no las ordenade forma activa, por tanto), pero al ejecutar una operación, verifica que esta no contradice el ordende seriabilidad. Podríamos decir, por tanto, que es un método optimista.

Existen tres enfoques del método según qué hacer cuando al tratar de hacer una operación sepresenta el conflicto:

Ordenación básicaConsiste en lo siguiente:

Cuando la transacción T emite una operación escribir_elemento(X):-- Si alguna de las marcas de X son mayores que la marca de tiempo de T, entoncesla operación no se lleva a cabo y se aborta T.-- Si no, se procede con normalidad, y se asigna el valor de la marca de tiempo de Ta marca_lectura(X)

Si alguna de las marcas son mayores que la marca de T, significa que una transacciónposterior a T escribió o leyó de X, y por tanto, que T usara el elemento X estaría en contra del ordenpor antigüedad de transacción; la transacción más vieja debería escribir en X antes de que la jovenusara este elemento.

Cuando la transacción T emite una operación leer_elemento(X)Si la marca_escritura(X) es mayor que la marca de tiempo de T, se rechaza laoperación y se aborta y revierte T.Si no, se procede con normalidad, y se asigna a marca_lectura(X) el mayor valorentre la marca de tiempo de T y la marca_lectura(X) actual.

6


En esta ocasión, dado que lo que queremos hacer, leer, no afecta a otras transiciones, sólodebe preocuparnos que una transacción más joven haya escrito en la variable en cuestión.

Al abortar una transacción, se vuelve a introducir en el sistema, con una nueva marca detiempo, para probar suerte como una transacción nueva.

Ventajas: Al ser un método semioptimista, da mejor rendimiento cuando la interacción entrelas transacciones es reducida. Con este método no se puede producir interbloqueo.

Inconvenientes:• Una transacción puede verse sometida a un reinicio cíclico.• Si existe mucha interacción, puede ser muy costoso, al tener que deshacer muchas veces.• Se puede producir una restauración en cascada: Al deshacer una transacción T1, cualquier

transacción T2 que haya utilizado un valor escrito por T1 habrá de deshacerse también, y asísucesivamente.

Regla de escritura de ThomasEs una variante del protocolo anterior diseñada para rechazar menos operaciones de

escritura. Si se va a escribir un elemento que haya sido escrito por una transacción más joven,simplemente se ignora la escritura, obteniendo el mismo efecto como ésta escribiese su valor justodespués de que la transacción que está intentando escribir hubiera escrito su valor, lo que seríaválido. El caso del intento de operación lectura(X) queda por tanto así:

-- Si marca_lectura(X) es mayor que la marca de T, abortar, y deshacer T.-- Si marca_lectura(X) es mayor que la marca de T, ignorar esta operación ycontinuar.-- En otros casos se ejecuta la operación y se asigna a marca_lectura(X) el valor dela marca de lectura de T.

Ordenamiento estricto o conservadorOtra variante del primero. El ordenamiento básico por marcas de tiempo trata de ejecutar

una operación tan pronto como se recibe ésta. Así, la ejecución de las operaciones es progresiva,pero, como hemos como hemos comentado antes, se pueden producir muchos reinicios detransacciones.

En esta variación, una transición que emita una operación de lectura o escritura tal que lamarca de la transacción es menor que marca_escritura(X), sufre un retraso de su operación hasta quela transacción que escribió el valor de X haya abortado o se haya terminado.

Su principal ventaja, por tanto, es que evita el reinicio y la restauración en cascada.Inconveniente: Al frenar una transacción se daña la concurrencia en general y el rendimiento

de dicha transacción en particular, a expensas de lo que haga la transacción a la que se espera.

7


Protocolos de control multiversiónSe basan en conservan los valores antiguos de un elemento cuando es actualizado. El

mantener varios valores del mismo elemento es lo que da al nombre de estos protocolos.Tener varias versiones de un elemento facilita que algunas operaciones de lectura que no se

llevarían a cabo por protocolos como los anteriores, pueden ser aceptadas si se hacen sobre unaversión más antigua del mismo. De esta manera, al escribir en un elemento, se escribe en una uevaversión, conservando las antiguas o algunas de ellas para otras transacciones más antiguas quepudieran necesitarlas más tarde, evitando así que reinicien.

Protocolo de ordenación por marcas de tiempo multiversiónPara cada elemento X, el sistema guarda varias versiones, X1, X2,...,Xk, teniendo para cada

versión una marca_lectura(Xi), y una marca_escritura(Xi), similares a las marcas utilizadas porotros métodos ya comentados, pero referidos a la versión concreta Xi.

Para asegurar la seriabilidad, usamos dos reglas:1. Si la transacción T emite una operación escribir_elemento(X), tomamos versión de X,

llamémosla Xi, con mayor marca_lectura(X). Si este valor es mayor que la marca detiempo de T, abortamos y deshacemos la transacción. Caso contrario, se crea una nuevaversión de X y se asigna la etiqueta de tiempo de T a sus valores marca_lectura(X) ymarca_escritura(X).

2. Si la transacción T emite una operación leer_elemento(X), se busca la versión Xi que tengasu marca_escritura(Xi) mayor posible pero sin sobrepasar la marca de tiempo de T. Seutiliza este elemento y después asignamos a marca_lectura(Xi) el mayor valor entre lamarca de tiempo de T y el valor que tuviera antes.

La principal ventaja de este método salta a la vista; no hay operación de lectura rechazada,que provoque un reinicio de la transacción.

El principal inconveniente también cae por su propio peso. El mantener varias versiones deun elemento puede llegar a resultar costoso. En el caso peor, la base de datos puede degenerar enuna base de datos temporal, que sigue la pista a todos los cambios y los momentos en los queocurrieron. Cabe destacar también que en este método, abortar una transacción puede provocar unarestauración en cascada, ya comentada antes.

Protocolo de bloqueo en dos fases multiversiónEs una ampliación del bloqueo en dos fases antes comentado. En esta versión se tienen tres

tipos de bloqueo; los dos anteriores, de escritura y lectura, y uno más, llamado de certificación. Alcontrario que en el bloqueo en dos fases simple, un bloqueo de escritura no impide que otrastransacciones bloqueen otros elementos para lectura. Lo que se hace, en caso de que transacciónbloquee un elemento para lectura, para poder conseguir esto es crear una nueva versión de X,llamémosla X', en la que la transacción bloqueante podrá realizar cuantos cambios quiera, mientraslas demás transacciones seguirán viendo el valor anterior de X para lectura. Es importante señalar,que si bien con este método se pueden realizar una lectura y una escritura simultáneas, sigue sinpoder realizarse dos escrituras al mismo tiempo.

Cuando una transacción que haya bloqueado un elemento para escritura esté lista paraconfirmarse, debe obtener el bloqueo de certificación de X. Ahora sí, el bloqueo de certificación es

8


exclusivo respecto a los otros dos. Una vez lo obtiene, el valor de X pasa a ser el de X', con lo que apartir de ese momento es visible para todas las transacciones.

La novedad de este método con respecto al bloqueo en dos fases ya visto es que permite lalectura a mismo tiempo que la escritura. Sin embargo, una transacción deberá esperar a confirmarsehasta tener los bloqueos de certificación de todos los elementos que ha modificado.

Este esquema evita el aborto en cascada, ya que siempre se leen versiones confirmadas de X.Sin embargo, si permitimos que un bloqueo se convierta en un bloqueo de escritura, tal como yavimos anteriormente para la versión simple de este bloqueo, se puede producir un interbloqueo.

Protocolos de control optimistasLos protocolos anteriores, que podemos clasificar como pesimistas, comprueban que la

operación que la transacción se dispone a hacer es válida antes de modificar el elemento en la basede datos. Los protocolos de control optimistas, por el contrario, presuponen que todas lasoperaciones se van a efectuar en orden correcto, y por tanto no controlan la validez de lasoperaciones realizadas hasta que la transacción termina, en la llamada fase de validación ocertificación.

La forma de implementar estos protocolos para este contexto (transacciones que han de serconfirmadas) es hacer que las transacciones lleven a cabo sus modificaciones en un espacioparticular, al que se han copiado previamente los datos que la transacción vaya a necesitar. Si alfinal del proceso, los datos resultantes son válidos, se pasan del espacio particular a la base de datos.

Con esto tenemos que los protocolos de bloqueo optimistas tienen tres fases biendiferenciadas:• Fase de lectura/ejecución: En ella las transacciones leen cuantos elementos necesiten de la base

de datos, pero realizan las modificaciones en un espacio particular, como ya hemos señalado.• Fase de certificación/validación: Se verifica que los resultados de la transacción no violan la

seriabilidad. De ser así (el resultado no es correcto), la transacción reinicia (como lasmodificaciones eran en un espacio aparte de variables, no hace falta deshacer. Simplemente sedescartan estas variables).

• Fase de escritura/confirmación: Llegados a este punto, aplicamos las actualizaciones de latransacción a la base de datos.

Este protocolo necesita de marcas de tiempo de transacciones, guardar las horas de inicio yterminación de al menos una de las tres fases y además requiere que el sistema mantenga controlsobre los conjuntos de lectura y escritura de cada transacción.

En la fase de validación de la transacción T, el protocolo comprueba que que T no interfiereen ninguna transacción confirmada ni en cualquier otra que actualmente esté en su fase devalidación. La fase de validación consiste por tanto en, para toda otra transacción T', comprobar quese cumplan alguna de estas condiciones:

1. La transacción T' completa su fase de escritura antes de que T inicie su fase de lectura.2. T inicia su fase de lectura después de que T' complete su fase de escritura y el conjunto de

lectura de T no tiene elementos en común con el conjunto de escritura de T'.3. Ni el conjunto de lectura ni el conjunto de escritura de T tienen elementos en común con el

conjunto de lectura de T', y T' completa su fase de lectura antes de que T complete su fase delectura.

9


El control optimista es más rápido y permite mayor grado de paralelismo, al menos, concargas de trabajo bajas o medias. Para cargas altas, aumenta la probabilidad de que se produzca unconflicto, y las cancelaciones e intentos sucesivos causan un incremento apreciable del trabajo.

10

metodos de control de concurrencia

Documents

Transcript of metodos de control de concurrencia