El manual para el clustering con openMosix - Sistemas operativos (I)

Introducción

Los ordenadores se están convirtiendo en una plataforma cada vez más abierta y los sistemas operativos tienen que dar los servicios necesarios para que esto pueda gestionarse de manera adecuada. Dando un breve repaso a la historia de los sistemas operativos puede verse que cada vez tienen más posibilidades de comunicación.

Cuando se construyeron las primeras redes de computadores se vio la potencia que tenían estos sistemas y se desarrolló el paradigma cliente/servidor. Se crearon los sistemas operativos de red con servicios como NFS o FTP para acceder a sistemas de ficheros de otros ordenadores. Xwindow para entorno gráfico, lpd para poder imprimir remotamente además de un conjunto de herramientas que permitían el acceso a recursos compartidos.

En los aurales de la informática el sistema operativo ni siquiera existía: se programaba directamente el hardware. Se vio que era muy pesado y se programó una capa de abstracción que evitaba al programa tener que tener un conocimiento total del hardware: el sistema operativo. Se descubrió también que con un solo proceso se desperdiciaba tiempo de procesador y como tales dispositivos eran carísimos se empezaron a inventar mecanismos que evitasen que el programa esperase bloqueado por ejemplo las operaciones de entrada/salida. Se llegó a la multiprogramación en el ambicioso MULTICS y el posterior UNIX. Estos dos sistemas se desarrollaron a finales de los años 60 y se basaban en el MIT Compatible Timesharing System realizado en 1958.

En los años 70 se añadieron las primeras capacidades de interconexión:

• Xerox inventó la red Ethernet
• IBM la Token Ring
• y surgió UNIX BSD 4.2

Este sistema operativo fue ampliamente usado porque integraba capacidades de comunicación: implementaba TCP/IP y tenía capacidades de intercomunicación entre procesos.

---

Un sistema operativo distribuido puede acceder a cualquier recurso transparentemente y tiene grandes ventajas sobre un sistema operativo de red. Pero es muy difícil de implementar y algunos de sus aspectos necesitan que se modifique seriamente el núcleo del sistema operativo, por ejemplo para conseguir memoria distribuida transparente a los procesos. También se tiene que tener en cuenta que ahora la máquina sobre la que corre todo el sistema es el sistema distribuido (un conjunto de nodos) por lo que tareas como planificación de procesos (scheduling) o los hilos ( threads) y señales entre procesos toman una nueva dimensión de complejidad. Por todo esto aún no existe ningún sistema distribuido con todas las características de transparencia necesarias para considerarlo eficiente.
A partir de ahora no hablaremos de computadores, ordenadores ni PC. Cualquier dispositivo que se pueda conectar a nuestro sistema y donde se pueda desarrollar un trabajo útil para el sistema se referenciará como nodo. El sistema operativo tiene que controlar todos estos nodos y permitir que se comuniquen eficientemente.

Aunque tras leer este capítulo el lector podrá intuir esta idea, queremos hacer notar que un sistema distribuido se puede ver como el siguiente nivel de abstracción sobre los sistemas operativos actuales. Como hemos visto la tendencia es a dar más servicios de red y más concurrencia. Si pusiéramos otra capa por encima que aunara ambos, esta capa sería el sistema operativo distribuido. Esta capa debe cumplir los criterios de transparencia que veremos en el próximo apartado.

Podemos comprender esto mejor haciendo una analogía con el SMP: cuando sólo existe un procesador todos los procesos se ejecutan en él, tienen acceso a los recursos para los que tengan permisos, se usa la memoria a la que puede acceder el procesador, etc. Cuando hay varios procesadores todos ellos están corriendo procesos (si hay suficientes para todos) y los procesos migran entre procesadores.

En un sistema multiprocesador al igual que un sistema multicomputador hay una penalización si el proceso tiene que correr en un elemento de proceso (procesador o nodo) distinto al anterior: en multiprocesador por la contaminación de cache y TLB; en multicomputador por la latencia de la migración y pérdidas de cache. En un sistema multicomputador se persigue la misma transparencia que un sistema operativo con soporte multiprocesador, esto es, que no se deje ver a las aplicaciones que realmente están funcionando en varios procesadores.

