Sincronización
en Sistemas Distribuidos
-
Introducción
a la Sincronización en Sistemas Distribuidos
-
Sincronización
de Relojes
-
Relojes Lógicos
-
Relojes Físicos
-
Algoritmos
Para la Sincronización de Relojes
-
Algoritmo de
Cristian
-
Algoritmo de
Berkeley
-
Algoritmos con
Promedio
-
Varias Fuentes
Externas de Tiempo
-
Exclusión
Mutua
-
Un Algoritmo
Centralizado
-
Un Algoritmo
Distribuido
-
Un Algoritmo
de Anillo de Fichas (Token Ring)
-
Algoritmos de
Elección
-
El Algoritmo
del Grandulón o de García-Molina
-
Un Algoritmo
de Anillo
-
Transacciones
Atómicas
-
El Modelo de
Transacción
-
Almacenamiento
Estable
-
Primitivas de
Transacción
-
Propiedades
de las Transacciones
-
Transacciones
Anidadas
-
Implantación
del Modelo de Transacción
-
Espacio de Trabajo
Particular
-
Bitácora
de Escritura Anticipada
-
Protocolo de
Compromiso de Dos Fases (Two - Phase Commit)
-
Control de Concurrencia
en el Modelo de Transacción
-
Cerradura (locking)
-
Control Optimista
de la Concurrencia
-
Marcas de Tiempo
-
Resumen
-
Bloqueos en Sistemas
Distribuidos
-
Detección
Distribuida de Bloqueos
-
Detección
Centralizada de Bloqueos
-
Detección
Distribuida de Bloqueos
-
Prevención
Distribuida de Bloqueos
-
Fin
Introducción
a la Sincronización en Sistemas Distribuidos
Además de la comunicación, es fundamental la forma
en que los procesos [25, Tanenbaum]:
-
Cooperan.
-
Se sincronizan entre sí.
Ejemplos:
-
Forma de implantar las regiones críticas.
-
Forma de asignar recursos en un sistema distribuido.
Los problemas relativos a las regiones críticas, exclusión
mutua y la sincronización:
-
Generalmente se resuelven en sistemas de una sola cpu con métodos
como los semáforos y los monitores:
-
Se basan en la memoria compartida.
-
No son aplicables a sistemas distribuidos.
Otro problema de gran importancia es el tiempo y la forma de
medirlo, ya que juega un papel fundamental en algunos modelos
de sincronización.
Inicio:
Fin:
Sincronización
de Relojes
Generalmente los algoritmos distribuidos tienen las siguientes
propiedades
[25,
Tanenbaum]:
-
La información relevante se distribuye entre varias máquinas.
-
Los procesos toman las decisiones solo con base en la información
disponible en forma local.
-
Debe evitarse un único punto de fallo en el sistema.
-
No existe un reloj común o alguna otra fuente precisa
del tiempo global.
Los primeros tres puntos indican que es inaceptable reunir toda la información
en un solo lugar para su procesamiento, pero lograr la sincronización
sin centralización requiere hacer las cosas distintas
al caso de los sistemas operativos tradicionales.
El último punto también es crucial:
-
En un sistema centralizado el tiempo no es ambiguo.
-
En un sistema distribuido no es trivial poner de acuerdo a todas las máquinas
en la hora.
-
Se requiere un acuerdo global en el tiempo, pues la falta de sincronización
en los relojes puede ser drástica en procesos dependientes del tiempo.
La pregunta es si es posible sincronizar todos los relojes en
un sistema distribuido.
Inicio:
Fin:
Relojes Lógicos
Las computadoras poseen un circuito para el registro del tiempo conocido
como dispositivo reloj [25, Tanenbaum].
Es un cronómetro consistente en un cristal de cuarzo de
precisión sometido a una tensión eléctrica que:
-
Oscila con una frecuencia bien definida que depende de:
-
Al forma en que se corte el cristal.
-
El tipo de cristal.
-
La magnitud de la tensión.
-
A cada cristal se le asocian dos registros:
-
Registro contador.
-
Registro mantenedor.
-
Cada oscilación del cristal decrementa en “1” al contador.
-
Cuando el contador llega a “0”:
-
Se genera una interrupción.
-
El contador se vuelve a cargar mediante el registro mantenedor.
-
Se puede programar un cronómetro para que genere una interrupción
“x” veces por segundo.
-
Cada interrupción se denomina marca de reloj.
Para una computadora y un reloj:
-
No interesan pequeños desfasajes del reloj porque:
-
Todos los procesos de la máquina usan el mismo reloj y tendrán
consistencia
interna.
-
Importan los tiempos relativos.
Para varias computadoras con sus respectivos relojes:
-
Es imposible garantizar que los cristales de computadoras distintas oscilen
con la misma frecuencia.
-
Habrá una pérdida de sincronía en los relojes (de
software), es decir que tendrán valores distintos al
ser leidos.
La diferencia entre los valores del tiempo se llama distorsión
del reloj y podría generar fallas en los programas dependientes
del tiempo.
Lamport demostró que la sincronización de relojes es
posible y presentó un algoritmo para lograrlo.
Lamport señaló que la sincronización
de relojes no tiene que ser absoluta:
-
Si 2 procesos no interactúan no es necesario que sus relojes estén
sincronizados.
-
Generalmente lo importante no es que los procesos estén de acuerdo
en la hora, pero sí importa que coincidan en el orden en que
ocurren los eventos.
Para ciertos algoritmos lo que importa es la consistencia interna
de los relojes:
-
No interesa su cercanía particular al tiempo real (oficial).
-
Los relojes se denominan relojes lógicos.
Los relojes físicos son relojes que:
-
Deben ser iguales (estar sincronizados).
-
No deben desviarse del tiempo real más allá de cierta
magnitud.
Para sincronizar los relojes lógicos, Lamport definió
la relación ocurre antes de (happens-before):
-
Si “a” y “b” son eventos en el mismo proceso y “a”
ocurre antes de “b”, entonces “a –> b” es verdadero.
-
“Ocurre antes de” es una relación transitiva:
-
Si “a –> b” y “b –> c”, entonces “a –> c”.
-
Si dos eventos “x” e “y” están en procesos diferentes
que no intercambian mensajes, entonces “x –> y” no es verdadero,
pero tampoco lo es “y –> x”:
-
Se dice que son eventos concurrentes.
Necesitamos una forma de medir el tiempo tal que a cada evento “a”,
le podamos asociar un valor del tiempo “C(a)” en el que todos
los procesos estén de acuerdo:
-
Se debe cumplir que:
-
Si “a –> b” entonces “C(a) < C(b)”.
-
El tiempo del reloj, “C”, siempre debe ir hacia adelante
(creciente), y nunca hacia atrás (decreciente).
El algoritmo de Lamport asigna tiempos a los eventos.
Consideramos tres procesos que se ejecutan en diferentes máquinas,
cada una con su propio reloj y velocidad (ver Figura 9.1 [25,
Tanenbaum]):
-
El proceso “0” envía el mensaje “a” al proceso “1”
cuando el reloj de “0” marca “6”.
-
El proceso “1” recibe el mensaje “a” cuando su reloj marca
“16”.
-
Si el mensaje acarrea el tiempo de inicio “6”, el proceso “1”
considerará que tardó 10 marcas de reloj en viajar.
-
El mensaje “b” de “1” a “2” tarda 16 marcas de reloj.
-
El mensaje “c” de “2” a “1” sale en “60” y
llega en “56”, tardaría un tiempo negativo, lo cual
es imposible.
-
El mensaje “d” de “1” a “0” sale en “64” y
llega en “54”.
-
Lamport utiliza la relación “ocurre antes de”:
-
Si “c” sale en “60” debe llegar en “61” o en un tiempo
posterior.
-
Cada mensaje acarrea el tiempo de envío, de acuerdo con el reloj
del emisor.
-
Cuando un mensaje llega y el reloj del receptor muestra un valor anterior
al tiempo en que se envió el mensaje:
-
El receptor adelanta su reloj para que tenga una unidad más
que el tiempo de envío.
Este algoritmo cumple nuestras necesidades para el tiempo global,
si se hace el siguiente agregado:
-
Entre dos eventos cualesquiera, el reloj debe marcar al menos una vez.
-
Dos eventos no deben ocurrir exactamente al mismo tiempo.
Con este algoritmo se puede asignar un tiempo a todos los eventos en
un sistema distribuido, con las siguientes condiciones:
-
Si “a” ocurre antes de “b” en el mismo proceso, “C(a)
< C(b)”.
-
Si “a” y “b” son el envío y recepción de un
mensaje, “C(a) < C(b)”.
-
Para todos los eventos “a” y “b”, “C(a)” es distinto
de “C(b)”.
Inicio:
Fin:
Relojes Físicos
El algoritmo de Lamport proporciona un orden de eventos sin ambigüedades,
pero [25, Tanenbaum]:
-
Los valores de tiempo asignados a los eventos no tienen porqué ser
cercanos a los tiempos reales en los que ocurren.
-
En ciertos sistemas (ej.: sistemas de tiempo real ), es importante
la hora real del reloj:
-
Se precisan relojes físicos externos (más de uno).
-
Se deben sincronizar:
-
Con los relojes del mundo real.
-
Entre sí.
La medición del tiempo real con alta precisión no es sencilla.
Desde antiguo el tiempo se ha medido astronómicamente.
Se considera el día solar al intervalo entre dos tránsitos
consecutivos del sol, donde el tránsito del sol es el evento en
que el sol alcanza su punto aparentemente más alto en el cielo.
El segundo solar se define como 1 / 86.400 de un día
solar.
Como el período de rotación de la tierra no es constante,
se considera el segundo solar promedio de un gran número
de días.
Los físicos definieron al segundo como el tiempo que tarda
el átomo de cesio 133 para hacer 9.192.631.770 transiciones:
-
Se tomó este número para que el segundo atómico
coincida con el segundo solar promedio de 1958.
La Oficina Internacional de la Hora en París (BIH) recibe
las indicaciones de cerca de 50 relojes atómicos en el mundo y calcula
el tiempo atómico internacional (TAI).
Como consecuencia de que el día solar promedio (DSP)
es cada vez mayor, un día TAI es 3 mseg menor que un DSP:
-
La BIH introduce segundos de salto para hacer las correcciones necesarias
para que permanezcan en fase:
-
El sistema de tiempo basado en los segundos TAI.
-
El movimiento aparente del sol.
-
Surge el tiempo coordenado universal (UTC).
El Instituto Nacional del Tiempo Estándar (NIST) de
EE. UU. y de otros países:
-
Operan estaciones de radio de onda corta o satélites de comunicaciones.
-
Transmiten pulsos UTC con cierta regularidad establecida (cada segundo,
cada 0,5 mseg, etc.).
-
Se deben conocer con precisión la posición relativa del emisor
y del receptor:
-
Se debe compensar el retraso de propagación de la señal.
-
Si la señal se recibe por módem también se debe compensar
por la ruta de la señal y la velocidad del módem.
-
Se dificulta la obtención del tiempo con una precisión extremadamente
alta.
Inicio:
Fin:
Algoritmos
Para la Sincronización de Relojes
Si una máquina tiene un receptor de UTC, todas
las máquinas deben sincronizarse con ella [25,
Tanenbaum].
Si ninguna máquina tiene un receptor de UTC:
-
Cada máquina lleva el registro de su propio tiempo.
-
Se debe mantener el tiempo de todas las máquinas tan cercano
como sea posible.
Se supone que cada máquina tiene un cronómetro que
provoca una interrupción “h” veces por segundo.
Cuando el cronómetro se detiene, el manejador de interrupciones
añade “1” a un reloj en software.
El reloj en software mantiene un registro del número
de marcas (interrupciones) a partir de cierta fecha acordada antes;
al valor de este reloj se lo llama “C”.
Cuando el tiempo UTC es “t”, el valor del reloj en la
máquina “p” es “Cp(t)”:
-
Lo ideal sería que “Cp(t)” = “t” para toda “p”
y todo “t”:
-
Lo real es que los cronómetros no realizan interrupciones
exactamente
“h” veces por segundo:
-
Poseen un error relativo de aproximadamente 10-5 .
-
El fabricante especifica una constante “ r ”
llamada
tasa
máxima de alejamiento que acota el error.
-
El cronómetro funciona dentro de su especificación si existe
una constante “ r ” y se cumple:
Si dos relojes se alejan de UTC en la dirección opuesta:
-
En un instante Dt luego de la sincronización
podrían estar tan alejados como: 2 rDt.
-
Para garantizar que no difieran más de d:
-
Se deben volver a sincronizar (en software) al menos cada d
/ 2 r segundos.
Inicio:
Fin:
Algoritmo de Cristian
Es adecuado para sistemas en los que:
-
Una máquina tiene un receptor UTC, por lo que se la llama
despachador
del tiempo.
-
El objetivo es sincronizar todas las máquinas con ella.
Cada máquina envía un mensaje al servidor para solicitar
el tiempo actual, periódicamente, en un tiempo no mayor que d
/ 2 r segundos.
El despachador del tiempo responde prontamente con un mensaje
que contiene el tiempo actual “CUTC”.
Cuando el emisor obtiene la respuesta puede hacer que su tiempo sea
“CUTC”.
Un gran problema es que el tiempo no puede correr hacia atrás:
-
“CUTC” no puede ser menor que el tiempo actual “C”
del emisor.
-
La atención del requerimiento en el servidor de tiempos requiere
un tiempo del manejador de interrupciones.
-
También se debe considerar el tiempo de transmisión.
El cambio del reloj se debe introducir de manera global:
-
Si el cronómetro genera 100 interrupciones por segundo:
-
Cada interrupción añade 10 mseg al tiempo.
-
Para atrasar solo agregaría 9 mseg.
-
Para adelantar agregaría 11 mseg.
La corrección por el tiempo del servidor y el tiempo de transmisión
se hace midiendo en el emisor:
-
El tiempo inicial (envío) “T0”.
-
El tiempo final (recepción) “T1”.
-
Ambos tiempos se miden con el mismo reloj.
El tiempo de propagación del mensaje será (T1
- T0) / 2.
Si el tiempo del servidor para manejar la interrupción
y procesar el mensaje es “I”:
-
El tiempo de propagación será (T1 -
T0 - I) / 2.
Para mejorar la precisión:
-
Se toman varias mediciones.
-
Se descartan los valores extremos.
-
Se promedia el resto.
El tiempo de propagación se suma al tiempo del servidor
para sincronizar al emisor cuando éste recibe la respuesta.
Inicio:
Fin:
Algoritmo de Berkeley
En el algoritmo de Cristian el servidor de tiempo es pasivo.
En el algoritmo de Berkeley el servidor de tiempo:
-
Es activo.
-
Realiza un muestreo periódico de todas las máquinas para
preguntarles el tiempo.
-
Con las respuestas:
-
Calcula un tiempo promedio.
-
Indica a las demás máquinas que avancen su reloj o disminuyan
la velocidad del mismo hasta lograr la disminución requerida.
Es adecuado cuando no se dispone de un receptor UTC.
Inicio:
Fin:
Algoritmos con Promedio
Los anteriores son algoritmos centralizados.
Una clase de algoritmos descentralizados divide el tiempo en
intervalos
de resincronización de longitud fija:
-
El i -ésimo intervalo:
-
Inicia en “T0 + i R” y va hasta “T0 + (i
+ 1) R”.
-
“T0” es un momento ya acordado en el pasado.
-
“R” es un parámetro del sistema.
Al inicio de cada intervalo cada máquina transmite el tiempo
actual según su reloj.
Debido a la diferente velocidad de los relojes las transmisiones
no serán simultáneas.
Luego de que una máquina transmite su hora, inicializa un cronómetro
local para reunir las demás transmisiones que lleguen en cierto
intervalo “S”.
Cuando recibe todas las transmisiones se ejecuta un algoritmo para calcular
una nueva hora para los relojes.
Una variante es promediar los valores de todas las demás
máquinas.
Otra variante es descartar los valores extremos antes de promediar
(los “m” mayores y los “m” menores).
Una mejora al algoritmo considera la corrección por tiempos
de propagación.
Inicio:
Fin:
Varias Fuentes Externas
de Tiempo
Los sistemas que requieren una sincronización muy precisa
con UTC se pueden equipar con varios receptores de UTC.
Las distintas fuentes de tiempo generaran distintos rangos (intervalos
de tiempo) donde “caerán” los respectivos UTC, por lo
que es necesaria una sincronización.
Como la transmisión no es instantánea se genera una cierta
incertidumbre en el tiempo.
Cuando un procesador obtiene todos los rangos de UTC:
-
Verifica si alguno de ellos es ajeno a los demás y de serlo lo descarta
por ser un valor extremo.
-
Calcula la intersección (en el tiempo) de los demás rangos.
-
La intersección determina un intervalo cuyo punto medio será
el UTC y la hora del reloj interno.
Se deben compensar los retrasos de transmisión y las diferencias
de velocidades de los relojes.
Se debe asegurar que el tiempo no corra hacia atrás.
Se debe resincronizar periódicamente desde las fuentes
externas de UTC.
Inicio:
Fin:
Exclusión
Mutua
Cuando un proceso debe leer o actualizar ciertas estructuras de datos
compartidas [25, Tanenbaum]:
-
Primero ingresa a una región crítica para lograr la
exclusión
mutua y garantizar que ningún otro proceso utilizará
las estructuras de datos al mismo tiempo.
En sistemas monoprocesadores las regiones críticas se protegen con
semáforos, monitores y similares.
En sistemas distribuidos la cuestión es más compleja.
Inicio:
Fin:
Un Algoritmo Centralizado
La forma más directa de lograr la exclusión mutua en
un sistema distribuido es simular a la forma en que se lleva a cabo
en un sistema monoprocesador.
Se elige un proceso coordinador.
Cuando un proceso desea ingresar a una región crítica:
-
Envía un mensaje de solicitud al coordinador:
-
Indicando la región crítica.
-
Solicitando permiso de acceso.
-
Si ningún otro proceso está en ese momento en esa región
crítica:
-
El coordinador envía una respuesta otorgando el permiso.
-
Cuando llega la respuesta el proceso solicitante entra a la región
crítica.
Si un proceso pide permiso para entrar a una región crítica
ya asignada a otro proceso:
-
El coordinador no otorga el permiso y encola el pedido.
Cuando un proceso sale de la región crítica envía
un mensaje al coordinador para liberar su acceso exclusivo:
-
El coordinador extrae el primer elemento de la cola de solicitudes diferidas
y envía a ese proceso un mensaje otorgando el permiso, con lo cual
el proceso queda habilitado para acceder a la región crítica
solicitada.
Es un esquema sencillo, justo y con pocos mensajes de control.
La limitante es que el coordinador puede ser un cuello de botella
y puede fallar y bloquear a los procesos que esperan una respuesta de habilitación
de acceso.
Inicio:
Fin:
Un Algoritmo Distribuido
El objetivo es no tener un único punto de fallo (el coordinador
central).
Un ej. es el algoritmo de Lamport mejorado por Ricart y Agrawala.
Se requiere un orden total de todos los eventos en el sistema
para saber cuál ocurrió primero.
Cuando un proceso desea entrar a una región crítica:
-
Construye un mensaje con el nombre de la región crítica,
su número de proceso y la hora actual.
-
Envía el mensaje a todos los demás procesos y de manera conceptual
a él mismo.
-
Se supone que cada mensaje tiene un reconocimiento.
Si el receptor no está en la región crítica y no
desea entrar a ella, envía de regreso un mensaje o.k. al emisor.
Si el receptor ya está en la región crítica
no responde y encola la solicitud.
Si el receptor desea entrar a la región crítica pero
aún no lo logró, compara:
-
La marca de tiempo del mensaje recibido con,
-
La marca contenida en el mensaje que envió a cada uno.
-
La menor de las marcas gana.
-
Si el mensaje recibido es menor el receptor envía un o.k.
-
Si su propio mensaje tiene una marca menor el receptor no envía
nada y encola el pedido.
Luego de enviar las solicitudes un proceso:
-
Espera hasta que alguien más obtiene el permiso.
-
Cuando llegan todos los permisos puede entrar a la región crítica.
Cuando un proceso sale de la región crítica:
-
Envía mensajes o.k. a todos los procesos en su cola.
-
Elimina a todos los elementos de la cola.
La exclusión mutua queda garantizada sin bloqueo ni inanición.
El número de mensajes necesarios por entrada es “2(n - 1)”,
siendo “n” el número total de procesos en el sistema.
No existe un único punto de fallo sino “n”:
-
Si cualquier proceso falla no responderá a las solicitudes.
-
La falta de respuesta se interpretará como negación de acceso:
-
Se bloquearán los siguientes intentos de los demás
procesos por entrar a todas las regiones críticas.
Se incrementa la probabilidad de fallo en “n” veces y también
el tráfico en la red.
Se puede solucionar el bloqueo si:
-
El emisor espera y sigue intentando hasta que regresa una respuesta o,
-
El emisor concluye que el destinatario está fuera de servicio.
Otro problema es que:
-
Se utilizará una primitiva de comunicación en grupo o,
-
Cada proceso debe mantener la lista de miembros del grupo, incluyendo los
procesos que ingresan, los que salen y los que fallan.
-
Se complica para gran número de procesos.
Un importante problema adicional es que:
-
Todos los procesos participan en todas las decisiones referentes
a las entradas en las regiones críticas.
-
Se sobrecarga el sistema.
Una mejora consiste en permitir que un proceso entre a una región
crítica con el permiso de una mayoría simple de los demás
procesos (en vez de todos):
-
Luego de que un proceso otorgó el permiso a otro para entrar a una
región crítica, no puede otorgar el mismo permiso a otro
proceso hasta que el primero libere su permiso.
Inicio:
Fin:
Un Algoritmo de Anillo
de Fichas (Token Ring)
Los procesos se organizan por software formando un anillo lógico
asignándose a cada proceso una posición en el anillo.
Cada proceso sabe cuál es el siguiente luego de él.
Al inicializar el anillo se le da al proceso “0” una ficha
(token) que circula en todo el anillo, que se transfiere del proceso
“k”
al “k + 1” en mensajes puntuales.
Cuando un proceso obtiene la ficha de su vecino verifica si intenta
entrar a una región crítica:
-
En caso positivo:
-
El proceso entra a la región crítica, hace el proceso necesario
y sale de ella.
-
Después de salir pasa la ficha a lo largo del anillo:
-
No se puede entrar a una segunda región crítica con la misma
ficha (token o permiso).
-
En caso negativo:
En un instante dado solo un proceso puede estar en una región
crítica.
Si la ficha se pierde debe ser regenerada, pero es difícil
detectar su perdida:
-
La cantidad de tiempo entre las apariciones sucesivas de la ficha en la
red no está acotada, por ello es difícil decidir si está
perdida o demorada en algún proceso que no la libera.
La falla de un proceso es detectada cuando su vecino intenta sin
éxito pasarle la ficha:
-
Se lo debe eliminar del grupo y pasar la ficha al siguiente proceso activo.
-
Todos los procesos deben mantener la configuración actual del
anillo.
Inicio:
Fin:
Algoritmos
de Elección
Son los algoritmos para la elección de un proceso coordinador,
iniciador, secuenciador, etc. [25, Tanenbaum].
El objetivo de un algoritmo de elección es garantizar
que iniciada una elección ésta concluya con el acuerdo
de todos los procesos con respecto a la identidad del nuevo coordinador.
Inicio:
Fin:
El Algoritmo del Grandulón
o de García-Molina
Un proceso “P” inicia una elección cuando observa que
el
coordinador ya no responde a las solicitudes.
“P” realiza una elección de la siguiente manera:
-
Envía un mensaje elección a los demás procesos
con un número mayor.
-
Si nadie responde asume que gana la elección y se convierte en el
nuevo
coordinador.
-
Si un proceso con un número mayor responde, toma el control
y el trabajo de “P” termina.
Un proceso puede recibir en cualquier momento un mensaje elección
de otros procesos con un número menor:
-
Envía de regreso un mensaje o.k. al emisor para indicar que está
vivo y que tomará el control.
-
Realiza una elección salvo que ya esté haciendo alguna.
En cierto momento todos los procesos han declinado ante uno de ellos,
que será el nuevo coordinador, que envía un mensaje
coordinador
a todos los procesos para anunciarlo.
Si un proceso inactivo se activa realiza una elección:
-
Si él tiene el número más alto será el nuevo
coordinador:
-
Siempre gana el proceso que posee el número mayor, de ahí
el nombre “algoritmo del grandulón”.
Inicio:
Fin:
Un Algoritmo de Anillo
Se supone que los procesos tienen un orden físico o lógico,
es decir que cada proceso conoce a su sucesor.
Cuando algún proceso observa que el coordinador no funciona:
-
Construye un mensaje elección con su propio número
de proceso.
-
Envía el mensaje a su sucesor.
-
Si el sucesor está inactivo:
-
El emisor va hacia el siguiente número del anillo o al siguiente
de éste.
-
Continúa hasta localizar un proceso en ejecución.
-
En cada paso, al emisor añade su propio número de proceso
a la lista en el mensaje.
-
En cierto momento el mensaje regresa al proceso que lo inició:
-
El proceso lo reconoce al recibir un mensaje con su propio número
de proceso.
-
El mensaje de elección se transforma en mensaje coordinador
y circula nuevamente:
-
Informa a los demás procesos:
-
Quién es el coordinador, es decir, el miembro de la lista
con el número mayor.
-
Quiénes son los miembros del nuevo anillo.
-
Concluida la ronda de información el mensaje coordinador
se elimina y continúan los procesos.
Inicio:
Fin:
Transacciones
Atómicas
Las técnicas de sincronización ya vistas son de
bajo
nivel [25, Tanenbaum]:
-
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.
Inicio:
Fin:
El Modelo
de Transacción
Supondremos que [25, Tanenbaum]:
-
El sistema consta de varios procesos independientes que pueden fallar
aleatoriamente.
-
El software subyacente maneja transparentemente los errores de comunicación.
Inicio:
Fin:
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.
Inicio:
Fin:
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.
Inicio:
Fin:
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.
Inicio:
Fin:
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.
Inicio:
Fin:
Implantación
del Modelo de Transacción
Existen varios métodos de implantación [25,
Tanenbaum].
Inicio:
Fin:
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.
Inicio:
Fin:
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).
Inicio:
Fin:
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.
Inicio:
Fin:
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
[25, Tanenbaum]:
-
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.
Inicio:
Fin:
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.
Inicio:
Fin:
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.
Inicio:
Fin:
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.
Inicio:
Fin:
Resumen
Los diferentes esquemas ofrecen distintas ventajas pero el problema
principal es la gran complejidad de su implantación.
Inicio:
Fin:
Bloqueos en
Sistemas Distribuidos
Son peores que los bloqueos en sistemas monoprocesador [25,
Tanenbaum]:
-
Son más difíciles de evitar, prevenir, detectar y solucionar.
-
Toda la información relevante está dispersa en muchas máquinas.
Son especialmente críticos en sistemas de bases de datos
distribuidos.
Las estrategias usuales para el manejo de los bloqueos son:
-
Algoritmo del avestruz:
-
Detección:
-
Permitir que ocurran los bloqueos, detectarlos e intentar recuperarse de
ellos.
-
Prevención:
-
Hacer que los bloqueos sean imposibles desde el punto de vista estructural.
-
Evitarlos:
-
Evitar los bloqueos mediante la asignación cuidadosa de los recursos.
El algoritmo del avestruz merece las mismas consideraciones que
en el caso de mono-procesador.
En los sistemas distribuidos resulta muy difícil implantar
algoritmos para evitar los bloqueos:
-
Se requiere saber de antemano la proporción de cada recurso que
necesitará cada proceso.
-
Es muy difícil disponer de esta información en forma práctica.
Las técnicas más aplicables para el análisis de
los bloqueos en sistemas distribuidos son:
Inicio:
Fin:
Detección
Distribuida de Bloqueos
Cuando se detecta un bloqueo en un S. O. convencional se resuelve eliminando
uno o más procesos [25, Tanenbaum].
Cuando se detecta un bloqueo en un sistema basado en transacciones
atómicas se resuelve abortando una o más transacciones:
-
El sistema restaura el estado que tenía antes de iniciar la transacción.
-
La transacción puede volver a comenzar.
Las consecuencias de la eliminación de un proceso son mucho
menos severas si se utilizan las transacciones que en caso de que
no se utilicen.
Inicio:
Fin:
Detección Centralizada
de Bloqueos
Cada máquina mantiene la gráfica de recursos
de
sus propios procesos y recursos.
Un coordinador central mantiene la gráfica de recursos
de todo el sistema, que es la unión de todas las gráficas
individuales.
Cuando el coordinador detecta un ciclo elimina uno de los procesos
para
romper el bloqueo.
La información de control se debe transmitir explícitamente,
existiendo las siguientes variantes:
-
Cada máquina informa cada actualización al coordinador.
-
Cada máquina informa periódicamente las modificaciones desde
la última actualización.
-
El coordinador requiere la información cuando la necesita.
La información de control incompleta o retrasada puede
llevar a falsos bloqueos:
-
El coordinador interpreta erróneamente que existe un bloqueo y elimina
un proceso.
-
Una posible solución es utilizar el algoritmo de Lamport
para disponer de un tiempo global.
Inicio:
Fin:
Detección Distribuida
de Bloqueos
Un algoritmo típico es el de Chandy-Misra-Haas.
Los procesos pueden solicitar varios recursos (por ejemplo cerraduras)
al
mismo tiempo, en vez de uno cada vez.
Se permiten las solicitudes simultáneas de varios procesos:
-
Un proceso puede esperar a uno o más recursos simultáneamente.
-
Los recursos que espera un proceso pueden ser locales o remotos
(de otra máquina).
Si el proceso “0” se bloquea debido al proceso “1”:
-
Se genera un mensaje de exploración que se envía al
proceso (o procesos) que detienen los recursos necesarios.
-
El mensaje consta de tres números:
-
El proceso recién bloqueado, el proceso que envía el mensaje
y el proceso al cual se envía.
-
Al llegar el mensaje el receptor verifica si él mismo espera a algunos
procesos, en cuyo caso:
-
El mensaje se actualiza:
-
Se conserva el primer campo.
-
Se reemplaza el segundo por su propio número de proceso y el tercero
por el número del proceso al cual espera.
-
El mensaje se envía al proceso debido al cual se bloquea:
-
Si se bloquea debido a varios procesos les envía mensajes (diferentes)
a todos ellos.
-
Si un mensaje recorre todo el camino y regresa a su emisor original (el
proceso enlistado en el primer campo), entonces:
-
Existe un ciclo y el sistema está bloqueado.
Una forma de romper el bloqueo es que el proceso que inició
la exploración se comprometa a suicidarse y, si varios procesos
se bloquean al mismo tiempo e inician exploraciones, todos ellos se suicidarán.
Una variante es eliminar solo al proceso del ciclo que tiene el número
más alto.
Inicio:
Fin:
Prevención
Distribuida de Bloqueos
La prevención consiste en el diseño cuidadoso del sistema
para que los bloqueos sean imposibles estructuralmente [25,
Tanenbaum].
Entre las distintas técnicas se incluye:
-
Permitir a los procesos que solo conserven un recurso a la vez.
-
Exigir a los procesos que soliciten todos sus recursos desde un principio.
-
Hacer que todos los procesos liberen todos sus recursos cuando soliciten
uno nuevo.
En un sistema distribuido con tiempo global y transacciones atómicas:
-
Se puede asociar a cada transacción una marca de tiempo
global al momento de su inicio.
-
No pueden haber parejas de transacciones con igual marca de tiempo asociada.
La idea es que cuando un proceso está a punto de bloquearse en espera
de un recurso que está utilizando otro proceso:
-
Se verifica cuál de ellos tiene la marca de tiempo mayor (es más
joven).
-
Se puede permitir la espera solo si el proceso en estado de espera tiene
una marca inferior (más viejo) que el otro.
Al seguir cualquier cadena de procesos en espera:
-
Las marcas aparecen en forma creciente.
-
Los ciclos son imposibles.
Otra posibilidad es permitir la espera de procesos solo si el
proceso que espera tiene una marca mayor (es más joven) que
el otro proceso; las marcas aparecen en la cadena en forma descendente.
Es más sabio dar prioridad a los procesos más viejos:
-
Se ha invertido tiempo de proceso en ellos.
-
Probablemente conservan más recursos.
Inicio:
Fin:
Número de visitas efectuadas desde el 17/12/2001:
Estadísticas diarias desde el
10/07/2002:
Número de visitantes actuales disponible
desde el 14/07/2002:
Autor: lrmdavid@exa.unne.edu.ar
Ó FACENA - http://exa.unne.edu.ar
Servicios WEB: webmaster@exa.unne.edu.ar