Noche de estreno

Atomicidad

Una sola instrucción puede parecer una acción indivisible sin serlo en absoluto. Piensa en sumar cinco a un valor en memoria:

add qword [rel counter], 5

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

1. leer el valor actual de la memoria;
2. modificar ese 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 read-modify-write (RMW).

Fíjate que la lectura (o carga) y la escritura (o almacenamiento) son eventos separados, así que hay una ventana de tiempo entre ellos. Normalmente no lo notamos porque, en un solo núcleo, se garantiza que cada instrucción produce su efecto por completo antes de la siguiente. Por eso esa ventana es 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 ningún orden entre ellos. Con varios núcleos ejecutándose en el mismo instante, otro núcleo puede leer o escribir counter dentro de esa ventana, después de la carga de este núcleo y antes de su almacenamiento. Dos hilos cargan cada uno el mismo valor antiguo, cada uno le 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 sufrir una carrera. Solo la memoria que comparten los hilos, 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 de origen, mientras que el operando de origen 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 es habitual, se puede usar con dos operandos de registro o con un operando de memoria y un operando 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 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 retiene la memoria en exclusiva durante todo el proceso, así que ningún otro núcleo puede leer o escribir esa ubicación mientras tanto.

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 a nivel de bits, como and, or, xor, not;
3. las operaciones de bits bts, btr, btc;
4. algunas otras instrucciones dedicadas, como xadd y cmpxchg, que se describen más abajo.

Intercambio y suma

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

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

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.

Al igual que 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 quien la llama.

Comparación e intercambio

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 ofrece cmpxchg, comparación e intercambio, 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, entonces dest = src y ZF = 1.
• Si dest != rax, entonces rax = dest y ZF = 0.

Fíjate que dest solo se actualiza cuando es igual al valor esperado, que se cargó antes en rax. Esta igualdad garantiza 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 hace de cmpxchg 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 reintentos es el corazón de las actualizaciones sin bloqueos. La ventana entre la lectura y la comparación e intercambio 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.

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 se vuelven visibles las escrituras de un hilo para otro? Las reglas que responden a 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 de una en una. Mantiene muchas en vuelo a la vez y se adelanta cuando puede. Esto significa que una escritura puede volverse visible para los demás 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 las cargas y los almacenamientos normales, 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 distinta.

Una instrucción con el prefijo lock, o un xchg con un operando de memoria, es una barrera completa: nada parece cruzar de un lado a otro. Por eso bastan para garantizar un ordenamiento completo en la mayoría de las situaciones.

Espera activa y pause

Las instrucciones que ponen una bandera y además devuelven su estado anterior se conocen como test-and-set. Pueden usarse como base de un spinlock, que garantiza 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, significa que otro núcleo retiene el bloqueo. Entonces el núcleo actual espera y vuelve a intentar adquirir el bloqueo.
4. Si el valor devuelto es 0, significa que el bloqueo estaba libre. xchg ya lo puso en 1, y los demás núcleos esperarán hasta que este núcleo lo libere.
5. Cuando el núcleo actual termina su trabajo, 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 del bucle de espera no cambia lo que calcula el código. Le indica al procesador que se trata de una espera activa. Así, la CPU puede reducir el consumo de energía del hilo que espera y ceder el paso a un hilo hermano que comparte el mismo núcleo. Un bucle de espera activa sin pause sigue siendo correcto, solo que desperdicia recursos.

Cuando el hilo termina su trabajo, puede liberar el bloqueo con un simple almacenamiento de 0 usando mov. No se necesita nada 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 de liberación, y en x86 todo almacenamiento normal lo tiene.