Work-Stealing es un algoritmo de balanceo de carga descentralizado y dinámico utilizado en entornos de computación paralela y concurrente. En este modelo, cada 'worker' (hilo, procesador o core) mantiene su propia cola de tareas (generalmente un 'deque' para permitir 'push' y 'pop' eficientes desde un extremo por el propietario, y 'steal' desde el otro extremo por los 'ladrones'). Cuando un worker termina sus propias tareas y se queda inactivo, en lugar de esperar, busca activamente trabajo en las colas de otros workers que aún están ocupados. Si encuentra una tarea, la 'roba' y comienza a procesarla. Este enfoque contrasta con el 'work-sharing' donde los workers ocupados distribuyen proactivamente el trabajo a los inactivos.
Esta técnica es fundamental en muchos runtimes de lenguajes de programación y frameworks de concurrencia de alto rendimiento. Ejemplos notables incluyen el runtime de Go (goroutine scheduler), que utiliza un algoritmo de Work-Stealing para distribuir goroutines entre los hilos del sistema operativo. El framework 'Fork/Join' de Java, implementado en el 'java.util.concurrent.ForkJoinPool', también se basa en Work-Stealing para gestionar la ejecución de tareas recursivas. Otros sistemas como Intel TBB (Threading Building Blocks) y Microsoft PPL (Parallel Patterns Library) también emplean Work-Stealing para optimizar la ejecución de tareas paralelas en arquitecturas multi-core.
Para un Arquitecto de Sistemas, Work-Stealing es crucial para diseñar sistemas concurrentes escalables y eficientes. Su valor estratégico radica en su capacidad para lograr un excelente balanceo de carga con baja sobrecarga de coordinación, ya que la mayoría de las operaciones son locales (acceso a la propia cola) y el 'stealing' ocurre solo cuando hay inactividad. Esto conduce a una alta utilización de los recursos y un mejor throughput, especialmente en cargas de trabajo irregulares o dinámicas. Sin embargo, los trade-offs incluyen la complejidad de la implementación (garantizar la seguridad de los hilos y la consistencia de las colas), y el potencial de contención en las colas de trabajo si muchos workers intentan robar del mismo worker ocupado. La elección de la política de 'stealing' (ej. qué cola robar, qué tarea robar) y la gestión de la localidad de los datos son decisiones de diseño críticas que impactan directamente el rendimiento y la escalabilidad del sistema.