Consigna y contexto
Implementa un planificador con una cantidad fija de N workers. Su API pública es submit(task), shutdown() y awaitTermination(). Cada worker posee una deque: el propietario toma el trabajo local en orden LIFO, mientras que un worker inactivo roba del extremo opuesto en orden FIFO. Las tareas pueden crear más tareas, pero los nuevos envíos raíz se rechazan una vez que comienza el apagado.
Puedes comenzar con una línea base de corrección protegida por mutex y luego explicar cómo una deque lock-free al estilo Chase–Lev la reemplazaría. El planificador no debe perder ni ejecutar una tarea dos veces. El fallo de una tarea no debe terminar el bucle del worker. Considera colas vacías, ausencia de víctimas para robar, condiciones de carrera durante el apagado y workers bloqueantes.
Qué evalúa el entrevistador
Una respuesta sólida define el límite de concurrencia entre las operaciones del propietario y los robos en lugar de decir simplemente "usa un pool de hilos". El LIFO local preserva la localidad y el comportamiento en profundidad (depth-first); el FIFO remoto le da al ladrón trabajo más antiguo y a menudo más grande. El entrevistador también verifica si el envío, la detención de la aceptación, el vaciado (draining) y la salida del worker forman una máquina de estados explícita, y si puedes identificar el punto de linealización que hace que el reclamo de una tarea sea único.
Preguntas para clarificar
- ¿Pueden las tareas bloquearse en E/S? Si es así, utiliza un pool de E/S separado o una compensación de bloqueo contabilizada; más robos no pueden ayudar cuando todos los workers están bloqueados.
- ¿
submitdevuelve un future? Si es así, define la propagación de excepciones y la cancelación; esta respuesta devuelve un future, mientras que la cancelación solo garantiza que el trabajo que aún no ha sido reclamado no se ejecutará. - ¿La deque debe ser lock-free y no acotada? Si no es necesario, implementa primero la deque con bloqueos y actualízala solo cuando se demuestren los requisitos de contención y recuperación de memoria.
- ¿El apagado es inmediato o progresivo (graceful)? Esta respuesta es progresiva: rechaza nuevas raíces, vacía el trabajo aceptado y luego sale.
Respuesta de 30 segundos
Le doy a cada worker una deque y uso LIFO en el extremo del propietario y FIFO en el extremo de robo. Primero construyo una línea base con bloqueos: submit selecciona una cola y despierta a un worker; un worker extrae (pop) trabajo local y luego roba de otras colas cuando está vacío. Una tarea se ejecuta solo después de que una operación la elimina con éxito, por lo que no se puede reclamar dos veces. El apagado detiene nuevos envíos y los workers salen solo cuando el planificador está en proceso de vaciado, el trabajo pendiente es cero y todas las colas están vacías. Las pruebas cubren envíos concurrentes, carreras de robo, creación de tareas hijas, excepciones, apagado y espera por inactividad.
Análisis detallado paso a paso
Define los estados accepting, draining y terminated. Durante accepting, submit coloca el trabajo en una deque con poca carga, incrementa un contador de pendientes atómicamente y despierta a un worker. Durante draining, el hecho de que las tareas en ejecución puedan crear hijas forma parte del contrato; esta versión permite hijas y continúa vaciando hasta que el contador llega a cero.
type Task = () => void;
class WorkStealingScheduler {
private readonly queues: Array<Deque<Task>>;
private accepting = true;
private outstanding = 0;
submit(task: Task): void {
if (!this.accepting) throw new Error("scheduler is shutting down");
const queue = this.chooseQueue();
queue.pushBottom(task);
this.outstanding += 1;
this.wakeOneWorker();
}
run(workerId: number): void {
while (true) {
const task = this.queues[workerId].popBottom()
?? this.stealFromOtherQueues(workerId);
if (!task) {
if (!this.accepting && this.outstanding === 0) return;
this.parkBriefly();
continue;
}
try { task(); } finally { this.outstanding -= 1; }
}
}
}El fragmento es intencionalmente pseudocódigo de un solo hilo para las transiciones de estado. Una implementación real debe usar un protocolo de sincronización para submit, outstanding, el apagado y los despertares. Para evitar la carrera de despertar perdido (lost-wakeup) donde una tarea llega justo después de una verificación de vacío, usa una variable de condición, un semáforo o un evento contabilizado en lugar de un sleep directo.
La línea base con bloqueos preserva tres invariantes: una tarea se ejecuta solo después de una eliminación exitosa de una deque; no hay dos operaciones que puedan eliminar la misma tarea; y outstanding es igual al trabajo aceptado pero no finalizado. Cuando una tarea en ejecución crea hijas, registra a las hijas antes de decrementar al padre, o un cero transitorio puede desencadenar una terminación prematura.
La equidad depende de la selección de víctimas y del tamaño del lote de robo. La aleatoriedad pura puede sesgarse durante mucho tiempo; un round-robin fijo puede sincronizar a muchos ladrones en una sola cola concurrida. Utiliza inicios aleatorizados, retroceso (backoff) tras robos fallidos y lotes acotados. Las tareas pequeñas y uniformes favorecen robos individuales o pequeños; las cargas de trabajo recursivas a menudo se benefician de tomar un fragmento más antiguo y más grande.
Lock-free es una optimización, no la respuesta por defecto. El ForkJoinPool de Oracle utiliza work-stealing y expone contadores de robo para ajustes. Una deque de Chase–Lev necesita adicionalmente índices atómicos, ordenamiento de memoria (memory ordering), crecimiento y recuperación segura de memoria. Sin un modelo explícito de un solo propietario/múltiples ladrones y un plan de recuperación, el código "lock-free" escrito a mano es más propenso a duplicar trabajo o usar memoria liberada que la línea base con bloqueos.
El costo esperado de push/pop local es O(1); un robo es O(1) u O(lote), mientras que escanear V víctimas de manera ingenua cuesta O(V). El espacio es O(T + N), donde T es el trabajo no finalizado y N es la cantidad de workers. Las E/S bloqueantes invalidan la suposición de que un worker inactivo siempre puede robar, así que aísla el trabajo bloqueante o ponle un límite.
Respuesta de muestra de alta calidad
Presentaría primero una versión correcta con bloqueos y luego discutiría una actualización lock-free. Cada worker tiene una deque privada; el propietario usa LIFO en la parte inferior y los ladrones usan FIFO en la parte superior, con sincronización separada para el propietario y para el robo. Una tarea entra en ejecución solo después de un pop o robo exitoso, que es su punto de linealización para el reclamo.
El envío y el apagado son preocupaciones separadas. El apagado rechaza nuevas raíces y luego espera a que el trabajo pendiente llegue a cero. Si las tareas en ejecución pueden crear hijas, el contrato de vaciado debe permitirlas y contarlas explícitamente; de lo contrario, debe rechazarlas y dejar que la tarea maneje el error. Los workers esperan en una variable de condición o semáforo en lugar de hacer un bucle de sondeo (spin), y las excepciones de las tareas se capturan en futures y métricas en lugar de escapar del bucle del worker.
Liberaría tareas cortas y largas simultáneas con una barrera, verificaría la ejecución de exactamente una vez y los robos reales, y comprobaría que las colas se vacían. Luego inyectaría creación de hijas, apagado durante un robo, trabajo bloqueante, excepciones de tareas y llamadas repetidas de apagado. Solo si la contención y las mediciones lo justifican, reemplazaría la línea base con una deque de Chase–Lev cuyo ordenamiento de memoria y recuperación de memoria estén especificados.
Errores comunes
- Una cola global → cada worker compite por un único bloqueo → usa deques por worker y deja que el robo gestione el desbalance.
- Comprobar que no está vacía y hacer pop por separado → otro ladrón cambia la cola entre operaciones → haz que la eliminación exitosa sea el reclamo atómico.
- Salir cuando las colas parecen vacías durante el apagado → un padre en ejecución puede crear hijas inmediatamente después → usa el estado de vaciado (draining) y el invariante de pendientes.
- Dejar que la excepción de una tarea escape del bucle del worker → una mala tarea reduce el paralelismo → captúrala en un future y continúa con la planificación.
- Escribir código lock-free a mano sin reglas de memoria o de recuperación → trabajo duplicado o uso tras liberación de memoria (use-after-free) → valida primero la semántica con bloqueos y sigue un algoritmo comprobado.
- Robar siempre de una sola víctima → una cola concurrida permanece en contención → combina inicios aleatorizados, backoff y lotes acotados con métricas.
Preguntas de seguimiento y respuestas
¿Cómo evitas que el trabajo bloqueante detenga a todos los workers?
¿Cómo demuestras que el apagado no puede perder tareas hijas?
¿Cuándo es mejor el robo por lotes que el robo de una sola tarea?
La E/S bloqueante pertenece a un pool separado o a un mecanismo de bloqueo gestionado contabilizado; robar solo mueve el trabajo en espera. La prueba de apagado utiliza la máquina de estados y el invariante del contador: detener nuevas raíces, registrar a las hijas antes de completar a los padres y terminar solo en estado de vaciado con cero trabajo pendiente. El robo por lotes ayuda cuando la creación de tareas es densa y cada sincronización es costosa; para colas pequeñas o tareas minúsculas, los costos de movimiento y de equidad pueden superar los ahorros.