Relojes lógicos de Lamport y Ejemplo PDF

Preview

Summary

Introducción:La sincronización de relojes en sistemas distribuidos nos permite garantizar que los procesos se ejecutan cronológicamente y además respetar el orden de los eventos dentro del sistema.Las computadoras poseen un circuito para el registro del tiempo conocido como dispositivo “reloj”. Es u...

Description

Introducción: La sincronización de relojes en sistemas distribuidos nos permite garantizar que los procesos se ejecutan cronológicamente y además respetar el orden de los eventos dentro del sistema. Las computadoras poseen un circuito para el registro del tiempo conocido como dispositivo “reloj”. Es un cronómetro consistente en un cristal de cuarzo de precisión que cuando es sometido a una tensión eléctrica, oscila con frecuencia bien definida. A cada cristal se le asocian dos registros, un contador y un registro mantenedor. Cada oscilación del cristal disminuye en 1 a contador, cuando el contador toma el valor 0, se genera una interrupción y el contador se vuelve a cargar mediante el registro mantenedor. De esta forma, es posible programar un cronómetro de modo que genere una interrupción 60 veces por segundo o con cualquier frecuencia que se desee. Cada interrupción recibe el nombre de marca de reloj. La sincronización de relojes está relacionada con el tiempo real. Pero también cada nodo coincida con un tiempo actual sin importar el tiempo real. Por ejemplo, para ejecutar make, debe ser adecuado que dos nodos acuerden que input.o sea actualizado por una versión de input.c. (dar seguimientos a los otros eventos de cada uno). Para lograr esto existen varios métodos o algoritmos que se programan dentro del sistema operativo, entre los cuales tenemos Leslie Lamport (1978) apunta a que la sincronización no necesita ser absoluta: Si dos procesos no interactúan, no es necesario que sus relojes están sincronizados. Señaló que lo más importante es que todos los procesos coincidan en el orden que ocurren los eventos. El Algoritmo de Lamport sincroniza los relojes lógicos. Definición: Reloj Lógico: contador de software que se incrementa monótonamente, cuyo valor no necesita estar relacionado con ningún reloj físico. Eventos Concurrentes: Eventos no relacionados. Contenido: Algoritmo de Lamport: Fue el primer algoritmo propuesto para lograr la exclusión mutua en redes cuyos nodos se comuniquen solamente mediante mensajes y que no comparten memoria. Fue propuesto por Lamport en 1978. Lamport inventó un mecanismo simple con el cual la relación sucedió antes pueda capturarse numéricamente, denominado reloj

lógico. 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 sincronizar los relojes lógicos, Lamport definió la relación ocurre antes de (ocurrencia anterior). La expresión a → b se lee como “a ocurre antes que b”, y significa que primero ocurre el evento “a” y luego ocurre el evento “b”. La relación puede observarse en dos situaciones: 1. Si a y b son eventos del mismo proceso, y a ocurre antes que b, entonces a → b es verdadera. 2. Si a es el evento donde un proceso envía un mensaje, y b es el evento de recepción del mensaje por otro proceso, entonces a → b también es verdadero. El evento de enviar mensaje siempre ocurre antes que el vento de recibirlo. La ocurrencia anterior es una relación transitiva, por lo que si a → b y b → c, entonces a → c. Si dos eventos, “x” y “y”, ocurren en diferentes procesos que no intercambian mensajes ni a través de terceras partes, entonces x → y no es verdadera y tampoco y → x. Estos eventos son concurrentes, significa que nada se puede decir sobre cuándo ocurren estos eventos, o sobre cuál ocurrió primero.

Reloj lógico de Lamport: Asociar una marca de tiempo (timestamp) a todos los sucesos que se pueden ordenar mediante relaciones “sucede antes que”

Se necesita una manera de medir el tiempo en un evento “a” por lo que se le asigna un valor de tiempo C(a) en el que todos los procesos coincidan. Estos valores también tienen las propiedades que establecimos en el principio y, además: -

De que si a → b, entonces C(a) < C(b)

-

El tiempo del reloj C siempre va hacia delante “incrementando” y nunca hacia atrás “disminuyendo”. Se puede corregir al tiempo agregando un valor positivo, pero no quitando.

Las tareas para llevar a cabo en cada computadora son relativamente sencillas, aunque afectan, en cierta manera, la forma en que se procesan los mensajes: 1. Se tiene un reloj local. 2. Cada vez que se envía un mensaje, se le agrega al mismo una marca de tiempo (timestamp) con el tiempo local del que envía. 3. Cada vez que llega un mensaje, se analiza la marca de tiempo del que envió: a. si la marca de tiempo es menor que el tiempo local, se asume que las computadoras están sincronizadas. b. si la marca de tiempo es mayor o igual que el tiempo local, se cambia el tiempo local con la marca de tiempo del mensaje que se recibió más 1 (asumiendo, por ejemplo, que la transmisión necesita 1 unidad de tiempo) El algoritmo de Lamport propuesto para asignar tiempos a eventos. Se considera 3 procesos. Los procesos se ejecutan en diferentes maquinas, cada una con su propio reloj. Cuando el reloj ha hecho marca 6 veces en el proceso P1, éste ha hecho marca 8 veces en el proceso P2, y 10 veces en el proceso P3. Cada reloj avanza a velocidad constante, pero las velocidades son diferentes debido a las diferencias en los cristales.

En el tiempo 6, el proceso P1 envía el mensaje m1 al proceso P2. El tiempo que demore en llegar el mensaje depende del reloj al que se le crea. El reloj del proceso P2 dice 16 cuando llega el mensaje. Si el mensaje lleva inscrito el tiempo de inicio 6, el proceso P2 concluirá que le tomó 10 marcas realizar el recorrido. Este valor es, desde luego, posible. De acuerdo con este razonamiento, el mensaje m2 desde P2 hasta P3 se lleva 16 marcas, de nuevo un valor plausible. Ahora consideremos el mensaje m3. Éste deja el proceso P3 al 60 y llega a P2 al 56. De manera similar, el mensaje m4 desde P2 hasta P1 sale en el 64 y llega en el 54. Estos valores son claramente imposibles. Es tal situación la que debe evitarse. La solución de Lamport se deriva a partir de la relación “ocurrencia anterior”. Debido a que m3 salió en el 60, debe llegar en el 61 o después. Por tanto, cada mensaje lleva el tiempo de envío de acuerdo con el reloj del remitente. Cuando un mensaje llega y el reloj del destinatario muestra un valor anterior al tiempo en que el mensaje fue enviado, el destinatario rápidamente adelanta su reloj para estar una unidad adelante del tiempo de envío. En la figura 6-9(b) observamos que m3 ahora llega en el 61. De manera similar, m4 llega en el 70. Para implementar los relojes lógicos de Lamport, cada proceso Pi mantiene un contador local Ci. Estos contadores se actualizan de acuerdo con los siguientes pasos: 1. Antes de ejecutar cualquier evento, Pi ejecuta ci ← Ci +1 2. Cuando el proceso Pi envía un mensaje m a Pj, éste ajusta el registro de tiempo de m, ts(m). 3. Una vez que se recibe el mensaje m, el proceso Pj asusta su propio contador local como Cj ← max {Cj, ts(m)}, y ejecuta el primer paso para la entrega el mensaje a la aplicación. Es recomendable un requerimiento adicional que dos eventos nunca deben ocurrir exactamente al mismo tiempo. Para lograr este objetivo podemos incluir el número del proceso en el que ocurre el evento al final del tiempo de menor orden, separado por un punto decimal. Por ejemplo, un evento en el tiempo 40 del proceso Pi será registrado como 40.i. Observe que al asignar el tiempo del evento C(a) ← Ci(a) si a ocurrió en el proceso Pi al tiempo Ci(a), tenemos una implementación distribuida del valor de tiempo global que originalmente buscábamos.

El avance del tiempo en dos computadoras, C1 y C2, y la forma en que la computadora C2 cambia su tiempo local a partir de la llegada de un mensaje con una marca de tiempo mayor que su tiempo local.

Ejemplo: transmisión totalmente ordenada Es una situación donde la base de datos se ha replicado a través de varios sitios. Para mejorar el rendimiento de las consultas, un banco puede colocar copias de una base de datos contable en dos ciudades diferentes, Nueva York y San Francisco. Una consulta siempre se reenvía a la copia más cercana. El precio de una respuesta rápida a una consulta es el de altos costos de actualización, debido a que cada operación de actualización debe realizarse en cada réplica. De hecho, hay un requerimiento más estricto con respecto a las actualizaciones. Por ejemplo, un cliente en San Francisco desea agregar $100 a su cuenta, la cual actualmente contiene $1000. Al mismo tiempo, en Nueva York un empleado del banco inicia una actualización mediante la cual la cuenta del cliente se verá incrementada con el 1% de interés. Ambas actualizaciones deben realizarse en ambas copias de la base de datos. Sin embargo, debido a los retrasos en la comunicación de la red subyacente, las actualizaciones pueden llegar en el orden que muestra la figura.

La operación de actualización del cliente se realiza en San Francisco antes de la actualización del interés. Por lo que, la copia de la cuenta en Nueva York se actualiza primero con el 1% de interés, y después con el depósito de $100. En consecuencia, la base de datos de San Francisco registrará un monto total de $1111, mientras que la base de datos de Nueva York registra $1110. El problema es que las 2 operaciones debieron realizarse en el mismo orden en cada uno. El orden entre el depósito y la actualización del interés no es importante, sino que ambas copias deben ser iguales. Estas situaciones requieren una transmisión totalmente ordenada es decir una operación de transmisión mediante la cual todos los mensajes se entreguen en el mismo orden a cada destinatario. Los relojes lógicos de Lamport pueden utilizarse para implementar transmisiones totalmente ordenadas de modo completamente distribuido. Un grupo de procesos que transmiten mensajes entre sí. Cada mensaje se registra con el tiempo actual de su remitente. Además, los mensajes del remitente se reciben en el orden en que fueron enviados, y que ningún mensaje se pierde. Cuando un proceso recibe un mensaje, éste se coloca en una cola local, y se ordena de acuerdo con su registro de tiempo. El destinatario transmite un acuse de recibo a los otros procesos. Observe que, si seguimos el algoritmo de Lamport para ajustar los relojes locales, el registro de tiempo del mensaje recibido es menor que el registro de tiempo del acuse. El aspecto interesante de este método es que todos los procesos tienen, en algún momento, la misma copia de la cola local (debido a que ningún mensaje es eliminado). Un proceso puede entregar un mensaje de la cola a la aplicación que está ejecutando sólo cuando ese mensaje se encuentra a la cabeza de la cola, y si todos los demás procesos recibieron un acuse. En ese punto, el mensaje es eliminado de la cola y entregado a la aplicación; los acuses asociados pueden simplemente eliminarse. Debido a que cada proceso tiene la misma copia de la cola, todos los mensajes se entregan en el mismo orden en todas partes. En otras palabras, hemos establecido una transmisión totalmente ordenada. Aplicación Sistema de Atención mediante Tickets

En la vida real, hay muchas entidades públicas y privadas que utilizan la atención mediante tickets y es que cuando las personas entran al lugar obtienen un numero de turno, con el cual se le atiende en su orden de llegada respectivamente. El sistema mantiene un número (variable global) que refleja el número de turno del cliente que se está atendiendo en el instante actual. Los clientes deben esperar en una cola hasta que llega su turno. Una vez que se termine con un cliente, la variable global se incrementa en uno y el cliente que tenga un boleto con ese número pasa a ser atendido. Cuando termina una compra, el cliente se desprende de su boleto por lo que ya no sirve. En el modelo algorítmico que se propone, cada cliente es un hilo, identificado con un número único i. Los hilos se deben coordinar para decidir en cada momento qué hilo tiene derecho a ejecutar su código de sección crítica. El servidor entrega un número a cada hilo que desea acceder a este y les atiende de uno en uno por orden de llegada. Una vez que toca le toca su turno, el proceso ingresa a su etapa crítica y después de realizada esta, el servidor le libera y atiende al siguiente proceso.

Ventajas 

Reloj lógico totalmente ordenado: Se crea un orden, uno para el que todos los pares de sucesos distintos están ordenados, teniendo en cuenta los

identificadores de los procesos en los que ocurren los sucesos. Lamport la utilizo, para ordenar la entrada de procesos en una sección. 

Soluciona el problema de escabilidad: ya que solo exige un mensaje entrante y uno saliente para sincronizar cada máquina, pero no tiene un orden total de los eventos que suceden entre diferentes computadoras, excepto los relacionados directamente con envío y recepción de mensajes.

Desventajas 

Infinitos procesos se pueden poner en cola esperando su turno para ejecutarse.



Cada proceso debe realizar revisiones internas para comprobar su turno de ejecución lo cual genera disparidad en el tiempo en el que se espera que se ejecute, el tiempo nunca puede correr hacia atrás.

Conclusiones 

La transmisión totalmente ordenada es un medio importante para servicios replicados en los cuales las réplicas se mantienen consistentes dejándolas ejecutar las mismas operaciones en el mismo orden en todas partes.



Aunque algunos piensen que lo más importante no es saber el tiempo absoluto no es cierto, lo que cuenta es que los eventos relacionados en diferentes procesos ocurran en el orden correcto.



Lamport mostró que introduciendo la idea de los relojes lógicos es posible que una colección de procesos logre la coincidencia global sobre el ordenamiento correcto de eventos. En esencia, a cada evento e, tal como enviar o recibir un mensaje, se le asigna un registro de tiempo lógico y globalmente único, C(e), tal que cuando el evento a ocurre antes que el b, C(a) < C(b).



Los registros de tiempo de Lamport pueden extenderse a registros vectoriales: si C(a) < C(b), incluso sabemos que el evento a causalmente precedió a b.



Lamport definió las dos condiciones temporales lógicas que podemos conocer: el evento de recepción ocurre antes que el evento de envío y los eventos locales ocurren en orden. Estas condiciones permiten establecer relaciones antes-que y trabajar mediante relojes lógicos.

Bibliografía Tanenbaum, A. S. (2008). Sistemas Distribuidos: Principios y Paradigmas. México: Pearson

Educación.

Obtenido

de

http://www.academia.edu/21420808/SISTEMAS_DISTRIBUIDOS_SISTEMAS_DISTRI BUIDOS_Principios_y_Paradigmas Rolando (2009). Algoritmo de Lamport para la Sincronización de Relojes Lógicos en Sistemas Distribuidos. Obtenido de http://blog.rolandopalermo.com/2009/12/algoritmode-lamport-para-la.html Romero, L.F (2009). Sincronización de Relojes en Ambientes Distribuidos. Obtenido de https://postgrado.info.unlp.edu.ar/wp-content/uploads/2014/07/Romero_Fernando.pdf Cardinale, Y. (2018). Sincronización en

sistemas distribuidos. Obtenido de

https://ldc.usb.ve/~yudith/docencia/ci-4821/Temas/Tema3-Sincronizacion.pdf Sincronización

en

Sistemas

Distribuidos.

Obtenido

http://sistemasdistribuidosaisseccion1.blogspot.com/p/sincronizacion-en-sistemasdistribuidos.html

de...