Podemos determinar si una historia es serializable o no analizando un grafo derivado de la historia llamado grafo de serialización. Sea H una historia sobre T={T₁, T₂, ..., T_n}. El grafo de serialización (SG) para H es una grafo dirigido cuyos nodos son las transacciones en T que están confirmadas en H y cuyos arcos son todos aquellos de la forma T_i -› T_j (i =/ j) tal que una de las operaciones de T_i preceda y esté en conflicto con una de las operaciones de T_j en H. Por ejemplo, para la historia

El arco T₁ -› T₃ está en SG(H₅) porque w₁[x] < r₃[x], y el arco T₂ -› T₃ está en SG(H₅) porque r₂[x] < w₃[x]. Es importante resaltar que un arco en SG(H₅) puede originarse por más de un par de operaciones conflictivas; por ejemplo, el arco T₂ -› T₁ es causado tanto por r₂[x] > w₁[x] y w₂[y] > w₁[y].

Cada arco T_i -› T_j en SG(H) significa que al menos una de las operaciones de T_i precede y está en conflicto con una de las operaciones de T_j. Esto indica que T_i debe preceder a T_j en cualquier historia serial que es equivalente a H. Si es posible encontrar una historia serial, H_s, consistente de todos los arcos en SG(H), entonces H_s es equivalente a H y por lo tanto, H es serializable siempre que SG(H) sea acíclico.

en el ejemplo anterior, SG(H₅) es acíclico. Una historia serial en la que las transacciones aparecen en un orden consistente con los arcos de SG(H₅) es T₂ T₁ T₃, es decir,

Teorema de Seriabilidad

Una historia H es serializable si y sólo si SG(H) es acíclico.

Este teorema se usa para caracterizar el conjunto de historias permitido por un algoritmo de control de concurrencia y probar que cualquiera de esas historias debe tener un grafo de serialización acíclico, por lo tanto, el algoritmo de control de concurrencia garantiza las ejecuciones serializables.


5 Métodos 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 (bloqueos) 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 sincronizan 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. Ambos grupos de métodos, pesimistas y optimistas, consisten de algoritmos basados en bloqueos y algoritmos basados en marcas de tiempo, entre otros.

En la siguiente sección se presenta uno de los métodos pesimistas basado en bloqueos más utilizado conocido como Bloqueo de Dos Fases


6 Bloqueo de Dos Fases

El bloqueo es un mecanismo usado comúnmente para resolver el problema de la sincronización en el acceso a datos compartidos. La idea fundamental del bloqueo es simple y de sentido común. Cada dato tiene un bloqueo asociado con él. Antes de que una transacción T₁ pueda accesar al dato, el sincronizador primero examina el bloqueo asociado. Si ninguna transacción tiene el bloqueo, entonces el sincronizador obtiene el bloqueo en representación de T₁. Si alguna otra transacción T₂ tiene el bloqueo, T₁ debe esperar hasta que T₂ libere el bloqueo. Esto significa que el sincronizador no le asignará el bloqueo a T₁ hasta que T₂ lo libere. Por lo tanto, el sincronizador asegura que sólo una transacción a la vez pueda tener el bloqueo y, de acuerdo a esto, sólo una transacción puede acceder al dato a la vez.

El bloqueo puede ser usado por un sincronizador para garantizar la seriabilidad. Debido a que las transacciones acceden a los datos para leerlos o escribirlos, existen dos tipos de bloqueos asociados con los datos: bloqueos de lectura y bloqueos de escritura. Usaremos rl[x] para denotar un bloqueo de lectura sobre el elemento x y wl[x] para denotar un bloqueo de escritura sobre x. Específicamente, usaremos rl_i[x] (o wl_i[x]) para denotar la operación por la cual T_i obtiene un bloqueo de lectura (o escritura) sobre x; mientras que ru_i[x] (o wu_i[x]) denota la operación mediante la cual T_i libera el bloqueo de lectura (o escritura) sobre x.

