Actividad 6 - Implementación del Algoritmo Distribuido

La sincronización en sistemas distribuidos consiste en garantizar que los procesos se ejecuten en forma cronológica y a la misma vez respetar el orden de los eventos dentro del sistema.

Esta sincronización, en sistemas distribuidos, se hace más compleja que en los sistemas centralizados puesto que la información y el procesamiento se mantienen en diferentes nodos. 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.

Luego de esta pequeña introducción a la sincronización vamos a hablar acerca del Algoritmo de Lamport. Y es que en este post hablaremos de la propuesta que hizo el científico en computación Dr Leslie Lamport.

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.

Y es aquí dónde aparece el concepto de reloj lógico. Un reloj lógico de Lamport es un contador software que se incrementa monótonamente, cuyos valores no necesitan tener ninguna relación particular con ningún reloj físico.

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:

o Si “a –> b” entonces “C(a) < C(b)”.

o 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.

Para la implementación  se ejemplifica con el paso de mensajes entre 3 "procesos, con un tiempo especifico cada uno, dando como resultado el envio de un mensaje con su tiempo de envio.

En la interfaz, observamos el "time", que es tiempo que transcurre desde que inicia el proceso, el "message" que es el mensaje que queremos enviar, "to:" en esta area seleccionamos a que proceso queremos enviar el mensaje, "received" que es la variable que escucha el mensaje enviado por cualquier otro proceso, aqui es donde recibimos el mensaje y el tiempo en el cual fue enviado el mensaje.

Otras referencias:

http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO9.htm

http://rubmarin.galeon.com/algoritmolamport.htm

http://blog.rolandopalermo.com/2009/12/algoritmo-de-lamport-para-la.html

http://tele.informatik.uni-freiburg.de/lehre/ws01/dsys/Lectures/Lecture10.pdf

Actividad 4 - Análisis y Conclusion de las Aplicaciones

Actividad 5 - Algoritmo Distribuido

Una subclase de los algoritmos paralelos, los algoritmos distribuidos son algoritmos diseñados para trabajar en entornos tipo clusters y de computación distribuida, donde se usan otras técnicas, fuera del alcance de los algoritmos paralelos clásicos.

Estado Global

Estado global: estado local de cada proceso + estado de cada canal.

Estado de cada proceso: sólo las variables que nos interesen.

Estado de cada canal: mensajes enviados y todavía no entregados.

• Usos del estado global: 
• Detección de terminación.
• Depuración distribuida.

Algoritmo de Chandy-Lamport

El algoritmo de Chandy y Lamport, bajo determinadas suposiciones, permite determinar el estado global de un sistema distribuido

Conceptos previos

Una instantánea distribuida refleja el estado que pudo haberse alcanzado en el sistema.
Las instantáneas reflejan sólo estados consistentes.
Si el estado de P, dice que P ha recibido un mensaje de Q, en la instantánea, Q envió antes un mensaje a P.
La noción de estado global se refleja por el concepto de corte.

• Cualquier proceso inicia el algoritmo.
• Sea P el proceso iniciador.
• P guarda su estado local, luego envía un mensaje de marca a todos los demás procesos.
• Cuando un proceso recibe el mensaje de marca:
• Si no ha guardado su estado local: guarda su estado local y envía marca a todos los demás procesos. A partir de este momento almacenará lo que llegue por los canales entrantes.
• Si ha guardado su estado local, guarda los mensajes recibidos por el canal (desde que el proceso guardó su estado local, hasta que recibió marca por este canal).
• Un proceso termina, cuando ha recibido marca por todos los canales.
• Cuando termina, envía su estado y el de sus canales al iniciador.

Actividad 3 - Algoritmo Paralelo. Aplicación en 3 Lenguajes de Programación

Para nuestra 3ª actividad, implementaremos el algoritmo paralelo descrito en la Actividad 2, en 3 lenguajes de programación diferentes.

Cabe mencionar que la paralelización como tal sera implementada por medio de hilos, los cuales se ejecutan simultaneamente efectuando las operaciones de "acomodar" los números de nuestro arreglo.

Diagrama de Flujo

Ejemplo en Java 

 Para el ejemplo en java, utilizamos una sola clase, la cual implementa los metodos de la clase Runnable y nos permite instanciarla como un hilo independiente, cada vez que se ejecuta el metodo run()

Para el acomodo de los objetos utilizamos el metodo de ordenamiento QuickSort

Ejemplo en Ruby 

 Implementacion de hilos en Ruby

Metodo de ordenamiento QuickSort en Ruby

Ejemplo en Python 

 Implementacion de hilos en Python

Metodo de ordenamiento QuickSort en Python