Planteamiento y contexto
Implementa una cola de capacidad fija con un escritor y un lector. push falla cuando está llena y pop falla cuando está vacía. El entrevistador desea que aproveches la restricción SPSC y luego expliques los índices, la visibilidad, la recuperación de memoria y las pruebas de límites en lugar de copiar una cola multiproductor.
Qué está evaluando el entrevistador
El núcleo son las invariantes de concurrencia y las compensaciones (trade-offs). El productor debe escribir únicamente su tail y el consumidor únicamente su head; cada uno lee el índice del otro y utiliza atómicos para establecer una relación happens-before de "escribir los datos, luego publicar el índice". cppreference documenta la relación de sincronización entre un store release y un load acquire; de manera similar, VarHandle de Java distingue entre modos de acceso acquire, release y volatile.
Preguntas de aclaración para hacer primero
Aclara si los elementos se copian o se mueven, si se permite sobrescribir datos antiguos, si la capacidad se elige en tiempo de ejecución, si se requieren API bloqueantes, si hay exactamente un productor y un consumidor, y cómo se manejan la destrucción o las excepciones. Si la restricción cambia a MPSC o MPMC, este algoritmo no puede reutilizarse sin modificaciones.
Una estructura de respuesta de 30 segundos
Di: "Mantengo contadores head y tail monótonamente crecientes y los asigno a ranuras (slots) mediante módulo. El productor lee su tail local y el head publicado por el consumidor, verifica el espacio, escribe en la ranura y luego publica mediante release el nuevo tail. El consumidor carga mediante acquire tail, verifica que no esté vacío, mueve el elemento y luego publica mediante release el nuevo head. El módulo maneja capacidades que no son potencias de dos; las pruebas cubren el desbordamiento cíclico (wraparound), los límites de lleno/vacío y la visibilidad".
Análisis detallado paso a paso
1. Establecer las invariantes
Utiliza tail - head como el número de entradas ocupadas, asumiendo contadores sin signo suficientemente amplios con desbordamiento cíclico natural. El productor nunca debe permitir que la diferencia exceda la capacidad; el consumidor nunca debe leer fuera de head != tail. Cada ranura es escrita por el productor una vez antes de ser consumida.
2. Separar índices locales y compartidos
El productor actualiza frecuentemente tail, y el consumidor actualiza frecuentemente head; cada uno puede mantener su propio índice en una variable local normal. Leer el índice del otro hilo utiliza acquire, mientras que publicar tu propio nuevo índice utiliza release, evitando una carrera de escritura en el mismo contador.
3. Publicar en el orden de push
El productor carga el head del consumidor y verifica tail - head < capacity. Escribe en buffer[tail % capacity], y luego almacena mediante release el nuevo tail. El consumidor solo puede leer esa ranura después de que una carga acquire observe el nuevo tail.
4. Reclamar en el orden de pop
El consumidor carga el tail publicado del productor y verifica head != tail. Después de mover el valor de la ranura, almacena mediante release el nuevo head. El productor solo puede reutilizar esa ranura después de que una carga acquire observe el nuevo head.
5. Manejar la capacidad y el desbordamiento cíclico (wraparound)
Una capacidad que sea potencia de dos puede utilizar una máscara de bits, pero la implementación debe declarar sus suposiciones de desbordamiento y ancho de bits. Para una capacidad ordinaria, % capacity es más fácil de verificar. Para contadores de larga duración, utiliza un tipo sin signo amplio y compara diferencias en lugar de truncar los índices en un entero pequeño.
6. Definir fallos, ciclo de vida y pruebas
Devuelve false cuando esté lleno y empty cuando esté vacío; no hagas espera activa (spin). Si la escritura de un elemento falla, no publiques tail; mover o destruir un elemento requiere una restricción de tipo explícita o una regla de recuperación. Prueba capacidad uno, capacidad más uno, desbordamiento cíclico repetido, velocidades desiguales de productor y consumidor, límites de lleno/vacío y elementos restantes al momento de finalizar.
Respuesta de muestra de alta calidad
push(x):
t = tail.load(relaxed)
h = head.load(acquire)
if t - h == capacity: return false
buffer[t % capacity] = x
tail.store(t + 1, release)
return true
pop():
h = head.load(relaxed)
t = tail.load(acquire)
if h == t: return empty
x = move(buffer[h % capacity])
head.store(h + 1, release)
return xhead y tail son contadores atómicos; el productor escribe únicamente en tail, y el consumidor escribe únicamente en head. La escritura ordinaria en el búfer ocurre antes de la publicación con release de tail, por lo que la carga acquire del consumidor hace visible el elemento. El release inverso de head permite que el productor reutilice la ranura de forma segura. Utiliza módulo para capacidades que no sean potencia de dos y una máscara solo con suposiciones adicionales de potencia de dos y desbordamiento. Esta versión es SPSC, no una cola general para múltiples escritores o múltiples lectores.
Errores comunes y mejoras
- Ambos hilos escriben en un solo índice: Declara la propiedad SPSC y cambia a un algoritmo dedicado MPSC/MPMC cuando la restricción cambie.
- Publicar antes de escribir el elemento: Escribe primero en la ranura y publica el índice mediante release al final.
- Usar relaxed en todas partes: Relaxed proporciona atomicidad, no la publicación de datos ordinarios; los índices compartidos entre hilos necesitan acquire/release.
- Asumir que toda capacidad es una potencia de dos: Utiliza módulo para capacidades ordinarias en lugar de una máscara no verificada.
Preguntas de seguimiento y respuestas
¿Por qué las lecturas de índices locales pueden usar relaxed?
El productor modifica únicamente su tail y el consumidor únicamente su head, por lo que las lecturas locales no se sincronizan con el otro hilo. Leer el índice del otro hilo aún necesita acquire porque también proporciona visibilidad.
¿Cuándo se puede reutilizar una ranura que contiene un valor por referencia?
Solo después de que el consumidor termine de mover o destruir el valor y publique mediante release el nuevo head. El productor carga ese valor mediante acquire antes de sobrescribir la ranura; observar que el consumidor ha comenzado no es suficiente.
¿Cómo lo extenderías a múltiples productores?
Múltiples productores no pueden escribir directamente en el mismo tail. Necesitas reserva de secuencias basada en CAS, números de secuencia por ranura o un bloqueo, y debes volver a demostrar el orden de reserva, publicación y recuperación. No presentes el código SPSC como una cola general.
¿Cómo sabes que la optimización es más rápida?
Compara el throughput, la latencia p99, los cambios de contexto y los fallos de caché bajo igualdad de tamaño de elementos, afinidad de hilos, tamaño de lote y carga. Si el productor alcanza frecuentemente al consumidor, la capacidad, el procesamiento por lotes o la contrapresión (backpressure) pueden importar más que relajar el ordenamiento de memoria.