Dos bloqueos cualesquiera pl_i[x] y ql_j[y] están en conflicto si x=y, i =/ j, y las operaciones p y q son de tipo conflictivo. Es decir, dos bloqueos son conflictivos si son sobre el mismo dato, son requeridos por transacciones diferentes y uno o ambos son bloqueos de escritura. Por lo tanto, dos bloqueos en diferentes datos no están en conflicto ni tampoco dos bloqueos sobre el mismo dato requeridos por la misma transacción aún cuando sean de tipo conflictivo.

La función del sincronizador de Bloqueo de Dos Fases (2PL) es manejar los bloqueos controlando cuando las transacciones obtienen y liberan sus bloqueos, de acuerdo a las siguientes reglas :

1. Cuando recibe una operación p_i[x] del Administrador de Transacciones (TM), el sincronizador verifica si pl_i[x] está en conflicto con algún ql_j[x] que ya esté establecido. Si es así, retrasa pl_i[x], forzando a T_i a esperar hasta que pueda recibir el bloqueo que necesita. Si no, el sincronizador acepta pl_i[x] y envía p_i[x] al Administrador de Datos (DM).

2. Una vez que el sincronizador ha establecido un bloqueo para T_i, digamos pl_i[x], no puede liberar el bloqueo al menos hasta que el DM reconozca que se ha procesado la operación corresponidente al bloqueo, es decir p_i[x].

3. Una vez que el sincronizador ha liberado un bloqueo para una transacción, no puede, subsecuentemente, obtener ningún otro bloqueo para esa transacción (sobre ningún dato).

La primera regla previene que dos transacciones accedan concurrentemente al mismo dato con operaciones conflictivas. Por lo tanto, las operaciones conflictivas son planificadas en el mismo orden en el que se obtienen sus correspondientes bloqueos. La regla (2) complementa la primera regla, garantizando que el DM procese operaciones sobre el dato en el orden en el que el sincronizador las envía. Por ejemplo, supongamos que T_i obtiene rl_i[x], el cual libera antes que el DM haya confirmado que r_i[x] se haya procesado. Entonces, es posible que algún T_j obtenga un bloqueo conflictivo sobre x, wl_j[x], y envíe w_j[x] al DM. A pesar que el sincronizador ha enviado r_i[x] antes que w_j[x] al DM, sin la regla (2) no hay garantía de que el DM recibirá y procesará las operaciones en ese orden.

La tercera regla, conocida como la regla de las dos fases, es el origen del nombre del sincronizador. Cada transacción debe ser dividida en dos fases: una fase de crecimiento durante la cual obtiene bloqueos, y una fase de encogimiento durante la cual libera sus bloqueos.

Consideremos dos transacciones T₁ y T₂ :

Como r₁[x] > w₂[x] y w₂[y] > w₁[y], se presenta el ciclo T₁ -› T₂ -› T₁ y, como consecuencia, H₁ no es serializable.

El problema en H₁ es que T₁ libera un bloqueo (ru₁[x]) y luego obtiene otro (wl₁[y]), violando la regla de las dos fases. Entre ru₁[x] y wl₁[y], otra transacción T₂ escribe sobre x y y, y es así que aparece después de T₁ con respecto a x y la precede con respecto a y. Si T₁ hubiese seguido la regla de las dos fases, esta "ventana" entre ru₁[x] y wl₁[y] no se habría abierto, y T₂ no se hubiera podido ejecutar como ocurrió en H₁. Por ejemplo, T₁ y T₂ pudo haberse ejecutado como sigue.

1. Inicialmente, ninguna transacción tiene bloqueo alguno.
   

2. El sincronizador recibe r₁[x] del TM. De acuerdo a esto, asigna rl₁[x] y envía r₁[x] al DM. Luego el DM reconoce el procesamiento de r₂[x].

3. El sincronizador recibe w₂[x] del TM. El sincronizador no puede asignar wl₂[x], puesto que está en conflicto con rl₁[x], por lo que retrasa la ejecución de w₂[x] colocándolo en una cola de espera.

4. El sincronizador recibe w₁[y] del TM. Asigna wl₁[y] y envía w₁[y] al DM. Luego el DM reconoce el procesamiento de w₁[y].

