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