En este capítulo además se tratarán las zonas de un sistema operativo que se ven más afectadas para conseguirlo. Éstas son:

• Scheduling.

El scheduling de los procesos ahora puede ser realizado por cada nodo de manera individual, o mediante algún mecanismo que implemente el cluster de manera conjunta entre todos los nodos.

• Deadlocks.

Las técnicas usadas hasta ahora en un nodo local no se pueden generalizar de una forma eficiente en el sistema distribuido.

• Manejo de memoria.

Hay que disponer de memoria distribuida: poder alojar y desalojar memoria de otros nodos de una forma transparente a las aplicaciones.

• Intercomunicación de procesos.

Los procesos podrían estar ubicados en cualquier nodo del sistema. Se deben proveer de los mecanismos necesarios para permitir esta intercomunicación de tipo señales, memoria distribuida por el cluster u otros.

• Sistemas de ficheros.

Pretenden que todo el sistema distribuido tenga la misma raíz para que no sea necesario explicitar en qué nodo se encuentra la información.

• Entrada/salida.

Tendría que ser posible acceder a todos los recursos de entrada/salida globalmente, sin tener que indicar explícitamente a que nodo están estos recursos conectados.

Procesos y Scheduling

Utilidad de migrar procesos

La migración de un proceso consiste en mover el proceso desdel nodo donde se está ejecutando a un nuevo entorno. Aunque no se suela emplear en este caso, se podría hablar de migración cuando un proceso se mueve de procesador. Aquí consideraremos migración cuando un proceso se mueve de un nodo a otro.

En un sistema de tipo cluster lo que se pretende, como se verá en el capítulo Clusters, es compartir aquellos dispositivos (a partir de ahora serán los recursos) conectados a cualquiera de los nodos. Uno de los recursos que más se desearía compartir, aparte del almacenamiento de datos, es el procesador de cada nodo. Para compartir el procesador entre varios nodos lo más lógico es permitir que las unidades atómicas de ejecución del sistema operativo (procesos, con PID propio) sean capaces de ocupar en cualquier momento cualesquiera de los nodos que conforman el cluster.

En un sistema multiusuario de tiempo compartido la elección de qué proceso se ejecuta en un intervalo de tiempo determinado la hace un segmento de código que recibe el nombre de scheduler, el planificador de procesos. Una vez que el scheduler se encarga de localizar un proceso con las características adecuadas para comenzar su ejecución, es otra sección de código llamada dispatcher la que se encarga de substituir el contexto de ejecución en el que se encuentre el procesador, por el contexto del proceso que queremos correr. Las cosas se pueden complicar cuando tratamos de ver este esquema en un multicomputador. En un cluster, se pueden tener varios esquemas de actuación.

• Scheduling conjunto. En el cual todos los nodos del cluster hacen la elección de los procesos que se ejecutaran en el cluster y quizá incluso en cada nodo. Esto requiere una actuación conjunta de todos los nodos, lo que implica que el scheduling podría ser:
  • Centralizado: una o varias máquinas trabajando para efectuar las tareas de scheduler y organizar el resto del cluster. Es sencillo de implementar, pero tiene más inconvenientes que ventajas, aparte que los inconvenientes son de mucho peso y muy obvios.
  • Distribuido: requieren un modelo matemático adecuado y una implementación más complicada.
• Scheduling individual: cada nodo actúa de la manera comentada en sistemas individuales, pero añade la acción de migrar procesos a otros nodos, de manera que se optimice tiempo de ejecución global en el cluster. Para esto, los nodos comparan la carga de otros nodos y deciden cúal de los procesos que tienen en la cola de espera para ser ejecutados es el óptimo para ser enviado a otro nodo.

