Test-and-set y compare-and-swap

1. Test-and-set

Test-and-set (TAS) es la instrucción atómica más simple: lee el valor de una variable, lo establece a 1 (o a un valor específico) y devuelve el valor anterior. Todo esto de forma atómica, en una sola operación indivisible.

TAS es la instrucción sobre la que se construyen los spinlocks y, por extensión, todos los mecanismos de sincronización. Es la primitiva más básica del hardware para la sincronización.

La operación se puede expresar como:

int test_and_set(int *lock) {
    int old = *lock;    /* leer el valor actual */
    *lock = 1;          /* establecer a 1 */
    return old;         /* devolver el valor anterior */
}

La clave es que las tres operaciones (leer, escribir, devolver) se ejecutan de forma atómica: ningún otro procesador puede acceder a la variable entre la lectura y la escritura.

2. Cómo funciona test-and-set

Test-and-set se usa típicamente para implementar un spinlock:

1. Un hilo quiere entrar a la sección crítica. Llama a test_and_set(&lock). solicitar
2. Si el valor anterior era 0 (libre): el hilo adquirió el lock. Puede entrar a la sección crítica. adquirir
3. Si el valor anterior era 1 (ocupado): el hilo no adquirió el lock. Debe reintentar (espera activa). reintentar
4. Cuando sale de la sección crítica: establece lock = 0 (libera el lock). liberar

La espera activa (spin) es la característica principal del spinlock: el hilo gira en un bucle hasta que el lock se libera. Esto es eficiente si el lock se libera rápidamente, pero desperdicia CPU si el lock se mantiene mucho tiempo.

3. Test-and-set en x86

En x86, test-and-set se implementa con la instrucción XCHG (exchange), que tiene un prefijo LOCK implícito:

; Implementación de test_and_set en x86 (AT&T syntax)
; lock: dirección de la variable (en %rdi)
; devuelve: valor anterior (en %eax)

test_and_set:
    movl    $1, %eax        ; eax = 1
    xchgl   %eax, (%rdi)    ; intercambiar eax con *lock (atómico)
    ret                      ; devolver el valor anterior (en eax)

La instrucción XCHG con un operando de memoria tiene un prefijo LOCK implícito en x86: siempre es atómica, incluso sin el prefijo explícito. Esto la hace ideal para test-and-set.

Alternativamente, se puede usar LOCK BTS (bit test and set), que establece un bit y devuelve su valor anterior:

; Establecer el bit 0 de lock y devolver su valor anterior
lock btsl   $0, (%rdi)     ; atómico: bit 0 = 1, devuelve valor anterior

4. Test-and-set en ARM

En ARM, test-and-set se implementa con las instrucciones LDREX (load exclusive) y STREX (store exclusive):

; Implementación de test_and_set en ARM
; r0: dirección de lock
; devuelve: valor anterior en r0

test_and_set:
    mov     r1, #1          ; r1 = 1
1:  ldrex   r2, [r0]        ; r2 = *lock (exclusive)
    strex   r3, r1, [r0]    ; *lock = 1, r3 = 0 si éxito, 1 si fallo
    cmp     r3, #0
    bne     1b              ; si fallo, reintentar
    mov     r0, r2          ; devolver valor anterior
    bx      lr

LDREX marca la línea de caché como «exclusiva». STREX escribe solo si la línea no ha sido modificada por otro procesador. Si otro procesador modificó la línea, STREX falla y se debe reintentar.

Este enfoque (load-linked/store-conditional) es más flexible que el prefijo LOCK de x86: permite implementar cualquier operación atómica, no solo test-and-set.

5. Construir un spinlock con test-and-set

Un spinlock es el mecanismo de sincronización más simple: un candado que se adquiere con test-and-set y se libera estableciendo el valor a 0:

typedef struct {
    volatile int lock;
} spinlock_t;

void spinlock_init(spinlock_t *s) {
    s->lock = 0;
}

void spinlock_lock(spinlock_t *s) {
    while (test_and_set(&s->lock)) {
        /* espera activa: el lock está ocupado */
    }
}

void spinlock_unlock(spinlock_t *s) {
    s->lock = 0;
}

El spinlock cumple la exclusión mutua: test_and_set es atómico, así que solo un hilo puede adquirir el lock a la vez. El progreso y la espera acotada dependen de la implementación: con test-and-set puro, no hay garantía de espera acotada (puede haber inanición).

6. Compare-and-swap

Compare-and-swap (CAS) es una instrucción atómica más poderosa que test-and-set: compara el valor actual de una variable con un valor esperado y, si son iguales, lo reemplaza por un nuevo valor. Todo esto de forma atómica.

CAS es la instrucción fundamental de los algoritmos lock-free. Permite implementar operaciones complejas (insertar en una lista, actualizar un contador) de forma atómica, sin usar mutex.

La operación se puede expresar como:

int compare_and_swap(int *ptr, int expected, int desired) {
    int old = *ptr;              /* leer el valor actual */
    if (old == expected) {
        *ptr = desired;          /* escribir el nuevo valor */
    }
    return old;                  /* devolver el valor anterior */
}

La diferencia con test-and-set es que CAS compara con un valor esperado (no solo con 0). Esto permite implementar operaciones condicionales: «si el valor es X, cámbialo a Y».

