• Author / Uploaded
• Hector Martinez

Citation preview

PATRÓN MASTER SLAVE José Valentín Morales Robles Eduardo de la Garza Cerrato Noé Martínez Olivas

TEMAS Introducción  Master-Slave  Implementación  Características  Ejemplo  Contexto  Problema  Solución  Estructura  Dinámica 

Implementación  Variantes  Usos conocidos  Consecuencias 

MASTER SLAVE El patrón Master-Slave soporta tolerancia a fallos, computación paralela y precisión computacional. Un componente maestro distribuye el trabajo a componentes esclavos iguales y calcula el resultado final a partir de los resultados de los esclavos. 





El patrón aplica el principio de divide y vencerás. El trabajo se divide en subtareas que son procesadas de forma independiente. El resultado del ejercicio total se calcula usando los resultados que cada operación de procesamiento proporciona. Este patrón es muy usado en áreas de computación paralela

MASTER SLAVE También se aplica el patrón en la implementación del principio denominado “redundancia modular triple”: 

En esta aproximación, la ejecución de un servicio es delegada a tres componentes independientes, para que el resultado sea válido al menos dos de tales componentes deben dar el mismo resultado.

IMPLEMENTACIÓN ● La implementación puede ser relativamente compleja. ● Los esclavos se implementan como hilos ó procesos separados. ● Maestro-esclavo pueden correr sobre una sola máquina ó también pueden ser distribuidos en varias máquinas (Ej. Cluster)

CARACTERÍSTICAS ● Maestro-esclavo no siempre es factible porque algunas tareas no pueden ser particionadas. ● Difícil de implementar. ● Dificultad en la portabilidad, si se tiene una fuerte dependencia sobre el hardware al que fué configurado.

EJEMPLO  El

problema del agente viajero es bien conocido en la teoría de grafos. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades minimice la distancia recorrida por el viajante

EJEMPLO La mayoría de las implementaciones del problema del agente viajero son aproximaciones a la solución óptima comparando un número fijo de rutas. Una de las aproximaciones más simples es seleccionar rutas aleatorias para comparar, y esperar que la mejor ruta encontrada se aproxime a la solución óptima. Se debe asegurar que las rutas a investigar son seleccionadas de forma aleatoria, y que el número de rutas seleccionadas es suficientemente grande.

PROBLEMA 

Divide y vencerás es un principio común para solucionar muchos tipos de problemas. El trabajo es dividido en varias subtareas iguales que son procesadas independientemente. El resultado del cálculo total es calculado a partir de los resultados proporcionados por cada proceso parcial.

PROBLEMA 7 7

3

3 3

4

2

1

9

4

2

1

9

2

1

2

1

1

8

10 8

8

10

PROBLEMA Surgen varias fuerzas cuando se implementa cada estructura:  Los clientes no deben ser conscientes de que cada cálculo se basa en el principio de divide y vencerás.  Ni los clientes ni las subtareas de procesamiento deben depender en los algoritmos para dividir el trabajo y ensamblar el resultado final.

PROBLEMA Puede ser útil usar diferentes implementaciones, semánticamente idénticas, para procesar subtareas. Por ejemplo para incrementar la precisión computacional.  Algunas veces el procesar las subtareas necesita coordinación, este es el caso de aplicaciones de simulación. 

SOLUCIÓN Introduzca una instancia de coordinación entre los clientes del servicio y el procesamiento de las subtareas individuales. Un componente maestro divide el trabajo en subtareas iguales, delega estas subtareas a varios componentes esclavos independientes, y regresa un resultado final a partir de los resultados parciales que retornan los esclavos. El principio general se aplica en tres áreas: 

Tolerancia a fallas. La ejecución de un servicio es delegada a varias implementaciones replicadas. Las fallas de ejecuciones del servicio pueden ser detectadas y manejadas.

SOLUCIÓN 



Computación paralela. Una tarea compleja es dividida en un número fijo de subtareas idénticas que son ejecutadas en paralelo. El resultado final es construido con la ayuda de los resultados obtenidos del procesamiento de estas subtareas. Precisión computacional. La ejecución de un servicio es delegada a varias implementaciones diferentes. Los resultados imprecisos pueden ser detectados y manejados.

ESTRUCTURA 

En una estructura Master-Slave hay al menos dos instancias de los componentes esclavos conectados al maestro.

DINÁMICA

Diagrama de secuencia del patrón Master Slave

IMPLEMENTACIÓN La implementación del patrón Master-Slave sigue cinco pasos. 1. Divida el trabajo. Especifique como la computación de la tarea se puede dividir e un conjunto igual de subtareas. Identifique los subservicios que son necesarios para procesar una subtarea. 2. Combine los resultados de las subtareas. Especifique como el resultado final del servicio puede ser computado con la ayuda de los resultados obtenidos del procesamiento de las subtareas individuales. 3. Especifique la cooperación entre maestro y esclavos. Defina una interfaz para el subservicio identificado en el paso 1. 4. Implemente los componentes esclavos de acuerdo con las especificaciones desarrolladas en el paso previo. 5. Implemente el maestro de acuerdo con las especificaciones de los pasos 1 a 3.

VARIANTES Maestro-Esclavo con tolerancia a fallas . El maestro delega la ejecución de un servicio a un número fijo de implementaciones replicadas, cada una representada por un esclavo. Tan pronto como el primer esclavo termina, el resultado es regresado al cliente del maestro. La tolerancia a fallas se basa en que por lo menos si un esclavo no falla, el cliente puede recibir un resultado válido. El maestro puede manejar la situación en la que fallen todos los esclavos, lanzando una excepción que el cliente deba manejar. El maestro puede usar time-outs para detectar la falla de un esclavo; sin embargo, esta variante no ayuda cuando el que falla es el maestro.

VARIANTES Maestro-Esclavo para computación paralela . Este es el uso más común del patrón. El maestro divide una tarea compleja en varias subtareas idénticas, cada una de las cuales es ejecutada en paralelo por un esclavo. El maestro construye el resultado final a partir de los resultados obtenidos por los esclavos. El maestro contiene las estrategias para dividir la tarea global y para computar el resultado final. El algoritmo para subdividir la tarea y coordinar los esclavos es dependiente de la arquitectura de hardware de la máquina en la que el programa corre. Antes de que el maestro pueda calcular el resultado final debe esperar a que termine la ejecución de cada una de las subtareas. 

VARIANTES Maestro-Esclavo con coordinación de esclavos . Los cómputos de un esclavo puede dependen del estado de computación de otros esclavos. En esta situación, los cálculos de todos los esclavos deben ser suspendidos regularmente para que cada esclavo se coordine con los esclavos de que depende, después de lo cual los esclavos continúan sus cómputos individuales.

USOS CONOCIDOS Multiplicación de matrices

Transformación-codificación de una imagen. Por ejemplo el cálculo de la transformación coseno de un bloque de 8x8 pixeles de una imagen.