Sistemas operativos modernos

cesos listos— no funciona porque cada proceso sólo puede ejecutarse en la CPU en la que es­ tá actualmente. No obstante, cuando se crea un proceso puede decidirse dónde colocarlo, por ejemplo para balancear la carga. Dado que cada nodo tiene sus propios procesos, puede usarse cualquier algoritmo de calen­ darización local. Sin embargo, también es posible usar calendarización tipo pandilla, de la mis­ ma forma en que se usa en un multiprocesador, porque para ello tan sólo se requiere un acuerdo inicial en cuanto a qué proceso ejecutar en cuál porción de tiempo, y alguna forma de coordinar el principio de las porciones de tiempo. 8.2.7 Balanceo de carga Hay relativamente poco que decir acerca de la calendarización de multicomputadoras porque, una vez que un proceso se ha asignado a un nodo, puede usarse cualquier algoritmo de calendariza­ ción local, a menos que se esté usando calendarización tipo pandilla. Sin embargo, precisamen­ te porque se tiene muy poco control cuando se ha asignado un proceso a un nodo, es importante la decisión de cuál proceso debe ir en cuál nodo. Esto contrasta con los sistemas multiprocesa­ dor, en los que todos los procesos residen en la misma memoria y se les puede calendarizar en cualquier CPU a voluntad. Por ello, vale la pena estudiar la forma de asignar con eficacia los procesos a los nodos. Los algoritmos y heurísticas empleados para efectuar tal asignación se denominan algoritmos de asignación de procesador. Se ha propuesto un gran número de algoritmos de asignación de procesador (es decir, nodo) al paso de los años. Las diferencias radican en lo que se supone conocido y en lo que se desea lograr. Entre las propiedades de un proceso que podrían conocerse están las necesidades de tiem­ po de CPU, el consumo de memoria y la cantidad de comunicación con todos los demás proce­ sos. Entre las posibles metas están reducir al mínimo el desperdicio de ciclos de CPU debido a la falta de trabajo local, reducir al mínimo el ancho de banda total de comunicación y garanti­ zar la equidad a los usuarios y procesos. A continuación examinaremos unos cuantos algoritmos para tener una idea de las posibilidades. Un algoritmo determinista por teoría de grafos Una clase de algoritmos estudiada con amplitud se usa en sistemas que constan de procesos con necesidades de CPU y de memoria conocidas, y una matriz conocida que da la cantidad promedio de tráfico entre cada par de procesos. Si el número de procesos es mayor que el nú­ mero de procesadores, k, será preciso asignar varios procesos a cada CPU. Lo que se busca es realizar esta asignación a modo de reducir al mínimo el tráfico de red. El sistema puede representarse como un grafo ponderado, en el que cada vértice es un pro­ ceso y cada arco representa el flujo de mensajes entre dos procesos. Desde el punto de vista matemático, el problema se reduce entonces a hallar una forma de dividir el grafo en k subgra- fos disjuntos, sujeta a ciertas restricciones (como que las necesidades totales de CPU y de me­ moria estén por debajo de algunos límites para cada subgrafo). Para cada solución que satisface las restricciones, los arcos que están en su totalidad dentro de un mismo subgrafo representan