Soporte de hardware: atómicas, spinlocks e interrupciones

Por qué un flag no basta (diapositivas Sem05)

T1: cmp byte [lock_flag], 0   ; ¿libre?          T2: cmp byte [lock_flag], 0
    jne T1                                          jne T2
    mov byte [lock_flag], 1   ; tomar (¡NO atómico!)    mov byte [lock_flag], 1

1. Check-then-act: T1 y T2 leen 0 antes de que alguno escriba 1, así que los dos entran.
2. Lecturas obsoletas (stale reads): cada núcleo gira sobre su copia en caché. Si la liberación no se propaga, el otro puede girar sin ver el 0.

Soluciones: instrucciones atómicas, deshabilitar interrupciones o mecanismos más sofisticados (semáforos y monitores).

Las instrucciones atómicas

Una operación atómica es indivisible: nadie ve un estado intermedio. El hardware la garantiza con un lock del bus o de la línea de caché (prefijo lock en x86) o con LL/SC en ARM y RISC-V. El pseudocódigo en C de abajo solo describe la semántica: en la CPU cada operación es una instrucción.

int  test_and_set(int *p)             { int old = *p; *p = 1;   return old; }  // TAS / TSL
void exchange(int *reg, int *mem)     { int t = *mem; *mem = *reg; *reg = t; } // XCHG
int  compare_and_swap(int *w, int testval, int newval)                          // CAS / CMPXCHG
                                      { int old = *w; if (old == testval) *w = newval; return old; }
int  fetch_and_add(int *p, int inc)   { int old = *p; *p = old + inc; return old; } // XADD

• TAS, XCHG y CAS sirven para construir locks. FAA protege un contador sin lock: counter++ se vuelve correcto sin sección crítica.
• En C11: atomic_flag_test_and_set, atomic_exchange, atomic_compare_exchange_strong, atomic_fetch_add. En GCC: __sync_* y __atomic_*.

; Spinlock correcto con XCHG (diapositivas Sem05)
spin_lock:   mov  al, 1
             xchg al, [lock_flag]   ; intercambio atómico AL ↔ lock_flag
             test al, al            ; ¿estaba libre (AL = 0)?
             jnz  spin_lock         ; no: seguir girando
             ret
spin_unlock: mov  byte [lock_flag], 0
             ret

; TSL (Tanenbaum): enter_region
enter_region: TSL REGISTER, LOCK    ; copia LOCK al registro y pone LOCK = 1
              CMP REGISTER, #0      ; ¿era 0?
              JNE enter_region      ; no: reintentar
              RET

Protocolo con exchange (Stallings): cada proceso tiene una key local. Se cumple el invariante $\text{bolt} + \sum_i \text{key}_i = n$. Si bolt == 0, nadie está en la SC; si bolt == 1, está justo el proceso que tiene key == 0.

Ventajas y desventajas (tabla de Stallings)

✔ Ventajas	✘ Desventajas
sirve para cualquier número de procesos, con una o varias CPUs	busy waiting: consume CPU mientras espera
simple y fácil de verificar	starvation posible: quién entra al liberarse es arbitrario
soporta varias SC (una variable por SC)	deadlock posible por prioridades: uno de baja prioridad tiene el lock, lo expropia uno de alta que gira por el mismo lock, y el de baja nunca vuelve a correr (inversión de prioridad)

Espera acotada con TAS (arreglo waiting[])

TAS y CAS solos no garantizan espera acotada. Esta es la versión que muestran las diapositivas:

bool waiting[n];  bool lock = false;
do {
    waiting[i] = true;  bool key = true;
    while (waiting[i] && key) key = test_and_set(&lock);   // entra por TAS o porque le pasan el turno
    waiting[i] = false;
    /* SC */
    int j = (i + 1) % n;
    while (j != i && !waiting[j]) j = (j + 1) % n;          // busca al siguiente que espera (circular)
    if (j == i) lock = false;                                // nadie espera: libera
    else        waiting[j] = false;                          // le pasa el turno directo a j
    /* resto */
} while (true);

Cada proceso espera como mucho n − 1 turnos, porque el turno se pasa en orden circular.

