Algoritmos o Modelos de Asignación

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.