Conforme se avance en este manual se verá cuál puede convenir más para cada caso. Otra de las políticas que puede variar del scheduling en un ordenador individual a un cluster es la de diseminación de la información de los nodos. A la hora de elegir sobre qué nodo migrar un proceso, tanto en el scheduling conjunto como en el individual, se debe conocer la información de los nodos para balancear convenientemente el sistema. Esta diseminación puede estar basada en:

• Información global.
• Información parcial.

De estos dos, el primero no es muy escalable, pero probablemente sea más adecuado en ciertas condiciones. Lo más habitual es que un cluster deje las decisiones sobre cuándo ejecutar cada proceso a cada nodo particular, por tanto la principal novedad en un sistema distribuido es que hay que permitir que los procesos se ejecuten en cualquier computador no necesariamente en el que se crearon. Y transparentemente a los mismos procesos. Este ha sido un tema estudiado numerosas veces, con todo tipo de conclusiones, seguramente la más sorprendente es la de Tanenbaum3.1. Se equivocó (una vez más) porque openMosix ha conseguido la migración en la práctica. Esta migración de procesos tiene varias ventajas, como son:

• Compartición de carga: los procesos se trasladarán a la máquina con menos carga para evitar que haya sistemas sobrecargados. También se tiene en cuenta cuándo se está acabando la memoria de la máquina. En definitiva los procesos van donde tengan más recursos. En el caso óptimo se tendría la potencia de todas las máquinas sumadas, pues con un balanceo perfecto podrían tenerse a todos los nodos trabajando a máximo rendimiento, aunque el trabajo original se produjese en un nodo solo.

Por supuesto este este es el caso ideal y no se puede dar en la realidad pues siempre se necesita potencia de cálculo para enviar y recibir los procesos así como para tomar las decisiones (overhead).

• Rendimiento de las comunicaciones: los procesos que necesitan entrada/salida en un nodo se desplazan a éste para evitar traer todos los datos a través de la red. Otra variante es mantener a todos los procesos que interactúan fuertemente entre ellos en una misma máquina.

Las principales decisiones que se deben tomar en un sistema distribuido para hacer esta migración eficiente las podemos englobar en tres políticas distintas:

• Políticas de localización
• Políticas de migración
• Políticas de ubicación

A parte de estas políticas también hay que hacer otras consideraciones que no tienen que ver con las decisiones que se toman sino cómo van a ser implementadas en la práctica, estas son:

• Parte del proceso a migrar
• Mecanismos de migración

Política de localización

Cubre las decisiones referentes a desde dónde se lanzaran los procesos.

Este tipo de planteamiento sólo se efectúa en los sistemas SSI de los que se hablará más tarde, ya que necesita un acoplamiento muy fuerte entre los nodos del cluster. Un ejemplo puede ser el requerimiento de un cluster que dependiendo del usuario o grupo de usuario elija un nodo preferente donde ejecutarse por defecto. En openMosix no se hace uso de esta política, ya que el sistema no está tan acoplado como para hacer que otro nodo arranque un programa.

Política de migración

La política de migración plantea las decisiones que hay que hacer para responder a preguntas, a saber:

• ¿cuándo se inicia la migración?
• ¿quién inicia la migración?

Para saber cuándo se debe realizar una migración nuestro nodo debe estar en contacto con los demás nodos y recolectar información sobre su estado y así, y teniendo en cuenta otros parámetros como la carga de la red, se debe hacer una decisión lo más inteligente posible y decidir si es momento de migrar y qué es lo que se migra.

Las causas que hacen que se quiera realizar la migración van a depender del objetivo del servicio de la migración. Así si el objetivo es maximizar el tiempo usado de procesador, lo que hará que un proceso migre es el requerimiento de procesador en su nodo local, así gracias a la información que ha recogido de los demás nodos decidirá si los merece la pena migrar o en cambio los demás nodos están sobrecargados también.

La migración podría estar controlada por un organismo central que tuviera toda la información de todos los nodos actualizada y se dedicase a decidir como colocar los procesos de los distintos nodos para mejorar el rendimiento. Esta solución aparte de ser poco escalable, pues se sobrecargan mucho la red de las comunicaciones y uno de los equipos, es demasiado centralizada ya que si este sistema falla se dejarán de migrar los procesos.