7. Cómo funciona CAS

CAS se usa típicamente en un bucle para implementar operaciones atómicas complejas:

1. Leer el valor actual: old = *ptr. leer
2. Calcular el nuevo valor: new = f(old). calcular
3. Intentar CAS: CAS(ptr, old, new). CAS
4. Si tiene éxito: la operación se completó. Salir del bucle. éxito
5. Si falla: otro hilo modificó el valor. Reintentar desde el paso 1. reintentar

El bucle CAS es el patrón fundamental de los algoritmos lock-free: se intenta la operación, y si falla (porque otro hilo interfirió), se reintenta con el nuevo valor.

8. El bucle CAS

El bucle CAS se usa para implementar operaciones atómicas complejas. Por ejemplo, incrementar un contador atómicamente:

void atomic_increment(int *counter) {
    int old = *counter;
    while (1) {
        int new_val = old + 1;
        if (compare_and_swap(counter, old, new_val)) {
            break;  /* éxito */
        }
        /* Fallo: old se actualiza con el valor actual. */
        old = *counter;
    }
}

En C11, esto se simplifica con atomic_fetch_add, pero el bucle CAS es la implementación subyacente:

/* Equivalente a atomic_fetch_add(counter, 1) */
int old = atomic_load(counter);
while (!atomic_compare_exchange_weak(counter, &old, old + 1)) {
    /* old se actualiza automáticamente si falla */
}

9. Construir un spinlock con CAS

Un spinlock con CAS es más flexible que uno con test-and-set porque puede usar cualquier valor como «libre»:

typedef struct {
    volatile int lock;
} spinlock_t;

void spinlock_init(spinlock_t *s) {
    s->lock = 0;  /* 0 = libre */
}

void spinlock_lock(spinlock_t *s) {
    int expected = 0;
    while (!atomic_compare_exchange_weak(&s->lock, &expected, 1)) {
        expected = 0;  /* reintentar */
    }
}

void spinlock_unlock(spinlock_t *s) {
    s->lock = 0;
}

El spinlock con CAS es equivalente al de test-and-set, pero usa CAS en lugar de TAS. La ventaja es que CAS es más general: se puede usar para implementar operaciones más complejas.

10. El problema ABA

El problema ABA ocurre cuando un valor cambia de A a B y vuelve a A, engañando a un CAS que esperaba A. El CAS tiene éxito (porque el valor es A), pero el estado del sistema ha cambiado (pasó por B), lo que puede causar errores.

Ejemplo con una pila lock-free:

1. La pila tiene [A, B, C]. El tope es A. inicial
2. Hilo 1 lee el tope (A) y el siguiente (B). Va a hacer CAS para cambiar el tope de A a B. leer
3. Hilo 2 saca A y B de la pila. La pila queda [C]. sacar
4. Hilo 2 mete A de nuevo. La pila queda [A, C]. meter
5. Hilo 1 hace CAS: compara tope con A, es igual, cambia a B. Pero B ya no está en la pila. La pila queda corrupta. corrupción

El problema ABA es sutil: el CAS tiene éxito porque el valor es el esperado, pero el estado intermedio (B) se perdió. Esto puede causar corrupción de datos en estructuras lock-free.

11. Soluciones al problema ABA

Hay varias soluciones al problema ABA:

La solución más común en C es el contador de versión: se empaqueta el puntero y un contador en una sola palabra (usando los bits altos para el contador) y se usa CAS sobre la palabra completa. Así, aunque el puntero vuelva al mismo valor, el contador será diferente y el CAS fallará.

12. Orden de memoria

Las operaciones atómicas también tienen un orden de memoria (memory ordering) que determina cómo se ordenan las operaciones de memoria respecto a la operación atómica:

El orden por defecto en C11 es memory_order_seq_cst (secuencialmente consistente), que es el más seguro pero el más costoso. Para mejor rendimiento, se pueden usar órdenes más relajados (memory_order_relaxed, memory_order_acquire, memory_order_release), pero requieren más cuidado.

13. Simulador interactivo

Este simulador muestra cómo funciona CAS y el problema ABA:

14. Resumen

• Test-and-set lee, establece a 1 y devuelve el valor anterior, todo atómicamente.
• En x86, se implementa con XCHG (LOCK implícito). En ARM, con LDREX/STREX.
• Un spinlock con TAS cumple la exclusión mutua pero no garantiza espera acotada.
• Compare-and-swap compara con un valor esperado y reemplaza si son iguales.
• CAS es la base de los algoritmos lock-free.
• El bucle CAS permite implementar operaciones atómicas complejas.
• El problema ABA ocurre cuando un valor cambia y vuelve al original.
• Las soluciones al ABA incluyen contador de versión, hazard pointers y RCU.
• El orden de memoria determina cómo se ordenan las operaciones de memoria.

15. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Implementa un spinlock con test-and-set en C y verifica la exclusión mutua.
2. Implementa un spinlock con CAS y compara con el de test-and-set.
3. Implementa un contador atómico usando CAS en un bucle.
4. Diseña un escenario donde ocurra el problema ABA.
5. Implementa la solución con contador de versión.
6. Investiga qué es RCU y cómo se usa en Linux.