29 · Estructuras de datos concurrentes con locks
Apuntes propios sobre el capítulo 29 de OSTEP (Lock-based Concurrent Data Structures). Fuente: https://ostep.org
29.1 El problema general
Con locks en la mano, ¿cómo se hace thread-safe una estructura de datos (contador, lista, cola, hash)? La respuesta trivial siempre funciona: un lock grande alrededor de toda operación. La pregunta interesante es la segunda: ¿escala? — es decir, ¿N hilos en N CPUs van más rápido que uno? Con un lock único, jamás: la estructura se serializa.
29.2 Contadores: del exacto al aproximado
- Contador con un lock: correcto; con 4 hilos machacándolo, más lento que con 1 (contención + ping-pong de la línea de caché).
- Contador aproximado (sloppy counter): un contador local por CPU (cada uno con su lock) + uno global. Los hilos incrementan su local (sin pelear con nadie); periódicamente — al superar un umbral S — el local se vacía al global. Leer el global da un valor aproximado (retrasado hasta S×CPUs). S regula el compromiso: grande = escala perfecto, menos preciso; pequeño = lo contrario.
La lección generaliza: particionar el estado por CPU/hilo y reconciliar de vez en cuando es EL patrón de escalabilidad (aparece en asignadores de memoria por arena, estadísticas del kernel, contadores per-CPU de Linux…).
29.3 Listas enlazadas
- Versión un-lock: correcta y simple. Refinamiento del capítulo: minimizar lo que está bajo el lock (p. ej. el
mallocdel nodo nuevo puede ir fuera; solo la manipulación de punteros necesita exclusión) — también simplifica los caminos de error, fuente clásica de bugs. - Hand-over-hand (lock coupling): un lock por nodo; al recorrer, coges el del siguiente antes de soltar el del actual. Concurrencia teórica máxima… y en la práctica más lento que un lock (adquirir/soltar un lock por nodo cuesta más que lo que se gana). Moraleja explícita del capítulo: más concurrencia de grano fino no implica más velocidad; mide.
29.4 Colas y tablas hash
- Cola de Michael & Scott (dos locks): un lock para la cabeza (dequeue) y otro para la cola (enqueue) + un nodo tonto (dummy) que separa ambas operaciones → productores y consumidores no compiten entre sí.
- Tabla hash con un lock por bucket: escala magníficamente — la contención se reparte entre B buckets — y es la demostración estrella del capítulo: la hash concurrente simple aplasta a la lista con un lock. Estructura y granularidad natural bien casadas.
29.5 Consejos finales del capítulo
Empezar simple (un lock); refinarlo solo si hay un problema de rendimiento medido. Evitar la optimización prematura (Knuth). Ejemplo con historia: Linux pasó del Big Kernel Lock a locks finos cuando las máquinas multi-CPU lo exigieron — no antes.
Ampliación (no está en OSTEP)
- El siguiente escalón es prescindir de locks: estructuras lock-free con CAS (la cola M&S tiene versión lock-free canónica; ver Herlihy & Shavit, The Art of Multiprocessor Programming), y RCU para estructuras leídas masivamente y escritas rara vez (listas y hashes del kernel Linux: lectores sin ninguna barrera, escritores difieren la liberación).
- En la práctica de aplicación: usa estructuras concurrentes ya hechas —
ConcurrentHashMap(Java, lock por segmento→CAS por bucket),dashmap(Rust), tcmalloc/jemalloc para el “contador sloppy” hecho asignador. - False sharing: dos contadores per-CPU en la misma línea de caché se sabotean mutuamente aunque no compartan lock — alinear a 64 B (
alignas(64)). El sloppy counter mal alineado no escala; el detalle de hardware manda (cap. 10 §coherencia).
Referencias
- OSTEP cap. 29.
- Michael & Scott, Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms, PODC 1996.
- Herlihy & Shavit, The Art of Multiprocessor Programming — el libro del área.
- McKenney, Is Parallel Programming Hard? (libre online) — RCU y patrones per-CPU.