El otro mecanismo es una toma de decisiones distribuida: cada nodo tomará sus propias decisiones usando su política de migración. Dentro de esta aproximación hay dos entidades que pueden decidir cuando migrar un proceso: el propio proceso o el kernel del sistema operativo.

• Si el proceso es quien va a decidirlo hay el problema de que él tiene que ser consciente de la existencia de un sistema distribuido.
• En cambio si es el kernel quien decide, la función de migración y la existencia de un sistema distribuido pueden ser transparentes al proceso.

Esta última es la política que usa openMosix.

Política de ubicación

Encontrar el mejor nodo donde mandar un proceso que está sobrecargando el nodo de ejecución no es una estrategia fácil de implementar. Entran en juego una gran amplia gama de algoritmos generalmente basados en las funcionalidades o recursos a compartir del cluster, y dependiendo de cuáles sean estos, se implantarán unas medidas u otras. El problema no es nuevo y puede ser tratado como un problema de optimización normal y corriente, pero con una severa limitación. A pesar de ser un problema de optimización se debe tener en cuenta que este código va a ser código de kernel, por lo tanto y suponiendo que está bien programado, el tiempo de ejecución del algoritmo es crucial para el rendimiento global del sistema. ¿De qué sirve optimizar un problema de ubicación de un proceso que va a tardar tres segundos en ejecutarse, si dedicamos uno a decidir donde colocarlo de manera óptima y además sin dejar interactuar al usuario?

Este problema penaliza a ciertos algoritmos de optimización de nueva generación como las redes neuronales, o los algoritmos genéticos y beneficia a estimaciones estadísticas.

Parte de los procesos a migrar

Una vez se sabe cuándo, de dónde y hacia dónde migrará el proceso, falta saber qué parte del proceso se va a migrar. Hay dos aproximaciones:

1. Migrar todo el proceso.

Implica destruirlo en el sistema de origen y crearlo en el sistema de destino. Se debe mover la imagen del proceso que consta de, por lo menos, el bloque de control del proceso (a nivel del kernel del sistema operativo). Además, debe actualizarse cualquier enlace entre éste y otros procesos, como los de paso de mensajes y señales (responsabilidad del sistema operativo). La transferencia del proceso de una máquina a otra es invisible al proceso que emigra y a sus asociados en la comunicación.
El movimiento del bloque de control del proceso es sencillo. Desde el punto de vista del rendimiento, la dificultad estriba en el espacio de direcciones del proceso y en los recursos que tenga asignados. Considérese primero el espacio de direcciones y supóngase que se está utilizando un esquema de memoria virtual (segmentación y/o paginación). Pueden sugerirse dos estrategias:

• • Transferir todo el espacio de direcciones en el momento de la migración. No hace falta dejar rastro del proceso en el sistema anterior. Sin embargo si el espacio de direcciones es muy grande y si es probable que el proceso no necesite la mayor parte, este procedimiento puede ser costoso.
  • Transferir sólo aquella parte del espacio de direcciones que reside en memoria principal. Cualquier bloque adicional del espacio de direcciones virtuales será transferido sólo bajo demanda. Esto minimiza la cantidad de datos que se transfieren. Sin embargo, se necesita que la máquina de origen siga involucrada en la vida del proceso, pues mantiene parte de su espacio de direcciones, nótese que este sistema no tiene nada que ver con el anterior, pues el sistema de origen es un mero almacenador de información.

También es una estrategia obligada cuando lo que se migran son hilos en vez de procesos y no migramos todos los hilos de una vez. Esto está implementado en el sistema operativo Emerald3.2 y otras generalizaciones de este a nivel de usuario.

1. Migrar una parte del proceso.

En este sistema:

• • el contexto del nivel de usuario del proceso es llamado remote: contiene el código del programa, la pila, los datos, el mapeo de la memoria y los registros del proceso. El remote encapsula el proceso cuando éste está corriendo en el nivel de usuario.
  • El contexto del kernel es llamado deputy: contiene la descripción de los recursos a los cuales el proceso está unido, y la pila del kernel para la ejecución del código del sistema cuando lo pida el proceso.

