Transacciones
Atómicas
Las técnicas de
sincronización son de bajo nivel:
- El programador debe
enfrentarse directamente con los detalles de:
- La exclusión mutua.
- El manejo de las regiones
críticas.
- La prevención de bloqueos.
- La recuperación de fallas.
Se
precisan técnicas de abstracción de mayor nivel que:
- Oculten estos aspectos
técnicos.
- Permitan a los programadores concentrarse
en los algoritmos y la forma en que los procesos trabajan juntos en
paralelo.
Tal
abstracción la llamaremos transacción atómica, transacción o acción
atómica.
La principal
propiedad de la transacción atómica es el “todo o nada”:
- O se hace todo lo que se tenía
que hacer como una unidad o no se hace nada.
- Ejemplo:
- Un cliente llama al Banco
mediante una PC con un módem para:
- Retirar dinero de una cuenta.
- Depositar el dinero en otra
cuenta.
- La operación tiene dos etapas.
- Si la conexión telefónica
falla luego de la primer etapa pero antes de la segunda:
- Habrá un retiro pero no un
depósito.
- La solución consiste en
agrupar las dos operaciones en una transacción atómica:
- Las dos operaciones
terminarían o no terminaría ninguna.
- Se debe regresar al estado
inicial si la transacción no puede concluir.
El
Modelo de Transacción
- El sistema consta de varios procesos
independientes que pueden fallar aleatoriamente.
- El software subyacente maneja transparentemente
los errores de comunicación.
Almacenamiento
Estable
Se puede implantar
con una pareja de discos comunes.
Cada bloque de la
unidad 2 es una copia exacta (espejo) del bloque correspondiente en la unidad
1.
Cuando se actualiza
un bloque:
- Primero se actualiza y verifica
el bloque de la unidad 1.
- Luego se actualiza y verifica
el bloque de la unidad 2.
Si
el sistema falla luego de actualizar la unidad 1 y antes de actualizar la
unidad 2:
- Luego de la recuperación se
pueden comparar ambos discos bloque por bloque:
- Se puede actualizar la unidad
2 en función de la 1.
Si
se detecta el deterioro espontáneo de un bloque, se lo regenera partiendo del
bloque correspondiente en la otra unidad.
Un esquema de este
tipo es adecuado para las aplicaciones que requieren de un alto grado de
tolerancia de fallos, por ej. las
transacciones atómicas.
Primitivas
de Transacción
Deben ser proporcionadas
por el sistema operativo o por el sistema de tiempo de ejecución del lenguaje.
Ejemplos:
- Begin_transaction: los comandos siguientes
forman una transacción.
- End_transaction: termina la transacción
y se intenta un compromiso.
- Abort_transaction: se elimina la transacción;
se recuperan los valores anteriores.
- Read: se leen datos de un
archivo (o algún otro objeto).
- Write: se escriben datos en un
archivo (o algún otro objeto).
Las
operaciones entre Begin y End forman el cuerpo de la transacción y
deben ejecutarse todas o ninguna de ellas:
- Pueden ser llamadas al sistema,
procedimiento de biblioteca o enunciados en un lenguaje.
Propiedades
de las Transacciones
Las propiedades
fundamentales son:
- Serialización:
- Las transacciones concurrentes
no interfieren entre sí.
- Atomicidad:
- Para el mundo exterior, la
transacción ocurre de manera indivisible.
- Permanencia:
- Una vez comprometida
una transacción, los cambios son permanentes.
La serialización garantiza que si dos o más
transacciones se ejecutan al mismo tiempo:
- El resultado final aparece como
si todas l as transacciones se ejecutasen de manera secuencial en
cierto orden:
- Para cada una de ellas y para
los demás procesos.
La atomicidad
garantiza que cada transacción no ocurre o bien se realiza en su totalidad:
- Se presenta como una acción
indivisible e instantánea.
La permanencia
se refiere a que una vez comprometida una transacción:
- Sigue adelante y los resultados
son permanentes.
Transacciones
Anidadas
Se presentan cuando
las transacciones pueden contener subtransacciones
(procesos hijos) que:
- Se ejecuten en paralelo entre
sí en procesadores distintos.
- Pueden originar nuevas subtransacciones.
Implantación
del Modelo de Transacción
Existen varios
métodos de implantación:
Espacio
de Trabajo Particular
Consiste en que
cuando un proceso inicia una transacción se le otorga un espacio de
trabajo particular:
- Contiene todos los archivos (y
otros objetos) a los cuales tiene acceso.
- Las lecturas y escrituras irán
a este espacio hasta que la transacción se complete o aborte:
- El “espacio real” es el
sistema de archivos normal.
- Significa alto consumo de
recursos por las copias de los objetos al espacio de trabajo particular.
Cuando
un proceso inicia una transacción, basta crear un espacio de trabajo
particular para él que sea vacío excepto por un apuntador de regreso al espacio
de trabajo de su proceso padre.
Para una transacción
del nivel superior el espacio de trabajo del padre es el sistema
de archivos “real”.
Cuando el proceso abre
un archivo para lectura, se siguen los apuntadores de regreso hasta
localizar el archivo en el espacio de trabajo del padre (o algún antecesor).
Cuando se abre
un archivo para escritura:
- Se lo localiza de manera
similar que para lectura.
- Se copia en primer lugar al
espacio de trabajo particular:
- Una optimización consiste en
copiar solo el índice del archivo en el espacio de trabajo particular:
- El índice es el bloque de
datos asociado a cada archivo e indica la localización de sus bloques en
el disco.
- Es el nodo-i correspondiente.
La
lectura por medio del índice particular (del espacio de trabajo particular)
no es problemática, pues las direcciones en disco a las que referencia son las
originales.
La modificación
de un bloque de un archivo requiere:
- Hacer una copia del bloque.
- Insertar en el índice la
dirección de la copia.
La
modificación sobre la copia no afecta al bloque original.
Un tratamiento
similar se da al agregado de bloques; los nuevos bloques se llaman bloques
sombra (shadow blocks).
El proceso que
ejecuta la transacción ve el archivo modificado pero los demás procesos ven el
archivo original.
Si la
transacción aborta (termina anormalmente):
- El espacio de trabajo
particular se elimina.
- Los bloques particulares a los
que apunta se colocan nuevamente en la lista de bloques libres.
Si
la transacción se compromete (termina normalmente):
- Los índices particulares se
desplazan al espacio de trabajo del padre de manera atómica.
- Los bloques que no son
alcanzables se colocan en la lista de bloques libres.
Bitácora
de Escritura Anticipada
Este método también
se denomina lista de intenciones.
Los archivos realmente
se modifican pero antes de cambiar cualquier bloque:
- Se graba un registro en la bitácora
(“log”) de escritura anticipada en un espacio
de almacenamiento estable:
- Se indica la transacción que
produce el cambio, el archivo y bloque modificados y los valores anterior
y nuevo.
Si
la transacción tiene éxito y se hace un compromiso:
- Se escribe un registro del compromiso
en la bitácora.
- Las estructuras de datos no
tienen que modificarse, puesto que ya han sido actualizadas.
Si
la transacción aborta:
- Se puede utilizar la bitácora
para respaldo del estado original:
- A partir del final y hacia
atrás:
- Se lee cada registro de la
bitácora.
- Se deshace cada cambio descripto en él.
- Esta acción se denomina retroalimentación.
Por
medio de la bitácora se puede:
- Ir hacia adelante (realizar la
transacción).
- Ir hacia atrás (deshacer la
transacción).
Protocolo
de Compromiso de Dos Fases (Two - Phase
Commit)
Uno de los procesos
que intervienen funciona como el coordinador.
El coordinador
escribe una entrada en la bitácora para indicar que inicia el
protocolo.
El coordinador
envía a cada uno de los procesos relacionados (subordinados) un mensaje para
que estén preparados para el compromiso.
Cuando un subordinado
recibe el mensaje:
- Verifica si está listo para
comprometerse.
- Escribe una entrada en la
bitácora.
- Envía de regreso su decisión.
Cuando
el coordinador ha recibido todas las respuestas sabe si debe establecer
el compromiso o abortar:
- Si todos los procesos están
listos para comprometerse cierra la transacción.
- Si alguno de los procesos no se
compromete (o no responde) la transacción se aborta.
- El coordinador:
- Escribe una entrada en la
bitácora.
- Envía un mensaje a cada
subordinado para informarle de la decisión.
Control de Concurrencia en el Modelo de
Transacción
Los algoritmos
de control de concurrencia son necesarios cuando se ejecutan varias
transacciones de manera simultánea:
- En distintos procesos.
- En distintos procesadores.
Los
principales algoritmos son:
- El de la cerradura.
- El del control optimista de la
concurrencia.
- El de las marcas de tiempo.
Cerradura
(locking)
Cuando un proceso
debe leer o escribir en un archivo (u otro objeto) como parte de una
transacción, primero cierra el archivo.
La cerradura
se puede hacer mediante:
- Un único manejador centralizado
de cerraduras.
- Un manejador local de cerraduras
en cada máquina.
El manejador
de cerraduras:
- Mantiene una lista de los
archivos cerrados.
- Rechaza todos los intentos por
cerrar archivos ya cerrados por otros procesos.
El
sistema de transacciones generalmente adquiere y libera las cerraduras sin
acción por parte del programador.
Una mejora
consiste en distinguir las cerraduras para lectura de las cerraduras
para escritura.
Una cerradura
para lectura no impide otras cerraduras para lectura:
- Las cerraduras para lectura se
comparten.
Una
cerradura para escritura sí impide otras cerraduras (de lectura o de
escritura):
- Las cerraduras para escritura no
se comparten, es decir que deben ser exclusivas.
El elemento
por cerrar puede ser un archivo, un registro, un campo, etc. y lo relativo
al tamaño del elemento por cerrar se llama la granularidad
de la cerradura.
Mientras más fina
sea la granularidad:
- Puede ser más precisa la
cerradura.
- Se puede lograr un mayor
paralelismo en el acceso al recurso.
- Se requiere un mayor número de
cerraduras.
Generalmente
se utiliza la cerradura de dos fases:
- El proceso adquiere todas las
cerraduras necesarias durante la fase de crecimiento.
- El proceso las libera en la fase
de reducción.
Se
deben evitar situaciones de aborto en cascada:
- Se graba en un archivo y luego
se libera su cerradura.
- Otra transacción lo cierra,
realiza su trabajo y luego establece un compromiso.
- La transacción original aborta.
- La segunda transacción (ya
comprometida) debe deshacerse, ya que sus resultados se basan en un archivo
que no debería haber visto cuando lo hizo.
Las
cerraduras comunes y de dos fases pueden provocar bloqueos cuando
dos procesos intentan adquirir la misma pareja de cerraduras pero en orden
opuesto, por lo tanto se deben utilizar técnicas de prevención y de detección
de bloqueos para superar el problema.
Control
Optimista de la Concurrencia
La idea es muy
sencilla:
- Se sigue adelante y se hace
todo lo que se deba hacer, sin prestar atención a lo que hacen los demás.
- Se actúa a posteriori si se presenta
algún problema.
Se
mantiene un registro de los archivos leídos o grabados.
En el momento del compromiso:
- Se verifican todas las demás
transacciones para ver si alguno de los archivos ha sido modificado desde
el inicio de la transacción:
- Si esto ocurre la transacción
aborta.
- Si esto no ocurre se realiza
el compromiso.
Las
principales ventajas son:
- Ausencia de bloqueos.
- Paralelismo máximo ya que no se
esperan cerraduras.
La principal
desventaja es:
- Re-ejecución de la transacción
en caso de falla.
- La probabilidad de fallo puede
crecer si la carga de trabajo es muy alta.
Marcas de Tiempo
Se asocia a cada
transacción una marca de tiempo al iniciar (begin_transaction).
Se garantiza que
las marcas son únicas mediante el algoritmo de Lamport.
Cada archivo del
sistema tiene asociadas una marca de tiempo para la lectura y otra para
la escritura, que indican la última transacción comprometida que
realizó la lectura o escritura.
Cuando un proceso
intente acceder a un archivo, lo logrará si las marcas de tiempo de lectura y
escritura son menores (más antiguas) que la marca de la transacción activa.
Si la marca de
tiempo de la transacción activa es menor que la del archivo que intenta
acceder:
- Una transacción iniciada
posteriormente ha accedido al archivo y ha efectuado un compromiso.
- La transacción activa se ha
realizado tarde y se aborta.
En
el método de las marcas no preocupa que las transacciones concurrentes utilicen
los mismos archivos, pero sí importa que la transacción con el número menor esté
en primer lugar.
Las marcas de
tiempo tienen propiedades distintas a las de los bloqueos:
- Una transacción aborta cuando
encuentra una marca mayor (posterior).
- En iguales circunstancias y en
un esquema de cerraduras podría esperar o continuar inmediatamente.
Las
marcas de tiempo son libres de bloqueos, lo que es una gran ventaja.