Ticket lock (FAA): my = fetch_and_add(&next, 1); while (serving != my); … serving++;. Es FIFO: la versión en hardware de Bakery.

Deshabilitar interrupciones

Mientras no haya interrupciones, el dispatcher no puede quitarle la CPU al proceso (salvo que ceda voluntariamente), así que no hay intercalado.

• ✘ Solo funciona con una CPU: con varias, otro núcleo sigue ejecutando.
• ✘ Es peligroso en modo usuario: un bucle infinito con las interrupciones apagadas cuelga el sistema.
• ✘ Si la SC es larga, se pierden las garantías de tiempo de respuesta.
• ✔ Es aceptable dentro del kernel, por poco tiempo (handlers, planificador).

El lock del kernel (versión correcta): las interrupciones se deshabilitan solo alrededor de la variable del lock, no durante toda la SC.

Acquire() {                               Release() {
    disable interrupts;                       disable interrupts;
    if (value == BUSY) {                      if (anyone on wait queue) {
        put thread on wait queue;                 take thread off wait queue;
        go to sleep();   // ¿y las interrupciones?  place on ready queue;
    } else value = BUSY;                      } else value = FREE;
    enable interrupts;                        enable interrupts;
}                                         }

¿Cuándo se vuelven a habilitar las interrupciones al dormir?

• Antes de encolarse: Release podría no verlo en la cola, y no lo despierta.
• Después de encolarse pero antes de sleep(): Release lo pasa a listo, pero el hilo igual ejecuta sleep() y el despertar se pierde (queda dormido para siempre con el lock).
• Solución: las habilita el siguiente hilo que recibe la CPU, dentro del planificador, después del cambio de contexto. Al despertar, el hilo vuelve a Acquire y las habilita ahí.

¿Spin o bloquear?

	Spinlock (busy wait)	Lock bloqueante (mutex, semáforo)
CPU mientras espera	la consume	0: el hilo duerme
Costo de adquirir	mínimo (sin syscall)	cambio de contexto al dormir y al despertar
Cuándo conviene	SC muy cortas, multicore, en el kernel donde no se puede dormir (handlers de interrupción)	esperas largas o impredecibles

E1 2024-I · P5

«¿Cómo harías exclusión mutua en rutinas del kernel donde no se puede bloquear?». Con spinlocks: no duermen, y el costo del busy waiting es despreciable porque la SC es corta. En monoprocesador, además, se deshabilitan las interrupciones.

FUTEX (Fast Userspace muTEX): es lo que usa pthread_mutex_t en Linux. Sin contención, se resuelve en espacio de usuario con una instrucción atómica. Con contención, se hace una syscall:

• futex_wait(addr, val): el kernel verifica atómicamente que *addr == val antes de dormir al hilo, y así evita el lost wake-up;
• futex_wake(addr, n): despierta hasta n hilos.

Todo el detalle (el mutex de 3 estados, mediciones, pthread_mutex a fondo y semáforos POSIX entre procesos) está en Mutex POSIX y futex.

¿Peterson y Dekker funcionan en hardware real? (probado)

Las demostraciones suponen consistencia secuencial. Pero x86 usa TSO: una escritura puede quedar en el store buffer mientras se ejecuta una lectura posterior (reordenamiento store → load). Eso es exactamente lo que rompe a Peterson: flag[i] = 1; turn = j; queda en el buffer y, al mismo tiempo, se lee flag[j].

Lo compilé con -O2, variables volatile, 2 hilos y 5·10⁶ iteraciones cada uno (prueba propia verif_parcial/peter.c, en un x86 de 12 núcleos):

sin barrera: counter=9999439 esperado=10000000  FALLA
sin barrera: counter=9999503 esperado=10000000  FALLA
sin barrera: counter=9999538 esperado=10000000  FALLA
con mfence:  counter=10000000 esperado=10000000  OK
con mfence:  counter=10000000 esperado=10000000  OK

