Prompt y contexto
Tienes una pila lock-free de alta contención cuyos nodos están enlazados mediante un puntero atómico. Un hilo lee y extrae la cabeza mediante CAS mientras otro hilo podría liberarla. Diseña una liberación segura utilizando el modelo hazard_pointer de C++26, permitiendo lectores concurrentes sin un bloqueo global alrededor de la pila.
Lo que evalúa el entrevistador
Los hazard pointers protegen una dirección que se está leyendo actualmente; no mantienen un nodo vivo para siempre. Un lector publica un hazard, vuelve a comprobar que la cabeza atómica todavía apunta a ese nodo y solo entonces lo desreferencia. Un nodo eliminado entra en una lista de retirados (retired list) y se libera únicamente después de escanear cada hazard. Cubre acquire/release, registro y salida, costo de escaneo y el hecho de que ABA necesita protección por separado.
Preguntas aclaratorias para hacer primero
Estructura de datos y garantía de progreso
Confirma si se trata de una pila de Treiber, una lista enlazada o un bucket de tabla hash, si se requiere un progreso lock-free o wait-free, y si las listas de retirados locales al hilo (thread-local) son aceptables.
Ciclo de vida del hilo
Pregunta cómo obtienen los hilos las ranuras de hazard (hazard slots) y cómo la salida limpia la protección y transfiere los nodos retirados. Un hilo que falla no debe dejar un registro permanentemente no recuperable.
Política de ABA y etiquetado
Determina si las direcciones pueden reutilizarse y si se dispone de un contador de versiones o un puntero etiquetado. Los hazard pointers evitan liberar un nodo protegido, pero por sí mismos no impiden que ABA haga que un CAS tenga éxito de forma incorrecta.
Estructura de respuesta en 30 segundos
«El lector carga la cabeza de forma atómica, publica esa dirección en su ranura de hazard y vuelve a cargar la cabeza; solo se puede desreferenciar un valor sin cambios. Tras un CAS exitoso, el nodo anterior va a una lista de retirados en lugar de eliminarse. Un escaneo recopila todas las direcciones de hazard y libera solo los nodos retirados ausentes de ese conjunto. Utiliza la semántica acquire/release correspondiente, limpia la ranura antes de la salida del hilo y maneja ABA con una versión o etiqueta por separado».
Respuesta detallada paso a paso
Paso 1: Definir las ranuras de hazard y las listas de retirados
Cada hilo que pueda desreferenciar nodos compartidos posee una ranura de hazard. Una lista de retirados contiene nodos eliminados de la estructura de datos pero que aún no son seguros de liberar. El registro y la propiedad de la ranura deben ser explícitos para que un puntero sin formato temporal no pueda eludir la protección.
Paso 2: Establecer la ventana de publicación y validación
Carga la cabeza, publícala en la ranura de hazard con release o un ordenamiento equivalente, luego vuelve a cargar la cabeza con acquire. Desreferencia los campos solo cuando ambos valores coincidan; de lo contrario, limpia la ranura y reintenta. Esto cierra la brecha en la que otro hilo podría eliminar y liberar el nodo.
Paso 3: CAS y diferir la liberación
Lee next y realiza un compare-exchange sobre head. Si el CAS falla, limpia el hazard y reintenta. Si tiene éxito, añade el nodo antiguo a la lista de retirados y limpia la ranura solo después de que el lector ya no necesite el nodo. Ninguna ruta puede eliminar directamente un nodo compartido.
Paso 4: Escanear y liberar
Escanea la ranura de hazard de cada hilo en un conjunto de direcciones protegidas. Recorre la lista de retirados y libera solo los nodos ausentes de ese conjunto. Ajusta los umbrales de escaneo a partir del recuento de ranuras y la longitud de la lista de retirados. El protocolo de publicación y validación de un lector conforme garantiza que un nodo no pueda quedar desprotegido antes de que el escaneo vea su hazard.
Paso 5: Manejar ABA y el ordenamiento de memoria
La liberación diferida reduce la reutilización de direcciones pero no elimina el problema ABA. Si un nodo puede eliminarse y reinsertarse rápidamente, usa un contador de versiones, un puntero etiquetado u otra defensa contra ABA. Define las relaciones happens-before para la cabeza atómica, las ranuras de hazard y los campos del nodo; no se deben usar operaciones relajadas (relaxed) simplemente por velocidad sin una demostración formal.
Paso 6: Manejar la salida de hilos y las excepciones
Limpia el hazard antes de detener las lecturas, luego transfiere los nodos retirados a un liberador activo o dominio compartido. El registro necesita un estado de propietario que pueda detectar la salida y evitar ranuras abandonadas. La destrucción se ejecuta solo después de que ningún lector pueda alcanzar el nodo; las suposiciones ordinarias sobre el ciclo de vida del objeto son insuficientes.
Paso 7: Probar la seguridad y el rendimiento
Usa ThreadSanitizer, planificación aleatorizada y pruebas de estrés para fallos de CAS, escaneos concurrentes, salida de hilos, reutilización y excepciones. Agrega centinelas de liberación retardada para detectar use-after-free. Mide el tiempo de escaneo, el pico de la lista de retirados, el throughput y la latencia de cola (tail latency), luego ajusta los umbrales de procesamiento por lotes en lugar de agregar un bloqueo global.
Respuesta de muestra de alta calidad
Asignaría a cada lector una ranura de hazard. pop carga head, publica el hazard, vuelve a cargar head y solo entonces lee next e intenta el CAS; un valor modificado limpia la ranura y reintenta. Una extracción exitosa entra en una lista de retirados, y un escaneo de todas las direcciones de hazard libera solo los nodos no protegidos. La salida del hilo limpia y transfiere su ranura. ABA utiliza una versión o un puntero etiquetado por separado. Las pruebas cubren contención, fallos de CAS, reutilización, salida y excepciones, mientras verifican use-after-free y el costo del escaneo.
Errores comunes
- Error: Desreferenciar head inmediatamente después de la primera carga. → Por qué falla: El nodo puede liberarse antes de que se publique la protección. → Solución: Publicar el hazard y validar head nuevamente.
- Error: Eliminar después de un CAS exitoso. → Por qué falla: Otro lector aún puede estar en su ventana de protección. → Solución: Retirar primero, escanear y luego liberar.
- Error: Asumir que los hazard pointers resuelven ABA. → Por qué falla: La liberación diferida no garantiza la estabilidad de la versión lógica. → Solución: Agregar un contador de versiones o un puntero etiquetado.
- Error: Usar solo atómicos relaxed. → Por qué falla: La publicación y la validación podrían no ser visibles en el orden requerido. → Solución: Demostrar acquire/release y las relaciones happens-before.
Preguntas de seguimiento y respuestas
Pregunta de seguimiento 1: ¿Por qué volver a cargar head después de publicar?
Existe una ventana entre la primera carga y la publicación del hazard en la que otro hilo puede eliminar y liberar el nodo. La recarga demuestra que el nodo sigue siendo la cabeza actual bajo protección; de lo contrario, se reintenta.
Pregunta de seguimiento 2: ¿Puede un escaneo pasar por alto un hazard publicado durante el escaneo?
El protocolo requiere que un lector publique antes de validar y que reintente cuando la validación falle. Con ese protocolo, solo se liberan los nodos retirados ausentes del conjunto protegido; un lector con puntero sin formato no protegido queda fuera de la garantía.
Pregunta de seguimiento 3: ¿Puede la lista de retirados crecer indefinidamente?
Puede crecer cuando los lectores retienen hazards durante mucho tiempo, un hilo se detiene o los escaneos son demasiado infrecuentes. Establece umbrales, monitorea el pico, limpia al salir y permite que un hilo liberador escanee proactivamente cuando sea necesario.
Pregunta de seguimiento 4: ¿Cuándo elegir hazard pointers en lugar de liberación basada en épocas (epoch-based reclamation)?
Los hazard pointers protegen con precisión un número reducido de direcciones y se adaptan a rutas de lectura dinámicas, pero escanear ranuras consume CPU. La liberación por épocas agrupa en lotes eficientemente pero puede verse retrasada por un hilo bloqueado. Elige en función del recuento de lectores, la tolerancia a pausas y los límites de memoria.