3.4.1 MODELOS ALGORITMOS DISEÑO IMPLANTACIÓN

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.

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.