Conclusión: volatile no basta, porque solo evita que el compilador cachee la variable, no que la CPU reordene. Hace falta una barrera de memoria (__sync_synchronize() o atomic_thread_fence, que genera mfence) entre la escritura de turn y la lectura de flag[j]. (El resumen previo de lab2 decía que «en x86 sí pasan la prueba»: la ejecución lo desmiente.)

False sharing (E1 2026-1 · P1.5)

Dos hilos escriben variables distintas que están en la misma línea de caché (64 B). Cada escritura invalida la línea en el otro núcleo (protocolo MESI), así que la línea «rebota» entre núcleos y el rendimiento se desploma, aunque no haya race lógica. La solución es padding o alignas(64).

Semáforo con TAS (E1 2022 · P2b)

Solución (Stallings fig. 5.14 · busy wait mínimo)

El TAS solo protege las pocas instrucciones que modifican el semáforo; la espera larga se hace bloqueando.

typedef struct { int flag; int count; queue_t q; } semaphore;

void semWait(semaphore *s) {
    while (test_and_set(&s->flag)) ;     // spin corto, solo para entrar
    s->count--;
    if (s->count < 0) {
        enqueue(&s->q, self());
        block_and_clear(&s->flag);       // bloquear y poner flag = 0, ATÓMICAMENTE
    } else
        s->flag = 0;
}

void semSignal(semaphore *s) {
    while (test_and_set(&s->flag)) ;
    s->count++;
    if (s->count <= 0)
        ready(dequeue(&s->q));
    s->flag = 0;
}

Por qué es correcto: flag hace mutuamente excluyentes a semWait y semSignal, así que count y la cola quedan consistentes. El giro dura unas pocas instrucciones, nunca toda la espera del recurso. El punto delicado es que bloquear y liberar flag debe ser atómico (lo hace el kernel, como en el lock de arriba); si no, un semSignal puede colarse entre ambos y perder el despertar.

Autoevaluación

0/8 correctas · 0 respondidas Reiniciar

1. Un spinlock con test-and-set es…

a) mutex, deadlock-free y starvation-freeb) mutex y deadlock-free, pero no starvation-freec) no es mutexd) solo para monoprocesador

2. ¿Deshabilitar interrupciones sirve en multicore?

a) Síb) No, otros núcleos siguen ejecutandoc) Solo con hyperthreadingd) Solo en modo usuario

3. compare_and_swap(&x, 5, 7) con x = 6:

a) x = 7, retorna 5b) x = 6, retorna 6 (no cambia)c) x = 5d) bloquea

4. ¿Qué primitiva sirve para un contador compartido SIN lock?

a) test_and_setb) fetch_and_addc) exchanged) deshabilitar interrupciones

5. Peterson con variables volatile en x86 multicore…

a) siempre funcionab) puede fallar: TSO reordena store→load; hace falta una barrera (mfence)c) nunca compilad) provoca deadlock

6. Lock en el kernel: si se habilitan las interrupciones DESPUÉS de encolarse pero ANTES de sleep()…

a) todo funcionab) se puede perder el despertar y el hilo duerme para siemprec) hay doble entrada a la SCd) el kernel entra en pánico

7. La ventaja de FUTEX sobre un lock que siempre hace syscall:

a) nunca duermeb) sin contención se resuelve en espacio de usuario con una instrucción atómicac) es FIFOd) funciona sin hardware atómico

8. Un proceso de baja prioridad tiene un spinlock y lo expropia uno de alta prioridad que gira por ese lock…

a) livelockb) deadlock por inversión de prioridadc) false sharingd) nada

Fuente ·Stallings §5.3 · lab2/Sem4_04-OST-Mutex mechanisms.pdf → Resumenes/02 · lab2/Sem05_05-OST-Mutex mechanisms monitors.pdf (diap. 3–20) · lab2/07-OSL-Atomic_Operations.pdf → Resumenes/08 y 08-Solucion · lab2/Resumenes/07-Locks-Semaphores-Pthreads-Futex.md · código del curso so/sem4/07_mutex/{spin,compare-exchange,atomic_inc,mutex_lock}.c · prueba propia verif_parcial/peter.c · for_partial/E1_OS_2021_2022_Solver.pdf (E1 2022 P2b)