MULTICOMPUTADORAS
Los multicomputadores, tal y como ya se ha comentado en la introducción, surgieron de la necesidad de poder escalar en número de procesadores sin un elevadísimo coste económico. Estos consisten en un conjunto de procesadores y bancos de memoria que se conectan a través de una red de interconexión con una determinada topología de red.
La principal característica de los multicomputadores es que los procesadores, al más bajo nivel, ya no pueden compartir datos a través de loads/stores, sino que lo tienen que hacer por medio de mensajes. Es por eso por lo que en este tipo de sistemas no hay problemas de coherencia de caché ni de consistencia de memoria. Aquí, la sincronización se hace explícita con los mensajes, tal y como muestra la figura 40, con primitivas estilo send y receive. En el send se especifíca el buffer a enviar y a quién se envía. Por el otro lado, el receive debe especificar el buffer de recepción y de quién lo recibe. Los buffer del send y del receive están en espacios de direcciones diferentes, suponiendo que son procesos diferentes.
HARDWARE DE UNA
MULTICOMPUTADORA
Los nodos más básicos de una multicomputadora consiste en
una CPU, la memoria, una interfaz de red y algunas veces un disco duro. El nodo
puede estar empaquetado en un gabinete de PC estándar, pero el adaptador de
gráficos, el monitor, el teclado y el ratón casi nunca están presentes. En
algunos casos la PC contiene un tablero de multiprocesador de 2 o 4 vías, en
donde cada nodo posiblemente tiene un chip de doble o cuádruple núcleo en vez
de una sola CPU, pero por cuestión de simplicidad vamos a suponer que cada nodo
tiene una CPU.
TECNOLOGÍA
DE INTERCONEXIÓN
La topología de red es un patrón en el cual los
switches están conectados a otros switches mediante links. Las interconexiones
se muestran con grafos donde los nodos representan o bien procesadores o
switches, y las aristas los links. La topología de red influye en la latencia de
los mensajes, en el bandwidth conseguido, y en la congestión que pueda haber en
las comunicaciones, tal y como se ha podido reflejar en las diferentes medidas
de rendimiento que se han comentado en el subapartado anterior.
INTERFACES DE RED
Todos los nodos en
una multicomputadora tienen una tarjeta insertable que contiene la conexión del
nodo hacia la red de interconexión, la cual mantiene unida toda la
multicomputadora. La forma en que están construidas estas tarjetas y la manera
en que se conectan a la CPU principal y la RAM tienen consecuencias
considerables para el sistema operativo. Ahora analizaremos brevemente algunas de
las cuestiones relacionadas.
SOFTWARE DE COMUNICACIÓN DE BAJO NIVEL
El enemigo de la
comunicación de alto rendimiento en los sistemas de multicomputadora es el
copiado de paquetes en exceso. En el mejor caso, habrá una copia de la RAM a la
tarjeta de interfaz en el nodo de origen, una copia de la tarjeta de interfaz
de origen a la tarjeta de interfaz de destino (si no hay almacenamiento y
retransmisión a lo largo de la ruta), y una copia de ahí a la RAM de destino:
un total de tres copias. Sin embargo, en muchos sistemas es aún peor. En
especial, si la tarjeta de interfaz está asignada al espacio de direcciones
virtuales del kernel y no al espacio de direcciones virtuales de usuario, un
proceso de usuario sólo puede enviar un paquete si emite una llamada al sistema
que se atrape en el kernel. Tal vez los kernels tengan que copiar los paquetes
a su propia memoria, tanto en la entrada como en la salida; por ejemplo, para evitar los fallos de
página mientras transmiten por la red. Además, el kernel receptor tal vez no
sepa en dónde debe colocar los paquetes entrantes sino hasta que haya tenido la
oportunidad de examinarlos.
INTERFAZ DE COMUNICACIÓN DE NODO A RED
Otra de las cuestiones es cómo llevar los paquetes a
la interfaz de red. La manera más rápida es utilizar el chip de DMA en la
tarjeta sólo para copiar los paquetes de la RAM. El problema con este método es
que el DMA utiliza direcciones físicas en vez de virtuales, y se ejecuta de
manera independiente a la CPU. Para empezar, aunque sin duda un proceso de
usuario conoce la dirección virtual de cada paquete que desea enviar, por lo
general no conoce la dirección física.
No es conveniente hacer una llamada al sistema
para realizar la asignación de dirección virtual a dirección física, ya que el
objetivo de colocar la tarjeta de interfaz en espacio de usuario en primer lugar
era para evitar tener que hacer una llamada al sistema para cada paquete que se
va a enviar.
COMPARACIÓN ENTRE LLAMADAS CON BLOQUEO Y
SIN BLOQUEO
Las llamadas antes
descritas son llamadas con bloqueo (que algunas veces se les conoce como llamadas
síncronas). Cuando un proceso llama a send, especifica un destino y un búfer
para enviarlo a ese destino. Mientras se está enviando el mensaje, el proceso emisor
se bloquea (es decir, se suspende). La instrucción que sigue a la llamada a
send no se ejecuta sino hasta que el mensaje se haya enviado por completo. De
manera similar, una llamada a receive no devuelve el control sino hasta que se
haya recibido en realidad un mensaje y se haya colocado en el búfer al que
apunta el parámetro. El proceso permanece suspendido en receive hasta que llega
un mensaje, aunque tarde horas en llegar. En algunos sistemas, el receptor
puede especificar de qué proceso desea recibir, en cuyo caso permanece bloqueado
hasta que llega un mensaje de ese emisor.
LLAMADA A PROCEDIMIENTO REMOTO
Aunque el modelo de paso de mensajes ofrece una manera
conveniente de estructurar un sistema operativo de multicomputadora, tiene una
falla incorregible: el paradigma básico sobre el que se basa toda la
comunicación es la entrada/salida. En esencia, los procedimientos send y
receive se dedican a realizar operaciones de E/S, y muchas personas creen que
la E/S es el modelo de programación incorrecto.
Este problema se
conoce desde hace mucho tiempo, pero no se había hecho mucho al respecto sino
hasta que Birrel y Nelson (1984) escribieron un artículo en el que introdujeron
una forma completamente distinta de atacarlo. Aunque la idea es gratificante y
simple (ya que alguien pensó en ella), a menudo las implicaciones son sutiles.
En esta sección examinaremos el concepto, su implementación, sus puntos fuertes
y sus puntos débiles.
ASPECTOS
DE IMPLEMENTACIÓN
A pesar de la elegancia conceptual de la RPC, hay unos
cuantos problemas a tratar. Uno de los más importantes es el uso de parámetros
tipo apuntador. Por lo general no hay problema al pasar un apuntador a un
procedimiento. El procedimiento al que se llama puede utilizar el apuntador de
la misma forma que lo hace el procedimiento que hace la llamada, debido a que
los dos procedimientos residen en el mismo espacio de direcciones virtuales.
Con la RPC es imposible pasar apuntadores, ya que el cliente y el servidor se
encuentran en distintos espacios de direcciones.
MEMORIA COMPARTIDA DISTRIBUIDA
Muchos programadores aún prefieren un modelo de
memoria compartida y les gustaría utilizarlo también en una multicomputadora.
Para nuestra sorpresa, es posible preservar muy bien la ilusión de la memoria
compartida mediante el uso de una técnica llamada DSM (Memoria
compartida distribuida), ccon
la DSM, cada página se localiza en una de las memoriasy cada máquina tiene su propia memoria virtual y sus
propias tablas de páginas.
DUPLICACIÓN
Una mejora al sistema
básico que puede mejorar el rendimiento en forma considerable es la duplicación
de páginas que sean de sólo lectura; por ejemplo: texto del programa,
constantes de sólo lectura u otras estructuras de datos de sólo lectura. Por
ejemplo, si es una sección de texto del programa, cuando la CPU 0 la utilice existe
la probabilidad de que se envíe una copia a la CPU 0 sin perturbar el texto
original en la memoria de la CPU 1. De esta forma, las CPUs 0 y 1 pueden hacer referencia
a todas las veces que lo requieran, sin producir trampas para obtener la
memoria faltante.
COMPARTICIÓN FALSA
Los sistemas de
DSM son similares a los multiprocesadores en ciertos puntos clave. En ambos
sistemas, cuando se hace referencia a una palabra de memoria que no sea local,
se obtiene una parte de memoria que contiene la palabra de su ubicación actual
y se coloca en la máquina que está haciendo la referencia (memoria
principal o caché, respectivamente).
PLANIFICACIÓN DE MULTICOMPUTADORAS
• Cada
nodo tiene su propia memoria y su
propio conjunto de procesos.
• Es un proceso similar a la planificación de
multiprocesadores
• Puede utilizar cualquier algoritmo de planificación local
• Es posible utilizar la planificación de pandilla de
los multiprocesadores
BALANCEO DE CARGA
ALGORITMO
DE TERMINÍSTICO BASADO EN TEORÍA DE GRAFOS
Clase de
algoritmos que se estudia mucho para los sistemas que consisten en procesos con
requerimientos de CPU y memoria conocidos, y una matriz conocida que
proporciona la cantidadpromedio de tráfico entre cada par de procesos.ç
UN
ALGORITMO HEURÍSTICO INICIADO POR EL EMISOR
Ahora veamos
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
