Importante bug solucionado en la migración de threads

A continuación  describiré brevemente acerca del problema descubierto en la migración de thread y como fue solucionado, no ahondaré en detalles.

En las versiones anteriores de Toro, cuando un thread intentaba crear otro thread remoto, la función ThreadCreate era ejecutada localmente y eran alocadas las estructuras: TThread, TLS y el Stack. Luego la   estructura completa era migrada al core remoto. 

El problema en este procedimiento era que los bloques de memoria TThread, TLS  y Stack ya no eran locales lo cual significa una grave infracción en el modelo NUMA. 

De este modo, se reemplazó la migración de la estrucutura TThread por la migración de un conjunto de parametros tales como: tamaño de pila, puntero al código de ejecución, etc. Así, ThreadCreate es ejecutado remotamente y le son pasados los parámetros guardados en esta estructura. Como antes, se retorna al thread padre el ThreadID del recien nacido.

Se puede observar que mientras la creación de un thread local es instantánea, la creación de un thread remoto involucra dos pasos: primero se migran los parámetros y luego se retorna el identificador de thread.

  

Parcheando GDB 7.3 para debug remoto

Esta vez voy a mostrar como parchear GDB 7.3 con el fin de debuguear de forma remota un kernel corriendo sobre la maquina virtual QEMU. Cuando corremos GDB e intentamos debuguear de forma remota nos retorna el siguiente mensaje de error:

Remote packet too long: 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ...

No estoy muy seguro del origen del problema pero parece que es por el tamaño de los registros. Cuando la máquina virtual salta de modo real a modo long o protegido, los registros cambian su tamaño pero GDB no detecta esta situación. Asi, cuando GDB recibe un paquete más grande que el esperado, tira este error. De esta manera, el parche implementado solo se encarga de incrementar el buffer de recepción cuándo suceden aquellos casos.

El primer paso es bajarse el source de GDB 7.3 desde http://www.gnu.org/s/gdb/download/, no estoy seguro si funciona en versiones más viejas pero supongo que si.

Una vez bajado y descomprimido, editar el archivo gdb-7.3/gdb/remote.c, línea 5693. Aqui nos encontramos con el procedimiento process_g_packet. Ahora será necesario buscar y reemplazar el código original por las siguientes líneas:

/* Further sanity checks, with knowledge of the architecture. */

//if (buf_len > 2 * rsa->sizeof_g_packet)

// error (_("Remote 'g' packet reply is too long: %s"), rs->buf);

if (buf_len > 2 * rsa->sizeof_g_packet)

{

rsa->sizeof_g_packet = buf_len;

for (i = 0; i < gdbarch_num_regs (gdbarch); i++)

{

if (rsa->regs[i].pnum == -1)

continue;

if (rsa->regs[i].offset >= rsa->sizeof_g_packet)

rsa->regs[i].in_g_packet = 0;

else

rsa->regs[i].in_g_packet = 1;

}

}

Finálmente, solo resta compilar:

$ ./configure

$ make

Esto debería ser suficiente para ejecutar GDB correctamente.

Matias E. Vara

www.torokernel.org

Toro en el Congreso de Micro-electronica (UNLP)

Presentaré un artículo referido al nucleo dedicado TORO en el Congreso de Microelectrónica a desarrollarse en la Universidad Nacional de La Plata, Facultad de Ingeniería. La presentación será el dia Jueves 8 de Septiembre a las 16.20 hs en la Sala A. La web del evento es http://www.ing.unlp.edu.ar/uea2011/ para mayor información. Saludos!

Matias E. Vara

www.torokernel.org

Toro en Ubuntu 11.04!

Finalmente es posible compilar TORO en Linux Ubuntu 11.04. Supongo que de aquí en más trabajaré solo sobre esta plataforma. También he dejado de utilizar SVN para comenzar con GIT.

En el wiki pueden encontrar el procedimiento para instalar y testear TORO en ubuntu. He realizado algunos cambios en la estructura del proyecto con el fin de facilitar la comprensión y permitir un mejor crecimiento del proyecto. Saludos.

Matias E. Vara

www.torokernel.org

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

e1000 driver para TORO

He comenzado el desarrollo del driver para tarjetas de red del tipo e1000, Intel Gigabit o compatibles. Estoy usando de base el codigo de Minix3 el cuál es muy claro y como emulador el qemu. La version 0.12.0 permite emular la placa e1000.
Aquí les pongo un screen de la detección y lectura de la MAC, por ahora es lo que tengo en el SVN.
Saludos!.
Matias E. Vara
www.torokernel.org

Organizacion de memoria en arquitecturas multicore II

Continuación del artículo "Organización de memoria en arquitecturas multicore".

Arquitecturas de memoria no uniforme.

Las arquitecturas de memoria no uniforme (NUMA por sus siglas en inglés) utilizan (como en SMP) un único espacio de direcciones, pero en este caso cada procesador es dueño de una parte de la memoria, a la cual puede acceder más rápido. Utiliza pasaje de mensajes escondido para el acceso a memoria remota.

