Toro bootloader

Como puedo empezar?. El bootloader es un proyecto en sí mismo. Si se quiere escribir un OS por Hobby, no hay que empezar por el bootloader claramente. Lleva tiempo, el debug es oscuro y te vas a decepcionar rápidamente. Terminás, no haciendo nada y dejando el proyecto de escritura de un OS. Creo que lo más importante e interesante ocurre dentro del kernel, es decir, una vez que el SO ya ha sido cargado en memoria. De todas formas, hay gente loca por ahi que aun quiere armarse su propio bootloader. Dirigido a ese tipo de personas he comenzado a escribir un poco de documentación sobre el Toro's bootloader en el wiki. Espero que lo encuentren interesante y aprecien el esfuerzo hecho (si, no me gusta escribir documentación, pero reconozco lo importante que es ;) ). El conocimiento es tal, si y solo si, es comunicado.

Matias E. Vara

www.torokernel.org

Mecanismos de comunicación entre procesos

Como se observó en el post anterior, es necesario disponer de mecanismos que sincronicen el acceso a variables compartidas. Los algoritmos más comunes para proteger recursos son: semáforos, paso de mensajes y spin-lock.

Estos mecanismos permiten hacer cumplir la exclusión mutua, requerida para el acceso a variables compartidas, es decir, que se garantiza que en un instante dado sólo un proceso está leyendo o escribiendo sobre la variable.

Los semáforos son manejados por dos primitivas P y V, ambas utilizan operaciones atómicas para incrementar y decrementar el contador del semáforo. Éstos son fáciles de implementar y requieren poca memoria.

Otro mecanismo muy utilizado es el paso de mensajes. Este permite el paso de información entre procesos. Las primitivas utilizadas son Send y Receiv. La principal ventaja de este mecanismo es que las partes intervinientes pueden ser totalmente independientes unas de otras.

Los spin-lock

Los procedimientos más utilizados para proteger recursos en sistemas de Multiprocesamiento en el entorno del kernel son los denominados spin-lock. Los mecanismos de comunicación antes mencionados son construidos internamente con spin-lock.

Los recursos son protegidos con variables de cierre denominados Locks, estas son variables binarias; la variable tomará el valor “1” si un proceso se encuentra utilizando el recurso o “0” si ningún proceso está utilizando el recurso. Cuando hablamos de recurso nos referimos a una dada variable del sistema.

Para modificar una variable Lock se utilizan operaciones atómicas, por ejemplo la instrucción: Test and Set. Esto garantiza que el procesador que se quede con el recurso sea uno solo.

El proceso que quiere acceder a una zona crítica permanece en un bucle realizando Polling hasta que la variable Lock vuelva a “0”. Cuando esto ocurre la vuelve “1” (esta última operación se realiza en un solo paso). Mientras la variable está en estado “ocupado” el proceso se encuentra en un bucle. El proceso saldrá del bucle cuando logre cambiar el valor de la variable Lock.

En sistemas con pocos procesadores un proceso suele estar poco tiempo en el bucle intentando modificar a la variable Lock. Pero a medida que incrementamos el número de procesos, este tiempo se vuelve crítico, y la solución simple de implementar un spin-lock para proteger recursos compartidos, debe ser re-evaluada.

Impacto del uso de spin-lock

En el test[1] realizado sobre 5 aplicaciones Linux, se compara el número de procesos involucrados y el porcentaje de tiempo que los procesos permanecen en el bucle de Lock (denominado Lock Overhead).

Para cada tarea se fue incrementando el número de procesos involucrados, cada uno trabajando en paralelo.

Se observa que a medida que más procesos se utilizan, más tiempo pasa la aplicación realizando Locking debido a la utilización de variables compartidas por todos los procesos. De esta manera si utilizamos variables compartidas estamos limitando la paralelización de una aplicación porque a medida que incrementamos el número de procesos involucrados la aplicación destina más tiempo en obtener el permiso para usar una variable compartida que para realizar trabajo efectivo.

[1] Yoav Etison, Dan Tsafrir et. al.: Fine Grained Kernel Logging with KLogger:

Experience and Insights. Hebrew University, 2005.

Matias E. Vara

www.torokernel.org

Protección de memoria en sistemas multicore

Este artículo forma parte del trabajo final “Paralelización de algoritmos numéricos con TORO kernel” por Matías Vara, para el título de Ingeniería en Electrónica, Universidad Nacional de La Plata. Estos apuntes teóricos sirven para poder entender el diseño del núcleo.

Introducción

