Algoritmos de Procesos, Memoria y Disco
Algoritmos de ProcesosSon 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 buscar una estación inactiva.
Para el modelo de la pila de procesadores:
* Decidir dónde ejecutar cada nuevo proceso.
Modelos de AsignaciónGeneralmente 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:
o Una vez colocado un proceso en una máquina permanece ahí hasta que termina.
* Migratorias:
o Un proceso se puede trasladar aunque haya iniciado su ejecución.
o Permiten un mejor balance de la carga pero son más complejas.
Los algoritmos de asignación intentan optimizar algo:
* Uso de las cpu:
o Maximizar el número de ciclos de cpu que se ejecutan para trabajos de los usuarios.
o Minimizar el tiempo de inactividad de las cpu.
* Tiempo promedio de respuesta:
o Minimizar no los tiempos individuales de respuesta sino los tiempos promedio de respuesta.
* Tasa de respuesta:
o 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.
Aspectos del Diseño de Algoritmos de Asignación de ProcesadoresLos 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:
o Un emisor sobrecargado que busca una máquina inactiva.
o Un receptor desocupado que busca trabajo.
Aspectos de la Implantación de Algoritmos de Asignación de ProcesadoresCasi 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:
o Son correctos luego de intercambiar la información y de que todo se ha registrado.
o Son poco confiables mientras las tablas continúan su actualización, es decir que se presentan situaciones de no equilibrio.
Ejemplos de Algoritmos de Asignación de ProcesadoresUn Algoritmo Determinista Según la Teoría de Gráficas
Es aplicable a sistemas donde se conoce:
* Requerimientos de cpu y de memoria de los procesos.
* Tráfico promedio entre cada par de procesos.
Si el número de procesos supera al número de cpu:
* Habrá que asignar varios procesos a la misma cpu.
* La asignación deberá minimizar el tráfico en la red.
El sistema se puede representar en una gráfica con pesos:
* Cada nodo es un proceso.
* Cada arco es el flujo de mensajes entre dos procesos.
* Los arcos que van de una subgráfica a la otra representan el tráfico en la red.
* Cada subgráfica es una unidad de asignación.
* El algoritmo debe buscar unidades de asignación fuertemente acopladas:
o Tráfico intenso dentro de la unidad de asignación.
o Tráfico escaso entre unidades de asignación.
Un Algoritmo CentralizadoEs un algoritmo heurístico que a diferencia del anterior no precisa información anticipadamente.
Es un algoritmo arriba-abajo (Mutka y Livny) centralizado porque un coordinador mantiene una tabla de usos:
* Contiene una entrada por estación de trabajo inicializada en “0”.
* Cuando ocurren eventos significativos se envían al coordinador mensajes para actualizar la tabla.
* Las decisiones de asignación se basan en la tabla:
o Se toman cuando ocurren eventos de planificación, tales como: se realiza una solicitud, se libera un procesador, el reloj produce una marca de tiempo.
* No se intenta maximizar el uso de la cpu.
* Se procura otorgar a cada usuario una parte justa del poder de cómputo.
* Cuando la máquina donde se crea un proceso decide que se debe ejecutar en otra parte:
o Le pide al coordinador de la tabla de usos que le asigne un procesador:
+ Si existe uno disponible y nadie más lo desea, se otorga el permiso.
+ Si no, la solicitud se niega y se registra.
* Si un usuario ejecuta procesos en máquinas de otros usuarios acumula puntos de penalización por segundo, lo que se registra en la tabla de usos.
* Si un usuario tiene solicitudes pendientes insatisfechas, se restan puntos de penalización.
* Si no existen solicitudes pendientes y ningún procesador está en uso, la entrada de la tabla de usos se desplaza un cierto número de puntos hacia el “0”, hasta alcanzarlo.
* El movimiento de puntos hacia arriba y abajo da nombre al algoritmo.
Un puntaje positivo en una entrada de la tabla de usos indica que la estación de trabajo relacionada es un usuario de los recursos del sistema.
Un puntaje negativo significa que precisa recursos.
Una puntuación “0” es neutra.
La heurística utilizada para la asignación de procesadores es la siguiente:
* Cuando un procesador se libera gana la solicitud pendiente cuyo poseedor tiene la puntuación menor.
* Un usuario que no ocupe procesadores y que tenga pendiente una solicitud durante mucho tiempo:
o Siempre vencerá a alguien que utilice muchos procesadores.
o Se cumple con el principio de asignar la capacidad de manera justa.
Un Algoritmo JerárquicoEl algoritmo anterior no se adapta bien a los sistemas de gran tamaño, pues el nodo central se convierte en un cuello de botella y en un único punto de fallo.
Una solución son los algoritmos jerárquicos que:
* Mantienen la sencillez de los centralizados.
* Se escalan mejor que los centralizados.
Un método consiste en organizar a los procesadores en jerarquías lógicas independientes de la estructura física:
* Se establece un árbol jerárquico con distintos niveles.
* Para cada grupo de máquinas hay una máquina administradora:
o Mantiene un registro de las máquinas ocupadas y las inactivas.
* Cada procesador se comunica con un superior y un número reducido de subordinados:
o El flujo de información es controlable.
En caso de falla de un equipo con funciones jerárquicas:
* Lo puede reemplazar un subordinado:
o La elección la pueden hacer los subordinados, los pares jerárquicos del equipo fallado o el superior jerárquico del mismo.
Para disminuir la vulnerabilidad se puede tener en la cima del árbol jerárquico no uno sino un grupo de equipos; si alguno del grupo falla los restantes eligen a un subordinado para integrar el grupo superior.
Las tareas se pueden crear en cualquier parte de la jerarquía y pueden requerir varios procesos, es decir varios procesadores.
Cada administrador debe mantener un registro de sus equipos dependientes que estén disponibles.
Si el administrador que recibe una solicitud determina que no tiene suficientes procesadores disponibles, transfiere la solicitud hacia arriba a su superior, quien también podría trasladarla hacia arriba nuevamente.
Si el administrador determina que sí puede satisfacer la solicitud:
* Divide la solicitud en partes y la distribuye a los administradores subordinados a él.
* Los subordinados repiten esta operación hasta llegar al nivel inferior.
* Los procesadores se señalan como “ocupados” y el número de procesadores asignados se informa hacia arriba.
Un importante problema consiste en que podría haber varias solicitudes en distintas etapas del algoritmo de asignación:
* Puede conducir a estimaciones no actualizadas del número de procesadores disponibles (también pudieron salir de servicio algunos de los considerados disponibles).
* Podrían presentarse situaciones de competencia, bloqueo, etc. en el intento de asignación de procesadores.
Un Algoritmo Distribuido Heurístico (Eager)Al crearse un proceso:
* La máquina donde se origina envía mensajes de prueba a una máquina elegida al azar; pregunta si su carga está por debajo de cierto valor de referencia.
* Si la respuesta es positiva el proceso se envía a ese lugar.
* Si no, se elige otra máquina para la prueba.
* Luego de “n” pruebas negativas el algoritmo termina y el proceso se ejecuta en la máquina de origen.
Un Algoritmo de RematesUtiliza un modelo económico con:
* Compradores y vendedores de servicios.
* Precios establecidos por la oferta y la demanda.
Los procesos deben comprar tiempo de cpu.
Cada procesador anuncia su precio mediante un archivo que todos pueden leer (es el precio pagado por el último cliente).
Los distintos procesadores pueden tener distintos precios según sus características y servicios.
Cuando un proceso desea iniciar un proceso hijo:
* Verifica si alguien ofrece el servicio que necesita.
* Determina el conjunto de procesadores que pueden prestar sus servicios.
* Selecciona el mejor candidato según precio, rapidez, relación precio / desempeño, tipo de aplicación, etc.
* Genera una oferta y la envía a su primer opción.
Los procesadores:
* Reúnen las ofertas recibidas y eligen una.
* Informan a los ganadores y perdedores.
* Ejecutan los procesos.
* Actualizan los precios.
Planificación en Sistemas DistribuidosGeneralmente cada procesador hace su planificación local (si tiene varios procesos en ejecución) independientemente de lo que hacen los otros procesadores .
La planificación independiente no es eficiente cuando se ejecutan en distintos procesadores un grupo de procesos:
* Relacionados entre sí.
* Con una gran interacción entre los procesos.
Se necesita una forma de garantizar que los procesos con comunicación frecuente se ejecuten de manera simultánea.
En muchos casos un grupo de procesos relacionados entre sí iniciarán juntos.
La comunicación dentro de los grupos debe prevalecer sobre la comunicación entre los grupos.
Se debe disponer de un número de procesadores suficiente para soportar al grupo de mayor tamaño.
Cada procesador se multiprograma con “n” espacios para los procesos (multiprogramación de nivel “n”).
El algoritmo de Ousterhout utiliza el concepto de coplanificación:
* Toma en cuenta los patrones de comunicación entre los procesos durante la planificación.
* Debe garantizar que todos los miembros del grupo se ejecuten al mismo tiempo.
* Se emplea una matriz conceptual donde:
o Las filas son espacios de tiempo.
o Las columnas son las tablas de procesos de los procesadores.
* Cada procesador debe utilizar un algoritmo de planificación Round Robin:
o Todos los procesadores ejecutan el proceso en el espacio “0” durante un cierto período fijo.
o Todos los procesadores ejecutan el proceso en el espacio “1” durante un cierto período fijo, etc.
* Se deben mantener sincronizados los intervalos de tiempo.
* Todos los miembros de un grupo se deben colocar en el mismo número de espacio de tiempo pero en procesadores distintos.