En un entorno NUMA el programador puede acceder de forma transparente a cualquier posición de memoria y es el hardware quien crea esta abstracción.

Unas de las pioneras en tecnología NUMA fue la empresa Sequent Computer Systems, quien introdujo los sistemas de multiprocesamiento y diseño de memoria NUMA a comienzo de los ‘90. Luego fue adquirida por IBM y estos desarrollos fueron implementados en los procesadores Power.

La arquitectura análoga a la NUMA desarrollada por IBM fue denominada SE (Shared Everything por sus siglas en ingles). En la actualidad esta tecnología se encuentra integrada en los procesadores Power6, los cuales la heredaron de los Power4.

La tecnología desarrollada por Intel se denomina QuickPath Interconnect, incluye un controlador de memoria en el chipset y permite compartir toda la memoria física entre los procesadores de forma transparente para el Sistema Operativo. Cada procesador posee un enlace punto a punto de alta velocidad.

AMD implementó el sistema de acceso a memoria no uniforme (NUMA) que permite la conexión entre procesadores a través de enlaces de alta velocidad denominados Hypertransport Links. En este diseño cada procesador posee su propio controlador de memoria y su propia memoria local. Cuando el procesador accede a la memoria local, la latencia es baja; mientras que si intenta acceder a memoria remota (memoria alocada en otro procesador) la latencia es alta.

Cada uno de los procesadores está conectado entre sí a través de un enlace coherente de Hypertransport de alta velocidad. Cada procesador posee un enlace bidireccional no coherente para dispositivos de entrada-salida y dos enlaces bidireccionales coherentes, que permiten la conexión entre los procesadores.

Los accesos punto a punto permiten acceder a ciertas regiones de memoria de forma más rápida y penaliza el acceso a otras. Por ejemplo en una PC con 2 GB de memoria y dos procesadores, se podría privilegiar el acceso al primer GB para un procesador y el acceso al segundo GB para el otro procesador. Cada procesador tendría su propio controlador de acceso a memoria y ya no sería requerido un bus compartido por ambos procesadores.

Cada CPU en un sistema NUMA pueden acceder a dos tipos de memoria: memoria local y memoria remota. La memoria local es aquella que se encuentra en el mismo nodo que la CPU, que se accede con baja latencia, y la memoria remota se encuentra en otro nodo, en otra CPU. La CPU debería acceder a través del nodo de interconexión para la memoria remota, el cual presentaría una alta latencia.

Matias E. Vara
www.torokernel.org

Organizacion de memoria en arquitecturas 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. Continuaré agregando partes de mi trabajo final al blog.

Organizacion de memoria en arquitecturas multicore

El sistema más común de multiprocesamiento utilizado en la actualidad es el de acceso uniforme a memoria (SMP por sus siglas en inglés).
En esta arquitectura cada procesador puede acceder a cualquier región de memoria independiente uno del otro. El acceso se realiza por un único bus compartido, o sea que cada procesador compite con el resto para escribir o leer. Los accesos se realizan de a uno por vez –es decir- que solo un procesador en un instante dado, puede utilizar al bus. Todos los procesadores son similares y tienen capacidades equivalentes. Todos los procesadores tienen el mismo tiempo de acceso a cualquier posición de memoria. En ambientes SMP el acceso a memoria por el programador es totalmente transparente.

El primer microprocesador de Intel con soporte para multiprocesamiento, fue el Pentium PRO en 1992. El bus utilizado para la interconexión de la CPU con la memoria fue denominado Front Side Bus (FSB desde ahora).

Este es un bus bidireccional muy simple; el costo es bajo y en teoría no hay límite acerca del número de procesadores que se pueden interconectar.

El siguiente paso dado por Intel para incrementar el ancho de banda del FSB fue dividir el bus en dos buses independientes. Sin embargo el ancho de banda se vio reducido debido al tráfico que debía ser reenviado por todo los buses para mantener los caches coherentes.

En 2007 se implementó un bus dedicado por procesador.

En la actualidad esta arquitectura es utilizada por los procesadores Atom, Celeron, Pentium y Core 2 de Intel.

A medida que se incrementaron el número de procesadores en las computadoras modernas también se incrementó el tráfico por el bus, convirtiéndolo en un cuello de botella y degradando la performance de la configuración SMP, fijando un límite entre 16 a 64 procesadores.

El FSB fue fuertemente criticado debido a que éste representa una barrera para las nuevas tecnologías emergentes multicore.

Mientras que una CPU puede ejecutar instrucciones rápidamente, esta velocidad será desperdiciada si no puede hacer la captura y decodificación de las instrucciones tan rápido como las ejecuta. Cuando ocurre esto la CPU debe esperar por lo menos un ciclo más de reloj hasta retornar el valor desde la memoria.

El FSB se comenzó a sustituir a partir de 2001 por dispositivos de acceso punto a punto como Hypertransport de AMD o QuickPath Interconnect de Intel, remplazándose el modelo de acceso uniforme por el modelo de acceso no uniforme.

Matias E. Vara

www.torokernel.org