Las soluciones de exclusión mutua anteriores tienen en común una espera activa que continuamente verifica el estado de un registro. Este tipo de algoritmos se denominan spinlocks; el de Dekker, Peterson, la panadería o cualquiera de las soluciones de exclusión mutua del capítulo anterior son también spinlocks.
Tiene sentido usarlos si se cumple una de las siguientes condiciones:
- La sección crítica es muy breve y la competencia es relativamente baja
-
Los spinlocks se emplean en rutinas críticas de los sistemas operativos y para implementar mecanismos de sincronización sin esperas activas. Tienen en común que sus secciones críticas son breves y que no pueden o no tienen acceso a otros tipos de mecanismos.
- Los procesos se ejecutan en paralelo
-
Mientras unos están en sus spinlocks otros pueden avanzar y salir de la sección crítica. Los spinlocks permiten evitar mayores pérdidas de tiempo ocasionadas por llamadas de sistema o cambios de estado de procesos. No obstante, si hay más procesos concurrentes que CPUs se llega a una situación similar a la de un único procesador: los procesos avanzarán muy lentamente. En estos casos quizás tiene más sentido utilizar construcciones sin esperas activas.
El problema de las soluciones algorítmicas, además de la espera activa, es el número de registros necesarios y la necesidad de iterar en cada uno de ellos. Las primitivas de hardware reducen el impacto eliminando esos requisitos. Es una mejora importante, requieren solo una palabra por cada sección crítica (o lock) y simplifican los algoritmos de sincronización.
Pero no todos los procesadores ofrecen las mismas instrucciones. Para obtener el máximo de eficiencia hay que programar para cada arquitectura (como es habitual en el núcleo de los sistemas operativos). Para facilitar la programación y portabilidad, los compiladores incluyen macros (o intrinsics) que son traducidas a las operaciones que implementan o simulan esas primitivas; son los que usé para los programas de ejemplo[1].
Analizaremos el comportamiento de cada uno de los spinlocks previos. Luego veremos las técnicas y algoritmos que se desarrollaron para reducir sus ineficiencias.
En la siguiente figura se muestran los tiempos de CPU –en segundos– de los algoritmos del capítulo anterior con diferentes procesadores: Intel i5 con cuatro núcleos, Intel Xeon con dos procesadores independientes de ocho núcleos cada uno (16 en total) y Raspberry Pi 2 con ARMv7 de cuatro núcleos.
Cada grupo de barras es una medición diferente. El primero por la izquierda (none) son los tiempos sin ningún mecanismo de exclusión mutua; el segundo los tiempos del algoritmo de la panadería; el tercero (best) es el más eficiente: el incremento de counter se hace directamente con la instrucción atómica get&add. Los siguientes hacia la derecha son los algoritmos con instrucciones de hardware del capítulo anterior swap, get&add, TAS, get&set y CAS respectivamente.
Los algoritmos de exclusión mutua imponen un sobrecoste importante[2] que no es uniforme en todos los procesadores. En Intel i5 y Xeon de 16 núcleos los que mejores tiempo obtienen son get&set y TAS, en Raspberry Pi 2 es casi un empate entre CAS y get&add. Puede observarse también que con CAS el procesador ARM tiene resultados mejores que los más potentes procesadores Intel. Sorprendente, dado que Intel tiene CAS nativo (cmpxhg) pero en ARM se emula con LL/SC.[3]
Las implementaciones anteriores son ineficientes por dos razones:
- Uso y competencia por el procesador
-
Los procesos consumen el 100% CPU verificando el valor de una variable. Si hay más hilos concurrentes que procesadores la mayor parte del tiempo se pierde en el bucle de verificación.
- La presión sobre la memoria caché
-
Estos algoritmos no son escalables. En sistemas con varios procesadores todos los procesos verifican el estado de la misma variable (hot spot), por lo que se generan mensajes extras de sincronización de caché.
Aunque en principio son preferibles los spinlocks escalables, antes veremos técnicas básicas para mejorar el rendimiento de los anteriores. Al final del capítulo estudiaremos los dos algoritmos escalables más importantes: MCS y CLH.
|
Note
|
Spinlocks escalables
Se denominan spinlocks escalables aquellos en que los fallos[4] de memoria caché se mantienen constantes, independientemente de las iteraciones necesarias en la entrada a la sección crítica ([MCS1], [Boyd-Wickizer]). En cada iteración (o spin) los procesos en diferentes procesadores verifican las mismas posiciones de memoria. Cada vez que un proceso cambia el valor se debe invalidar la caché local en cada procesador y propagar el valor actualizado. El problema se agrava por el false sharing, los datos que se modifican en la sección crítica suelen estar en áreas cercanas a las variables de los spinlocks. Cada modificación de esas variables supone un fallo de caché en cada uno de los procesos. El objetivo de los spinlocks escalables es minimizar el sobrecoste inducido por los fallos. La estrategia es que la espera activa de cada proceso se haga sobre posiciones de memoria diferentes. |
Veremos tres técnicas de optimización de spinlocks que se pueden aplicar a cualquier espera activa sobre una variable compartida. Comprobaremos que sus mejoras en eficiencia son considerables.
Se trata de reducir la presión sobre el sistema de coherencia de caché y reducir las llamadas a las relativamente costosas primitivas de sincronización. Antes de ejecutarlas se verifica (o cortocircuita) el valor del registro –mutex en los ejemplos–; si vale 1 ya no hace falta continuar con la instrucción atómica. Cuando se usa con TAS esta estrategia es conocida como TTAS o TATAS; con CAS se llama TCAS.
mutex = 0
def lock():
while mutex or TAS(mutex):
pass mutex = 0
def lock():
local = 0
while mutex or not CAS(mutex, local, 1):
local = 0Las mejoras dependen de la instrucción atómica y las características del sistema de coherencia de caché. En los tiempos de ejecución se observa que la mejora es notable (algo menor en el procesador ARM), tanto en tiempos de CPU como en tiempos de retorno[5].
Si un proceso debe continuar en la espera activa no tiene sentido volver a comparar inmediatamente si la variable cambió de valor. El tiempo es muy breve, la probabilidad de que la sección crítica se haya liberado es muy baja. En un sistema con un único procesador es aún peor, se seguirá consumiendo CPU hasta que finalice el cuanto y no se dejará avanzar a otro proceso.
Lo más lógico es ceder el procesador para dar más tiempo a que el proceso en la sección crítica avance. Una opción es usar la llamada de sistema sched_yield, el núcleo quita de ejecución al proceso y lo mueve a la cola de listos.
mutex = 0
def lock():
while mutex or TAS(mutex):
sched_yield()Como puede observarse en los gráficos, la cesión del procesador produce reducciones importantes de tiempos en todas las arquitecturas (código fuente para TAS, swap y CAS).
La forma de reducir la competencia y evitar el efecto ping-pong de los procesos pasando de listos a ejecución es bloquearlos por un tiempo variable. Este tipo de esperas se denomina exponential backoff, el tiempo depende de las veces que ha fallado la condición durante la espera activa.
|
Note
|
Exponential backoff
Exponential backoff es la técnica usada por redes como Ethernet y WiFi para calcular el tiempo de espera para reenviar una trama después de una colisión. El término backoff se refiere a la espera sin interferir; exponential a que el límite del tiempo de espera se duplica en cada fallo. El tiempo efectivo de espera de cada proceso es un número aleatorio entre 1 y el límite[6]. El siguiente es el código en C usado en los ejemplos, provoca esperas de tiempos que se duplican con cada incremento del valor de failures: #define FAILURES_LIMIT 12
void backoff(int failures) {
struct timespec deadline = {.tv_sec = 0};
unsigned limit;
if (failures > FAILURES_LIMIT) {
limit = 1 << FAILURES_LIMIT;
} else {
limit = 1 << failures;
}
deadline.tv_nsec = 1 + rand() % limit;
clock_nanosleep(CLOCK_REALTIME, 0, &deadline, NULL);
}
En cada iteración fallida del spinlock el proceso incrementa el contador de fallos (failures) y llama a la función backoff. Esta calcula el límite (limit) con desplazamiento de bits. Cada posición desplazada multiplica por dos desplazando el bit 1 hacia la izquierda con un máximo de 12 posiciones, unos 4096 nanosegundos. Luego se calcula el tiempo que esperará con un número aleatorio entre 1 y el límite. |
mutex = 0
def lock():
failures = 0
while mutex or TAS(mutex):
failures += 1
backoff(failures)El problema con el backoff es la elección de la unidad de tiempo y el límite de espera, los valores adecuados dependen de las arquitecturas y casos de uso. Si la espera es muy breve podría producir un efecto ping-pong similar a sched_yield, pero con una sobrecarga mayor del núcleo[7]. Por el contrario, si la unidad es muy grande producirá demoras innecesarias y CPUs inactivas porque todos los procesos están bloqueados.
Sin embargo, la mejora del backoff es general para todos los procesadores probados, tanto en tiempos de CPU como de retorno[8] (en los procesadores Intel la diferencia es importante, en ARM es mínima).
A continuación tres gráficas que representan los tiempos de CPU de los diferentes algoritmos en procesadores distintos. Cabe recordar que el ejemplo que usamos –hilos que solo incrementan un contador compartido– es muy extremo. Aunque la sección crítica es muy breve, lo único que hacen es entrar y salir continuamente sin ejecutar código fuera de ella; implica que la competencia es extremadamente elevada y muy lejos de ser un caso realista. Pero nos sirve para tener una base de comparación.
También hay que tener en cuenta que los ejemplos están programados con los macros atómicos de GCC. Estos no generan el código más eficiente para cada arquitectura. Por ejemplo, para ARM los macros de barreras de memoria siempre generan una barrera completa, aunque se haya especificado una barrera release. La solución es programar en ensamblador de la arquitectura, como se hace en el núcleo de los sistemas operativos. Pero este nivel de optimización supera los objetivos de este libro.
Algunos aspectos que vale la pena destacar:
-
El buen comportamiento y uniformidad de ARM para todas las instrucciones, sobre todo porque se emulan con el LL/SC. En ambas versiones del procesador, ARMv6 y ARMv7 (de Raspberry Pi 1 y 2 respectivamente), CAS es la más eficiente.
-
En las plataformas con varios procesadores sched_yield y backoff producen reducciones de tiempos importantes, incluso cuando el número de procesos concurrentes (cuatro) es igual al número de procesadores. La mejora no se debe solo a la reducción de uso de la CPU; también por las reducción de llamadas a instrucciones de sincronización y a la menor presión sobre el sistema de coherencia de caché[9]. La reducción de la presión al sistema de caché fue el objetivo del estudio de los spinlocks escalables que vemos más adelante.
En los análisis anteriores usamos tiempos de CPU, no el tiempo de retorno. ¿Cuál es más representativo o útil? Es una duda razonable.
El tiempo de CPU es útil para conocer efectivamente cuánto cálculo real requieren[10], pero no nos da información sobre cuánto tarda la ejecución. Por ejemplo, con más procesadores se consume más CPU, aunque el tiempo de retorno se haya reducido.
La duda es mayor cuando se analiza la conveniencia de usar yield y backoff. Sabemos que lo más probable es que el consumo de ciclos de CPU en la espera activa se reducirá, pero también que aumentará la carga del núcleo por los cambios de contexto. Sin tener los datos de tiempos de retorno no podemos estar seguros que realmente se ejecuten más rápido.
Intento evitar el exceso de gráficos, pero valía la pena mostrar estos tiempos. En los siguientes se puede observar el tiempo de retorno (medido en tiempo de reloj) de los algoritmos anteriores.
Aún en arquitecturas tan diferentes, la cesión del procesador representa una reducción importante de tiempo de CPU y de retorno. La mayor diferencia a favor del backoff ocurre en el Xeon de 16 núcleos. Este tiene más núcleos que procesos concurrentes, por lo que un yield solo hace que un proceso abandone el procesador para que el scheduler lo lleve inmediatamente a ejecución en otro núcleo (depende de los algoritmos de afinidad de CPU). También pudo ocurrir que la unidad de tiempo elegida (un nanosegundo) haya sido más adecuada para el Xeon que para el ARM, a pesar de ello se ganan unos pocos milisegundos.
|
Tip
|
Cesión del procesador
Las esperas activas ya son suficientemente malas si no son imprescindibles. A menos que se trate de rutinas críticas del núcleo o un sistema de tiempo real medido y calibrado casi al nivel de instrucciones, es conveniente usar yield o backoff exponencial en los spinlocks con mucha competencia. Esta regla es válida aún cuando parezca que sobran procesadores. |
En aplicaciones reales, la mayoría de las operaciones sobre la memoria son lecturas. En estos casos lo importante es que estas sean consistentes. En los ejemplos –un único contador entero– no existe el problema de lectura inconsistente: las palabras de 32 bits son registros atómicos en las arquitecturas modernas de 32 o más bits, si un proceso lee la variable siempre obtendrá el último valor escrito. Para estructuras de mayor tamaño –o para acceder a ficheros o dispositivos externos– hay que imponer restricciones para que la memoria no sea modificada cuando otros procesos la están leyendo.
La solución de exclusión mutua no es la más adecuada, la serialización de los accesos de solo lectura provoca esperas innecesarias. Una de las relajaciones más importantes a las condiciones de la exclusión mutua es que se permita más de un lector en la sección crítica. Estos algoritmos son conocidos como lectores-escritores (reader-writer).
Las condiciones que deben cumplir son:
-
Se permite más de un lector en la sección crítica.
-
Mientras haya un lector en la sección crítica no puede entrar ningún escritor.
-
Los lectores no pueden entrar si hay un escritor en la sección crítica.
-
Solo puede haber un escritor en la sección crítica.
Así como la exclusión mutua tiene un protocolo de entrada (lock) y otro de salida (unlock), los de lectores-escritores necesitan distinguir entre ellos con protocolos diferenciados: reader_lock, writer_lock, reader_unlock y writer_unlock.
El siguiente algoritmo es relativamente simple (código en C), está implementado con las instrucciones CAS y get&add. Se usa una variable global entera mutex como en los algoritmos anteriores, pero el bit más significativo se reserva para indicar si un escritor está en la sección crítica. Los bits restantes se usan para contar el número de lectores, para un entero de 32 bits se permiten hasta 231 lectores[11].
Los lectores primero esperan a que no haya ningún escritor, luego incrementan el número de lectores e intentan hacer el CAS. Si fue posible entran a la sección crítica, caso contrario vuelven a intentar desde el inicio del bucle.
rw_lock = 0 (1)
def reader_lock():
while True:
while rw_lock & 0x80000000: (2)
pass
old = rw_lock & 0x7fffffff (3)
new = old + 1 (4)
if CAS(rw_lock, old, new): (5)
return
def reader_unlock():
getAndAdd(rw_lock, -1) (6)-
La variable global mutex, en el ejemplo es de 32 bits.
-
Verifica si el bit más significativo es 1, si es así hay un escritor e itera hasta que sea 0.
-
No hay escritores, obtiene el número de lectores.
-
Incrementa el número de lectores.
-
Si rw_lock no fue modificado, CAS almacenará el nuevo valor. Si rw_lock fue modificado volverá al inicio del while y lo intentará nuevamente.
-
Decrementa atómicamente el número de lectores.
Los escritores primero esperan a que no haya otro escritor en la sección crítica, luego ponen el bit más significativo en 1 e intentan el intercambio con CAS. Si no fue posible vuelven a intentarlo desde el principio. Si fue satisfactorio esperan a que no queden lectores para entrar a la sección crítica.
def writer_lock():
while True:
while rw_lock & 0x80000000: (1)
pass
old = rw_lock & 0x7fffffff (2)
new = old | 0x80000000 (3)
if CAS(rw_lock, old, new): (4)
while rw_lock & 0x7fffffff: (5)
pass
return
def writer_unlock():
rw_lock = 0 (6)-
Verifica el bit más significativo e itera hasta que no haya ningún escritor.
-
Obtiene el número de lectores actuales.
-
Calcula el nuevo valor, será el número de lectores con el bit más significativo en 1 indicando que hay un escritor.
-
Si el valor tomado de rw_lock no cambió se almacena el nuevo, caso contrario vuelve al principio del while para reintentar.
-
Espera que salgan todos los lectores, los siguientes ya no podrán entrar porque el bit más significativo está en 1.
-
Para salir solo debe poner rw_lock en cero ya que no quedan lectores ni escritores en la sección crítica.
Una característica importante de los algoritmos de lectores-escritores es la prioridad de unos y otros. Si lo que interesa es rendimiento (throughput) y lecturas muy rápidas, es mejor dar prioridad a los lectores. Si interesa que las actualizaciones sean rápidas y acceder a los últimos valores lo antes posible, es mejor usar algoritmos que den prioridad a los escritores. El problema es el riesgo de inanición de los de menor prioridad, aunque hay algoritmos que aseguran equidad los más comunes dan prioridad a uno de ellos ([MCS2]).
Queda a ejercicio del lector encontrar si este algoritmo da prioridad a los lectores o escritores[12].
Los algoritmos con instrucciones de hardware anteriores no cumplen uno de los requisitos deseables de la exclusión mutua, asegurar espera limitada. Aunque estadísticamente no se pueden producir esperas infinitas[13], presenta problemas de equidad: unos procesos pueden retrasarse más que otros. Por ejemplo, en 2008 se detectó este efecto en el núcleo de Linux ([Corbet1], [Corbet2]):
En un Opteron con 8 núcleos (2 procesadores), la injusticia de los spinlocks es extremadamente notable, con un test en espacio de usuario se obtienen diferencias de tiempo de CPU de hasta 2 veces por hilo, y mientras algunos hilos sufren inanición a otros se les garantiza el lock hasta 1 000 000 (!) de veces.
Para evitarlo hay que usar algoritmos que aseguran que los procesos entran a la sección crítica en el orden que llegaron (FIFO).
Una solución sencilla la hemos descubierto al introducir la instrucción get&add. La idea es la misma que el algoritmo de la panadería solo que la obtención del número se hace con esta operación atómica. Así se evita que los procesos puedan seleccionar el mismo número.
Se usan dos variables: la secuencia creciente de números y el turno. Un proceso obtiene su número y luego espera por su turno. Cuando sale de la sección crítica incrementa el turno para que entre el siguiente proceso.
El código en C de este algoritmo es idéntico al anterior de get&add, para hacerlo más eficiente se unificaron ambas variables en una única estructura de 32 bits: 16 bits para turn y number respectivamente. Con ejecuciones extensas número y turno llegarán hasta 216 y rotarán.
struct tickets {
uint16_t turn;
uint16_t number;
};Con la base el algoritmo ticket-lock se puede implementar un algoritmo de lectores-escritores equitativo. Se necesitan dos registros diferentes para los turnos, uno para lectores y otro para escritores. El esquema de la estructura es la siguiente:
En C se define de la siguiente forma:
struct ticket_rw {
uint16_t number;
union {
uint32_t combined;
struct {
uint16_t writer_turn;
uint16_t reader_turn;
};
};
};El campo number es similar al algoritmo ticket-lock: writer_turn y reader_turn indicarán los turnos para escritores y lectores respectivamente. Ambas variables serán incrementadas para permitir que entren lectores o escritores de forma equitativa. El orden en que se haga la suma dejará entrar a unos o a otros:
-
Un lector dará paso a otros lectores en cuanto haya entrado a la sección crítica, permitirá la entrada de escritores cuando haya salido.
-
Un escritor solo dará el turno a otros lectores o escritores cuando salga de la sección crítica.
Se define el campo combined que incluye a ambos turnos, así se puede asignar a ambos simultáneamente en una única operación atómica. Para el desarrollo del algoritmo suponemos una variable global rw_local del tipo o clase ticket_rw.
def writer_lock():
number = getAndAdd(rw_lock.number, 1) (1)
while number != rw_lock.writer_turn: (2)
pass-
El escritor obtiene su número.
-
Espera a que sea su turno.
def writer_unlock():
tmp.writer_turn = rw_lock.writer_turn + 1 (1)
tmp.reader_turn = rw_lock.reader_turn + 1 (1)
rw_lock.combined = tmp.combined (2)-
Incrementa el turno para lectores y escritores en una variable temporal.
-
Asigna atómicamente ambos turnos. Cuando el escritor sale de la sección crítica debe poder entrar el siguiente lector o escritor, por lo tanto, incrementa ambas variables.
def reader_lock:
number = getAndAdd(rw_lock.number, 1) (1)
while number != rw_lock.reader_turn: (2)
pass
rw_lock.reader_turn++ (3)-
El lector obtiene su número.
-
Espera su turno.
-
Cuando entró incrementa el turno de lectores para que pueda entrar el siguiente lector. Este hará lo mismo, así puede haber varios lectores en la sección crítica[14].
def reader_unlock:
getAndAdd(rw_lock.writer_turn) (1)-
El lector al salir incrementa el turno de escritor por si el siguiente es uno de ellos. No hace falta incrementar el turno de lectores, ya lo hizo al entrar a la sección crítica.
El algoritmo es equitativo, los procesos entran en el orden en que obtuvieron su número independientemente de que sean lectores o escritores. Los lectores incrementan el turno de lectores inmediatamente, si el siguiente proceso es un escritor ningún lector podrá entrar. Estos esperarán hasta que entre el escritor que tiene el turno y a su salida incremente el turno dando oportunidad de entrada a un lector o escritor.
Es deseable que los spinlocks sean escalables: el número de invalidaciones de caché (generan fallos de caché, también llamados cache bouncing o cache thrashing) debe ser constante, independientemente del número de procesos o procesadores involucrados. La forma de lograrlo es que cada proceso itere sobre posiciones de memoria diferentes.
La solución es que cada proceso tenga su propia posición en un array de locks inicializados a cero; salvo la primera posición que se inicializará con 1 para que el primer proceso pueda entrar. La posición del último proceso en espera está indicada por la variable tail (también inicializada a cero). Cada proceso obtiene su posición con la operación get&add sobre tail.
La variable que indica si un proceso puede entrar es booleana, usa un único byte. Para evitar el false sharing hay que separar las posiciones por varios bytes. Para ello se define una estructura de mayor tamaño, con un campo de un byte para la verificación. La alternativa equivalente es definir un array con posiciones que no se usarán, solo servirán de relleno (padding).
La siguiente figura es un esquema general del funcionamiento. Las zonas grises del array son las variables booleanas de verificación en el spinlock de cada proceso. Las zonas blancas son el relleno o padding. El proceso en verde está en la sección crítica, los amarillos en espera activa en su posición del array.
Thread 0 ya entró en la sección crítica, Thread 1 y Thread 2 esperan verificando el estado de sus respectivas posiciones en el array, tail apunta a la siguiente posición. Cuando Thread 0 salga de la sección crítica cambiará el estado de flag[1] y podrá entrar Thread 1.
La inicialización (en C) es la siguiente:
#define PADDING 32
char flag[NUM_THREADS * PADDING];
int tail;
...
flag[0] = 1;Si hay cuatro hilos máximo la dimensión del array será 4 * 32 (128 bytes en total). El cálculo de la posición real (my_index) requiere de una multiplicación y módulo. El algoritmo simplificado (código completo en C) es el siguiente:
def lock(my_index):
slot = getAndAdd(tail, 1)
my_index = (slot % NUM_THREADS) * PADDING
while not flag[my_index]:
pass
flag[my_index] = 1
def unlock(my_index):
next = (my_index + PADDING) % SIZE
flag[next] = 1;Este algoritmo también es equitativo, los procesos entran en orden FIFO. Solo requiere la instrucción atómica get&add. Según la bibliografía especializada ([Herlihy12]), se evita el false sharing y por lo tanto es más eficiente que ticket-lock. Analizaremos cuánto hay de verdad más adelante.
Una estrategia para disminuir la presión sobre la caché es hacer que las esperas activas se hagan sobre una variable local de cada proceso. Así se asegura que no se comparten líneas de caché. Tampoco habrá penalización si la variable del spinlock está próxima a otras variables locales, pueden compartir las misma líneas de cache pero no están compartidas con los otros procesos.
El algoritmo de cola MCS[15] fue descubierto[16] en 1991 por John M. Mellor-Crummey y Michael L. Scott ([MCS1]). Se considera uno de los algoritmos más importantes e influyentes de exclusión mutua, sus autores recibieron el premio Edsger W. Dijkstra Prize in Distributed Computing de 2006.
Algoritmos derivados, conocidos como colas sin exclusión mutua (lock-free queues), son muy usados en librerías runtime y maquinas virtuales, como en los monitores de la máquina virtual de Java y en las librerías java.util.concurrent ([Lea]).
Cada proceso hace la espera activa en su propia posición de memoria. En lugar de un array se usa una lista ordenada FIFO. Cada nodo pertenece a un proceso que espera para entrar a la sección crítica. Para implementar MCS se requieren las operaciones atómicas swap y CAS. Es rápido, equitativo (FIFO) y no necesita asignación previa de memoria (como en array-lock). Los hilos deben pasar como argumento la dirección de un nodo, preferiblemente local para evitar el false sharing.
Cada nodo tiene la siguiente estructura:
struct mcs_spinlock {
struct mcs_spinlock *next;
unsigned char locked;
};El campo next es un puntero al nodo del siguiente proceso en la cola de espera. El campo locked es una variable booleana, será 1 si el proceso debe esperar, o 0 cuando puede entrar a la sección crítica. Cada proceso verifica su propia variable, el que sale de la sección crítica actualiza el campo del siguiente en la cola.
En la figura anterior se representa al hilo Thread 0 que ya salió de su sección crítica; Thread 1 está en ella; el siguiente en la cola es Thread 2; el último es Thread 3. Cada uno de los procesos en espera activa verifica el campo locked de su nodo local. La variable tail apunta al último proceso en la cola, si no hay ningún proceso será NULL.
El siguiente es el código en C simplificado del algoritmo[17]:
|
Note
|
Disculpas por las largas explicaciones en las leyendas, no tenía sentido hacerlo de otra manera. Este algoritmo, y sobre todo el siguiente, son breves pero complejos y abstractos. No hay otra manera de entenderlos, hay que leer y estudiar el código con paciencia y concentración. |
void lock(mcs_spinlock *node) {
mcs_spinlock *predecessor;
node->next = NULL;
node->locked = 1; (1)
predecessor = node; (2)
predecessor = SWAP(&tail, node); (2)
if (predecessor != NULL) { (3)
predecessor->next = node; (3)
while (node->locked); (4)
}
node->locked = 0;
}-
Inicialización del nodo, locked se pone en verdadero.
-
Preparación para el swap, predeccesor apunta inicialmente al nodo actual. Cuando se haga el intercambio, si había un proceso esperando o en la sección crítica predecessor apuntará al nodo de ese proceso, caso contrario será NULL.
-
Si hay otro proceso hará que su campo next apunte al nodo actual.
-
Espera activa hasta que el predecesor cambie el estado de locked a falso.
void unlock(mcs_spinlock *node) {
mcs_spinlock *last;
if (! node->next) {
last = node; (1)
if ( CAS(&tail, &last, NULL) ) { (1)
return; (2)
} else {
while (! node->next); (3)
}
}
node->next->locked = 0; (4)
}-
Si next del proceso actual es NULL entonces podría ser el último de la cola; prepara last para hacer el CAS.
-
Se pudo hacer el intercambio, significa que no hay competencia, retorna sin hacer nada más; el puntero tail valdrá NULL.
-
Si no se pudo hacer el intercambio, hay un proceso que está ejecutando el lock pero todavía no ejecutó la instrucción predecessor->next = node. Se espera hasta que lo haga.
-
Se ejecuta solo si había un proceso esperando, en este caso asigna 0 al campo locked de su nodo para que pueda continuar.
|
Note
|
Barreras de memoria
En el código C de algunos de los algoritmos se usa Si algunos caminos del protocolo de salida (unlock) no ejecutan ninguna instrucción atómica no habrá barreras de memoria. Puede ocurrir que instrucciones de la sección crítica se ejecuten después de haber superado la salida. Durante las pruebas y validación del código comprobé que en algunos procesadores se manifestaba esta condición de carrera, en particular con el ARMv7 de Raspberry Pi 2. Preferí mostrar la versión simplificada en estas páginas, pero la versión completa y correcta para todas las arquitecturas en el listado del código fuente. |
Una par de años después de la publicación del algoritmo de MCS, dos grupos descubrieron el CLH de forma independiente: Travis Craig de la Universidad de Washington ([Craig]) y Anders Landin y Eric Hagersten del Instituto Sueco de Ciencias de la Computación ([CLH]).
Como el MCS, este algoritmo también está basado en una cola y es equitativo, pero los punteros son en sentido inverso. Apuntan al proceso con el turno anterior, no al siguiente.
El algoritmo es breve pero más complejo. Tiene más niveles de indirección[18] y, a diferencia de MCS, los procesos verifican el estado de una variable en el nodo predecesor. Sus ventajas son:
-
Como MCS, la espera activa se hace sobre variables independientes, aunque no necesariamente locales a cada proceso.
-
Solo requiere la instrucción atómica get&set.
-
La memoria de los nodos puede ser gestionada independientemente. Los procesos pueden proveer un nodo a una dirección estática, o puede gestionarlo el propio módulo de spinlocks. [19].
-
Puede ser adaptado a sistemas sin coherencia de caché.
La estructura de cada nodo es similar a MCS:
struct clh_node {
unsigned char locked;
struct clh_node *prev;
};A diferencia de MCS, se debe comenzar con un nodo inicializado sin propietario y la variable tail apuntando a dicho nodo.
Por ejemplo:
struct clh_node lock_node; (1)
struct clh_node *tail = &lock_node; (2)-
El nodo sin propietario.
-
tail apunta inicialmente a ese nodo.
La versión simplificada del algoritmo en C es la siguiente:
void lock(clh_node *node) {
clh_node *predecessor;
node->locked = 1; (1)
node->prev = getAndSet(&tail, node); (2)
predecessor = node->prev; (2)
while (predecessor->locked); (3)
}-
Se almacena al nodo actual como locked, este campo será verificado por el siguiente proceso que pretenda entrar a la sección crítica.
-
Se obtiene la dirección de tail, indica cuál es el predecesor del proceso actual y se almacena en tail la dirección del nodo actual. El valor que tenía tail se almacena en el campo prev (es el puntero al nodo del proceso anterior) y se hace una copia en predecessor.
-
Se hace la espera activa sobre el campo locked del nodo anterior, cuando sea falso el proceso actual podrá continuar.
void unlock(clh_node **node) {
clh_node *pred;
clh_node *tmp;
pred = (*node)->prev; (1)
tmp = *node; (2)
*node = pred; (3)
tmp->locked = 0; (4)
}-
Se hace una copia del puntero al nodo del proceso anterior (sobre el que este proceso iteró en el lock).
-
Se hace una copia temporal para no perder la dirección del nodo actual.
-
El puntero que apuntaba al nodo del proceso actual ahora apuntará al del predecesor. Se podría liberar esa memoria pero en estos ejemplos la reciclamos para no hacer malloc/free en cada lock y unlock.
-
Se almacena falso en el campo locked del nodo actual, el proceso que está a continuación en la cola podrá entrar a la sección crítica.
Ticket-lock es un algoritmo equitativo muy utilizado pero no es escalable, los procesos verifican la misma posición de memoria. La respuesta es usar un array, además con posiciones de relleno (padding) para evitar el false sharing. Algunos autores proponen que el relleno complete el tamaño de una palabra (cuatro u ocho bytes), otros que sean de mayor longitud para que no compartan líneas de caché.
¿Cuál es la separación apropiada?, depende de la arquitectura, es difícil saber a priori cuál es la mejor para cada una. Depende de muchos factores, el tipo de instrucción, los canales de comunicación para sincronización, o el mecanismo de monitorización de los registros de LL/SC (en las arquitecturas que lo implementan).
Para tomar una decisión informada hice pruebas con diferentes procesadores y tamaños de relleno. La siguiente figura muestra los tiempos de CPU de cada procesador para diferentes tamaños. El eje horizontal muestra la separación entre las diferentes posiciones del array (desde 2 a 256 bytes) y el vertical el tiempo de CPU en segundos.
En Intel Xeon e i5 los tiempos son constantes, en Raspberry Pi 2 se produce un descenso importante a los 16 y 32 bytes. Para hacer una comparación razonable elegí un relleno de 32 bytes.
En las dos imágenes a continuación se muestran los tiempos comparados de CPU y tiempo de reloj para los algoritmos ticket-lock, array-lock, MCS y CLH.
En las arquitecturas modernas no hay demasiada diferencia entre ticket-lock y array-lock, de hecho en Intel Xeon esta última es peor. Además, array-lock necesita más espacio –una palabra más el relleno por cada proceso concurrente– que hay que reservar desde el principio (como en el algoritmo de la panadería), mientras que ticket-lock solo requiere una palabra.
En general MCS y CLH son los más eficientes en tiempos de CPU, pero la diferencia no es considerable. Como array-lock, también requieren más espacio: un nodo por cada proceso activo, aunque la asignación puede ser dinámica y solo cuando se necesita. Esta es una de las razones por la que ticket-lock sigue siendo el spinlock preferido en el núcleo de Linux.
Muchos artículos afirman que CLH es mejor que MCS, aunque en los procesadores probados la diferencia es despreciable y en algunos casos es a peor[20]. La ventaja de CLH es la mayor flexibilidad para gestionar la memoria, puede hacerse en las propias funciones lock y unlock de forma transparente a los procesos.
Comenzamos con las optimizaciones básicas a spinlocks construidos con las instrucciones de hardware de capítulo anterior. La primera fue agregar un control local a la variable compartida para evitar consumir ciclos con instrucciones más complejas. Esta solución no requiere nada especial ni cambia el estado del proceso.
A continuación vimos dos optimizaciones que sí cambian el estado del proceso, son adecuadas cuando se puede permitir que el proceso en el spinlock abandone el procesador[21]. Ambas soluciones mejoran mucho la eficiencia, tanto en tiempos de CPU como de retorno.
Luego vimos la implementación de lectores-escritores con spinlocks. Este mecanismo es muy común, lo volveremos a ver implementado con otras técnicas en capítulos posteriores. Su utilidad se basa en que las actualizaciones son menos frecuentes que las lecturas, interesa relajar las restricciones de exclusión mutua para permitir mayor concurrencia.
A continuación se introdujo el tema de los spinlocks equitativos (fair). Estos aseguran que los procesos entran a la sección crítica en el orden que llegan (FIFO), se puede demostrar formalmente que no se produce inanición (starvation).
El primer algoritmo fue ticket-lock, basado en las mismas ideas del algoritmo de la panadería. Cada proceso obtiene un número único y creciente que sirve para sincronizar la entrada a la sección crítica mediante un turno que también crece monótonamente. A continuación extendimos este algoritmo para lectores-escritores, que además tiene la propiedad de ser equitativo.
Finalmente, vimos dos algoritmos fundamentales de concurrencia que implementan colas sin exclusión mutua (lock-free queues), MCS y CLH. Ambos son equitativos y escalables, no incrementan la presión sobre el sistema de caché cuando se incrementa el número de procesos. Estos algoritmos funcionan sobre sistemas de caché coherentes, pero hay modificaciones que permiten que sean usados en sistemas no coherentes y en arquitecturas NUMA.
A partir del siguiente capítulo veremos construcciones y abstracciones de más alto nivel. Sus objetivos son evitar las esperas activas y facilitar la programación de mecanismos de sincronización más sofisticados que la exclusión mutua.