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.
No hay comentarios:
Publicar un comentario