Operaciones atómicas en

Acerca de Operaciones atómicas

Una sola instrucción puede parecer una acción indivisible sin serlo 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 en 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 habitual llamado lectura-modificación-escritura (RMW).

Fíjate en que la lectura (o carga) y la escritura (o almacenamiento) son eventos separados, así que hay una ventana de tiempo entre ellos. Normalmente no nos damos cuenta porque, en un solo núcleo, cada instrucción tiene garantizado producir su efecto por completo antes de la siguiente. Por lo tanto, 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 escritura. Dos hilos cargan cada uno el mismo valor antiguo, cada uno suma cinco y cada uno almacena su resultado. Se produjeron 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 habitual en código multihilo.

No todos los valores están 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 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, puede pensarse como dos instrucciones mov que ocurren a la vez.

Como de costumbre, puede usarse con dos operandos de registro o con un operando de memoria y otro 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 fija un bloqueo sobre la posición durante ese tiempo, el mismo mecanismo que el prefijo lock usa para otras instrucciones y que se describe a continuación.

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 bits, como and, or, xor, not;
3. las operaciones de bits bts, btr, btc;
4. algunas otras instrucciones específicas, como xadd y cmpxchg, descritas más abajo.

En cualquier otra instrucción, como un mov simple, el prefijo no es válido y el procesador genera un fallo de código de operación no válido. Una carga aislada o un almacenamiento aislado no necesitan prefijo: un acceso alineado de forma natural ya es atómico por sí mismo.

Operaciones de bits atómicas

Entre las instrucciones que admiten bloqueo, las pruebas de bits se combinan de forma natural con el bloqueo giratorio del final de este documento. Cada una de bts, btr y btc copia un bit elegido a la bandera de acarreo y luego lo pone a 1, lo pone a 0 o lo invierte. Con el prefijo lock, eso se convierte en una lectura-modificación-escritura de un solo bit: el bit cambia de forma atómica y CF indica 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

Una puesta a 1 que encuentra el bit ya a 1 significa que otro hilo lo reclamó primero. Esto es una versión de un solo bit de la reclamación de bandera que xchg hace para una palabra entera.

Intercambio y suma

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

La instrucción xadd (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 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. Si muchos hilos lo ejecutan sobre el mismo contador, cada llamada devuelve un valor anterior 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 llamador.

El origen puede ser cualquier registro de propósito general, y la anchura 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 ni 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.

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

Fíjate en que dest solo se actualiza cuando es igual al valor esperado, cargado previamente 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 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 la operación de 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.

Merece la pena conocer una sutileza. cmpxchg comprueba que el valor sea igual al que se leyó, no que la posición no se haya tocado nunca. Si otro hilo mueve el valor de A a B y de vuelta a A dentro de la ventana, el intercambio sigue teniendo éxito, aunque el mundo haya cambiado por debajo.

Para un contador simple eso es inofensivo, ya que un recuento igual es un recuento igual de bueno. Para una dirección de memoria en la cabeza de una lista sin bloqueo no lo es, porque esa misma dirección puede llevar ahora a otro sitio. 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 coincidente demuestra que la posición no se tocó entretanto, y no solo que parece no haber cambiado.

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 basta para actualizarla y actualizar también otro valor a la vez.

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

Ordenación de memoria

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

El concepto 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 a 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 ninguna dirección. Por eso bastan para garantizar la ordenación completa en la mayoría de las situaciones.

El mecanismo que hay detrás del único reordenamiento que sobrevive es el búfer de almacenamiento. Para seguir adelantándose, un núcleo aparca 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 demás núcleos pueden ver. Una escritura seguida de una lectura de una posición distinta puede por tanto parecer desordenada: la escritura puede seguir en el búfer mientras la lectura posterior avanza. Este modelo, en el que todo está ordenado salvo ese hueco entre escritura y lectura, se llama total store order.

Ese único hueco basta para romper un intercambio de señales de almacenar y comprobar. Si dos hilos escriben cada uno su propia bandera y luego leen la del otro, ambas lecturas pueden volver sin establecer, porque ninguno de los dos almacenamientos ha salido aún de su búfer. La instrucción mfence cierra el hueco vaciando el búfer de almacenamiento: toda escritura anterior se hace visible antes que cualquier lectura posterior.

    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 no temporales y en streaming;
• lfence ordena las lecturas.

Para los patrones atómicos ordinarios de arriba, las instrucciones con el prefijo lock ya conllevan la ordenación completa, así que una barrera explícita solo hace falta para un intercambio de señales construido con simples almacenamientos y cargas como el de arriba.

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

El giro 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 bloqueo giratorio, 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 lo ha puesto ahora a 1, y los demás núcleos esperarán hasta que este núcleo lo libere.
5. Cuando 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 del bucle de espera no cambia lo que calcula el código. Le indica al procesador que esto es una espera giratoria. 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 giro sin pause sigue siendo correcto, solo que derrocha recursos.

Fíjate en 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 retenido.

Hay una variante de este algoritmo, conocida como test-and-test-and-set, que primero prueba (lee) la bandera para comprobar si ya está establecida. Después solo intenta el test-and-set (el xchg en este caso) cuando 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

Cuando el hilo termina su trabajo, puede liberar el bloqueo con un simple almacenamiento de 0 usando 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 release, y en x86 todo almacenamiento simple la lleva consigo.