Operaciones atómicas en

Acerca de Operaciones atómicas

Una sola instrucción puede parecer una acción indivisible cuando no lo es en absoluto. Tomemos como ejemplo sumar cinco a un valor en memoria:

add qword [rel counter], 5

Por debajo, el procesador no tiene forma de sumar directamente a memoria. Descompone esta única instrucción en tres pasos más pequeños, llamados microoperaciones:

1. leer el valor actual de la memoria;
2. modificar este valor en un registro, sumándole cinco;
3. escribir el resultado de vuelta.

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

Este es un patrón común llamado leer-modificar-escribir (RMW).

Nota que la lectura (o carga) y la escritura (o almacenamiento) son eventos separados, así que hay una ventana de tiempo entre ellos. Por lo general no lo notamos porque en un solo núcleo cada instrucción garantiza producir su efecto por completo antes que la siguiente. Esa ventana es, por lo tanto, invisible, y add se comporta como una sola unidad.

Sin embargo, las CPU modernas rara vez tienen un solo núcleo, y las aplicaciones suelen ejecutarse en muchos núcleos a la vez, sin secuenciación entre ellos. Con varios núcleos ejecutándose en el mismo instante, otro núcleo puede leer o escribir counter dentro de la ventana, después de la carga de este núcleo y antes de su almacenamiento. Dos hilos cargan el mismo valor antiguo, cada uno suma cinco y cada uno almacena su resultado. Ocurrieron dos sumas, pero el valor solo avanzó cinco. Una actualización se perdió en silencio.

Esto es una carrera de datos, y es un problema común en el código multihilo.

No todos los valores quedan expuestos de esta manera. Cada hilo tiene sus propios registros y su propia pila, así que un valor que está en un registro, o una variable local en la pila de un hilo, es exclusivo de ese hilo y no puede tener una carrera. Solo la memoria que los hilos comparten, como counter arriba, necesita protección.

x86-64 ofrece un conjunto de instrucciones para resolver este problema, haciendo que una instrucción sea indivisible. Se comporta como una sola unidad no solo para el núcleo que la procesa, sino también para todos los demás núcleos. Una operación que se mantiene unida, que ningún otro núcleo puede dividir, se llama atómica.

Intercambio atómico

La instrucción xchg intercambia dos operandos. El operando de destino pasa a ser igual al valor anterior del operando fuente, mientras que el operando fuente pasa a ser igual al valor anterior del operando de destino. Conceptualmente, se puede pensar en ella como dos instrucciones mov que ocurren a la vez.

Como de costumbre, se puede usar con dos operandos de registro o con un operando de memoria y uno de registro:

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

Cuando se usa con un operando de memoria, xchg es siempre atómica. El procesador afirma un bloqueo sobre la ubicación durante toda la operación, el mismo mecanismo que usa el prefijo lock para otras instrucciones, descrito a continuación.

El prefijo lock

La forma más común de hacer que una instrucción sea atómica en x86-64 es añadir el prefijo lock. Fusiona la lectura, la modificación y la escritura en un solo paso indivisible. Esto significa que el núcleo mantiene la memoria en exclusiva durante todo el proceso, así que ningún otro núcleo puede leer ni escribir esa ubicación en el medio.

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

lock solo funciona cuando el destino es memoria, y solo en instrucciones que leen, modifican y escriben esa memoria:

1. operaciones aritméticas, como add, sub, inc, dec, neg;
2. operaciones bit a bit, como and, or, xor, not;
3. las operaciones de bits bts, btr, btc;
4. algunas otras instrucciones dedicadas, como xadd y cmpxchg, descritas más abajo.

En cualquier otra instrucción, como un mov simple, el prefijo es inválido y el procesador genera una falla por código de operación inválido. Una carga sola o un almacenamiento solo no necesitan prefijo: un acceso alineado naturalmente ya es atómico por sí mismo.

Operaciones atómicas de bits

Entre las instrucciones bloqueables, las pruebas de bits se combinan de forma natural con el spinlock del final de este documento. Cada una de bts, btr y btc copia un bit elegido en la bandera de acarreo y luego lo establece, lo borra o lo invierte. Con el prefijo lock, eso se convierte en un leer-modificar-escribir de un bit: el bit se cambia atómicamente, y CF informa cuál era antes.

    lock bts qword [rdi], 0 ; set bit 0; CF = the bit's previous value
    setc al                 ; al = 1 when the bit was already set

Un establecimiento que encuentra el bit ya establecido significa que otro hilo lo reclamó primero. Esta es una versión de un solo bit del reclamo de bandera que xchg hace para una palabra completa.

Intercambio y suma