5. El sincronizador recibe c₁ del TM, señalando que T₁ ha terminado. El sincronizador envía c₁ al DM. Después que el DM reconoce el procesamiento de c₁, el sincronizador libera rl₁[x] y wl₁[y]. Esto está de acuerdo a la regla (2) porque r₁[x] y w₁[y] ya han sido procesadas, y de acuerdo a la regla (3) porque T₁ no solicitará ningún otro bloqueo.

6. El sincronizador asigna wl₂[x] tal que w₂[x], que había sido retrasada, puede ser enviada al DM. Luego el DM reconoce w₂[x].

7. El sincronizador recibe w₂[y] del TM. Asigna wl₂[y] y envía w₂[y] al DM. El DM luego reconoce el procesamiento de w₂[y].

8. T₂ termina y el TM envía c₂ al sincronizador. El sincronizador envía c₂ al DM. Después que el DM reconoce el procesamiento de c₂, el sincronizador libera wl2[x] y wl₂[y].

H₂ = rl₁[x] r₁[x] wl₁[y] w₁[y] c₁ ru₁[x] wu₁[y] wl₂[x] w₂[x] wl₂[y] w₂[y] c₂ wu₂[x] wu₂[y]

Una importante desventaja de los sincronizadores de 2PL es que están propensos a bloqueos mutuos (deadlocks), conocidos también como "abrazo mortal". Por ejemplo, supongamos que un sincronizador 2PL está procesando las transacciones T₁ y T₃

T₁ = r₁[x] -› w₁[y] -› c₁
T₃ = w₃[y] -› w₃[x] -› c₃

1. Inicialmente, ninguna transacción tiene bloqueo alguno.

2. El sincronizador recibe r₁[x] del TM. Asigna rl₁[x] y envía r₁[x] al DM.

3. El sincronizador recibe w₃[y] del TM. Asigna wl₃[y] y envía w₃[y] al DM.

4. El sincronizador recibe w₃[x] del TM. El sincronizador no puede asignar wl₃[x] porque entra en conflicto con rl₁[x] que ya está asignado. Por lo tanto, se retrasa la ejecución de w₃[x].

5. El sincronizador recibe w₁[y] del TM. Como en (4), se retrasa la ejecución de w₁[y].

Aún cuando el sincronizador se ha desempeñado exactamente de acuerdo a las reglas del 2PL, ni T₁ ni T₃ pueden ser completadas sin violar una de estas reglas. Si el sincronizador envía w₁[y] al DM sin asignar wl₁[y] estaría violando la regla (1). Similarmente para w₃[x]. Supongamos que el sincronizador libera wl₃[y], de modo que se puede asignar wl₁[y] y sería posible enviar w₁[y] al DM. En este caso, el sincronizador no podría asignar wl₃[x] (y por lo tanto, tampoco podría procesar w₃[x]), o, en caso contrario, violaría la regla (3). Similarmente si libera rl₁[x]. Esta es una clásica situación de bloqueo mutuo. Antes de que cualquiera de las transacciones pueda ser procesada, una de ellas debe liberar un bloqueo que la otra necesita para continuar.

Los bloqueos mutuos también aparecen cuando las transacciones tratan de convertir bloqueos de lectura en bloqueos de escritura, Supongamos que la transacción T_i lee un dato x y luego intenta escribir sobre él. T_i transmite r_i[x] al sincronizador, el cual asigna rl_i[x]. Cuando T_i transmite w_i[x] al sincronizador, éste debe actualizar rl_i[x] a wl_i[x]. Esta actualización de bloqueo se conoce como conversión de bloqueo. Para seguir las reglas de 2PL, el sincronizador no debe liberar rl_i[x]. Esto no es un problema, porque los bloqueos asignados por la misma transacción no son conflictivos entre sí. Sin embargo, si dos transacciones intentan concurrentemente convertir sus bloqueos de lectura sobre un dato en bloqueos de escritura, el resultado es un bloqueo mutuo.

Por ejemplo, supongamos que T₄ y T₅ transmiten operaciones a un sincronizador 2PL.

T₄ = r₄[x] -› w₄[x] -› c₄
T₅ = r₅[x] -› w₅[x] -› c₅

1. El sincronizador recibe r₄[x], y por consiguiente, asigna rl₄[x] y envía r₄[x] al DM.

