Sistemas operativos modernos

comunicación dentro de la máquina y pueden ignorarse. Los arcos que van de un subgrafo a otro representan tráfico de red. La meta entonces es hallar la división que reduzca al mínimo el tráfico de red y satisfaga todas las restricciones. Por ejemplo, la figura 8-25 muestra un sis­ tema de nueve procesos, A a /, con cada arco rotulado con 1a carga de comunicación promedio entre esos dos procesos (por ejemplo, en Mbps). Figura 8-25. Dos formas de asignar nueve procesos a tres nodos. En la figura 8-25a hemos dividido el grafo con los procesos A, £ y G en el nodo 1, los pro­ cesos B, F y H en q \ nodo 2 y los procesos C, D e I en e\ nodo 3. El tráfico total de la red es la suma de los arcos atravesados por los cortes (las líneas de guiones), que en este caso es de 30 unidades. En la figura 8-25b tenemos una división distinta que sólo tiene 28 unidades de tráfi­ co de red. Suponiendo que esta división safisface todas las restricciones de memoria y CPU, es una mejor opción porque requiere menos comunicación. De manera intuitiva, lo que estamos haciendo es buscar agolpamientos que estén fuertemen­ te acoplados (flujo de tráfico elevado dentro del agrupamiento). Entre los primeros trabajos que analizan el problema están Chow y Abraham (1982), Lo (1984), y Stone y Bokhari (1978). Un algoritmo heurístico distribuido Iniciado por el transmisor Examinemos ahora algunos algoritmos distribuidos. Un algoritmo dice que cuando se crea un proceso se ejecuta en el nodo que lo creó, a menos que ese nodo esté sobrecargado. La métri­ ca para determinar si un nodo está sobrecargado o no podría ser el número de procesos, el ta­ maño del conjunto de trabajo total o alguna otra. Si el nodo está sobrecargado, escoge otro nodo al azar y le pregunta cuánta carga tiene (utilizando la misma métrica). Si la carga del no­ do elegido está por debajo de cierto valor de umbral, el nuevo proceso se envía allí (Eager et al., 1986). Si no lo está, se escoge otra máquina para examinar. Las pruebas no continúan en forma indefinida. Si no se encuentra un anfitrión apropiado después de N pruebas, el algo­ ritmo termina y el proceso se ejecuta en la máquina que lo originó. Lo que se busca es que los nodos con mucha carga traten de deshacerse del exceso de trabajo, como se ilustra en la figu­ ra 8-26a.