Un lock add simple actualiza la memoria pero descarta el valor antiguo. A menudo el valor antiguo es exactamente lo que se quiere, por ejemplo, para dar a cada hilo un número de ticket distinto.

La instrucción xadd (la x de exchange, intercambio) devuelve el valor anterior mientras suma. Escribe la suma en el destino y deja el valor original del destino en el registro fuente.

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

Con el prefijo lock, esto es un fetch-and-add atómico. Ejecutado por muchos hilos sobre el mismo contador, cada llamada devuelve un valor antiguo distinto.

Como con lock add, el contador termina en el número exacto de llamadas. Sin embargo, a diferencia de lock add, también se devuelve cada valor intermedio, uno a cada llamador.

La fuente puede ser cualquier registro de propósito general, y el ancho del operando va de un byte a un quadword. Sumar un valor negativo convierte la misma instrucción en un fetch-and-subtract.

Comparar e intercambiar

xadd suma y xchg sobrescribe, pero ninguna de las dos puede hacer que el valor nuevo dependa del actual y aplicarlo solo si nada cambió por debajo. Esa actualización condicional es lo que proporciona cmpxchg, el comparar e intercambiar, y es la más general de estas primitivas.

cmpxchg dest, src usa rax como acumulador implícito y lo compara con dest:

• Si dest == rax, dest = src y ZF = 1.
• Si dest != rax, rax = dest y ZF = 0.

El acumulador sigue el tamaño del operando: al para un byte, luego ax, eax y rax para las formas más anchas.

Nota que dest solo se actualiza cuando es igual al valor esperado, previamente cargado en rax. Esta igualdad asegura que dest todavía contiene el valor a partir del cual se calculó el nuevo, así que nunca se aplica una actualización basada en una lectura obsoleta. Eso convierte a cmpxchg en el bloque de construcción de una actualización atómica, también conocida como compare-and-swap (CAS):

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

Este bucle de reintento es el corazón de las actualizaciones sin bloqueo. La ventana entre la lectura y el comparar e intercambiar es exactamente cuando otro hilo podría intervenir, y cmpxchg lo detecta al negarse a almacenar un valor calculado a partir de una lectura obsoleta.

Vale la pena conocer una sutileza. cmpxchg verifica que el valor sea igual al que se leyó, no que la ubicación nunca haya sido tocada. Si otro hilo mueve el valor de A a B y de vuelta a A dentro de la ventana, el intercambio de todos modos tiene éxito, aunque el mundo haya cambiado por debajo.

Para un contador simple eso es inofensivo, ya que un conteo que coincide sirve igual de bien. Para una dirección de memoria en la cabeza de una lista sin bloqueo, no lo es, porque la misma dirección puede ahora llevar a otro lugar. Este es el problema ABA.

La solución habitual a este problema empareja el valor con algún «sello», por ejemplo un contador que solo crece. Como el sello solo avanza, un sello que coincide demuestra que la ubicación no fue tocada en el medio, no simplemente que se ve igual.

Sin embargo, para que esto funcione en un entorno multihilo, tanto la dirección de memoria como su sello deben actualizarse juntos. Como una dirección de memoria es un quadword completo en x86-64, un cmpxchg no alcanza para actualizarla y también otro valor al mismo tiempo.

Existe una instrucción de doble ancho llamada cmpxchg16b que es semánticamente igual a cmpxchg pero opera sobre 16 bytes a la vez y se puede usar en esa situación. No tiene un operando fuente; en su lugar usa rcx:rbx como valor de reemplazo. Su único operando es una ubicación de memoria alineada a 16 bytes. Esta instrucción también usa rdx:rax como acumulador, en lugar de solo rax.

Ordenamiento de memoria

Todas las operaciones hasta ahora han tocado una sola ubicación. Cuando los hilos se coordinan a través de más de una ubicación, aparece una nueva pregunta: en qué orden las escrituras de un hilo se vuelven visibles para otro. Las reglas que responden esta pregunta son el ordenamiento de memoria del procesador.

El concepto de código sin ramas introdujo la idea de que un núcleo moderno no avanza trabajosamente por las instrucciones una por una. Mantiene muchas en vuelo a la vez y se adelanta donde puede. Esto significa que una escritura puede volverse visible para los otros núcleos más tarde de lo que sugiere el programa, mientras que las instrucciones posteriores ya se adelantaron.

x86-64 mantiene un ordenamiento de memoria fuerte entre cargas y almacenamientos ordinarios, de modo que en cada núcleo:

1. una carga nunca se reordena después de una carga posterior;
2. un almacenamiento nunca se reordena después de un almacenamiento posterior;
3. una carga nunca se reordena después de un almacenamiento posterior.

El único reordenamiento posible es que un almacenamiento parezca completarse después de una carga posterior de una dirección diferente.

