Asignación de Procesadores:
Son necesarios algoritmos para decidir cuál proceso hay que ejecutar y en qué máquina.
Para el modelo de estaciones de trabajo:
· Decidir cuándo ejecutar el proceso de manera local y cuándo es necesario buscar estaciónes inactivas o no locales que tienen una conexion a la misma red pero fuera de ella.
Para el modelo de la pila de procesadores:
· Decidir dónde ejecutar cada nuevo proceso respecto de la misma maquina que es la tabla(lista) de los procesos que se crean dentro de la maquina.
Modelos y algoritmos con sus respectos diseños e implementación:
· Esta estrategia consiste como su nombre lo indica, en dedicar un grupo de procesadores a una aplicación mientras dure esta aplicación , de manera que cada hilo de la aplicación se le asigna un procesador.
·
·
·
· Figura 10.2 Ejemplo de planificación por grupos
· con uno y cuatro hilos.
·
· Una desventaja es que si un hilo de una aplicación se bloquea en espera de una E/S o por sincronizacion de otro hilo, el procesador de dicho hilo quedara desocupado: no hay multiprogramacion de procesadores.
·
· Esta forma de planificación presenta las siguientes ventajas:
·
· Ø En un sistema masivamente paralelo, con decenas o cientos de procesadores cada uno de los cuales representa una pequeña parte del coste del sistema, la utilización del procesador no es tan importante como medida de la efectividad o el rendimiento.
·
· Ø La anulación total del intercambio de procesos durante el tiempo de vida de un programa dara como resultado una aceleracion sustancial del programa.
·
·
·
· Figura 10.3 Aceleración de una aplicación en función
· del número de procesos.
·
· Experiencia: se ejecutan 2 aplicaciones, una multiplicacion de matrices y un calculo de la transformacion rapida de Fourriet ( FFT fast fourrier transform), en un sistema con 16 trabajadores,:Cada aplicación divide el problema en una serie de tareas, que se organizan en hilos que ejecutan la aplicación. Los programas se escribieron de forma que se permitiera variar el numero de hilos empleados. Basicamente cada aplicacion define una serie de tareas y las pone en cola. Se toman tareas de la cola y se corresponden con hilos disponibles. Si hay menos hilos que tareas , entonces las tareas restantes permanecen en la cola y son corregidas por hilos que hayan completado su tarea asignada.
· En la figura 10.3 puede verse la representacion de la aceleracion de la aplicación a medida que el numero de hilos que esta ejecutando las tareas varia desde 1 a 24. El eje vertical representa la aceleracion de una aplicación y el eje horizontal representa el numero de hilos.
· Al inicio ambas aplicaciones tienen una aceleracion de 2,8 para un solo hilo, la figura muestra que esto empeora notablemente cuando el numero de hilos crece.
· Una posible solucion :
· * Limitar el numero de hilos activos al numero de procesadores para el sistema.
· ANALOGIA:
· Se puede comparar analogicamente el problema de la asignacion del procesador en un multiprocesador con el problema de la asignacion de memoria en un monoprocesador.
· ¿Cómo se asignan muchos procesadores a un programa?
·
· Este problema podria llegar a ser equivalente a :
· ¿Como asignar varios marcos de pagina a un proceso en un instante dado?
·
· Se propone el concepto de:
· Conjunto de trabajo de actividades
·
· Analogo al:
· Conjunto de trabajo en memoria virtual. Etc.
·
Aspectos del Diseño de Algoritmos de Asignación de Procesadores
Los principales aspectos son los siguientes:
Algoritmos deterministas vs. Heurísticos.
Algoritmos centralizados vs. Distribuidos.
Algoritmos óptimos vs. subóptimos.
Algoritmos locales vs. Globales.
Algoritmos iniciados por el emisor vs. Iniciados por el receptor.
Los algoritmos deterministas son adecuados cuando se sabe anticipadamente todo acerca del comportamiento de los procesos, pero esto generalmente no se da, aunque puede haber en ciertos casos aproximaciones estadísticas. Los algoritmos heurísticos son adecuados cuando la carga es impredecible.
Los diseños centralizados permiten reunir toda la información en un lugar y tomar una mejor decisión; la desventaja es que la máquina central se puede sobrecargar y se pierde robustez ante su posible falla.
Generalmente los algoritmos óptimos consumen más recursos que los subóptimos, además, en la mayoría de los sistemas reales se buscan soluciones subóptimas, heurísticas y distribuidas.
Cuando se va a crear un proceso se debe decidir si se ejecutará en la máquina que lo genera o en otra (política de transferencia):
La decisión se puede tomar “solo con información local” o “con información global”.
Los algoritmos locales son sencillos pero no óptimos.
Los algoritmos globales son mejores pero consumen muchos recursos.
Cuando una máquina se deshace de un proceso la política de localización debe decidir dónde enviarlo:
Necesita información de la carga en todas partes, obteniéndola de:
Un emisor sobrecargado que busca una máquina inactiva.
Un receptor desocupado que busca trabajo.
‘’‘Aspectos de la Implantación de Algoritmos de Asignación de Procesadores’‘’
Casi todos los algoritmos suponen que las máquinas conocen su propia carga y que pueden informar su estado:
La medición de la carga no es tan sencilla.
Un método consiste en contar el número de procesos (hay que considerar los procesos latentes no activos). Otro método consiste en contar solo los procesos en ejecución o listos.
También se puede medir la fracción de tiempo que la cpu está ocupada.
Otro aspecto importante es el costo excesivo en consumo de recursos para recolectar medidas y desplazar procesos, ya que se debería considerar el tiempo de cpu, el uso de memoria y el ancho de banda de la red utilizada por el algoritmo para asignación de procesadores.
Se debe considerar la complejidad del software en cuestión y sus implicancias para el desempeño, la correctez y la robustez del sistema.
Si el uso de un algoritmo sencillo proporciona casi la misma ganancia que uno más caro y más complejo, generalmente será mejor utilizar el más sencillo.
Se debe otorgar gran importancia a la estabilidad del sistema:
Las máquinas ejecutan sus algoritmos en forma asíncrona por lo que el sistema nunca se equilibra.
La mayoría de los algoritmos que intercambian información:
Son correctos luego de intercambiar la información y de que todo se ha registrado.
Son poco confiables mientras las tablas continúan su actualización, es decir que se presentan situaciones de no equilibrio.
Modelos de Asignación
Generalmente se utilizan las siguientes hipótesis:
—Todas las máquinas son idénticas (o al menos compatibles en el código); difieren a lo sumo en la velocidad.
—Cada procesador se puede comunicar con los demás.
Las estrategias de asignación de procesadores se dividen en:
—No migratorias:
· Una vez colocado un proceso en una máquina permanece ahí hasta que termina.
—Migratorias:
· Un proceso se puede trasladar aunque haya iniciado su ejecución.
· Permiten un mejor balance de la carga pero son más complejas.
Los algoritmos de asignación intentan optimizar algo:
—Uso de las cpu:
· Maximizar el número de ciclos de cpu que se ejecutan para trabajos de los usuarios.
· Minimizar el tiempo de inactividad de las cpu.
—Tiempo promedio de respuesta:
· Minimizar no los tiempos individuales de respuesta sino los tiempos promedio de respuesta.
—Tasa de respuesta:
· Minimizar la tasa de respuesta, que es el tiempo necesario para ejecutar un proceso en cierta máquina dividido por el tiempo que tardaría en cierto procesador de referencia.
