PDF de programación - Algoritmo de equilibrio de carga en un cluster heterogéneo

Universidad Rey Juan CarlosI. T. Informática de SistemasAlgoritmo deAlgoritmo deequilibrio de cargaequilibrio de cargaen un clusteren un clusterheterogéneoheterogéneoDIEGO CHAPARRO GONZÁLEZTUTOR: JOSE LUIS BOSQUE ORERO Universidad Rey Juan CarlosDiego Chaparro GonzálezI. T. Informática de SistemasPROYECTO FIN DE CARRERAINDICE:Capítulo 1. Introducción .......................................................................................... 11.1.- Sistemas distribuidos .............................................................................. 11.2.- Distribución de carga .............................................................................. 21.3.- Objetivos ................................................................................................. 5Capítulo 2. Estado del arte ....................................................................................... 62.1.- Introducción ............................................................................................ 62.2.- Algoritmos centralizados ........................................................................ 72.3.- Algoritmos de clustering distribuidos ..................................................... 72.4.- Autómatas de aprendizaje automático .................................................... 82.5.- Política de localización aleatoria ............................................................ 92.6.- Algoritmo de sondeo ............................................................................... 92.7.- Algoritmos basados en ofertas .............................................................. 102.8.- Algoritmo de reclutamiento .................................................................. 102.9.- Algoritmo de compartición de carga flexible ....................................... 112.10.- Algoritmo adaptativo iniciado simétricamente ................................... 122.11.- Difusión natural .................................................................................. 12Capítulo 3. Solución propuesta .............................................................................. 143.1.- Introducción .......................................................................................... 143.2.- Principales características ..................................................................... 163.3.- Conceptos básicos ................................................................................. 173.4.- Descripción del algoritmo ..................................................................... 183.5.- Diagrama de flujo de datos ................................................................... 26Capítulo 4. Implementación ................................................................................... 314.1.- Aplicación CBIR .................................................................................. 314.2.- Implementación del algoritmo de distribución de carga ....................... 34Capítulo 5. Resultados ............................................................................................ 525.1.- Introducción .......................................................................................... 525.2.- Resultados sin carga local ..................................................................... 535.3.- Resultados con carga local .................................................................... 57Capítulo 6. Conclusiones ........................................................................................ 61Capítulo 7. Bibliografía .......................................................................................... 64 Universidad Rey Juan CarlosDiego Chaparro GonzálezI. T. Informática de SistemasPROYECTO FIN DE CARRERA Universidad Rey Juan CarlosDiego Chaparro GonzálezI. T. Informática de SistemasPROYECTO FIN DE CARRERAINTRODUCCIÓN:1.1.- Sistemas distribuidos:Los sistemas distribuidos cada vez tienen mayor relevancia y comienzan asustituir a los potentes mainframes. La aparición de estos sistemas se debe a dosavances tecnológicos. Uno de ellos es el desarrollo de los microprocesadores, quecada vez son más potentes y que hacen que ya no se cumpla una ley que hasta ahorasi se cumplía con los mainframes:“la potencia de CPU es proporcional al cuadrado de su precio”Y el otro avance es el desarrollo de las redes de área local de alta velocidad,que proporcionan un medio de comunicación entre docenas o cientos de ordenadorescon una velocidad cada vez mayor.Estos sistemas distribuidos se forman mediante una red (usualmente unaLAN) y un conjunto de CPU’s(nodos). Éste tipo de sistemas presentan muchasventajas con respecto a los mainframes:-ECONÓMICA: Mejor relación precio/rendimiento. Ya que a unprecio inferior al de un mainframe, se consigue un rendimientomuy alto.Página 1 de 64 Universidad Rey Juan CarlosDiego Chaparro GonzálezI. T. Informática de SistemasPROYECTO FIN DE CARRERA-VELOCIDAD: Pueden alcanzar un mayor nivel de cómputoque los mainframes.-ESCALABILIDAD: Son fácilmente escalables. Simplementehace falta añadir una nueva CPU.-ESTABILIDAD: Mayor estabilidad. Ya que aunque falle una delas CPU’s, el sistema sigue funcionando.Para conseguir que los sistemas distribuidos alcancen un mayor nivel derendimiento hay que tener en cuenta también los problemas que pueden presentar:-SOFWARE: Todavía no existe software suficientementedesarrollado para este tipo de sistemas.-REDES DE INTERCONEXIÓN: Las redes pueden llegar asaturarse y causar otro tipo de problemas, que no ocurren enmainframes.1.2.- Distribución de carga:Uno de los principales aspectos para obtener un buen rendimiento de estossistemas es la distribución de carga.Es un componente muy importante, ya que de él depende el buen uso que sehace de la capacidad global de rendimiento del sistema (eficiencia). El rendimientoglobal depende en gran medida del algoritmo elegido para la distribución de carga.La distribución de carga es el método para que los sistemas distribuidosobtengan el mayor grado de eficiencia posible. La distribución de carga consiste en elreparto de la carga entre los nodos del sistema para que la eficiencia sea mayor. Lacarga se distribuye y se traslada de los nodos más cargados a los nodos menoscargados del sistema. Con esto se consigue una reducción del tiempo de ejecución dePágina 2 de 64 Universidad Rey Juan CarlosDiego Chaparro GonzálezI. T. Informática de SistemasPROYECTO FIN DE CARRERAlas tareas en el sistema distribuido, y se consigue aproximar el tiempo de finalizaciónde la ejecución de las tareas de cada uno de los nodos, es decir, se consigue que losnodos terminen de ejecutar “al mismo tiempo”, y que no haya grandes diferenciasentre el término de uno de ellos y él de los demás. Con todo esto se consigue que nohaya nodos sobrecargados, y otros libres de trabajo, porque estos nodossobrecargados trasladarían parte de su trabajo a esos otros nodos más libres detrabajo.Los algoritmos de distribución de carga se basan en unos componentes, quemarcan las diferencias entre unos algoritmos y otros: -Política de información: La cuál decide qué tipo deinformación debe recoger de los nodos, de qué nodos deberecoger ésta información, y cuándo debe recogerla.-Política de transferencia: Decide si cada uno de los nodos esapto o no para llevar a cabo una transferencia, tanto de emisorcomo de receptor. -Política de selección: Decide cuál es la carga que se va atransferir en una transferencia.-Política de localización: Localiza el nodo adecuado pararealizar una determinada transferencia.De éste aspecto depende en gran medida el rendimiento global, ya quedependiendo de la elección del algoritmo de distribución, se puede conseguir quetodos los nodos del sistema estén trabajando en todo momento para minimizar eltiempo de ejecución de los procesos, o una mala elección del algoritmo dedistribución puede hacer que tan solo unos pocos nodos estén sobrecargados mientrasque otros no tengan nada de trabajo.Esa es la función principal que debe llevar a cabo el algoritmo dedistribución de carga, hacer que todos los nodos estén trabajando mientras que hayaPágina 3 de 64 Universidad Rey Juan CarlosDiego Chaparro GonzálezI. T. Informática de SistemasPROYECTO FIN DE CARRERAalgún proceso pendiente, y sea posible ejecutar dicho proceso en varios nodosconsiguiendo una disminución en el tiempo de proceso. Hay algunos casos en los queel algoritmo de distribución no debe repartir carga entre los demás nodos ya que eltiempo de ejecución de dicho proceso puede ser tan pequeño, que si se repartieraentre los nodos se perdería demasiado tiempo en la comunicación y el resultado seríaun tiempo de ejecución mayor.El algoritmo de distribución debe tener en cuenta todos estos detalles. Peroademás existen varios políticas que hay que definir para llegar a elegir un algoritmode distribución eficiente:•Centralizado vs Distribuido:Las políticas centralizadas son aquellas en las que la informaciónse concentra en una única ubicación física, que toma todas lasdecisiones de planificación. Esta solución presenta problemas decuellos de botella, y tiene un límite en su grado de escalabilidad.Por otro lado las políticas distribuidas son aquellas en las que lainformación está repartida entre los distintos nodos, y lasdecisiones son tomadas entre todos. Los problemas son que lainformación puede no ser coherente, se replica la información ynecesita más comunicaciones.•Estáticas vs Dinámicas:Las políticas estáticas toman decisiones de forma determinista oprobabilística sin tener en cuenta el estado actual del sistema. Estasolución puede ser efectiva cuando la carga se puede caracterizarsuficientemente bien antes de la ejecución, pero falla al ajustar lasfluctuaciones del sistema.Las políticas dinámicas utilizan información sobre el estado delsistema para tomar decisiones, por lo que potencialmente mejoranPágina 4 de 64 Universidad Rey Juan CarlosDiego Chaparro GonzálezI. T. Informática de SistemasPROYECTO FIN DE CARRERAa las políticas estáticas mejorand