Noche de estreno

Operaciones atómicas

Una sola instrucción puede parecer una acción indivisible cuando en realidad 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 dispone de 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 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 habitual llamado read-modify-write (RMW).

Fíjate en que la lectura (o carga) y la escritura (o almacenamiento) son eventos distintos, así que hay una ventana de tiempo entre ambos. Normalmente no nos damos cuenta porque, en un solo núcleo, cada instrucción tiene garantizado completar su efecto por entero antes que la siguiente. Esa ventana es, por tanto, invisible, y add se comporta como una única 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, le suman cinco cada uno y guardan cada uno su resultado. Se produjeron dos sumas, pero el valor solo avanzó cinco. Una de las actualizaciones se perdió en silencio.

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

No todos los valores quedan expuestos de esta forma. Cada hilo tiene sus propios registros y su propia pila, así que un valor guardado 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 única 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 destino pasa a ser igual al valor anterior del operando origen, mientras que el operando origen pasa a ser igual al valor anterior del operando destino. Conceptualmente, puede verse como dos instrucciones mov que ocurren a la vez.

Como es habitual, puede usarse 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 habitual de hacer atómica una instrucción en x86-64 es añadir el prefijo lock. Fusiona la lectura, la modificación y la escritura en un único paso indivisible. Esto significa que el núcleo retiene la memoria en exclusiva durante todo el proceso, de modo que ningún otro núcleo puede leer ni escribir esa posición entretanto.

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 bit, como and, or, xor, not;
3. las operaciones de bits bts, btr, btc;
4. otras instrucciones específicas, como xadd y cmpxchg, descritas 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 a la vez que suma. Escribe la suma en el destino y deja el valor original del destino en el registro 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.

Igual que con lock add, el contador acaba en el número exacto de llamadas. Sin embargo, a diferencia de lock add, también se devuelve cada valor intermedio, uno a cada llamada.

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 ha cambiado por debajo. Esa actualización condicional es lo que proporciona cmpxchg, 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.

Fíjate en que dest solo se actualiza cuando es igual al valor esperado, previamente cargado en rax. Esta igualdad garantiza que dest sigue conteniendo el valor a partir del cual se calculó el nuevo, de modo que nunca se aplica una actualización basada en una lectura obsoleta. Eso convierte a cmpxchg en el bloque básico 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 la operación de comparar e intercambiar es exactamente el momento en que otro hilo podría intervenir, y cmpxchg lo detecta negándose a almacenar un valor calculado a partir de una lectura obsoleta.

Ordenación de memoria

Todas las operaciones vistas hasta ahora han tocado una única posición de memoria. Cuando los hilos se coordinan a través de más de una posición, surge una pregunta nueva: en qué orden se hacen visibles las escrituras de un hilo para otro. Las reglas que responden a esa pregunta son la ordenación de memoria del procesador.

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

x86-64 mantiene una ordenación de memoria fuerte entre las cargas y los 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 distinta.

Una instrucción con el prefijo lock, o un xchg con un operando de memoria, es una barrera completa: nada parece moverse a través de ella en ningún sentido. Por eso bastan para garantizar una ordenación completa en la mayoría de las situaciones.

Espera activa y pause

Las instrucciones que establecen 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. El núcleo actual entonces espera y vuelve a intentar adquirir el bloqueo.
4. Si el valor devuelto es 0, significa que el bloqueo estaba libre. xchg lo ha puesto ahora 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. La CPU puede entonces 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 mediante mov. No hace falta 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 ordenación de liberación, y en x86 todo almacenamiento normal la posee.