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