Cuando se diseña un kernel para un sistema multicore la memoria compartida deberá ser protegida de accesos de escritura concurrentes. Las protecciones que utiliza el kernel incrementan la complejidad del código y decrementan el desempeño del SO.
Si uno o más procesadores acceden a los mismos datos al mismo tiempo, en el caso de sistemas multitarea debe cumplirse la exclusión mutua para proteger a los datos compartidos.
Para el caso de sistemas monoprocesadores multitarea apropiativos ocurre que cada cierto tiempo el planificador cambia de tarea, por lo tanto el único riesgo que se tiene es que mientras los datos están siendo modificados por un proceso, el planificador decida cambiar de tarea. La protección implementada en este caso es sencilla: simplemente se deshabilita el planificador mientras el proceso está en su zona crítica y luego se habilita nuevamente.
En sistemas con más de un procesador esta solución no puede ser implementada. Esto es debido a que los procesos se ejecutan en paralelo en los diferentes procesadores y puede existir otro proceso ejecutando la misma línea de código al mismo tiempo; por lo tanto de nada serviría inhabilitar el planificador del procesador local.

Metodos de proteccion de recursos

Para poder proteger recursos en sistemas con multiprocesamiento primero debemos definir operaciones atómicas. Estas son operaciones que si bien pueden estar constituidas por pasos más pequeños conforman un paquete indivisible de ejecución.

Operaciones atomicas

En los microprocesadores las operaciones tanto de escritura como de lectura tomadas de forma individual son siempre atómicas. Esto quiere decir que se garantiza que la operación terminará antes que cualquier otro procesador acceda a esa región de memoria.
Para ciertas operaciones el procesador utiliza el bloqueo del bus de memoria para controlar la lectura o escritura de una región. Para ello se proporciona la línea de control #Lock que es levantada cuando se realizan operaciones críticas de memoria. Mientras esta señal está en alto, las solicitudes provenientes de otros procesadores son bloqueadas.
El acceso al bus es no determinístico; esto quiere decir que el procesador que se quedará con el bus es el que llegue antes. Cada procesador compite con el resto, lo cual es un problema a medida que incrementamos el número de procesadores.
Pero ¿Por qué son necesarias las operaciones atómicas? Supongamos que queremos incrementar una variable contador, el código Pascal de esto sería:

contador = contador + 1 ;

Si esta línea se ejecuta simultáneamente en dos procesadores el resultado será incorrecto sino se utiliza protección.
El valor correcto de contador es 2 pero utilizando instrucciones que se realizan de forma atómica.
Al utilizar operaciones atómicas los procesadores se sincronizan para modificar de a uno la variable, y el resultado es correcto. El tiempo necesario para sincronizar la ejecución de la instrucción se incrementa con el número de procesadores que intentan acceder a la variable.

Las operaciones atómicas más comunes son TEST and SET y COMPARE and SWAP.

Impacto de las operaciones atomicas

La utilización de operaciones atómicas en sistemas con pocos procesadores no supone una gran carga para el sistema y es una solución rápida a problemas de memoria compartida; pero a medida que incrementamos el número de procesadores éstas se tornan en un cuello de botella.
Si suponemos una PC con 8 núcleos de 1.45 GHz cada uno [1], mientras que el tiempo consumido en promedio por instrucción es 0.24 ns, una instrucción de incremento atómico demora 42.09 ns.
Es claro que el tiempo consumido por las operaciones atómicas empieza a ser crítico.

[1] Paula McKenney: RCU vs. Locking Performance on Different Types of CPUs.
http://www.rdrop.com/users/paulmck/RCU/LCA2004.02.13a.pdf, 2005

Matias E. Vara
www.torokernel.org

Organizacion de memoria en arquitecturas multicore: Conclusion.

Desde la perspectiva del programador, la memoria remota y la local se acceden de forma transparente. En teoría un sistema NUMA podría implementarse en un sistema SMP sin problemas. Sin embargo el SO debería realizar un manejo eficiente de la asignación de memoria para sacar provecho a estas tecnologías.

Una de las principales ventajas del acceso uniforme a memoria es que la administración de la memoria por parte del SO es fácil de implementar, mientras que en un sistema de NUMA, no. El SO deberá asignar memoria a los procesos dependiendo sobre qué CPU esta ejecutándose y exige que se tenga un banco de memoria para cada CPU. La performance se degrada rápidamente si prevalecen los accesos remotos sobre los locales.

El SO Windows soporta NUMA desde la versión Server 2003 e incluye un conjunto de llamadas al sistema que permiten al programador explotar este recurso. Por otro lado Linux también es compatible con NUMA a partir de la versión 2.6.X.

Este aspecto se tuvo en cuenta en el desarrollo del kernel dedicado con el fin aprovechar las nuevas tecnologías NUMA presentes en los procesadores modernos. La única manera posible por el momento de optimizar los accesos a memoria en sistemas multicore es a través de buses dedicados y con un modelo de memoria NUMA. En especial en entornos de alta performance estas optimizaciones no pueden ser no tenidas en cuenta.

Matias E. Vara

www.torokernel.org