El control de concurrencia se puede implementar de diferentes maneras . Una forma de implementarlo es usando Locks . Ahora, analicemos el protocolo de ordenación de sellos de tiempo.
Como se presentó anteriormente, la marca de tiempo es un identificador único creado por el DBMS para identificar una transacción. Por lo general, se asignan en el orden en que se envían al sistema. Consulte la marca de tiempo de una transacción T como TS(T) . Para conocer los conceptos básicos de la marca de tiempo, puede consultar aquí .
Protocolo de ordenación de marcas de tiempo:
la idea principal de este protocolo es ordenar las transacciones en función de sus marcas de tiempo. Un programa en el que participan las transacciones es serializable y el único programa serial equivalente permitido tiene las transacciones en el orden de sus valores de marca de tiempo. En pocas palabras, el cronograma es equivalente a la orden en serie particular correspondiente a la orden de las marcas de tiempo de la transacción . Un algoritmo debe garantizar que, para cada elemento al que acceden Operaciones en conflicto en la programación, el orden en que se accede al elemento no infringe el ordenamiento. Para garantizar esto, use dos valores de marca de tiempo relacionados con cada elemento de la base de datos X .
- W_TS(X) es la marca de tiempo más grande de cualquier transacción que ejecutó write(X) con éxito.
- R_TS(X) es la marca de tiempo más grande de cualquier transacción que ejecutó read(X) con éxito.
Pedido básico de marca de tiempo:
cada transacción recibe una marca de tiempo en función de cuándo ingresa al sistema. Supongamos que si una transacción antigua Ti tiene una marca de tiempo TS(T i ), a una nueva transacción T j se le asigna una marca de tiempo TS(T j ) tal que TS(T i ) < TS(T j ) . El protocolo gestiona la ejecución concurrente de modo que las marcas de tiempo determinen el orden de serialización. El protocolo de ordenación de marcas de tiempo garantiza que cualquier operación de lectura y escritura en conflicto se ejecute en el orden de las marcas de tiempo. Cada vez que alguna Transacción T intenta emitir un R_item(X) o un W_item(X), el algoritmo básico TO compara la marca de tiempo de T conR_TS(X) y W_TS(X) para garantizar que no se viole la orden de la marca de tiempo. Esto describe el protocolo TO básico en los dos casos siguientes.
- Siempre que una Transacción T emita una operación W_item(X) , verifique las siguientes condiciones:
- Si R_TS(X) > TS(T) o si W_TS(X) > TS(T) , entonces cancela y revierte T y rechaza la operación. más,
- Ejecute la operación W_item(X) de T y establezca W_TS(X) en TS(T).
- Siempre que una Transacción T emita una operación R_item(X) , verifique las siguientes condiciones:
- Si W_TS(X) > TS(T) , entonces aborte y rechace T y rechace la operación, de lo contrario
- Si W_TS(X) <= TS(T), ejecute la operación R_item(X) de T y establezca R_TS(X) en el mayor de TS(T) y R_TS(X) actual.
Cada vez que el algoritmo básico TO detecta dos operaciones en conflicto que ocurren en un orden incorrecto, rechaza la última de las dos operaciones abortando la Transacción que la emitió. Se garantiza que los programas producidos por Basic TO son serializables en conflicto . Ya discutimos que el uso de la marca de tiempo puede garantizar que nuestro cronograma esté libre de puntos muertos .
Un inconveniente del protocolo básico TO es que todavía es posible la reversión en cascada . Supongamos que tenemos una Transacción T 1 y T 2 ha usado un valor escrito por T 1 . Si T 1 se anula y se vuelve a enviar al sistema, T también debe anularse y revertirse. Entonces, el problema de los abortos en cascada aún prevalece.
Resumamos las ventajas y desventajas del protocolo TO básico:
- El protocolo de orden de marca de tiempo garantiza la serialización ya que el gráfico de precedencia tendrá la forma:
Imagen – Gráfico de precedencia para ordenar TS
- El protocolo de marca de tiempo garantiza la ausencia de interbloqueos, ya que ninguna transacción espera.
- Pero es posible que la programación no esté libre de cascadas y que ni siquiera sea recuperable.
Orden estricto de marcas de tiempo:
una variación de Basic TO se llama Strict TO garantiza que los horarios sean tanto estrictos como serializables en conflicto. En esta variación, una Transacción T que emite un R_item(X) o W_item(X) tal que TS(T) > W_TS(X) tiene su operación de lectura o escritura retrasada hasta que la Transacción T ‘ que escribió los valores de X se ha comprometido o abortado.
Preguntas relacionadas con GATE: