Sistemas Distribuidos

Sincronización en sistemas distribuidos

Sincronización de relojes
En general los algoritmos distribuidos tienen las siguientes propiedades:
1. La información relevante se distribuye entre varias máquinas
2. Los procesos toman las decisiones sólo con base en la información
3. Debe evitarse un punto de fallo en el sistema
4. No existe un reloj común o alguna otra fuente precisadel tiempo global

Algoritmo de Lamport
Lamport señaló que la sincronización de relojes no tiene que ser absoluta. Si dos procesos no interactúan no es necesario que sus relojes estén sincronizados. Además lo que importa no es que los procesos concuerden de manera exacta en la hora, sino que coincidan en el orden en el cual ocurren los eventos. Así para cierta clase de algoritmos lo que importaes la consistencia interna de los relojes, no su particular cercanía al tiempo. Para estos algoritmos los relojes se denominan relojes lógicos.
Lamport definió una relación llamada “a ocurre antes de b“ (a(b). Esta relación se puede observar de manera directa en dos situaciones:
1. Si a y b son eventos en el mismo proceso y a ocurre antes de b, entonces a(b es verdadero.
2. Si a es elevento de envío de un mensaje por un proceso y b es el evento de la recepción del mensaje por otro proceso, entonces a(b también es verdadero.
El algoritmo de Lamport consiste en lo siguiente, cuando un proceso a envía un mensaje el mensaje lleva consigo su marca de tiempo C(a), si el proceso receptor b tiene un tiempo C(b) mayor que el del proceso a, entonces el mensaje es aceptado y no pasa nada.Pero si la marca de tiempo de a, es decir C(a) es mayor que C(b), entonces el proceso b ajusta su reloj, toma la marca de tiempo C(a) y le suma uno (Ver siguiente figura). Lamport plantea que dos eventos no ocurren exactamente al mismo tiempo.
Con este algoritmo se puede obtener un orden total para todos los eventos del sistema.




















Algoritmo de CristianCuando un sistema hace uso de un servidor de tiempo (quizá porque tiene instalado un receptor WWV para obtener un tiempo real), se puede usar el algoritmo de Cristian. Este algoritmo consiste en que todos los clientes se sincronicen con el servidor de tiempo en forma periódica. Según el algoritmo de Cristian el tiempo no debe correr hacia, por lo tanto el cambio debe realizarse de forma gradual, estose consigue haciendo lo siguiente, si se generan 100 interrupciones por segundo, lo normal es que se tengan que añadir 10 milisegundos en cada interrupción. Entonces si se quiere atrasar un reloj, se podrían añadir 9 o menos milisegundos en cada interrupción hasta que el reloj esté sincronizado. Si lo que se quiere es adelantar el reloj entonces en cada interrupción hay que añadir 11 milisegundoshasta lograrlo.
Otro problema en este algoritmo es que el tiempo que tarda el servidor en responder al emiso es distinto de cero. Pero este retraso depende de factores como, por ejemplo la carga de ese momento en el sistema. Una forma de medirlo es tomando el tiempo inicial TI y el tiempo final TF obtener la diferencia y dividirlo entre 2, (TF –TI)/2.

Algoritmo de Berkeley
En el algoritmo deCristian el servidor de tiempo es pasivo. En el caso del algoritmo de Berkeley está activo y realiza un muestreo de forma periódica a todas las máquinas para preguntarles su tiempo. En base al tiempo de todas las máquinas incluyédose él mismo, obtiene el promedio y les indica a cada máquina cuanto tiempo deben adelantarse o retrasarse para lograr la sincronización. Al igual que en Cristian, paraadelantar o retrasar el reloj hay que hacerlo paulatinamente de acuerdo a las interrupciones que genera el cronómetro.
Procedimiento.
1. El servidor de tiempo le envia a cada máquina su tiempo
2. Las máquinas cliente le indican el número de segundos que están adelantadas o retrasadas con respecto al tiempo del servidor, si es un número positivo entonces están adelantadas y si es...