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.
www.torokernel.org
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. VaraImpacto 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
www.torokernel.org
4 comments:
Matias, quiero decirte un par de cosas si me das el permiso.
1ro: Me alegra mucho entrar a tu blog depsues d evarios años y que la magia siga intacta, veo que seguiste con el proyecto, y ampliaste tus conocimientos enormemente. Ojala sigas asi.
2do: Desde la primera vez que programe en Pascal, fue amor a primera vista, y rompiendome la cabeza pensanod en como seria un SO en Pascal, llegue a Toro.
3ro: No puedo cree que entro a tu blog y leo tus articulos desde que estaba e la Secundaria por alla por el 2006... Han pasado 5 años y hoy en dia me encuentro estudiando en la UTN, en clase de Sistema Operativos me puse a discutir que se podian hacer SO que no fueran en C/C++ (Ademas de embeber codigo en ASM) y como prueba de ello mañana voy a ir a la clase con mi Notebook, a mostrarle orgulloso lo que vos hiciste con Toro.
Ademas de que para la materia me voy a poner a estudiar tu creacion, otra vez, solo que esta vez con motivos facultativos y no como hace 5 años por mera curiosidad de lo increible de tu proyecto.
Un millon 800 mil felicitaciones...
La verdad que si algun dia te cruzara en algun evento de Software libre no podria mas que estrechar tu mano, agradecerte y felicitarte por tus grandes aportes y trabajos cientificos con el proyecto Toro.
Felicitaciones y gracias por compartirlo con el mundo.
Saludos.
Atte. Jorge Abreu.
http://www.jorge1987.com.ar
Hola, me alegro mucho que sigas el proyecto. Por otro lado si vas a mostrar a TORO funcionando te recomiendo que uses la version 1.1.3 debido a que es "mas vistosa". Conseguite un disket y una pentium, y correlo allí, que va ser más divertido de observar que las version 0.xx.
Saludos!
Matias, hoy tuvimos clase de sistemas Virtualizados y metodos de VIrtualizacion, ais que no perdi oportunidad, y a nuestro profesor lo deje impresionado con tu trabajo en Pascal+ASM. Un simple VirtualBox configurado para funcionar como un Linux con Kernel 2.2 y funciona perfecto...
En este finde voy a estar echandole un vistaso al codigo y jugando un poco con el Torito de La Plata, jaja.
Un Abrazo Matias!
Saludos.
Me alegro, actualmente me encuentro parchendo unas cosas para compilar ToroOS 1.1.3 sobre ubuntu10. Cuando lo tenga terminado subire la imagen de la maquina virtual para que cualquiera compile y teste ToroOS rápidamente. Bajar todos los paquetes es muy decepcionante ... ;)
Post a Comment