2. El sincronizador recibe r₅[x], y por consiguiente, asigna rl₅[x] y envía r₅[x] al DM.

3. El sincronizador recibe w₄[x]. Debe retrasar la operación porque wl₄[x] está en conflicto con rl₅[x].

4. El sincronizador recibe w₅[x]. Debe retrasar la operación porque wl₅[x] está en conflicto con rl₄[x].

Dado que ninguna de las transacciones puede liberar el rl[x] que posee, y dado que ninguna de ellas puede continuar hasta que se asigne su wl[x], las transacciones están bloqueadas mutuamente. Este tipo de abrazo mortal ocurre comúnmente cuando una transacción busca una gran cantidad de datos que contengan un determinado valor y luego los actualiza. Esto origina la asignación de un bloqueo de lectura en cada uno de estos datos y luego la conversión de estos bloqueos en bloqueos de escritura.

El sincronizador requiere una estrategia para detectar bloqueos mutuos, de tal manera que no existan transacciones que permanezcan bloqueadas. Una estrategia es utilizar lapsos de tiempo. Si el sincronizador descubre que una transacción está esperando mucho tiempo por un bloqueo, simplemente asume que puede existir un bloqueo mutuo que involucre esta transacción y por lo tanto la cancela.


Referencias

1. Berstein P.A., Shipman D.W., Wong W.S., Formal Aspects of Serializability in Database Concurrency Control, IEEE Trans. on Software Engineering, 1979, 5, 3, 203-216, Mayo
   
   

2. Bjork L.A., Davies C.T., The Semantics of the Preservation and Recovery of Integrity in a Data System, Technical Report TR-02.540, IBM}, Diciembre,1972,
   
   

3. Papadimitriou C.H., Serializability of Concurrent Database Updates, Journal of the ACM, 1979, 26, 4, 631-653, Octubre
   
   

4. Papadimitriou C.H., The Theory of Concurrency Control, Computer Science Press, Rockville, MD, 1986
   
   

5. Lomet D.B., Process Structuring, Synchronization and Recovery using Atomic Actions, ACM SIGPLAN Notices, 1977, 12, 3, 128-137, Marzo
   
   

6. Devor C., Carlson C.R., Structural Locking Mechanisms and Their Effect on Database Management System Performance, Information Systems, 1982, 7, 2, 345-358.
   
   

7. Eswaran K.P., Gary J.N., Lorie R.A., Traiger I.L., Liu M.T., The Notions of Consistency and Predicate Locks in a Database System, Comm. ACM, 1976, 19, 11, 624-633, Noviembre.
   
   

8. Galler B.I., Bos L., A Model of Transaction Blocking in Databases, Performance Evaluation, 1983, 3, 95-122
   
   

9. Stearns R.E., Lewis P.M., Rosenkrantz D.J., Concurrency Control for Database Systems, Proc. 17th Symp. on Foundations of Computer Sience, IEEE, 1976, 19-32
   
   

10. Gary J.N., Lorie R.A., Putzulo G.R., Traiger J.L., Granularity of Locks and Degrees of Consistency in a Shared Database, Research Report RJ1654, IBM, 1975, Setiembre.
    
    

11. Yannakakis M., Serializability by Locking, Journal of the ACM, 1984, 31, 2, 227-244.
    
    

12. Mitra D., Weinberger P.J., Probabilistic Models of Database Locking: Solutions, Computational Algorithms and Asymptotics, Journal of the ACM, 1984, 31, 4, 855-878, Octubre.
    
    

13. Potier D., Leblanc P., Analysis of Locking Policies in Database Management Systems, Comm. ACM, 1980, 23, 10, 584-593, Octubre
    
    

14. Stearns R.E., Lewis P.M., Rosenkrantz D.J., Concurrency Control for Database Systems , Proc. 17th Symp. on Foundations of Computer Sience, IEEE, 1976, 19-32.

15. Hadzilacos V., An Operational Model for Database System Reliability, Proc. 2nd ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1983, Atlanta, GA, Marzo, 244-256
    
    

16. Hadzilacos V., A Theory of Reliability in Database System, Proc. 4th ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 1986, Atlanta, GA, Abril, 217-225.