miércoles, 21 de enero de 2009
INTRODUCCIÓN.
En este presente resumen se ve a conocer lo que es concurrencia. Cuando se ejecutan varias transacciones en la base de datos, se puede considerar dejar la propiedad de aislamiento. En varias ocasiones es llevar el control de todas las transacciones a través de esquemas de control de concurrencia.
Todos estos esquemas se describen a continuación, aquí se basan en la propiedad de secuencialidad.
PROTOCOLOS BÁSICOS EN EL BLOQUEO
Una forma de asegurar la secuencialidas es exigir que el acceso a los elementos de datos se haga en exclusión mutua; es decir, mientras una transacción accede a un elemento de datos, ninguna otra transacción puede modificar dicho elemento.
BLOQUEOS.
Existen muchos modos mediante los cuales se puede bloquear un elemento de datos.
1. Compartido. Si una transacción T obtiene un bloqueo en modo compartido (denotado por C) sobre le elemento Q, entonces T puede leer Q pero no escribir.
2. Exclusivo. Si una transacción T obtiene un bloqueo en modo exclusivo (denotado por X) sobre el elemento Q, entonces T puede tanto leer como escribir Q.
Es necesario que toda transacción solicite un bloqueo del modo apropiado sobre el elemento de datos Q dependiendo de los tipos de operaciones que se vayan a realizar sobre Q. La petición se hace al gestor se control de concurrencia. La transacción puede realizar la operación solo después de que el gestor de control de concurrencia conceda el bloqueo a la transacción.
.
Una transacción solicita un bloqueo compartido sobre el elemento de datos Q a través de la instrucción bloquear-C (Q). De forma similar se solicita un bloqueo exclusivo a través de la instrucción bloquear-X (Q). Se puede desbloquear un elemento de datos Q por medio de la instrucción desbloquear (Q).
Leer(B);
B:=B-50
Transacción T1
Escribir(B);
Desbloquear (B);
Bloquear-X(A);
Leer(A);
A:= A+50;
Escribir(A);
Desbloquear
Bloquear-C(A);
Leer(A);
Transacción T2
Desbloquear(A);
Bloquear-C(B);
Leer(B);
Desbloquear(B);
Visualizar (A+B).
Transacción T2
Se exige en toda transacción del sistema siga un conjunto de reglas llamado protocolo de bloqueo, que indica el momento en que una transacción puede bloquear y desbloquear cada uno de los elementos de datos. Los protocolos de bloqueo restringen el número de planificaciones posibles. El conjunto de tales planificaciones es un subconjunto propio de todas las planeaciones secuenciales posibles.
Bloquear-X(B);
Leer(B);
Transacción T3
B:=B-50;
Escribir(B);
Bloquear-X(A);
Leer(A);
A:=A-50;
Desbloquear(B);
Desbloquear(A).
Se dice que una planificación S es lega bajo un protocolo de bloqueo dado si S es una planificación posible para un subconjunto de transacciones que sigan las reglas de protocolo de bloqueos. Se dice que un protocolo asegura la secuencialidad en cuanto a conflictos si y solo si todas las planificaciones legales son secuenciables en cuanto a conflictos; en otras palabras, para todas las planificaciones legales la relación àasocia es a cíclica.
Bloquear-C(A);
Transacción T4
Leer(A);
Bloquear-C(B);
Leer(B);
Visualizar(A+B);
Desbloquear (A);
Desbloquear (B).
CONCESIÓN DE BLOQUEOS.
Cuando una transacción solicita un bloqueo de un modo particular sobre un elemento de datos y ninguna otra transacción posee un bloqueo sobre el mismo elemento de datos en un modo conflictivo, se puede conceder el bloqueo.
Se puede evitar la inanición de las transacciones al conceder los bloqueos de la siguiente manera: cuando una transacción T 1 solicita un bloqueo sobre un elemento de datos Q en un modo particular M, el gestor de control de concurrencia concede el bloqueo siempre que
1. No exista un transacción que posea un bloqueo sobre Q en un modo que este en conflicto con M.
2. No exista otra transacción que este esperando un bloqueo sobre Q y que lo haya solicitado antes que T.
De este modo, una partición de bloqueo nunca se quedara bloqueada por otra petición de bloqueo solicitada mas tarde.
PROTOCOLOS DE BLOQUEO EN DOS FASES.
Un protocolo que asegura la secuencialidad es el protocolo de bloqueos de dos fases. Este protocolo exige que cada transacción realice las peticiones de bloqueo y desbloqueo de dos fases:
1. Fase de crecimiento. Una transacción puede obtener bloqueos pero no puede liberarlos.
2. Fase de decrecimiento. Una transacción puede liberar bloqueos pero no puede obtener ninguno nuevo.
Inicialmente una transacción esta en la fase de crecimiento. La transacción adquiere los bloqueos que necesite. Una ves que la transacción libera un bloqueo, entra en la fase de decrecimiento y no puede realizar mas peticione de bloqueo.
Se pude mostrar que el protocolo de bloqueo de dos fases asegura la secuencialidad en cuanto a conflictos. Considérese cualquier transacción. Le punto de la planificación en el cual la transacción obtiene su bloqueo final (el final de la fase de crecimiento) se denomina punto de bloqueo de la transacción El protocolo de bloqueo de dos fases no asegura la ausencia de interbloqueos.
Los retrocesos en cascada se pueden evitar por medio de una modificación del protocolo de bloqueo de dos fases que se denomina protocolo de bloqueo estricto de dos fases. Este protocolo exige que, además de que el bloqueo sea de dos fases, una transacción debe poseer todos los bloqueos en modo exclusivo que tome hasta que dicha transacción se complete., este requisito asegura que todo dato que describe una transacción no comprometida esta bloqueado en modo exclusivo hasta que la transacción se complete.
Otra variante del bloqueo de dos fases es el protocolo riguroso de dos fases, el cual exige que se posean todos los bloqueos hasta que se comprometa la transacción .
´
IMPLEMENTACIÓN DE BLOQUEOS.
Un gestor de bloqueos se puede implementar como un proceso que recibe mensajes de transacciones y envía mensajes como respuesta. El proceso gestor de bloqueos responde a los mensajes de solicitud de bloqueo con mensajes de concesión de bloqueo, o con mensajes que solicitan un retroceso de la transacción. Los mensajes de desbloqueo tan solo requieren un reconocimiento como respuesta, pero pueden dar lugar a un menaje de concesión para otra transacción que este esperando.
El gestor de bloqueos utiliza la siguiente estructura de datos: para cada elemento de datos que esta actualmente bloqueado, mantiene una lista enlazada de registros, uno para cada solicitud en el orden en que llegaron las solicitudes. Utiliza una tabla de asociación, indexada por el nombre del elemento de datos, para encontrar la lista enlazada para cada miembro e datos; esta tabla se denomina tabla de bloqueos. Cada registro en la lista enlazada da cada elemento de datos anota que transacción hizo la solicitud, y en que modo de bloqueo se solicito. El registro también anota si la solicitud ya se ha concedido.
PROTOCOLOS BASADOS EN GRAFOS.
Si se desean desarrollar protocolos que no sean de dos fases, es necesario tener información adicional acerca de la forma en que cada transacción accede a la base de datos. Existen varios modelos que pueden obtener la información adicional, que difieren en la cantidad de información que proporcionan. El modelo mas simple exige que se tenga un conocimiento previo acerca del orden en el cual se accede a los elementos de la base de datos. Dada esta información es posible construir protocolos de bloqueo que no sean de dos fases pero que no obstante aseguren la secuencialidad.
En el protocolo de árbol solo se permite la instrucción de bloqueo bloquear-X. Cada transacción Ti puede bloquear un elemento de datos al menos una vez y debe seguir las siguientes reglas:
1. El primer bloqueo de T, puede ser sobre cualquier elemento de datos.
2. Posteriormente, T puede bloquear un elemento de datos Q solo si T esta bloqueando actualmente al padre de Q.
3. Los elementos de datos bloqueados se pueden desbloquear en cualquier momento.
4. T no puede desbloquear de nuevo un elemento de datos que ya haya bloqueado y desbloqueado anteriormente.
PROTOCOLOS BASADOS EN MARCAS TEMPORALES.
En los protocolos de bloqueo que se han descrito antes se determina el orden entre dos transacciones conflictivas en tiempo de ejecución a través del primer bloqueo que soliciten ambas que traiga consigo modos incompatibles. Otro método para determinar el orden de secuencialidad es seleccionar previamente un orden entre las transacciones. El método mas común para hacer esto es utilizar un esquema de ordenación por marcas temporales.
MARCAS TEMPORALES.
Existen dos métodos simples para implementar ese esquema:
1. Usar el valor del reloj del sistema como marca temporal; es decir, la marca temporal de una transacción es igual al valor del reloj en el momento en que la transacción entra en el sistema.
2. Usar un contador lógico que se incrementa cada vez que se asigna una nueva marca temporal; es decir, la marca temporal de una transacción es igual al valor del contador en el momento en el cual la transacción entra en el sistema.
Las marcas temporales de las transacciones determinan el orden da secuencia.
· Marca_temporal-E(Q) denota la mayor marca temporal de todas las transacciones que ejecutan con éxito escribir(Q).
· Marca_temporal-L(Q) denota la mayor marca temporal de todas las transacciones que ejecutan con éxito leer(Q).
Estas marcas temporales se actualizan cada vez que se ejecuta una nueva operación leer (Q) o escribir (Q).
PROTOCOLOS DE ORDENACIÓN POR MARCAS TEMPORALES.
Asegura que todas las operaciones leer y escribir conflictivas se ejecutan en el orden de las marcas temporales. Este protocolo opera como sigue:
1. Supóngase que la transacción T ejecuta leer(Q).
a. Si MT(T)<>
REGLA DE ESCRITURA DE THOMAS.
La modificación al protocolo de ordenación por marcas temporales, denominada regla de escritura de Thomas, es la siguiente. Supóngase que la transacción T ejecuta escribir Q.
1. Si MT(T) <>
PROTOCOLOS BASADOS EN VALIDACIÓN.
Se asume que una transacción T se ejecuta en dos o tres fases diferentes durante su tiempo de vida dependiendo de si es una transacción de solo lectura o una de actualización. Las fases son, en orden.
1. Fase de lectura. Durante esta fase tiene lugar la ejecución de la transacción T. Se leen los valores de varios elementos de datos y se almacenan en variables locales de T. Todas las operaciones escribir se realizan sobre las variables locales temporales sin actualizar la base de datos actual.
2. Fase de validación. La transacción T realiza una prueba de validación para determinar si puede copiar a la base da datos las variables locales temporales que tienen los resultados de las operaciones escribir sin causar una violación de secuencialidad.
3. Fase de escritura. Si la transacción T tiene éxito en la validación (paso 2) entonces las actualizaciones reales se aplican a la base de datos. En otro caso T se retrocede.
Cada transacción debe pasar por las tres fases y en el orden que se muestra. Sin embargo, se pueden entrelazar las tres fases de la ejecución concurrente de las transacciones.
Para realizar la prueba de validación se necesita conocer le momento en que tienen lugar las distintas fases de las transacciones T. Se asociaran por tanto tres marcas temporales distintas a las transacción T.
1. Inicio (T). momento en el cual T comienza si ejecución.
2. Validación (T), momento en el cual T termina su fase de lectura y comienza su fase de validación.
3. Fin (T), momento en el cual T termina su fase de escritura.
GRANULARIDAD MÚLTIPLE.
En los esquemas de control de concurrencia que se han descrito antes se ha tomado cada elemento de datos individual como la unidad sobre la cual se producía la sincronización.
Si una transacción T necesita acceder solo a unos cuantos datos, ya que en ese caso se perdería la concurrencia.
Lo que se necesita en un mecanismo que permita al sistema definir múltiples niveles de granularidad. Se puede hacer uno permitiendo que los elementos de datos sean de vario tamaños y definiendo una jerarquía de granularidades de los datos, en el cual las granularidades pequeñas están anidadas en otras mas grandes. Una jerarquía tal se puede representar gráficamente como un árbol.
Este protocolo permite la concurrencia y reduce la sobrecarga de bloqueos. Es particularmente útil en las aplicaciones con una mezcla de
· Transacciones cortas que solo acceden a algunos elementos de datos.
· Transacciones largas que producen informes a partir de un archivo completo o un conjunto de archivos.
ESQUEMAS DE MULTIPLEXIÓN.
En los esquema de control de concurrencia multiversión, cada operación escribir (Q ) crea una nueva versión de (Q). Cuando se realiza una operación leer (Q) el gestor de control de concurrencia elige una de las versiones de Q que se va a leer.
ORDENACIÓN POR MARCAS TEMPORALES.
La técnica mas frecuente utilizada en los sistemas multivesión es la de las marcas temporales . A cada transacción T del sistema se le asocia una única marca temporal estática que se denota MT(T).
A cada elemento de datos Q se le asocia una secuencia de versiones . Cada versión Q contiene tres campos:
· Contenido
· Marca_temporal-E(Q1)
· Marca_temporal-L(Q1)
BLOQUEO DE DOS FASES MULTIVERSION.
Intenta conocer las ventajas del control de concurrencia con la ventaja con las ventajas del bloqueo de dos fases. Este protocolo distingue entre transacciones de solo lectura y transacciones de actualización.
Las transacciones de actualización realizar un bloqueo de dos fases riguroso; es decir, mantienen todos los bloqueos hasta el final de la transacción. Así se pueden secuenciar según su orden de terminación. Cada elemento de datos tiene una única marca temporal. La marca temporal no es en este caso una marca temporal basada en un reloj real, sino que es un contador, que se denomina contador_mt, que se incrementa durante el procesamiento del compromiso.
El bloqueo de dos fases multiversión o variaciones de este se usan en algunos sistemas de base de datos comerciales.
TRATAMIENTO DE INTERBLOQUEOS.
Un sistema esta en estado de interbloqueo si existe un conjunto de transacciones tal que toda transacción de un conjunto esta esperando a otra transacción del conjunto.
El único remedio a esta situación no deseada es que el sistema invoque alguna acción drástica, como retroceder algunas de las transacciones involucradas en el interbloqueo. El retroceso de una transacción puede ser parcial: esto es, se puede retroceder una transacción hasta el punto donde obtuvo un bloqueo coya liberación resuelve el interbloqueo.
Existen dos métodos principales para tratar el problema de los interbloqueos. Se puede utilizar un protocolo de prevención de interbloqueos para asegurar que le sistema llegue a un estado de interbloqueo. De forma alternativa se puede permitir que el sistema llegue a un estado de interbloqueo, y tratar de recuperarse después a través de un esquema de detección y recuperación de interbloqueos.
PREVENCIÓN DE INTERBLOQUEOS.
Existen dos enfoques a la prevención de interbloqueos . Un enfoque asegura que no puede haber esperas cíclicas ordenando las peticiones de bloqueo o exigiendo que todos los bloqueos se adquieran juntos. El otro enfoque es mas cercano a la recuperación de interbloqueos y realiza retrocesos de las transacciones en lugar de esperar un bloqueo, siempre que el bloqueo puede llevar potencialmente a un interbloqueo.
Es esquema mas simple para la primera aproximación exige que cada transacción bloquee todos los elementos de datos antes de comenzar su ejecución. Este protocolo tiene dos inconvenientes principales:
1) A menudo es difícil predecir, antes que comience la transacción, cuales son los elementos de datos que es necesario bloquear.
2) La utilización de los elementos de datos puede ser muy baja, ya que muchos de los elementos de datos pueden estar bloqueados pero sin usar durante mucho tiempo.
ESQUEMAS BASADOS EN LÍMITE DE TIEMPO.
Otro enfoque simple del tratamiento de interbloqueos se basa en bloqueos con limite de tiempo. En este enfoque una transacción que haya solicitado un bloqueo espera por lo menos durante un intervalo de tiempo especificado. Si no se concede el bloqueo en ese tiempo, se dice que la transacción esta fuera de tiempo y ella misma se retrocede y vuelve a empezar.
DETECCIÓN Y RECUPERACIÓN DE INTERBLOQUEOS.
Si el sistema no utiliza algún protocolo que asegure la ausencia de interbloqueos, entonces se debe usar un esquema de detección y recuperación. Periódicamente se invoca a un algoritmo que examina el estado del sistema para determinar si hay interbloqueo. Si lo hay entonces el sistema debe intentar recuperarse del interbloqueo.
OPERACIONES PARA INSERTAR Y BORRAR.
Algunas transacciones necesitan no sólo acceder a los elementos de datos existentes; sino también poder crear nuevos elementos de datos. Otras necesitan tener la posibilidad de borrar elementos de datos.Para examinar la forma en que tales transacciones afectan al control de concurrencia se introducen las operaciones adicionales siguientes:
· Borrar (Q): borra de la base de datos el elemento de datos Q.
· Insertar (Q): inserta en la base de datos el nuevo elemento de datos Q y le asigna un valor inicial.
BORRADO.
Para comprender la manera en que puede afectar la presencia de las instrucciones borrar al control de concurrencia, se debe decidir en que casos una instrucción borrar está en conflicto con otro instrucción.
Se puede concluir lo siguiente:
En el protocolo de dos fases se necesita un bloqueo exclusivo en un elemento de datos antes de que se borre dicho elemento.
En el protocolo de ordenación por marcas temporales se debe hacer un prueba similar que la que se hacía con escribir.
INSERCIÓN
No se pueden realizar operaciones leer o escribir sobre un elemento de datos hasta que éste ultimo exista.
Puesto que insertar (Q) asigna un valor al elemento de datos Q, se trata de insertar de forma similar a escribir desde el punto de vista del control de concurrencia:En el protocolo de bloqueo de dos fases, si Ti realiza una operación insertar (Q) se da a Ti un bloqueo exclusivo sobre el elemento de datos Q recientemente creado.EL
FENÓMENO FANTASMA.
Considérese una transacción T29 que ejecuta la siguiente pregunta SQL a la base de datos bancaria:Select sum (saldo)From cuentaWhere nombre-sucursal = ‘Pamplona’La transacción T29 necesita acceder a todas las tuplas de la relación cuenta que pertenezcan a la sucursal pamplona.
Sea T30 una transacción que ejecuta la siguiente inserción SQL:
Insert into cuentValues (‘Pamplona’, C-201, 900)
Con lo anterior se espera que haya un conflicto potencial debido a las razones siguientes:Si T29 utiliza la tupla que ha insertado recientemente T30 al calcular sum(saldo), entonces T29 lee el valor que ha escrito T30. Así en una planificación secuencial equivalente a S, T30 debe ir antes de T29.
Si T29 no utiliza la tupla que ha insertado recientemente T30 al calcular sum(saldo), entonces en una planificación secuencial equivalente a S, T29 debe ir antes de T30.T29 y T30 no acceden a ninguna tupla común y sin embargo están en conflicto. En efecto, T29 y T30 están en conflicto en una tupla fantasma. Si se realiza el control de concurrencia con granularidad de tupla no se detecta dicho conflicto. Este problema recibe el nombre de fenómeno fantasma.
Una solución es la técnica de bloqueo de índice. Toda transacción que inserte una tupla en una relación debe insertar información en cada una de los índices que se mantengan en la relación.El protocolo de bloqueo de índice toma las ventajas de la disponibilidad de índices en una relación convirtiendo las apariciones del fenómeno fantasma en conflictos en los bloqueos sobre los nodos hoja índice. El protocolo opera de la siguiente manera.
· Toda relación debe tener al menos un índice.
· Una transacción T puede acceder a las tuplas de una relación únicamente después de haberlas encontrado primero a través de uno o mas índices de la relación.
· Una transacción T que realiza una búsqueda debe bloquear en modo compartido todos los nodos hoja índice a los que accede.
· Una transacción T no puede insertar, borrar o actualizar una tupla t en una relación r sin utilizar todos los índices de r.
· Hay que cumplir con las reglas del protocolo de bloqueo de dos fases.
Existen variantes de la técnica de bloqueo de índice para eliminar el fenómeno fantasma con otros protocolos de control de concurrencia.
NIVELES DÉBILES DE CONSISTENCIA.
La secuencialidad es un concepto útil porque permite a los programadores ignorar problemas relacionados con la concurrencia cuando codifican las transacciones.
Sin embargo, puede que los protocolos necesarios para asegurar la secuencialidad permitan muy poca concurrencia para algunas aplicaciones. En estos casos se utilizan los niveles más débiles de consistencia. El uso de niveles más débiles de consistencia añade una nueva carga a los programadores para asegurar la corrección de las bases de datos.
CONSISTENCIA DE GRADO DOS.
El objetivo de la consistencia de grado dos es evitar abortar en cascada sin asegurar necesariamente la secuencialidad. El protocolo de bloqueo para la consistencia de grado dos utiliza los mismos dos modos de bloqueo que se utilizan para el bloqueo de dos fases: compartido (C) y exclusivo (X). Las transacciones deben mantener el modo de bloqueo adecuado cuando tengan acceso a un elemento de datos.
ESTABILIDAD DEL CURSOR
La estabilidad del cursor es una forma de consistencia de grado dos diseñada para programas escritos en lenguajes de propósito general, los cuales iteran sobre las tuplas de una relación utilizando cursores. La estabilidad del cursor asegura que:
· La tupla que está procesando la iteración esté bloqueada en modo compartido.
· Todas las tuplas modificadas estén bloqueadas en modo exclusivo hasta que se comprometa la transacción.
NIVELES DÉBILES DE CONSISTENCIA EN SQL.
La norma SQL también permite que una transacción especifique si puede ser ejecutada de tal forma que se convierta en no secuenciable con respecto a otras transacciones.
Los nivekes de consistencia especificados por SQL-92 son los siguientes:
· Secuenciable es el predeterminado.
· Lectura repetible solo permite leer registros comprometidos, y además requiera que, entre dos lecturas de un registro realizadas por una transacción, no se permita que ninguna otra transacción actualice el registro.
· Compromiso de lectura solo permite leer registros comprometidos, pero ni siquiera requiere lecturas repetitivas.
· Sin compromiso de lectura permite incluso leer registros no comprometidos.
CONCURRENCIA EN ESTRUCTURAS DE ÍNDICE.
Los índices, se pueden convertir en un punto de mucho bloqueo, lo que prode un baja grado de concurrencia. Es aceptable que una transacción busque en un índice dos veces y se encuentre que la lectura del índice ha cambiado entre ambas búsquedas, mientras que las duplas devuelvan el conjunto correcto de tuplas. De este modo se acepta tener un acceso no secuenciable a un índice mientras siga siendo correcto dicho índice.Las técnicas que se presentan para el control de concurrencia en los arboles B+ se basan en el bloqueo, pero no se complementan ni el bloqueo de dos fases ni el protocolo de árbol.
Técnicas:
1. Se denomina protocolo de cangrejo.
a. Cuando se busca un valor clave, el protocolo de cangrejo bloquea primero el nodo raíz en modo compartido. Cuando se recorre el nodo hacia abajo, adquiere un bloqueo compartido sobre el siguiente nodo hijo. Después de adquirir el bloqueo de nodo hijo, libera el bloqueo sobre el nodo padre. Repite el proceso hasta que alcanza un nodo hoja.
b. Cuando se inserta o se borra un valor clave, el protocolo de cangrejo realiza estas acciones:
i. Sigue el mismo protocolo que para la búsqueda hasta que alcanza el nodo hoja deseado.
ii. Bloquea el nodo hoja en modo exclusivo e inserta o borra el valor clave
iii. Si se necesita dividir un nodo o combinarlo con sus hermanos, o redistribuir los valores claves entre hermanos, el protocolo del cangrejo bloquea al padre del nodo en modo exclusivo.
Si el padre requiere división, combinación o redistribución de valores clave, el protocolo mantienen el bloqueo sobre el padre, y la división, la combinación o la redistribución se siguen propagando de la misma manera.El avance de los bloqueos mientras que el protocolo baja del árbol o sube de nuevo actúa de forma similar al cangrejo.Una vez que una operación particular libere un bloqueo sobre un nodo, otras operaciones pueden acceder a ese nodo. Existe una posibilidad de interbloqueos entre las operaciones de búsqueda que bajan por el árbol, y las divisiones, combinaciones y redistribuciones que se propagan hacia arriba del árbol. El sistema puede manejar con facilidad tales interbloqueos reiniciando la operación de búsqueda desde la raíz, después de liberar los bloqueos mantenidos por la operación.
2. Consigue mas concurrencia, impidiendo que se mantenga un bloqueo sobre un nodo mientras que está adquiriendo el bloqueo sobre otro nodo, utilizando una versión modificada de los árboles B+ llamados árboles enlazados; requieren que todo el nodo mantenga un puntero a su hermano derecho.
a. Búsqueda. Se debe bloquear en nodo compartido cada nodo del árbol B+ antes que acceda a él.
b. Inserción y borrado. El sistema sigue las reglas de la búsqueda para localizar el nodo sobre el cual se va a realizar la inserción o el borrado.
c. División. Si se divide un nodo se crea uno nuevo y se convierte en el hermano derecho del nodo original.
d. Fusión. Si el nodo tiene muy pocos valores de clave de búsqueda después de un borrado, se debe bloquear en modo exclusivo el nodo con el que se debe fusionar.Una inserción o un borrado pueden bloquear un nodo, desbloquearlo y posteriormente volverlo a bloquear. Una búsqueda que se ejecute con operaciones de división o de combinación puede observar que la clave de búsqueda deseada se ha trasladado al nodo hermano derecho debido a la división o a la combinación.En la mayoría de las bases de datos las inserciones son mas frecuentes que los borrados, por lo que es probable que los nodos que tienen muy pocos valores claves de búsqueda ganen valores adicionales de forma relativamente rápida.En lugar de bloquear nodos hoja índice en dos fases algunos esquemas de control de concurrencia de índices utilizan bloqueo de valores claves individuales, permitiendo que se inserten o se borren otros valores claves de la misma hoja. Por lo tanto, el bloqueo de valores clave proporciona una concurrencia mejorada. Utilizar el bloqueo de valores clave podría permitir que se produjera el fenómeno fantasma; para prevenirlo se utiliza la técnica de bloqueo.
3. Esta técnica, cada búsqueda por índice debe bloquear no solo las claves encontradas dentro del rango, sino también el siguiente valor clave, esto es, el valor clave que es justo mayor que el ultimo valor clave que está dentro del rango de la búsqueda por índice de otra transacción, las dos transacciones entraran en conflicto en el valor clave que sigue al valor clave insertado. De forma similar, los borradores también deben bloquear el siguiente valor clave al valor que se ha borrado para asegurar que se detecten los conflictos con las subsiguientes búsquedas de otras consultas.
BIBLIOGRAFÍA:
Capitulo 16 Silverschatz.
En este presente resumen se ve a conocer lo que es concurrencia. Cuando se ejecutan varias transacciones en la base de datos, se puede considerar dejar la propiedad de aislamiento. En varias ocasiones es llevar el control de todas las transacciones a través de esquemas de control de concurrencia.
Todos estos esquemas se describen a continuación, aquí se basan en la propiedad de secuencialidad.
PROTOCOLOS BÁSICOS EN EL BLOQUEO
Una forma de asegurar la secuencialidas es exigir que el acceso a los elementos de datos se haga en exclusión mutua; es decir, mientras una transacción accede a un elemento de datos, ninguna otra transacción puede modificar dicho elemento.
BLOQUEOS.
Existen muchos modos mediante los cuales se puede bloquear un elemento de datos.
1. Compartido. Si una transacción T obtiene un bloqueo en modo compartido (denotado por C) sobre le elemento Q, entonces T puede leer Q pero no escribir.
2. Exclusivo. Si una transacción T obtiene un bloqueo en modo exclusivo (denotado por X) sobre el elemento Q, entonces T puede tanto leer como escribir Q.
Es necesario que toda transacción solicite un bloqueo del modo apropiado sobre el elemento de datos Q dependiendo de los tipos de operaciones que se vayan a realizar sobre Q. La petición se hace al gestor se control de concurrencia. La transacción puede realizar la operación solo después de que el gestor de control de concurrencia conceda el bloqueo a la transacción.
.
Una transacción solicita un bloqueo compartido sobre el elemento de datos Q a través de la instrucción bloquear-C (Q). De forma similar se solicita un bloqueo exclusivo a través de la instrucción bloquear-X (Q). Se puede desbloquear un elemento de datos Q por medio de la instrucción desbloquear (Q).
Leer(B);
B:=B-50
Transacción T1
Escribir(B);
Desbloquear (B);
Bloquear-X(A);
Leer(A);
A:= A+50;
Escribir(A);
Desbloquear
Bloquear-C(A);
Leer(A);
Transacción T2
Desbloquear(A);
Bloquear-C(B);
Leer(B);
Desbloquear(B);
Visualizar (A+B).
Transacción T2
Se exige en toda transacción del sistema siga un conjunto de reglas llamado protocolo de bloqueo, que indica el momento en que una transacción puede bloquear y desbloquear cada uno de los elementos de datos. Los protocolos de bloqueo restringen el número de planificaciones posibles. El conjunto de tales planificaciones es un subconjunto propio de todas las planeaciones secuenciales posibles.
Bloquear-X(B);
Leer(B);
Transacción T3
B:=B-50;
Escribir(B);
Bloquear-X(A);
Leer(A);
A:=A-50;
Desbloquear(B);
Desbloquear(A).
Se dice que una planificación S es lega bajo un protocolo de bloqueo dado si S es una planificación posible para un subconjunto de transacciones que sigan las reglas de protocolo de bloqueos. Se dice que un protocolo asegura la secuencialidad en cuanto a conflictos si y solo si todas las planificaciones legales son secuenciables en cuanto a conflictos; en otras palabras, para todas las planificaciones legales la relación àasocia es a cíclica.
Bloquear-C(A);
Transacción T4
Leer(A);
Bloquear-C(B);
Leer(B);
Visualizar(A+B);
Desbloquear (A);
Desbloquear (B).
CONCESIÓN DE BLOQUEOS.
Cuando una transacción solicita un bloqueo de un modo particular sobre un elemento de datos y ninguna otra transacción posee un bloqueo sobre el mismo elemento de datos en un modo conflictivo, se puede conceder el bloqueo.
Se puede evitar la inanición de las transacciones al conceder los bloqueos de la siguiente manera: cuando una transacción T 1 solicita un bloqueo sobre un elemento de datos Q en un modo particular M, el gestor de control de concurrencia concede el bloqueo siempre que
1. No exista un transacción que posea un bloqueo sobre Q en un modo que este en conflicto con M.
2. No exista otra transacción que este esperando un bloqueo sobre Q y que lo haya solicitado antes que T.
De este modo, una partición de bloqueo nunca se quedara bloqueada por otra petición de bloqueo solicitada mas tarde.
PROTOCOLOS DE BLOQUEO EN DOS FASES.
Un protocolo que asegura la secuencialidad es el protocolo de bloqueos de dos fases. Este protocolo exige que cada transacción realice las peticiones de bloqueo y desbloqueo de dos fases:
1. Fase de crecimiento. Una transacción puede obtener bloqueos pero no puede liberarlos.
2. Fase de decrecimiento. Una transacción puede liberar bloqueos pero no puede obtener ninguno nuevo.
Inicialmente una transacción esta en la fase de crecimiento. La transacción adquiere los bloqueos que necesite. Una ves que la transacción libera un bloqueo, entra en la fase de decrecimiento y no puede realizar mas peticione de bloqueo.
Se pude mostrar que el protocolo de bloqueo de dos fases asegura la secuencialidad en cuanto a conflictos. Considérese cualquier transacción. Le punto de la planificación en el cual la transacción obtiene su bloqueo final (el final de la fase de crecimiento) se denomina punto de bloqueo de la transacción El protocolo de bloqueo de dos fases no asegura la ausencia de interbloqueos.
Los retrocesos en cascada se pueden evitar por medio de una modificación del protocolo de bloqueo de dos fases que se denomina protocolo de bloqueo estricto de dos fases. Este protocolo exige que, además de que el bloqueo sea de dos fases, una transacción debe poseer todos los bloqueos en modo exclusivo que tome hasta que dicha transacción se complete., este requisito asegura que todo dato que describe una transacción no comprometida esta bloqueado en modo exclusivo hasta que la transacción se complete.
Otra variante del bloqueo de dos fases es el protocolo riguroso de dos fases, el cual exige que se posean todos los bloqueos hasta que se comprometa la transacción .
´
IMPLEMENTACIÓN DE BLOQUEOS.
Un gestor de bloqueos se puede implementar como un proceso que recibe mensajes de transacciones y envía mensajes como respuesta. El proceso gestor de bloqueos responde a los mensajes de solicitud de bloqueo con mensajes de concesión de bloqueo, o con mensajes que solicitan un retroceso de la transacción. Los mensajes de desbloqueo tan solo requieren un reconocimiento como respuesta, pero pueden dar lugar a un menaje de concesión para otra transacción que este esperando.
El gestor de bloqueos utiliza la siguiente estructura de datos: para cada elemento de datos que esta actualmente bloqueado, mantiene una lista enlazada de registros, uno para cada solicitud en el orden en que llegaron las solicitudes. Utiliza una tabla de asociación, indexada por el nombre del elemento de datos, para encontrar la lista enlazada para cada miembro e datos; esta tabla se denomina tabla de bloqueos. Cada registro en la lista enlazada da cada elemento de datos anota que transacción hizo la solicitud, y en que modo de bloqueo se solicito. El registro también anota si la solicitud ya se ha concedido.
PROTOCOLOS BASADOS EN GRAFOS.
Si se desean desarrollar protocolos que no sean de dos fases, es necesario tener información adicional acerca de la forma en que cada transacción accede a la base de datos. Existen varios modelos que pueden obtener la información adicional, que difieren en la cantidad de información que proporcionan. El modelo mas simple exige que se tenga un conocimiento previo acerca del orden en el cual se accede a los elementos de la base de datos. Dada esta información es posible construir protocolos de bloqueo que no sean de dos fases pero que no obstante aseguren la secuencialidad.
En el protocolo de árbol solo se permite la instrucción de bloqueo bloquear-X. Cada transacción Ti puede bloquear un elemento de datos al menos una vez y debe seguir las siguientes reglas:
1. El primer bloqueo de T, puede ser sobre cualquier elemento de datos.
2. Posteriormente, T puede bloquear un elemento de datos Q solo si T esta bloqueando actualmente al padre de Q.
3. Los elementos de datos bloqueados se pueden desbloquear en cualquier momento.
4. T no puede desbloquear de nuevo un elemento de datos que ya haya bloqueado y desbloqueado anteriormente.
PROTOCOLOS BASADOS EN MARCAS TEMPORALES.
En los protocolos de bloqueo que se han descrito antes se determina el orden entre dos transacciones conflictivas en tiempo de ejecución a través del primer bloqueo que soliciten ambas que traiga consigo modos incompatibles. Otro método para determinar el orden de secuencialidad es seleccionar previamente un orden entre las transacciones. El método mas común para hacer esto es utilizar un esquema de ordenación por marcas temporales.
MARCAS TEMPORALES.
Existen dos métodos simples para implementar ese esquema:
1. Usar el valor del reloj del sistema como marca temporal; es decir, la marca temporal de una transacción es igual al valor del reloj en el momento en que la transacción entra en el sistema.
2. Usar un contador lógico que se incrementa cada vez que se asigna una nueva marca temporal; es decir, la marca temporal de una transacción es igual al valor del contador en el momento en el cual la transacción entra en el sistema.
Las marcas temporales de las transacciones determinan el orden da secuencia.
· Marca_temporal-E(Q) denota la mayor marca temporal de todas las transacciones que ejecutan con éxito escribir(Q).
· Marca_temporal-L(Q) denota la mayor marca temporal de todas las transacciones que ejecutan con éxito leer(Q).
Estas marcas temporales se actualizan cada vez que se ejecuta una nueva operación leer (Q) o escribir (Q).
PROTOCOLOS DE ORDENACIÓN POR MARCAS TEMPORALES.
Asegura que todas las operaciones leer y escribir conflictivas se ejecutan en el orden de las marcas temporales. Este protocolo opera como sigue:
1. Supóngase que la transacción T ejecuta leer(Q).
a. Si MT(T)<>
REGLA DE ESCRITURA DE THOMAS.
La modificación al protocolo de ordenación por marcas temporales, denominada regla de escritura de Thomas, es la siguiente. Supóngase que la transacción T ejecuta escribir Q.
1. Si MT(T) <>
PROTOCOLOS BASADOS EN VALIDACIÓN.
Se asume que una transacción T se ejecuta en dos o tres fases diferentes durante su tiempo de vida dependiendo de si es una transacción de solo lectura o una de actualización. Las fases son, en orden.
1. Fase de lectura. Durante esta fase tiene lugar la ejecución de la transacción T. Se leen los valores de varios elementos de datos y se almacenan en variables locales de T. Todas las operaciones escribir se realizan sobre las variables locales temporales sin actualizar la base de datos actual.
2. Fase de validación. La transacción T realiza una prueba de validación para determinar si puede copiar a la base da datos las variables locales temporales que tienen los resultados de las operaciones escribir sin causar una violación de secuencialidad.
3. Fase de escritura. Si la transacción T tiene éxito en la validación (paso 2) entonces las actualizaciones reales se aplican a la base de datos. En otro caso T se retrocede.
Cada transacción debe pasar por las tres fases y en el orden que se muestra. Sin embargo, se pueden entrelazar las tres fases de la ejecución concurrente de las transacciones.
Para realizar la prueba de validación se necesita conocer le momento en que tienen lugar las distintas fases de las transacciones T. Se asociaran por tanto tres marcas temporales distintas a las transacción T.
1. Inicio (T). momento en el cual T comienza si ejecución.
2. Validación (T), momento en el cual T termina su fase de lectura y comienza su fase de validación.
3. Fin (T), momento en el cual T termina su fase de escritura.
GRANULARIDAD MÚLTIPLE.
En los esquemas de control de concurrencia que se han descrito antes se ha tomado cada elemento de datos individual como la unidad sobre la cual se producía la sincronización.
Si una transacción T necesita acceder solo a unos cuantos datos, ya que en ese caso se perdería la concurrencia.
Lo que se necesita en un mecanismo que permita al sistema definir múltiples niveles de granularidad. Se puede hacer uno permitiendo que los elementos de datos sean de vario tamaños y definiendo una jerarquía de granularidades de los datos, en el cual las granularidades pequeñas están anidadas en otras mas grandes. Una jerarquía tal se puede representar gráficamente como un árbol.
Este protocolo permite la concurrencia y reduce la sobrecarga de bloqueos. Es particularmente útil en las aplicaciones con una mezcla de
· Transacciones cortas que solo acceden a algunos elementos de datos.
· Transacciones largas que producen informes a partir de un archivo completo o un conjunto de archivos.
ESQUEMAS DE MULTIPLEXIÓN.
En los esquema de control de concurrencia multiversión, cada operación escribir (Q ) crea una nueva versión de (Q). Cuando se realiza una operación leer (Q) el gestor de control de concurrencia elige una de las versiones de Q que se va a leer.
ORDENACIÓN POR MARCAS TEMPORALES.
La técnica mas frecuente utilizada en los sistemas multivesión es la de las marcas temporales . A cada transacción T del sistema se le asocia una única marca temporal estática que se denota MT(T).
A cada elemento de datos Q se le asocia una secuencia de versiones . Cada versión Q contiene tres campos:
· Contenido
· Marca_temporal-E(Q1)
· Marca_temporal-L(Q1)
BLOQUEO DE DOS FASES MULTIVERSION.
Intenta conocer las ventajas del control de concurrencia con la ventaja con las ventajas del bloqueo de dos fases. Este protocolo distingue entre transacciones de solo lectura y transacciones de actualización.
Las transacciones de actualización realizar un bloqueo de dos fases riguroso; es decir, mantienen todos los bloqueos hasta el final de la transacción. Así se pueden secuenciar según su orden de terminación. Cada elemento de datos tiene una única marca temporal. La marca temporal no es en este caso una marca temporal basada en un reloj real, sino que es un contador, que se denomina contador_mt, que se incrementa durante el procesamiento del compromiso.
El bloqueo de dos fases multiversión o variaciones de este se usan en algunos sistemas de base de datos comerciales.
TRATAMIENTO DE INTERBLOQUEOS.
Un sistema esta en estado de interbloqueo si existe un conjunto de transacciones tal que toda transacción de un conjunto esta esperando a otra transacción del conjunto.
El único remedio a esta situación no deseada es que el sistema invoque alguna acción drástica, como retroceder algunas de las transacciones involucradas en el interbloqueo. El retroceso de una transacción puede ser parcial: esto es, se puede retroceder una transacción hasta el punto donde obtuvo un bloqueo coya liberación resuelve el interbloqueo.
Existen dos métodos principales para tratar el problema de los interbloqueos. Se puede utilizar un protocolo de prevención de interbloqueos para asegurar que le sistema llegue a un estado de interbloqueo. De forma alternativa se puede permitir que el sistema llegue a un estado de interbloqueo, y tratar de recuperarse después a través de un esquema de detección y recuperación de interbloqueos.
PREVENCIÓN DE INTERBLOQUEOS.
Existen dos enfoques a la prevención de interbloqueos . Un enfoque asegura que no puede haber esperas cíclicas ordenando las peticiones de bloqueo o exigiendo que todos los bloqueos se adquieran juntos. El otro enfoque es mas cercano a la recuperación de interbloqueos y realiza retrocesos de las transacciones en lugar de esperar un bloqueo, siempre que el bloqueo puede llevar potencialmente a un interbloqueo.
Es esquema mas simple para la primera aproximación exige que cada transacción bloquee todos los elementos de datos antes de comenzar su ejecución. Este protocolo tiene dos inconvenientes principales:
1) A menudo es difícil predecir, antes que comience la transacción, cuales son los elementos de datos que es necesario bloquear.
2) La utilización de los elementos de datos puede ser muy baja, ya que muchos de los elementos de datos pueden estar bloqueados pero sin usar durante mucho tiempo.
ESQUEMAS BASADOS EN LÍMITE DE TIEMPO.
Otro enfoque simple del tratamiento de interbloqueos se basa en bloqueos con limite de tiempo. En este enfoque una transacción que haya solicitado un bloqueo espera por lo menos durante un intervalo de tiempo especificado. Si no se concede el bloqueo en ese tiempo, se dice que la transacción esta fuera de tiempo y ella misma se retrocede y vuelve a empezar.
DETECCIÓN Y RECUPERACIÓN DE INTERBLOQUEOS.
Si el sistema no utiliza algún protocolo que asegure la ausencia de interbloqueos, entonces se debe usar un esquema de detección y recuperación. Periódicamente se invoca a un algoritmo que examina el estado del sistema para determinar si hay interbloqueo. Si lo hay entonces el sistema debe intentar recuperarse del interbloqueo.
OPERACIONES PARA INSERTAR Y BORRAR.
Algunas transacciones necesitan no sólo acceder a los elementos de datos existentes; sino también poder crear nuevos elementos de datos. Otras necesitan tener la posibilidad de borrar elementos de datos.Para examinar la forma en que tales transacciones afectan al control de concurrencia se introducen las operaciones adicionales siguientes:
· Borrar (Q): borra de la base de datos el elemento de datos Q.
· Insertar (Q): inserta en la base de datos el nuevo elemento de datos Q y le asigna un valor inicial.
BORRADO.
Para comprender la manera en que puede afectar la presencia de las instrucciones borrar al control de concurrencia, se debe decidir en que casos una instrucción borrar está en conflicto con otro instrucción.
Se puede concluir lo siguiente:
En el protocolo de dos fases se necesita un bloqueo exclusivo en un elemento de datos antes de que se borre dicho elemento.
En el protocolo de ordenación por marcas temporales se debe hacer un prueba similar que la que se hacía con escribir.
INSERCIÓN
No se pueden realizar operaciones leer o escribir sobre un elemento de datos hasta que éste ultimo exista.
Puesto que insertar (Q) asigna un valor al elemento de datos Q, se trata de insertar de forma similar a escribir desde el punto de vista del control de concurrencia:En el protocolo de bloqueo de dos fases, si Ti realiza una operación insertar (Q) se da a Ti un bloqueo exclusivo sobre el elemento de datos Q recientemente creado.EL
FENÓMENO FANTASMA.
Considérese una transacción T29 que ejecuta la siguiente pregunta SQL a la base de datos bancaria:Select sum (saldo)From cuentaWhere nombre-sucursal = ‘Pamplona’La transacción T29 necesita acceder a todas las tuplas de la relación cuenta que pertenezcan a la sucursal pamplona.
Sea T30 una transacción que ejecuta la siguiente inserción SQL:
Insert into cuentValues (‘Pamplona’, C-201, 900)
Con lo anterior se espera que haya un conflicto potencial debido a las razones siguientes:Si T29 utiliza la tupla que ha insertado recientemente T30 al calcular sum(saldo), entonces T29 lee el valor que ha escrito T30. Así en una planificación secuencial equivalente a S, T30 debe ir antes de T29.
Si T29 no utiliza la tupla que ha insertado recientemente T30 al calcular sum(saldo), entonces en una planificación secuencial equivalente a S, T29 debe ir antes de T30.T29 y T30 no acceden a ninguna tupla común y sin embargo están en conflicto. En efecto, T29 y T30 están en conflicto en una tupla fantasma. Si se realiza el control de concurrencia con granularidad de tupla no se detecta dicho conflicto. Este problema recibe el nombre de fenómeno fantasma.
Una solución es la técnica de bloqueo de índice. Toda transacción que inserte una tupla en una relación debe insertar información en cada una de los índices que se mantengan en la relación.El protocolo de bloqueo de índice toma las ventajas de la disponibilidad de índices en una relación convirtiendo las apariciones del fenómeno fantasma en conflictos en los bloqueos sobre los nodos hoja índice. El protocolo opera de la siguiente manera.
· Toda relación debe tener al menos un índice.
· Una transacción T puede acceder a las tuplas de una relación únicamente después de haberlas encontrado primero a través de uno o mas índices de la relación.
· Una transacción T que realiza una búsqueda debe bloquear en modo compartido todos los nodos hoja índice a los que accede.
· Una transacción T no puede insertar, borrar o actualizar una tupla t en una relación r sin utilizar todos los índices de r.
· Hay que cumplir con las reglas del protocolo de bloqueo de dos fases.
Existen variantes de la técnica de bloqueo de índice para eliminar el fenómeno fantasma con otros protocolos de control de concurrencia.
NIVELES DÉBILES DE CONSISTENCIA.
La secuencialidad es un concepto útil porque permite a los programadores ignorar problemas relacionados con la concurrencia cuando codifican las transacciones.
Sin embargo, puede que los protocolos necesarios para asegurar la secuencialidad permitan muy poca concurrencia para algunas aplicaciones. En estos casos se utilizan los niveles más débiles de consistencia. El uso de niveles más débiles de consistencia añade una nueva carga a los programadores para asegurar la corrección de las bases de datos.
CONSISTENCIA DE GRADO DOS.
El objetivo de la consistencia de grado dos es evitar abortar en cascada sin asegurar necesariamente la secuencialidad. El protocolo de bloqueo para la consistencia de grado dos utiliza los mismos dos modos de bloqueo que se utilizan para el bloqueo de dos fases: compartido (C) y exclusivo (X). Las transacciones deben mantener el modo de bloqueo adecuado cuando tengan acceso a un elemento de datos.
ESTABILIDAD DEL CURSOR
La estabilidad del cursor es una forma de consistencia de grado dos diseñada para programas escritos en lenguajes de propósito general, los cuales iteran sobre las tuplas de una relación utilizando cursores. La estabilidad del cursor asegura que:
· La tupla que está procesando la iteración esté bloqueada en modo compartido.
· Todas las tuplas modificadas estén bloqueadas en modo exclusivo hasta que se comprometa la transacción.
NIVELES DÉBILES DE CONSISTENCIA EN SQL.
La norma SQL también permite que una transacción especifique si puede ser ejecutada de tal forma que se convierta en no secuenciable con respecto a otras transacciones.
Los nivekes de consistencia especificados por SQL-92 son los siguientes:
· Secuenciable es el predeterminado.
· Lectura repetible solo permite leer registros comprometidos, y además requiera que, entre dos lecturas de un registro realizadas por una transacción, no se permita que ninguna otra transacción actualice el registro.
· Compromiso de lectura solo permite leer registros comprometidos, pero ni siquiera requiere lecturas repetitivas.
· Sin compromiso de lectura permite incluso leer registros no comprometidos.
CONCURRENCIA EN ESTRUCTURAS DE ÍNDICE.
Los índices, se pueden convertir en un punto de mucho bloqueo, lo que prode un baja grado de concurrencia. Es aceptable que una transacción busque en un índice dos veces y se encuentre que la lectura del índice ha cambiado entre ambas búsquedas, mientras que las duplas devuelvan el conjunto correcto de tuplas. De este modo se acepta tener un acceso no secuenciable a un índice mientras siga siendo correcto dicho índice.Las técnicas que se presentan para el control de concurrencia en los arboles B+ se basan en el bloqueo, pero no se complementan ni el bloqueo de dos fases ni el protocolo de árbol.
Técnicas:
1. Se denomina protocolo de cangrejo.
a. Cuando se busca un valor clave, el protocolo de cangrejo bloquea primero el nodo raíz en modo compartido. Cuando se recorre el nodo hacia abajo, adquiere un bloqueo compartido sobre el siguiente nodo hijo. Después de adquirir el bloqueo de nodo hijo, libera el bloqueo sobre el nodo padre. Repite el proceso hasta que alcanza un nodo hoja.
b. Cuando se inserta o se borra un valor clave, el protocolo de cangrejo realiza estas acciones:
i. Sigue el mismo protocolo que para la búsqueda hasta que alcanza el nodo hoja deseado.
ii. Bloquea el nodo hoja en modo exclusivo e inserta o borra el valor clave
iii. Si se necesita dividir un nodo o combinarlo con sus hermanos, o redistribuir los valores claves entre hermanos, el protocolo del cangrejo bloquea al padre del nodo en modo exclusivo.
Si el padre requiere división, combinación o redistribución de valores clave, el protocolo mantienen el bloqueo sobre el padre, y la división, la combinación o la redistribución se siguen propagando de la misma manera.El avance de los bloqueos mientras que el protocolo baja del árbol o sube de nuevo actúa de forma similar al cangrejo.Una vez que una operación particular libere un bloqueo sobre un nodo, otras operaciones pueden acceder a ese nodo. Existe una posibilidad de interbloqueos entre las operaciones de búsqueda que bajan por el árbol, y las divisiones, combinaciones y redistribuciones que se propagan hacia arriba del árbol. El sistema puede manejar con facilidad tales interbloqueos reiniciando la operación de búsqueda desde la raíz, después de liberar los bloqueos mantenidos por la operación.
2. Consigue mas concurrencia, impidiendo que se mantenga un bloqueo sobre un nodo mientras que está adquiriendo el bloqueo sobre otro nodo, utilizando una versión modificada de los árboles B+ llamados árboles enlazados; requieren que todo el nodo mantenga un puntero a su hermano derecho.
a. Búsqueda. Se debe bloquear en nodo compartido cada nodo del árbol B+ antes que acceda a él.
b. Inserción y borrado. El sistema sigue las reglas de la búsqueda para localizar el nodo sobre el cual se va a realizar la inserción o el borrado.
c. División. Si se divide un nodo se crea uno nuevo y se convierte en el hermano derecho del nodo original.
d. Fusión. Si el nodo tiene muy pocos valores de clave de búsqueda después de un borrado, se debe bloquear en modo exclusivo el nodo con el que se debe fusionar.Una inserción o un borrado pueden bloquear un nodo, desbloquearlo y posteriormente volverlo a bloquear. Una búsqueda que se ejecute con operaciones de división o de combinación puede observar que la clave de búsqueda deseada se ha trasladado al nodo hermano derecho debido a la división o a la combinación.En la mayoría de las bases de datos las inserciones son mas frecuentes que los borrados, por lo que es probable que los nodos que tienen muy pocos valores claves de búsqueda ganen valores adicionales de forma relativamente rápida.En lugar de bloquear nodos hoja índice en dos fases algunos esquemas de control de concurrencia de índices utilizan bloqueo de valores claves individuales, permitiendo que se inserten o se borren otros valores claves de la misma hoja. Por lo tanto, el bloqueo de valores clave proporciona una concurrencia mejorada. Utilizar el bloqueo de valores clave podría permitir que se produjera el fenómeno fantasma; para prevenirlo se utiliza la técnica de bloqueo.
3. Esta técnica, cada búsqueda por índice debe bloquear no solo las claves encontradas dentro del rango, sino también el siguiente valor clave, esto es, el valor clave que es justo mayor que el ultimo valor clave que está dentro del rango de la búsqueda por índice de otra transacción, las dos transacciones entraran en conflicto en el valor clave que sigue al valor clave insertado. De forma similar, los borradores también deben bloquear el siguiente valor clave al valor que se ha borrado para asegurar que se detecten los conflictos con las subsiguientes búsquedas de otras consultas.
BIBLIOGRAFÍA:
Capitulo 16 Silverschatz.
0 Comments:
Post a Comment