Mantiene la parte del contexto del sistema que depende del lugar por lo que se mantiene en el nodo donde se generó el proceso.
Como en Linux la interfície entre el contexto del usuario y el contexto del kernel está bien definida, es posible interceptar cada interacción entre estos contextos y enviar esta interacción a través de la red. Esto está implementado en el nivel de enlace con un canal especial de comunicación para la interacción.
El tiempo de migración tiene una componente fija que es crear el nuevo proceso en el nodo al que se haya decidido migrar; y una componente lineal proporcional al número de páginas de memoria que se vayan a transferir. Para minimizar la sobrecarga de esta migración, de todas las páginas que tiene mapeadas el proceso sólo se van a enviar las tablas de páginas y las páginas en las que se haya escrito.
OpenMosix consigue transparencia de localización gracias a que las llamadas dependientes al nodo nativo que realiza el proceso que ha migrado se envían a través de la red al deputy. Así openMosix intercepta todas las llamadas al sistema, comprueba si son independientes o no, si lo son las ejecuta de forma local (en el nodo remoto) sino la llamada se emitirá al nodo de origen y la ejecutará el deputy. Éste devolverá el resultado de vuelta al lugar remoto donde se continua ejecutando el código de usuario.

Mecanismos de migración

Normalmente las políticas de ubicación y localización no suelen influir en estos mecanismo pues en general, una vez que el proceso migra no importa donde migre. Si se ha decidido que los mismos procesos son quienes lo deciden todo (automigración) se llega a un mecanismo de migración que es el usado en el sistema operativo AIX de IBM. Para este caso el procedimiento que se sigue cuando un proceso decide migrarse es:

1. Se selecciona la máquina destino y envía un mensaje de tarea remota. El mensaje lleva una parte de la imagen del proceso y de información de archivos abiertos.
2. En el nodo receptor, un proceso servidor crea un hijo y le cede esta información.
3. El nuevo proceso extrae los datos, los argumentos, la información del entorno y de la pila que necesita hasta completar su operación.
4. Se indica con una señal al proceso originario que la migración ha terminado. Este proceso envía un mensaje final para terminar la operación al nuevo proceso y se destruye.

Si en cambio es otro proceso el que comienza la migración en vez de ser el propio proceso tenemos el sistema que se usa en Sprite: se siguen los mismos pasos que en AIX pero ahora el proceso que maneja la operación lo primero que hace es suspender el proceso que va a migrar para hacerlo en un estado de no ejecución. Si el proceso que decide no está en cada máquina sino que hay solamente uno que hace decisiones globales, hay una toma de decisiones centralizada. En este caso se suelen usar unas instrucciones especiales desde esa máquina a las máquinas origen y destino de la migración, aunque básicamente se sigue el patrón expuesto del sistema AIX.

También puede ocurrir que se necesite un consenso de un proceso en la máquina origen y otro proceso en la máquina destino, este enfoque tiene la ventaja de que realmente se asegura que la máquina destino va a tener recursos suficientes, esto se consigue así:

1. El proceso controlador de la máquina origen (después de las decisiones oportunas) le indica al proceso controlador de la máquina destino que le va a enviar un proceso, este proceso le responde afirmativamente si está preparado para recibir un proceso.
2. Ahora el proceso controlador de la máquina origen puede hacer dos cosas: ceder el control al núcleo para que haga la migración o pedir al núcleo estadísticas del proceso y se las envía al proceso controlador destino (el núcleo hace lo mismo si toma el control).
3. El proceso controlador de la máquina destino, o su kernel, toman esa información (el proceso se la enviaría al kernel) y deciden si hay suficientes recursos en el sistema para el nuevo proceso. Si lo hubiera el núcleo reserva los recursos necesarios para el proceso y lo notifica al proceso controlador que notifica al proceso controlador de la máquina origen que proceda con la migración.