28 · Locks
Apuntes propios sobre el capítulo 28 de OSTEP (Locks). Fuente: https://ostep.org
28.1 Qué pedimos a un lock
Un lock protege una sección crítica: lock() la abre (o bloquea al llamante si está cogido), unlock() la cierra. Tres criterios de evaluación:
- Corrección: exclusión mutua real.
- Equidad: ¿algún hilo puede esperar indefinidamente (inanición)?
- Rendimiento: coste sin contención; coste con muchos hilos y muchas CPUs.
28.2 Intentos fallidos que enseñan
- Deshabilitar interrupciones: funciona en monoprocesador para el kernel, pero: requiere privilegio (un proceso hostil monopoliza), no funciona con varias CPUs (el otro núcleo sigue entrando), y pierde interrupciones. Solo se usa dentro del kernel para secciones cortísimas.
- Un flag con load/store normales: comprobar-y-poner el flag son dos operaciones; una interrupción entre ambas mete a dos hilos dentro. Sin ayuda atómica del hardware, no hay lock correcto (los algoritmos de solo-loads/stores tipo Peterson existen, pero son frágiles con los reordenamientos de memoria modernos y no se usan).
28.3 Las primitivas hardware
Instrucciones atómicas (todo-o-nada, incluso entre CPUs):
- test-and-set (xchg): escribe 1 y devuelve el valor anterior, atómicamente.
- compare-and-swap (CAS): “si la dirección vale E, escribe N; devuelve lo que había”. Más potente (base también del lock-free).
- load-linked / store-conditional (RISC: ARM, RISC-V): el store solo triunfa si nadie tocó la dirección desde el load.
- fetch-and-add: suma atómica que devuelve el valor previo.
28.4 Spinlock: girar hasta entrar
void lock(lock_t *l) { while (TestAndSet(&l->flag, 1) == 1) ; } // girar
void unlock(lock_t *l) { l->flag = 0; }
- Correcto con la primitiva atómica.
- Equidad: ninguna garantía — un hilo puede girar para siempre.
- Rendimiento: en monoprocesador, desastroso (el que gira quema su rodaja entera mientras el dueño del lock ni siquiera corre); con varias CPUs y secciones cortas, razonable (el dueño está corriendo en otra CPU y suelta pronto).
Ticket lock (con fetch-and-add): cada hilo toma número (ticket) y espera a que el turno (turn) llegue a él. Garantiza orden FIFO → sin inanición. Es el patrón de la charcutería.
28.5 Dejar de girar: el papel del SO
Girar desperdicia CPU. Alternativas escalonadas:
- yield(): al no conseguir el lock, ceder la CPU. Mejor que girar la rodaja entera, pero con muchos hilos sigue habiendo tormenta de cambios de contexto, y no evita inanición.
- Colas de dormidos (park/unpark): el lock mantiene una cola; quien no lo consigue se duerme (
park), y el que libera despierta al primero (unpark). Detalles finos que trata el capítulo: la ventana entre “decidir dormirse” y “dormirse” (resuelta consetparko pasándole el problema al kernel), y el “traspaso” directo del lock al despertado (que evita carreras pero puede regalar el lock a quien tardará en correr). - Linux: futex (fast userspace mutex): el caso sin contención se resuelve enteramente en espacio de usuario con un CAS sobre un entero; solo si hay contención se llama al kernel (
futex_wait/futex_wake) para dormir/despertar. Lo mejor de ambos mundos: mutex baratísimo si no hay pelea, sin espera activa si la hay. Así están hechos los mutex de pthreads/glibc. - Híbrido two-phase: girar un poquito (por si el lock se libera ya) y dormir si no. Lo usan glibc con
PTHREAD_MUTEX_ADAPTIVE_NPy muchos runtimes.
28.6 Evaluación final
| Lock | Sin contención | Con contención | Equidad |
|---|---|---|---|
| Spin (TAS) | Muy barato | Malo (giro), cache-storm | No |
| Ticket | Muy barato | Giro pero FIFO | Sí |
| yield | Barato | Muchos switches | No |
| Cola + park | Algo más | Bueno | Sí |
| Futex/two-phase | Muy barato | Bueno | ~Sí |
Ampliación (no está en OSTEP)
- El spinlock TAS ingenuo además machaca el bus: N CPUs girando con escrituras atómicas invalidan la línea de caché sin parar. Paliativos: test-and-test-and-set (girar leyendo, intentar escribir solo al verlo libre), backoff exponencial, y locks de colas MCS/CLH (cada CPU gira sobre su propia línea de caché — estándar en kernels; el qspinlock de Linux es un MCS compacto).
- Priority inversion (mencionado en un aside del capítulo y célebre por el Mars Pathfinder, 1997): hilo de baja prioridad tiene el lock, uno de media lo desplaza, el de alta espera el lock → el de alta corre “detrás” del de media. Soluciones: herencia de prioridad (
PTHREAD_PRIO_INHERIT, los rt-mutex de Linux) o techo de prioridad. - Más allá de locks: lock-free con CAS (cap. siguiente lo roza), RCU (lectores sin lock alguno; omnipresente en el kernel Linux — Turing-worthy idea de McKenney), y locks de lectura/escritura (cap. 31).
Referencias
- OSTEP cap. 28.
- Mellor-Crummey & Scott, Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors, ACM TOCS 1991 (MCS; premio Dijkstra).
- Franke, Russell & Kirkwood, Fuss, Futexes and Furwocks, OLS 2002 (futex).
man 2 futex;Documentation/locking/del kernel.