Una instrucción con prefijo lock, o un xchg con un operando de memoria, es una barrera completa: nada parece moverse a través de ella en ninguna dirección. Por eso son suficientes para garantizar el ordenamiento completo en la mayoría de las situaciones.

El mecanismo detrás del único reordenamiento que sobrevive es el búfer de almacenamiento. Para seguir adelante, un núcleo estaciona cada almacenamiento en ese búfer y deja que las instrucciones posteriores continúen antes de que el almacenamiento llegue a la memoria que los otros núcleos pueden ver. Una escritura seguida por una lectura de una ubicación diferente puede por lo tanto aparecer fuera de orden: la escritura puede seguir en el búfer mientras la lectura posterior avanza. Este modelo, en el que todo está ordenado excepto esa brecha de escritura y luego lectura, se llama orden de almacenamiento total.

Esa única brecha alcanza para romper un handshake de almacenar y luego comprobar. Si dos hilos escriben cada uno su propia bandera y luego leen la del otro, ambas lecturas pueden volver sin establecer, porque ningún almacenamiento ha salido aún de su búfer de almacenamiento. La instrucción mfence cierra la brecha al vaciar el búfer de almacenamiento: cada escritura antes de ella se vuelve visible antes de cualquier lectura después de ella.

    mov dword [rdi], 1    ; publish: this thread is ready
    mfence                ; the store above must land before the load below
    mov eax, dword [rsi]  ; observe whether the other thread is ready

También existen dos barreras más estrechas:

• sfence ordena las escrituras entre sí y es relevante sobre todo con los almacenamientos de streaming, no temporales;
• lfence ordena las lecturas.

Para los patrones atómicos ordinarios de arriba, las instrucciones con prefijo lock ya llevan ordenamiento completo, así que una barrera explícita solo es necesaria para un handshake construido con almacenamientos y cargas simples como el de arriba.

Estas garantías tienen nombres que van más allá de x86. Una operación tiene ordenamiento acquire cuando ningún acceso posterior puede parecer moverse antes que ella, y ordenamiento release cuando ningún acceso anterior puede parecer moverse después que ella. En x86, toda carga es un acquire, todo almacenamiento es un release, y una instrucción con prefijo lock, o un xchg con memoria, es ambas cosas a la vez.

Espera activa y pause

Las instrucciones que establecen una bandera y a la vez devuelven su estado anterior se conocen como test-and-set. Se pueden usar como base de un spinlock, asegurando que un núcleo tenga acceso exclusivo a alguna parte del código.

Este es el algoritmo general, usando la instrucción xchg con una bandera binaria:

1. La bandera empieza en 0.
2. Para adquirir el bloqueo, un núcleo intercambia el valor de la bandera con 1.
3. Si el valor devuelto es 1, esto significa que el bloqueo está tomado por otro núcleo. El núcleo actual entonces espera e intenta adquirir el bloqueo de nuevo.
4. Si el valor devuelto es 0, esto significa que el bloqueo estaba libre. xchg ahora lo puso en 1, y los otros núcleos esperarán hasta que este núcleo lo libere.
5. Una vez que el núcleo actual termina de trabajar, actualizar la bandera con 0 libera el bloqueo.

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

La instrucción pause en el bucle de espera no cambia lo que calcula el código. Le indica al procesador que esto es una espera activa. La CPU puede entonces reducir el consumo de energía en el hilo que espera y ceder a un hilo hermano que comparte el mismo núcleo. Un bucle de giro sin pause sigue siendo correcto, solo que desperdicia recursos.

Nota que en un test-and-set, una instrucción como xchg siempre establece la bandera, incluso cuando ya estaba establecida. Esto significa que obtiene acceso exclusivo a la memoria en cada giro, incluso cuando es probable que el bloqueo siga tomado.

Existe una variante de este algoritmo, conocida como test-and-test-and-set, que primero prueba (lee) la bandera para comprobar si ya está establecida. Luego solo intenta el test-and-set (el xchg en este caso) una vez que el bloqueo parece libre:

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock
    test eax, eax
    jz   .taken           ; got it
.held:
    pause                 ; wait before trying again
    cmp  dword [rdi], 0   ; watch the lock without writing to it
    jne  .held            ; still held
    jmp  acquire          ; looks free: retry
.taken:
    ret

Una vez que el hilo termina su trabajo, puede liberar el bloqueo con un simple almacenamiento de 0 usando mov. No hace falta más que un mov, porque en x86-64 las cargas y los almacenamientos nunca se reordenan después de un almacenamiento posterior. Se dice que un almacenamiento que nunca adelanta a los accesos anteriores tiene ordenamiento release, y en x86 todo almacenamiento simple lo lleva.