Tiempo y
Estados
Globales
en los
Sistemas
Distribuidos
Grupo Nº 5. Integrantes:
·
Aguilar, Gladys Carolina ·
Avalos, Eduardo Daniel ·
Barrios, Verónica Vanesa ·
Basterra, Ricardo Daniel ·
Bender, Gisela ·
Busso, Mónica Silvana ·
Cassella, Maria Lorena ·
Martínez, Verónica Beatriz ·
Polizza, Maria Laura ·
Sánchez, Mariana Soledad ·
Torrez, Jésica Natalia Licenciatura en
Sistemas de Información Año 2002
1. INTRODUCCIÓN
El tiempo es un tema practico importante, necesitamos computadores en
todo el mundo para marcar en el tiempo las transacciones de comercio
electrónico consistentemente. El tiempo es también una construcción teórica
importante para comprender como se desarrollan las transacciones distribuidas.
Cada computador puede tener su propio reloj físico, también
explicaremos los relojes lógicos, incluyendo relojes vectoriales.
La ausencia de tiempo físico global hace difícil descubrir el estado de
nuestros programas distribuidos cuando se ejecutan.
También examinaremos algoritmos para determinar estados globales de
computaciones distribuidas a pesar de la falta de tiempo global.
Presentaremos conceptos y algoritmos fundamentales relacionados con la
monitorización de cómo se desarrolla la ejecución en los sistemas distribuidos,
y para temporizar los eventos que ocurren en sus ejecuciones.
El tiempo es una característica importante e interesante en los
sistemas distribuidos, por varias razones:
- El tiempo es una cantidad que
a menudo queremos medir de forma precisa, para ello es necesario sincronizar su
reloj, con una fuente de tiempo externa, fidedigna.
- Se han desarrollado algoritmos que dependen de la sincronización
de reloj para varios problemas en distribución. Estos incluyen el mantenimiento
en la consistencia de los datos distribuidos.
La teoría especial de la relatividad demostró las intrigantes
consecuencias que se siguen de la observación que la velocidad de la luz es
constante para todos los observadores. Esto probó que dos sucesos que se
consideran que son simultáneos en un marco de referencia no son necesariamente
simultáneos.
Sin embargo, el orden relativo de dos sucesos puede ser incluso
invertido por dos observadores diferentes. Pero esto no puede suceder si un
suceso pudiera haber sido la causa de que ocurra el otro.
No existe un reloj físico especial en el universo al que podamos
invocar cuando queramos medir intervalos de tiempo.
La noción de tiempo físico también es problemática en un sistema
distribuido, el problema se basa en una limitación similar de nuestra capacidad
para marcar sucesos en diferentes nodos de una manera suficientemente precisa
para conocer el orden en el que ocurrieron cualquier par de sucesos, o si ellos
ocurrieron simultáneamente. No hay un tiempo absoluto, global al que podamos
invocar, a veces necesitamos observar sistemas distribuidos y establecer si
ciertos estados de asuntos ocurrieron al mismo tiempo. Establecer esto requiere
observaciones de los estados de los procesos y de los canales de comunicación
entre los procesos.
Examinaremos métodos en los que los relojes de los computadores pueden ser sincronizados aproximadamente, utilizando paso de mensajes.
2. RELOJES, EVENTOS Y ESTADOS DE PROCESOS
Refinaremos el modelo introductorio de interacción entre procesos en un
sistema distribuido con el fin de ayudarnos a comprender como caracterizar la
evolución del sistema a medida que se ejecuta, y como marcar los eventos de la
ejecución del sistema que interesan a los usuarios. Comenzamos considerando
como ordenar y colocar marcas de tiempo a los eventos que ocurren en un único
proceso.
Consideramos que un sistema distribuido consta de una colección Q de N
procesos pi, i = 1,2.....N. cada proceso se ejecuta en un único procesador, y los procesadores no comparten
memoria. Cada proceso pi en Q tiene un estado Si que, en
general, se transforma a medida que se ejecuta. El estado del proceso incluye
los valores de todas sus variables, puede incluir también los valores de
cualquiera de los objetos en el entorno de sus S.O. local que lo afecte, como
los archivos. Los proceso solo pueden comunicarse entre ellos mediante el envío
de mensajes a través de la red.
A medida que cada proceso pi se ejecuta toma una serie de
acciones, cada una de las cuales es un mensaje Envía o Recibe, o una operación
que transforma el estado pi, que cambia uno o más valores de Si.
La secuencia de sucesos en único proceso pi puede ser colocada en
orden único, total que indicaremos con la relación ® i entre eventos. Es decir, e ® i
e’ si y solo si
el evento e ocurre antes del e’ en pi.
Ahora podemos definir la historia del proceso pi como la
serie de eventos que tienen lugar en él, ordenados de la forma que hemos
descrito con la relación ® i :
historia (pi) = hi = < e0i,
ei1,ei2,….. , >
RELOJES Los computadores pueden
disponer de su propio reloj físico, estos relojes son dispositivos electrónicos
que cuentan las oscilaciones que ocurren en un cristal a una frecuencia definida,
y que normalmente dividen esta cuenta y almacenan el resultado en un registro
contador. Los dispositivos de reloj pueden estar programados para generar
impulsos a intervalos regulares con el fin de que pueda ser implementada la
división de tiempo.
El SO lee el valor del reloj hardware Hi (t) del nodo, lo
escala y añade una compensación para producir un reloj software Ci
(t) = a Hi (t) + b que mide aproximadamente el tiempo real,
físico t para el proceso pi. En general, el reloj no es
suficientemente preciso. La tasa a la que ocurren los sucesos dependen de
factores tales como la longitud del ciclo de instrucción del procesador.
SESGO Y DERIVA DE RELOJ La diferencia
instantánea entre las lecturas de dos relojes cualquiera se llama su SESGO. Los
relojes basados en cristal utilizados en los computadores están sujetos a
derivas de reloj, que significa que ellos cuentan el tiempo a diferentes ritmos
y por lo tanto divergen.
Un ritmo de deriva de reloj es el cambio en la compensación entre el
reloj y un reloj de referencia nominal perfecto por unidad de tiempo medido por
el reloj de referencia. El ritmo de deriva
de relojes ordinarios es de 10-6 segundos/ segundo y de los
relojes de cuarzo de alta precisión es de 10-7 ó 10-8 .
TIEMPO UNIVERSAL COORDINADO (UTC) Los relojes físicos más
precisos utilizan osciladores atómicos, cuyo ritmo de deriva es de
aproximadamente de una parte en 1013. La salida de estos relojes
atómicos se utiliza como estándar para el tiempo real transcurrido, conocido
como “tiempo atómico internacional”. El segundo estándar se ha definido como
9.192.631.770 períodos de transición entre dos niveles hiperfinos del estado
fundamental del Cesio- 133 (Cs133 ). Los segundos, los años y otras
unidades de tiempo que nosotros utilizamos están arraigados en el tiempo
astronómico, fueron definidos originalmente en términos de la rotación de la
tierra sobre su eje y su rotación alrededor del sol. El tiempo astronómico y el
tiempo atómico tienen una tendencia a separarse. El UTC es un estándar
internacional de cronometraje. Esta basado en el tiempo atómico. Las señales
UTC se sincronizan y difunden regularmente desde las estaciones de radio
terrestres y los satélites.
También hay disponibles receptores comerciales. Comparados con UTC
perfecto, las señales recibidas desde las estaciones terrestres tienen una
precisión del orden de 0,1- 10 milisegundos.
Los computadores con receptores adjuntos pueden sincronizar sus relojes
con estas señales de tiempo. Los computadores pueden también recibir el tiempo
con una precisión de unos pocos milisegundos sobre una línea telefónica.
3. SINCRONIZACIÓN DE RELOJES FÍSICOS
Para conocer en que hora del día ocurren los sucesos en los procesos de
nuestro sistema distribuido Q, es necesario sincronizar los relojes de los
procesos Ci con una fuente de tiempo externa autorizada. Esto es la
SINCRONIZACIÓN EXTERNA. Y si los relojes Ci están sincronizados con
otro con un grado de precisión conocido, entonces podemos medir el intervalo
entre dos eventos que ocurren en diferentes computadores llamando a sus relojes
locales, incluso aunque ellos no estén necesariamente sincronizados con una
fuente externa de tiempo. Esto es SINCRONIZACION INTERNA. Definimos estos dos
modos de sincronización mas detalladamente, sobre un intervalo de tiempo real
I:
Sincronización Externa: para una sincronización dada D>0, y para una
fuente S de tiempo UTC, ½ Si (t) – Ci (t)½<D, para i = 1, 2, ...., N y para todos los
tiempos reales t en I. Otra forma de decir esto es que los relojes Ci son precisos con el límite D.
Sincronización Interna: para una sincronización dada D>0, ½Ci(t) – Cj(t)½<D, para i = 1,2,....N y para todos los
tiempos reales t en I.
Los relojes que están sincronizados internamente no están
necesariamente sincronizados externamente, puesto que pueden desplazarse
colectivamente desde una fuente de tiempo externa incluso aunque estén de
acuerdo entre si. Sin embargo, se deduce de las definiciones que si el sistema
Q está sincronizado externamente con un límite D entonces el mismo sistema esta
sincronizado internamente con un límite 2D.
Se han sugerido varias nociones de corrección para relojes. Es común
definir que un reloj hardware H es correcto si su ritmo de deriva cae dentro de
un límite conocido p>0. Esto significa que el error midiendo el intervalo
entre tiempos reales t y t’ (t’>1) está limitado por:
(I – p)(t’ – t) =< H(t’) – H(t)=< (I + p)=< (t’ –
t)
Esta condición prohíbe saltos en el valor de los relojes hardware. A
veces nosotros requerimos que nuestros relojes software obedezcan la condición.
Pero con una condición más débil de monotonicidad puede bastar. Monotonicidad
es la condición que un reloj C solo avanza siempre que:
t’
> t Þ C (t’) > C(t).
Podemos conseguir monotonicidad a pesar del hecho de que un reloj se
encuentre corriendo rápido. Solo necesitamos cambiar el ritmo al que se hacen
las actualizaciones al tiempo dado a las aplicaciones. Esto puede ser
conseguido por software sin cambiar el ritmo al que los ticks del reloj
hardware subyacente; recuerde que Ci(t)
= a Hi(t) + b, donde somos libres de elegir los valores de
b y de a. Un reloj que no se atiene
a ninguna de las condiciones de corrección aplicadas se dice que es defectuoso.
Un fallo de ruptura de reloj se dice que ocurre cuando el reloj deja de pulsar
por completo; cualquier otro fallo de reloj es un fallo arbitrario.
Tenga en cuenta que los relojes no tienen por que ser precisos para ser
correctos, de acuerdo con las definiciones. Puesto que el objetivo puede ser la
sincronización interna mas que la externa, los criterios para corrección están
relacionados únicamente con el funcionamiento adecuado del mecanismo del reloj,
no con su ajuste absoluto.
3.1. SINCRONIZACIÓN EN UN SISTEMA SÍNCRONO
El de sincronización interna entre dos procesos en un sistema
distribuido síncrono es el caso más simple posible. En un sistema síncrono se
conocen los limites para el ritmo de deriva de los relojes, el máximo retardo
de transmisión de mensajes y el tiempo para ejecutar cada paso de un proceso.
Un proceso envía el tiempo t de su reloj local a otro en un mensaje m.
En principio el proceso receptor podría tener su reloj en el tiempo t + Ttrans,
donde Ttrans es el tiempo preciso para transmitir m entre ellos. Los
dos relojes podrían coincidir. Desafortunadamente Ttrans esta sujeto
a variaciones y es desconocido, a pesar de todo, hay siempre un tiempo mínimo
de transmisión min que podría obtenerse si no se ejecutara ningún otro proceso y no existiera mas
trafico en la red; min puede ser medido o estimado de forma conservadora.
En un sistema síncrono, por definición hay también un limite superior
max del tiempo tomado para transmitir cualquier mensaje. Sea la incertidumbre
en el tiempo de transmisión del mensaje u, donde u = (max – min). En general,
para un sistema síncrono, el limite optimo que puede ser conseguido en el sesgo
de reloj cuando sincronizamos N relojes es u(I – I/N).
La mayoría de los sistemas distribuidos encontrados en la practica son
asíncronos: los factores que conducen a retardos de los mensajes no están
limitados en su efecto, y no hay limite superior may en los retardos de
transmisión de mensajes.
EL MÉTODO DE CRISTIAN PARA SINCRONIZAR RELOJES
Cristian (1989) sugirió la utilización de un servidor
de tiempo, conectado a un dispositivo que recibe señales de una fuente UTC,
para sincronizar computadores externamente. Bajo solicitud, el proceso servidor
S proporciona el tiempo de acuerdo con su reloj.
Cristian observó que aunque
no hay límite superior en los retardos de transmisión de mensajes en un sistema
asíncrono, los tiempos de ida y vuelta de los mensajes intercambiados entre
cada par de procesos son a menudo razonablemente cortos. El describe el
algoritmo como probabilístico: el método consigue sincronización sólo si los
tiempos de ida y vuelta entre el cliente y el servidor son suficientemente
cortos comparados con la precisión
requerida.
Un proceso p solicita
el tiempo en un mensaje mr, y recibe el valor del tiempo t en
un mensaje m t .el proceso p registra el tiempo total de ida
y vuelta Tround tomando para enviar la solicitud m
r y escribir la respuesta m t . Se puede este tiempo con
precisión razonable si su ritmo de
deriva de reloj es pequeño.
Una estimación sencilla del
tiempo al que p debe fijar su reloj es t + Tround /2, que
supone que el tiempo transcurrido se desdobla igualmente antes y después de que
S coloque t en m r . Esto es normalmente una suposición razonable de
precisión, a menos que los dos mensajes sean transmitidos sobre redes
diferentes. Si el valor del tiempo mínimo de transmisión min es conocido o puede ser estimado
conservativamente, entonces podemos determinar la precisión de este resultado
como sigue.
El instante más temprano
en el que S podría haber colocado el
tiempo en m t fue min después de que p
enviara m r . El
punto más tarde al que podría haberse hecho esto sería min antes de que
m t llegue a p . El tiempo del reloj de S cuando el mensaje
de respuesta llega estará en el
rango ½t + min, t + T round – min |. La anchura de este rango
es T round – 2min , por lo que la precisión es ± (T round /2
- min).
Se puede tratar con la
variabilidad en alguna medida haciendo varias solicitudes a S y tomando el
valor mínimo de T round para
conseguir una estimación más precisa. Cuanto más grande es la precisión
requerida, más pequeña es la probabilidad de conseguirla.
DISCUSIÓN DEL ALGORITMO DE CRISTIAN: el método de Cristian sufre el problema asociado con todos los servicios implementados por un servidor único, por los que el única servidor de tiempo puede caer y hacer que la sincronización sea imposible temporalmente. Cristian sugirió que el tiempo debería ser proporcionado por un grupo de servidores de tiempo sincronizados, cada uno con un receptor para señales de tiempo UTC.
Hay que tener en cuenta que
un servidor de tiempo erróneo que responda con valores espurios de tiempo, o un
servidor de tiempo impostor que responde con tiempos erróneos deliberadamente, podrían
causar muchos daños en un sistema de computadores. Estos problemas fueron más
allá del alcance del trabajo descrito por Cristian |1989|, que supone que las señales
de tiempo externo se autocomprueban. Cristian y Fetzer |1994| describen una familia de
protocolos probabilísticos para la sincronización de relojes internos.
El problema de tratar con
relojes defectuosos se aborda paralelamente por el algoritmo de Berkeley.
ALGORITMO DE BERKERLEY
Cristian y Zatty |1989| describieron un algoritmo
para sincronización interna que ellos desarrollaron para colecciones de
computadores ejecutando el UNIX Berkeley. En este algoritmo se elige, un
computador coordinador para actuar como maestro. A diferencia del protocolo de
Cristian, este computador consulta periódicamente a los otros computadores
cuyos relojes están para ser sincronizados, llamados esclavos. Los esclavos le
devuelven sus valores de reloj. El maestro estima sus tiempos locales de reloj
observando los tiempos de ida y vuelta. El balance de las probabilidades es que
este promedio contrarresta las tendencias de los relojes individuales a
funcionar rápido o lento. La precisión del protocolo depende de un tiempo de
ida y vuelta máximo nominal entre el maestro y los esclavos. El maestro elimina
cualquier lectura adicional asociado a tiempos más grandes que el máximo.
En lugar de reenviar el
tiempo actual actualizado a los demás computadores, que introduciría una nueva
imprecisión debido al tiempo de transmisión del mensaje, el maestro envía la
cantidad que precisa el esclavo para hacer su ajuste.
El algoritmo elimina las lecturas de relojes defectuosos. El maestro
toma un promedio tolerante a fallos. Esto es, se elige un subconjunto de los relojes que no difieran
entre ellos más de una determinada
cantidad, y el promedio se toma de las lecturas de sólo estos relojes
3.2. EL PROTOCOLO
DEL TIEMPO DE RED
El método de Cristian y el algoritmo de Berkeley están pensados
principalmente para utilizar en intranets. El Protocolo de Tiempo de Red
(Network Time Protocol, NTP) define una arquitectura para un servicio de tiempo
y un protocolo para distribuirla información del tiempo sobre Internet.
Los objetivos principales de
diseño de NTP son los siguientes:
Proporcionar
un servicio que permita a los clientes a lo largo de Internet estar
sincronizados de forma precisa a UTC: NTC emplea técnicas estadísticas para el filtrado
de los datos de tiempo y discrimina entre la calidad de los datos de tiempo de
los diferentes servidores.
Proporcionar un servicio fiable que pueda sobrevivir
a pérdidas largas de conectividad: los servidores pueden reconfigurarse para
continuar proporcionando el servicio si uno de ellos llega a ser inalcanzable.
Permitir a los clientes resincronizar con suficiente frecuencia para compensar las tasas de deriva encontradas en la mayoría de los computadores.
Proporcionar protección contra la interferencia con el servicio de tiempo, ya sea maliciosa o accidental.
El servicio de NTP está proporcionado por una red de servidores
localizados a través de Internet. Los servidores primarios están conectados
directamente a una fuente de tiempo como un radioreloj recibiendo UTC; los
servidores secundarios están sincronizados con servidores primarios. Los
servidores están conectados en una jerarquía lógica llamada subred de
sincronización cuyos niveles se llaman estratos. Los servidores primarios
ocupan el estrato 1: ellos están en la raíz. Los servidores del estrato 2 son
servidores secundarios que están sincronizados directamente con los servidores
primarios; los del estrato 3 están sincronizados con los del estrato 2; y así
sucesivamente. Los servidores del nivel más bajo (hojas) se ejecutan en las
estaciones de trabajo de los usuarios.
Los relojes de los servidores con números alto de estrato tienen
tendencia a ser menos fiables que aquellos con números bajos de estrato, porque
se introducen errores en cada nivel de
sincronización.
La subred de sincronización se puede reconfigurar cuando los servidores
llegan a ser inalcanzables o se producen fallos.
Los servidores NTP se sincronizan entre sí en uno de estos 3 modos:
multidifusión, llamada a procedimiento y modo simétrico. El modo multidifusión
está pensado para su uso en una LAN de alta velocidad. Uno o más servidores
reparten periódicamente el tiempo a los servidores que se ejecutan en otros
computadores conectados en la LAN, que fijan sus relojes suponiendo un pequeño
retardo. Este método puede alcanzar sólo precisiones relativamente bajas, pero
que no obstante son consideradas suficientes para muchos propósitos.
El modo de llamada a procedimiento es similar al funcionamiento del
algoritmo de Cristian, un servidor acepta solicitudes de otros computadores,
que el procesa respondiendo con su marca de tiempo. Este modo es adecuado donde
se requieren precisiones más altas que las que se pueden conseguir con
multidifusión, o donde la multidifución no viene soportada por hardware.
El modo simétrico está pensado para su utilización por servidores que
proporcionan información del tiempo en LANs y por los niveles más altos de la
subred de sincronización. Un par de servidores operando en modo simétrico
intercambian mensajes llevando información del tiempo. Los datos del tiempo son
retenidos como parte de una asociación entre los servidores que se mantiene con
el fin de mejorar la precisión de su sincronización en el tiempo.
En todos los modos, los mensajes se entregan de modo no fiable,
utilizando el protocolo de transporte estándar Internet UDP. En el modo de llamada
a procedimiento y en el simétrico, los procesos intercambian pares de mensajes.
Cada mensaje lleva marcas de tiempo de los sucesos del mensaje reciente: los
tiempos locales cuando el mensaje anterior NTP entre el par fue enviado y
recibido y el tiempo local cuando el mensaje actual fue transmitido. El
receptor del mensaje NTP anota el tiempo local cuando el recibe el mensaje. En
el modo simétrico, a diferencia del
algoritmo de Cristian puede haber un retardo no despreciable entre la llegada
de un mensaje y el envío del siguiente. También, se pueden perder mensajes,
pero las tres marcas de tiempo llevadas por cada son sin embargo válidas.
Por cada par de mensajes enviados entre dos servidores NTP calcula una
compensación o , que es una estimación de la deriva actual entre los dos
relojes, y un retardo di, que es el tiempo total de
transmisión para los dos mensajes. Si el verdadero desplazamiento del reloj B
con relación al de A es o, y si los tiempo de transmisión actuales para m
y m’ son t y t’ relativamente, entonces tenemos:
Ti-2= Ti-3 + t + o y
Ti = Ti-1 + t’ + o Esto conduce a: di = t + t’ =
Ti-2 - Ti-3 + Ti
– Ti-1
tiempo tiempo m’ Servidor
A Ti-3 Ti m Servidor
B Ti-2 Ti-1
También
se verifica que: o = oi
+ ( t’ – t)/2, donde oi =
(Ti-2 – Ti-3 + T i-1 – Ti)/2
Mensajes intercambiados entre un par de iguales NTP.
Los servidores NTP aplican un algoritmo de filtrado de datos a pares
sucesivos < oi,di
< , que estima la deriva o
y calculan la calidad de esta estimación como una cantidad estadística llamada el
filtro de dispersión. Un filtro de dispersión relativamente alto implica
datos relativamente poco fiables. Los ocho pares < oi,di < más recientemente retenidos.
Como con el algoritmo de Cristian, se
elige como estimación de o el valor oj que
corresponde con el mínimo valor di.
El valor del desplazamiento derivado de la comunicación con una única
fuente no se utiliza necesariamente en sí mismo para controlar el reloj local.
En general un servidor NTP se conecta en los intercambios de mensajes con
varios de sus iguales, o colegas. Además del filtrado de datos aplicados a los
intercambios con cada igual, NTP aplica
un algoritmo de selección de colega. Éste examina los valores obtenidos de los
intercambios con cada uno de los distintos colegas, buscando los valores
relativamente menos fiables. La salida de este algoritmo puede provocar que un
servidor cambie el colega que utilizaba inicialmente para la sincronización.
Los colegas con número de estrato más bajo son menos favorecidos que
aquellos en el estrato más alto porque están próximos a las fuentes de tiempo
primarias. Aquellos con la dispersión de sincronización más baja son
favorecidos relativamente. Ésta es la suma de las dispersiones del filtro
medidas entre el servidor y la raíz de la subred sincronización.
NTP emplea un modelo de bucle de bloqueo de fase que modifica la
frecuencia de actualización del reloj de acuerdo con las observaciones de su
tasa de deriva.
4. TIEMPOS LÓGICOS Y RELOJES LÓGICOS
Desde el punto de vista de un único proceso, los sucesos están
ordenados de forma única por los tiempos mostrados en el reloj lógico. Lamport
apunto, que no podemos sincronizar perfectamente los relojes a lo largo de un
sistema distribuido.
Podemos
utilizar un esquema similar a la causalidad física, que se aplica en los
sistemas distribuidos, para ordenar sucesos que ocurren en diferentes procesos.
Ordenación basada en dos puntos sencillos.
Si dos
sucesos han ocurrido en el mismo proceso pi (i = 1, 2,..., n),
entonces ocurrieron en el orden en el que les observa pi , este es
el orden gi .
Cuando se envía
un mensaje entre procesos, el suceso de enviar el mensaje ocurrió antes del de
recepción del mismo.
Esto se
llama suceder antes, o también se conoce como la relación de orden causal o
ordenación causal potencial.
Definimos
la relación suceder antes, indicada por g, como sigue:
SA1: si
existe en proceso pi : egie´, entonces ege´.
SA2: para
cualquier mensaje m, envía(m)grecibe(m).
SA3: si e,
e´ y e´´ son sucesos tal que ege´ y e´ge´´, entonces ege´´.
Si e y e´
son sucesos, y si ege´, entonces podemos encontrar una serie de sucesos e1,
e2,....en ocurriendo en uno o mas sucesos tal que e=e1
y e´=en, y para i = 1, 2, ... n-1 o bien se aplica SA1 o SA2 entre ei
y ei+1.
No todos
los sucesos están relacionados con la relación. Decimos que son concurrentes y
se escribe a//e.
La relación
g captura un flujo de información entre dos eventos.
Otro punto
a señalar es que aun produciéndose la relación sucedió antes entre dos sucesos,
el primero podría o no haber causado realmente el segundo. Un proceso podría
recibir un mensaje y consecuentemente enviar otro mensaje, pero uno que él
emite cada cinco minutos en cualquier caso y no tiene ninguna relación
especifica con el primer mensaje. No se ha supuesto ninguna causalidad real,
pero la relación gdebe ordenar estos sucesos.
Relojes
Lógicos. Lamport invento un
mecanismo simple por el que la relación sucedió antes puede capturarse
numéricamente, denominado reloj lógico. Un reloj lógico es un contador software
que se incrementa monótonamente, cuyos valores no necesitan tener ninguna
relación particular con ningún reloj físico. Cada proceso pi ,
mantiene su propio reloj lógico, Li , que él utiliza para las
llamadas marcas de tiempo de Lamport a los sucesos. Representamos la marca de
tiempo e del suceso pi por Li (e), y representamos por
L(e) la marca de tiempo del suceso e cualquiera que sea el proceso en el que
ocurrió.
Para
capturar la relación sucedió antes g, los
procesos actualizan sus relojes lógicos y trasmiten los valores de sus relojes
lógicos en mensajes como sigue:
RL1: Li se incrementa antes de
emitir cada suceso en el proceso pi:
Li = Li + 1
RL2:
(a) Cuando un proceso pi
envía un mensaje m, acarrea en m el valor de t = Li.
(b)
Al recibir (m,t), cada
proceso pi calcula Lj =max(Lj, t) y entonces
aplica RL1
Antes de realizar la marca de tiempo del suceso recibe(m).
Por
inducción en la longitud de cualquier secuencia de sucesos relacionados dos
sucesos e y e´, que e ge´ entonces L(e)<L(e´).
Hay que señalar
que el inverso no es verdadero. Si L(e)<L(e´), no podemos inferir que ege´.
Cada uno de
los procesos p1, p2, y p3 tienen su reloj
lógico inicializado en cero. Los valores del reloj dados son aquellos
inmediatamente después del suceso para el que son adyacentes. Tenga en cuenta ,
también,
L(b)>L(e)
pero b//e.
Relojes Lógicos Totalmente Ordenados: algunos pares de sucesos
distintos, generados por diferentes procesos, tienen marcas de tiempo Lamport
numéricamente idénticas .Se puede crear orden total sobre los sucesos , uno,
para el que todos los pares de sucesos distintos están ordenados (teniendo en
cuenta identificadores de procesos en los que ocurren los sucesos).
E es
un suceso que ocurre en Pi
Tiempo local
Ti.
E’ es un suceso que ocurre en Pj
Tiempo local
Tj.
Se deben definir las marcas de tiempos globales para dichos sucesos
como: (Ti, i) y (Tj, j);
definiendo (Ti, i) es menor o
igual (Tj,j), si y sólo si , Ti es menor que Tj ò Ti es igual a Tj, siendo i menor que j.
Lamport utilizó este tipo de ordenación para la entrada de procesos en
una sección crítica.
Relojes Vectoriales: (utilizados para mejorar la
deficiencia de los relojes Lamport).Un reloj vectorial para un sistema de N
procesos es un vector de N enteros. Cada proceso mantiene su propio reloj
vectorial Vi , que utiliza para colocar marcas de tiempo en los sucesos
locales. Cada proceso adhiere el vector de marcas de tiempo en los mensajes que
envía al resto.
Reglas para actualizar los relojes:
RV1: inicialmente , Vi(j) = 0 , para i,j = 1,2.....N
RV2: justo antes de que Pi coloque una marca de tiempo en un suceso,
coloca Vi(i) = Vi(i) + 1
RV3: Pi incluye el valor T = Vi
en cada mensaje que envía .
RV4:cuando Pi recibe una marca de tiempo y un mensaje establece Vi(j) =
max (Vi(j), T(j)), para j=1,2,....N.
Se pueden comparar vectores de marcas de tiempo de la siguiente forma:
V = V’ si y solo si V(j) =
V’(j) para j=1,2.....,N.
V es menor o igual que V’ si y solo si V(j) es menor que V’(j) para j =
1, 2,......N.
V es menor que V’ si y solo si V es menor o igual que V’ y Ves distinto de V’.
Los vectores de marcas de tiempo tienen la desventaja, comparados con las marcas de tiempo de Lamport, de precisar una cantidad de almacenamiento y de carga real de mensajes que es proporcional a N, el número de procesos .
5. ESTADOS GLOBALES
Se examina el problema de descubrir si una propiedad particular de un
sistema distribuido es cierta cuando esta se ejecuta .
Compactación automática de memoria: un objeto m se considera
desechable si no hay posteriormente ninguna referencia a él , desde cualquier
parte del sistema distribuido. La memoria ocupada por el objeto puede se
reclamada, una vez que se sabe que este es desechable. Para comprobar que un objeto
es desechable se debe verificar que no hay referencias a él en cualquier parte
del sistema .Pero pueden producirse una referencia a él a través de un mensaje
que transita en el sistema , por ello se debe considera el estado de los
canales así como el de los procesos.
Detección distribuida de bloques indefinidos: un bloque indefinidos
distribuido ocurre cuando cada una de los procesos de una colección espera por
otro para enviarle un mensaje y donde hay un ciclo, relación de espera
por. Por ello el sistema nunca progresará.
Detección de la Terminación distribuida: el problema aquí es
detectar que un algoritmo distribuido
ha terminado. A principio parece sólo necesario comprobar si cada proceso se ha
detenido. Para ver que esto no es así, consideramos un algoritmo distribuido
por dos procesos P1 y P2 cada uno de los cuales puede necesitar valores del
otro . Instantáneamente se puede encontrar que un proceso es activo o pasivo,
un proceso pasivo non está ligado a ninguna actividad por si mismo , pero está
preparado para responder con un valor solicitado por el otro .
Los fenómenos de terminación y bloqueo indefinido son semejantes, pero son problemas diferentes.
En primer lugar un bloqueo indefinido puede afectar sólo a un subconjunto de
procesos en el sistema, mientras que todos los procesos tienen que haber
terminado. En segundo lugar, la pasividad de un proceso no es lo mismo que la
espera de un ciclo de bloqueo indefinido: proceso bloqueado está intentando
realizar otra acción, por lo que espera a otro proceso; un proceso pasivo no
está ligado con ninguna actividad.
Depuración distribuida: los sistemas distribuidos
son complejos de depurar y es preciso tener cuidado al establecer que es lo que
ocurre durante la ejecución. Cada proceso Pi contiene una variable Xi (i =
1,2....N) . Las variables cambian a medida que se ejecuta el programa, pero se
precisa que estén a menos de cierto valor δ de otras.
5.1 ESTADOS GLOBALES Y CORTES CONSISTENTES
Es posible observar la sucesión de estados de un proceso individual,
pero la cuestión de cómo establecer un estado del sistema, el estado de la
colección de procesos, es más difícil de tratar.
El problema esencial es la ausencia de tiempo global. Debiéramos
preguntarnos si podemos elaborar un estado global significativo de los estados
locales registrados en diferentes tiempos reales. La respuesta es un sí
matizado, pero para ver esto debemos presentar antes algunas definiciones.
Consideremos a un sistema general φ de N procesos pi(i
= 1, 2..., N), cuya ejecución deseamos estudiar. Ocurre una serie
de eventos en cada proceso, y podemos caracterizar la ejecución de un proceso
por su historia:
historia(pi) = hi = <e0i
, e1i , e2i ,...>
De forma semejante, podemos considerar cualquier prefijo finito de la
historia del proceso:
hki
= <e0i , e1i ,..., eki
>
Cada evento es una acción interna del proceso (por ejemplo, la
actualización de una de sus variables) o el envío o la recepción de un mensaje
sobre los canales de comunicación que conectan los procesos.
Podemos registrar qué ocurrió con la ejecución de φ. Cada proceso puede
registrar los sucesos que se producen allí, y la sucesión de estados por la que
pasa. Denotamos con ski el estado del proceso pi
inmediatamente antes que ocurra el suceso k, por lo que e0i
es el estado inicial de pi.
Podemos formar la historia global de φ como la unión de las
historias individuales de los procesos:
H = h0 È h1 È …. È hN - 1
Podemos tomar cualquier conjunto de estados de los procesos
individuales para formar un estado global (s1, s2,....,
sN). Pero qué estados son significativos; esto es, ¿cuál de los
estados de los procesos podrían haber ocurrido al mismo tiempo? Un estado
global corresponde a los prefijos iniciales de las historias individuales de
los procesos. Un corte de la ejecución del sistema es un subconjunto de
su historia global que es la unión de los prefijos de las historias de los
procesos:
C = hC11 È hC11 È .... È hCNN
Consideramos los sucesos que ocurren en los procesos p1
y p2 mostrados en la figura 1. La figura representa dos
cortes, uno con frontera <e01 , e02>
y otro con la frontera <e21 , e22>.
El corte de más a la izquierda es inconsistente. Esto es porque p2
incluye la recepción del mensaje m1, pero en p1
no incluye el envío del mensaje. Esto se considera como un efecto sin
una causa. La ejecución actual no estuvo nunca en un estado global
correspondiente a los estados del proceso en la frontera. Por el contrario, el
corte de la derecha es consistente. Incluye tanto el envío como la
recepción del mensaje m1. Incluye el envío pero no la
recepción del mensaje m2. Esto es consistente con la
ejecución actual; después de todo, el mensaje se tomó algún tiempo para llegar.
Un corte C es consistente si, para cada suceso que contiene,
también contiene todos los sucesos que sucedieron antes del suceso.
Tiempo físico
Figura 1. Cortes
Un estado global consistente es uno que corresponde con un corte
consistente. Podemos caracterizar la ejecución de un sistema distribuido como una
serie de transiciones entre los estados globales del sistema:
S0 ® S1 ® S2 ...
Una ejecución es una ordenación de orden total de todos los
sucesos en una historia global que es consistente con cada ordenación de la
historia local. Una linealización o ejecución consistente es una
ordenación de los sucesos en una historia global que es consistente con su
relación sucedió antes ® en H. Una
linealización es también una ejecución.
No todas las ejecuciones pasan a través de estados consistentes globales,
pero todas las linealizaciones pasan sólo a través de estados globales
consistentes.
5.2
PREDICADOS DE ESTADO GLOBAL, ESTABILIDAD, SEGURIDAD Y VITALIDAD
Detectar una condición tal, como un bloqueo indefinido o una
terminación equivale a evaluar un predicado de estado global. Un predicado de
estado global es una función que pasa del conjunto de estados globales de los
procesos en el sistema a verdadero, falso.
Un sistema que esta siendo bloqueado indefinidamente o un sistema que
esta terminando es que todos son estables: una vez que el sistema entra en un
estado, permanece en todos los estados futuros alcanzables desde ese estado.
Por contraste, cuando monitorizamos o depuramos una aplicación a menudo estamos
interesados en predicados no estables.
Dos nociones relevantes para los predicados de estado global: seguridad
y vitalidad. Supongamos que hay una propiedad indeseable a que es un predicado del estado global del
sistema: por ejemplo, a podría ser la propiedad de
estar bloqueado indefinidamente. Sea S0 el estado original del
sistema. Seguridad con respecto a a es la aserción que a evalúa a falso para todos los estados S
alcanzables desde S0. A la inversa, sea b una propiedad deseable del estado global del
sistema: por ejemplo la propiedad de alcanzar la terminación. Vitalidad con
respecto a b es la propiedad que, para
cualquier linealización L comenzando en el estado S0, b se evaluara a verdadero para algún estado S1
alcanzable desde S0.
5.3 EL ALGORITMO DE INSTANTÁNEA DE CHANDY Y LAMPORT
El objetivo del algoritmo es registrar un conjunto de estados de
procesos y canales ( una instantánea) para un conjunto de procesos Pi
( i = 1,2,...n) tal que, incluso a través de una combinación de estados
registrados que nunca podrían haber ocurrido al mismo tiempo, el estado global
registrado sea consistente.
El algoritmo supone que:
·
No
falla ni los canales ni los procesos; la comunicación es fiable por lo que cada
mensaje enviado es recibido intacto, exactamente una vez.
·
Los
canales son unidireccionales y proporcionan la entrega de los mensajes con
ordenación FIFO.
·
El
grafo de los procesos y canales esta fuertemente conectado ( hay un recorrido
entre dos procesos cualquiera.)
·
Cualquier
proceso puede iniciar una instantánea global
en cualquier instante.
·
Los
procesos pueden continuar su ejecución y enviar y recibir mensajes normales
mientras tiene lugar la instantánea.
La idea esencial del algoritmo es como sigue. Cada proceso registra su
estado y para cada canal entrante también un conjunto de mensajes enviados a
él. El proceso registra, para cada canal, todos los mensajes que entraron
después de que él registrara el estado y antes de que el emisor registrara su
propio estado.
El algoritmo puede mediante el uso de mensajes marcador especiales, que
son distintos de cualquiera de los otros mensajes que envían los procesos, y
que los procesos podrán enviar y recibir mientras continua su ejecución normal.
El marcador tiene un papel dual: como un aviso para que el receptor guarde su
propio estado, sino lo ha hecho aun; y como un medio para determinar que
mensajes incluir en el estado del canal.
El algoritmo se define mediante dos reglas, la regla de recepción del
marcador y la regla del envío del marcador. La regla del envío del marcador
obliga a los procesos a enviar un marcador después de haber registrado su
estado, pero antes de que envíen cualquier otro mensaje.
La regla de recepción del marcador obliga a un proceso que no ha
registrado su estado a hacerlo.
Cualquier proceso puede iniciar el algoritmo en cualquier instante.
Actúa como si hubiera recibido un marcador (sobre un canal no existente) y
sigue la regla de recepción del marcador. Por lo tanto registra su estado y
comienza a registrar los mensajes que llegan sobre todos los canales entrantes.
Terminación del algoritmo de
instantánea. Un
proceso que ha recibido un mensaje marcador registra su estado en un tiempo
finito y envía mensajes marcador sobre cada canal saliente en un tiempo finito.
Si hay un recorrido de canales de comunicación y procesos desde un proceso
hasta otro distinto del primer proceso, entonces registrara su estado un tiempo
finito después que el primero haya registrado el suyo. Estamos suponiendo que
el grafo de procesos y canales esta conectado fuertemente, se deduce que todos
los procesos habrán registrado sus estados y los de los canales entrantes un
tiempo finito después que algunos procesos hayan registrado inicialmente su
estado.
Características del estado observado. El algoritmo de instantánea selecciona un corte de la historia de la ejecución. El corte, y por tanto el estado registrado por este algoritmo, es consistente.
Podríamos establecer una relación de
alcanzabilidad entre el estado global observado y los estados inicial y final
cuando se ejecuta el algoritmo. Sea Sis, una linealización del sistema tal y
como se ejecuta. Sea S-inicio el estado global inmediatamente antes que el
primer proceso registrara su estado; sea S-final el estado global cuando
termina el algoritmo de instantánea, después de la ultima acción de
registro de estado; y sea S-insi el estado global registrado.
Categorizamos inicialmente todos los sucesos
como sucesos pre-instantánea o post-instantánea. Un suceso
pre-instantánea en el proceso es uno que sucedió antecede que registrara su
estado; todos los demás sucesos son post-instantánea. Un suceso
post-instantánea puede suceder antes que uno pre-instantánea, si los sucesos
ocurren en diferentes procesos, ningún suceso post-instantánea puede suceder
antes que otro pre-instantánea en el mismo proceso.
Para cada proceso el conjunto de sucesos que
ocurrieron en él es exactamente el conjunto de sucesos que experimento antes de
que registrara su estado.
Por tanto el estado de cada proceso en ese punto, y el estado de los canales de comunicación, es el estado global S-insi registrado por el algoritmo. No hemos desordenado ninguno de los estados S-inicio o S-final con los que la linealización comienza y termina. Hemos establecido una relación de alcanzabilidad.
Estabilidad y alcanzabilidad
del estado observado. La propiedad de alcanzabilidad del algoritmo de instantánea se utiliza
para detectar predicados estables. En general, cualquier predicado no estable
que nosotros establezcamos como Verdadero puede o no haber sido Verdadero
en la ejecución actual cuyo estado global hemos registrado. Si un predicado
estable es Verdadero, entonces podemos concluir que el predicado es Verdadero
en el estado S-final, por definición un predicado estable que es Verdadero
en un estado lo es también en cualquier otro estado alcanzable. Si el predicado
se evalúa a Falso, entonces debe ser también Falso para S-inicio.
6.
DEPURACIÓN DISTRIBUÍDA
Se presenta ahora, el problema del registro de un estado global de un
sistema de manera de poder hacer afirmaciones útiles, sobre si un estado
transitorio, como opuesto a uno estable, ocurrió en la actual ejecución. Esto
es, lo que precisamos cuando depuramos un sistema distribuido. Un ejemplo es un
sistema distribuido controlando un sistema de tuberías en una fábrica donde
estamos interesados en si todas las válvulas (controladas por diferentes
procesos) fueron abiertas al mismo tiempo. En este ejemplo no se pueden
observar los valores de las variables o los estados de las válvulas simultáneamente.
El reto es monitorizar la ejecución del sistema a lo largo del tiempo, para
capturar información de la traza mas que una simple instantánea, por lo
que podemos establecer a posteriori si
la condición de seguridad requerida fue violada o pudo haberlo sido.
El algoritmo de instantánea de Chandy y Lamport recoge el estado
de una forma distribuida, el algoritmo
que se describirá ( debido a Marzullo y Neiger [ 1991]) es centralizado. Los
procesos observados envían sus estados a un
proceso llamado monitor, que ensambla estados globalmente consistentes
de los que recibe. Consideramos que el monito se encuentra fuera del sistema
observando su ejecución.
El objetivo es determinar casos en los que dado un predicado de estado
global f era sin duda alguna verdadero en algún punto de la ejecución y
los casos en los que posiblemente era verdadero. La noción posiblemente surge como un proceso
natural porque podemos extraer un estado global consistente S de un sistema en ejecución y encontrar que f(S) es verdadero. Una observación única de un
estado global consistente no permite concluir si un predicado no estable será
evaluado siempre a verdadero en
la ejecución actual.
La noción sin duda alguna se aplica a la ejecución actual y no a una ejecución que hayamos extrapolado
de ella. Puede parecer paradójico considerar que sucedió en la ejecución
actual. Sin embargo, es posible evaluar si f fue sin duda verdadero considerando todas la
linealizaciones de los sucesos observados. Se definen ahora las siguientes
nociones para un predicado f en función de la linealizaciones de H, la historia de la
ejecución del sistema.
Posiblemente f : esta afirmación significa
que hay un estado consistente S
a través del cual pasa una linealización H tal que f(S) es verdadero.
Sin duda alguna f : esta afirmación significa
que para todas las linealizaciones L de H, hay un estado
consistente S a través del cual pasa L tal que f(S) es verdadero.
Recolectado en estado. Los procesos observados pi
( i = 1, 2,..., N) envían su estado
inicial al proceso monitor inicialmente, y después de tiempo en tiempo, en mensajes
de estado. El proceso monitor registra los mensajes de estado de los
procesos pi en una cola separada
Qi , para cada i = 1,2,....N.
La actividad de preparar y enviar mensajes de estado puede retrazar la
ejecución normal de los procesos, pero aparte de eso no interfiere con ellos.
No hay necesidad de enviar el estado inicialmente o cuando cambia. Hay dos optimizaciones para reducir el tráfico
de mensajes de estado hacia el monitor.
Primero, el predicado de estado global puede depender solo de ciertas partes de
los estados de procesos. Segundo, solo necesitan enviar el estado en los
instantes en que el predicado f puede llegar a ser verdadero o dejar de serlo. No tiene sentido
enviar los cambios de estado que no afectan al valor del predicado.
6.1 OBSERVACIÓN DE ESTADOS GLOBALES CONSISTENTES
El monitor
debe recoger los estados globales consistentes a los que evaluar f. Estudiando procesos los sucesos en las líneas de tiempo estarán
ajustadas a los valores de las variables. El requisito es que /xi –
xj/ <= 50. Un proceso hace ajustes en sus variables, pero grandes
ajustes producen que se envíen a los otros procesos un mensaje conteniendo el
nuevo valor. Cuando cualquiera de los procesos recibe un mensaje de ajuste de
otro, coloca su variable homologa al valor contenido en el mensaje.
Cuando uno
de los procesos ajusta el valor de sus variables, envía el valor en un mensaje
de estado al proceso monitor. El ultimo mantiene los mensajes de estado en las
colas por procesos para el análisis.
Con el fin
que el monitor puede distinguir estados globales consistentes de estados
globales inconsistentes, los procesos engloban sus valores de reloj vectorial.
Con sus mensajes de estado. Cada cola Qi se mantiene ordenada por el
orden de envío, que puede ser establecido inmediatamente examinando el i-ésimo
componente del vector de marcas de tiempo.
El proceso
monitor no puede deducir nada sobre la ordenación de los procesos enviados por
los procesos a partir de su orden de llegada, a causa de las latencias de los
mensajes.
En un lugar
debe examinar los vectores de marcas de tiempo de los mensajes de estado.
Sea S= (S1,
S2,…., Sn) un estado global obtenido de los mensajes de
estado que ha recibido el proceso monitor. Sea V(Si) el vector de
marcas de tiempo del estado Si recibido desde Pi. Se
puede mostrar que S es un estado global consistente sí y solo sí:
V(Si) [i] >= V(Sj)[i] Para i, j = 1, 2, 3,.... n
Esto viene
a decir que el numero de sucesos de Pi conocidos en Pj
cuando este envía Sj no es mas que el numero de sucesos que han
ocurrido en Pi cuando envío Si . O sea el estado global
también abarca el estado del que depende.
Entonces el
proceso monitor puede establecer si un estado global dado es consistente,
usando un vector de marcas de tiempo mantenido por los procesos observados e
incluido en los mensajes de estado que ellos le enviaron.
La red de
estados globales consistentes captura la relación de alcanzabilidad entre estados
globales consistentes. Los nodos representan estados globales, y los arcos
representan posibles transiciones entre los estados.
La red esta
ordenada en niveles, Sij esta en el nivel (i + j). Una linealización
atraviesa la red desde cualquier estado global alcanzable desde él en el
siguiente nivel, es decir, en cada paso algún proceso experimenta un suceso.
La red nos
muestra todas las linealizaciones correspondientes a una historia, entonces
para evaluar posiblemente f , el proceso monitor comienza en el estadio inicial y salta desde ese
punto, evaluando f en cada etapa. Este se detendrá cuando f se evalúa a verdadero. Para
evaluar sin duda alguna, el proceso monitor deberá intentar encontrar el
conjunto de estados a través de los cuales deben pasar todas las
linealizaciones, y en cual de ellos f se avalúa verdadero.
6.2. EVALUANDO POSIBLEMENTE
Para evaluar posiblemente Ø, el proceso monitor debe atravesar la red de
estados alcanzables, comenzando desde el estado inicial (S01 ,S02 ,..., S0n ). El algoritmo se muestra en la figura 2.
Dicho algoritmo supone que la ejecución es infinita. Puede ser adaptado fácilmente para una ejecución finita.
El proceso monitor puede descubrir el conjunto de estados consistentes
en el nivel L + 1 alcanzable desde un estado consistente en el nivel L
por el método siguiente.Sea S = ( S1, S2, ..., Sn )
un estado consistente. Entonces un estado consistente en el siguiente nivel
alcanzable desde S es de la forma
S’ = ( S1, S2, ..., S’i, ..., Sn ), que difiere
de S sólo porque contiene el siguiente estado de algún proceso Pi. El monitor puede encontrar todos
esos estados atravesando las colas de estado Qi ( i = 1, 2, ..., n), el estado S’
es alcanzable desde S si y solo si:
Para j = 1, 2, ..., n, j <> i: V ( Sj ) [ j ] >= V ( S’i
) [ j ]
Esta condición se deduce de la anterior condición
EGC y del hecho que S ya estaba
en un estado consistente. Un estado dado, en general, puede ser alcanzado desde varios estados del nivel
anterior, por lo que el proceso monitor debería tener cuidado de evaluar la
consistencia de cada estado solo una vez.
-Figura 2 Algoritmos para evaluar posiblemente Ø y
sin duda alguna Ø.
1-Evaluando posiblemente Ø para la historia global H de N procesos
L :=
0
Estados := 0 { (S01 ,S02 ,..., S0n )} ;
Mientras (Ø ( S ) Falso para
todos los S E Estados)
L := L +1;
Alcanzable: {
S’; S’ alcanzable en H desde algún S E Estados ^ nivel (S) = L };
Estados :=
Alcanzable
Fin mientras
Salida “posiblemente Ø”
2-Evaluando sin duda alguna Ø para la historia global H de N procesos
L := 0
Si (Ø (S01 ,S02 ,..., S0n )) entonces Estados := {} sino Estados := {(S01 ,S02 ,..., S0n )};
Mientras (Estados <> {} )
L := L + 1;
Alcanzable :=
{S’; S’ alcanzable en H desde algún S E Estados ^ nivel (S) = L };
Estados := {S E Alcanzable: Ø (S) = Falso}
Fin mientras
Salida “sin
duda alguna Ø”
6.3 EVALUANDO SIN DUDA
ALGUNA
Para evaluar sin duda alguna Ø, el proceso monitor atraviesa de nuevo la red de estados alcanzables en un tiempo,
comenzando desde el estado inicial (S01 ,S02 ,...S0n ). El algoritmo (presentado en la figura 2)
supone de nuevo que la ejecución es infinita pero puede ser adaptado para que
sea finita. Mantiene el conjunto Estados, que contiene aquellos estados
en el nivel actual que pueden ser alcanzados en una linealización desde el
estado inicial atravesando solo estados en los que Ø se evalúa a Falso.
Por el hecho que exista una linealización, no podemos afirmar sin duda alguna
Ø; la
ejecución podría haber tomado esta linealización, y Ø sería Falso en cada
etapa a lo largo de ella. Si alcanzamos un nivel en el que no existe dicha
linealización, podemos concluir que sin duda alguna Ø.
En la figura 3, en el nivel 3 el conjunto Estados consta de un
solo estado, que es alcanzable por una linealización en la que todos los
estados están a Falso (marcado en líneas oscuras). El único estado
considerado en el nivel 4 es uno marcado con <F>. (El estado a su derecha
no se considera, puesto que solo puede ser alcanzado vía un estado para que Ø se evalúa a Verdadero.)
Si Ø se
evalúa a Verdadero en el estado del nivel 5, entonces podemos concluir
que sin duda alguna Ø. En otro caso el algoritmo debe continuar mas allá de este nivel.
Coste. Los algoritmos que
acabamos de describir explotan combinatoriamente. Supongamos que K es el
máximo número de sucesos de un único proceso. Entonces los algoritmos que hemos
descrito implican
O ( Kn ) comparaciones (el proceso monitor compara
los estados de cada uno de los n procesos observados con todos los demás).
Hay también un coste de espacio para estos algoritmos O ( Kn
). Sin embargo, observamos que el monitor puede borrar un mensaje conteniendo
el estado Si de la cola Qi
cuando ningún otro ítem de estado
llegando desde otro proceso pudiera estar posiblemente implicado en un estado
global consistente que contenga Si , Esto es cuando:
V( Sj último ) [ i ]
> V( Si ) [ i ] para j = 1, 2, ..., n, j <> i
Donde Sj último
es el último estado que el proceso
monitor ha recibido desde el proceso Pj.
Figura 3 Evaluando sin duda
alguna Ø.
Nivel 0
F
1 F
F
= (Ø (S) = Falso); T = (Ø (S) = Verdadero)
2 F
3
F T
4 F --
5 ?
6.4 EVALUANDO
DEFINITIVAMENTE Ø Y SIN DUDA ALGUNA Ø
EN SISTEMAS
SINCRONOS
En un sistema síncrono, suponemos que los procesos mantienen sus
relojes físicos sincronizados internamente con un límite conocido, y que los
procesos observados proporcionan marcas de tiempo físicas así como un vector de
marcas de tiempo en sus mensajes de estado. Entonces el proceso monitor
necesita considerar solo aquellos estados globales consistentes cuyos estados
locales podrían posiblemente haber existido simultáneamente, dada la
sincronización aproximada de los relojes. Con suficientemente buena
sincronización de los relojes, estos serian un número mucho menor que todos los
estados consistentes globalmente.
Damos ahora un algoritmo para explotar los relojes sincronizados de esta
forma. Suponemos que cada proceso observado Pi ( i = 1, 2, ..., n )
y el proceso monitor, que podríamos llamar Pi mantiene un reloj
físico
Ci (i = 1, 2,
..., n ). Estos
están sincronizados con un límite conocido D > 0; es decir, en el mismo
tiempo real:
| Ci( t ) – Cj( t ) | < D para i, j = 1, 2, …, n
Los procesos observados envían al proceso monitor tanto su tiempo
vectorial como el tiempo físico con sus mensajes de estado. El proceso monitor
aplica ahora una condición que no solo comprueba la consistencia de un estado
global S = (S1, S2, ..., Sn), sino también comprueba cualquier par de estados
que pudieran haber ocurrido en algún instante real, dado los valores del reloj
físico. En otras palabras, para i, j = 1, 2, ..., n;
V(Si) [ i ] >= V(Sj) [ i
] y
Si y Sj podrían haber ocurrido en el mismo tiempo real.
La primera cláusula es la condición que hemos utilizado anteriormente.
Para la segunda cláusula, hay que señalar que Pi esta en el estado Si desde el
momento en que notifica su estado al proceso monitor. Ci ( Si ),
Hasta algún tiempo local posterior Lj ( Sj ), por ejemplo, cuando
ocurre la transición al siguiente estado en Pi. Para que Si y Sj se hayan obtenido en el mismo instante real tenemos,
por tanto, que permitir para el límite en la sincronización del reloj.
Ci( Si ) – D <= Cj( Sj ) <= Li( Si ) + D, o viceversa (cambiando
i por j).
El proceso debe calcular un valor para Li ( Si ), que se mide contra el
reloj de Pi. Si el proceso monitor ha recibido un mensaje de estado para el siguiente
estado de Pi, entonces Li( Si ) es Ci( Si’ ). En caso contrario el proceso
monitor estima Li( Si ) como Co max + D, donde Co es el valor actual del reloj
del monitor, y max el tiempo máximo de transmisión para un mensaje de estado.
CONCLUSIÓN
En esta monografía comenzamos describiendo la importancia del
mantenimiento de la precisión del tiempo en los sistemas distribuidos. Después
hemos descrito algoritmos para sincronización de relojes a pesar de sus derivas
entre ellos y la variabilidad de los retardos en los mensajes entre
computadores. El grado de preescisión que es obtenible en la sincronización
satisface, en la practica muchos requisitos pero no es suficiente, sin embargo,
para determinar la ordenación de un par arbitrario de sucesos que ocurran en
diferentes computadores.
Los relojes vectoriales son una mejora de los relojes de Lamport,
porque es posible determinar, examinando sus vectores de marcas de tiempo, si
dos sucesos están ordenados en la relación “sucedió antes” o son concurrentes.
Presentamos los conceptos de eventos (sucesos), historias locales y
globales, recortes, estados globales y locales, ejecuciones, estados
consistentes, linealizaciones y alcanzabilidad. Un estado o ejecución
consistente es uno que esta de acuerdo con la relación “sucedió antes”.
Consideramos el problema de registrar un estado global consistente
observando la ejecución de un sistema. El objetivo ha sido evaluar un predicado
sobre este estado. Hemos descrito el algoritmo de instantánea de Chandy y
Lamport, que captura un estado consistente global y permite hacer aserciones
sobre si un predicado estable se mantiene en la ejecución actual. Dado el
algoritmo de Murzullo y Neiger para derivar afirmaciones sobre si se mantiene
un predicado o podría haberse mantenido en la ejecución actual.
