¿Cómo balancean la carga entre hilos los planificadores work-stealing (como el de Go o ForkJoinPool de Java)?

#El problema de una única cola compartida

La forma ingenua de repartir trabajo entre un pool de hilos es una cola global única: cada worker toma la siguiente tarea del mismo lugar. Esto es simple y correcto, pero no escala, porque cada extracción y cada inserción deben sincronizarse contra esa única cola; a medida que crece el número de núcleos, crece con él la contención sobre el lock de la cola (o los reintentos de CAS en una implementación lock-free), y con muchos núcleos los hilos terminan gastando más tiempo peleando por la cola que haciendo el trabajo que esta reparte. Además tiene mal comportamiento de caché: una tarea recogida por el hilo que gane el lock de la cola no tiene ninguna relación con qué hilo la produjo, así que no hay localidad que aprovechar.

Los planificadores work-stealing —el diseño detrás de ForkJoinPool de Java, el planificador de goroutines de Go, el thread pool de .NET, y rayon y Tokio en Rust— resuelven esto dándole a cada hilo worker su propia cola local (normalmente una cola doblemente terminada, o deque) y haciendo que el caso común no requiera sincronización con ningún otro hilo en absoluto.

#Cómo se usa el deque local

Cada worker trata su propio deque como una pila para sus propios fines: cuando crea nuevas subtareas (por ejemplo, dividiendo a la mitad un cómputo de divide y vencerás), las apila en un extremo de su propio deque, y cuando busca su siguiente unidad de trabajo, extrae de ese mismo extremo. Como solo el hilo dueño toca ese extremo, apilar y extraer son en la práctica operaciones de un solo hilo que no requieren locking: el camino rápido es tan barato como el de una pila ordinaria.

El deque solo se vuelve un punto de contención cuando la cola local de otro hilo se agota. Un worker ocioso se convierte en ladrón: en lugar de quedarse inactivo, elige a otro worker al azar como "víctima" e intenta robar una tarea del extremo opuesto del deque de esa víctima. Este diseño de dos extremos es deliberado, no incidental:

• El dueño trabaja LIFO en su propio extremo, lo que tiende a sacar primero las subtareas más recientemente creadas y de grano más fino: las que aún están calientes en caché y más cerca del fondo de una división recursiva.
• Los ladrones roban FIFO del otro extremo, lo que tiende a agarrar las tareas más antiguas y de grano más grueso: típicamente los trozos de trabajo más grandes que quedan en un árbol de divide y vencerás. Robar un trozo grande amortiza el costo del robo (y cualquier migración de caché resultante) sobre más trabajo real, en lugar de pagar overhead de sincronización por una tarea diminuta.
• Operar en extremos opuestos también minimiza las colisiones entre las extracciones locales rápidas del dueño y el robo ocasional de un ladrón: las dos operaciones solo necesitan coordinarse cuando el deque se ha reducido a su último uno o dos elementos.

#El planificador de Go: el modelo GMP

El planificador del runtime de Go nombra la misma idea con otras letras: las Goroutines son las unidades de trabajo, las M son hilos reales del sistema operativo, y las P son contextos lógicos de ejecución —hay GOMAXPROCS de ellos— y cada uno mantiene una cola de ejecución local de hasta 256 goroutines listas. Una goroutine solo corre mientras está adjunta a una M que está adjunta a una P; cuando la cola local de una P se vacía, su M mira, en orden, la cola global, luego el poller de red por goroutines desbloqueadas por E/S completada y, finalmente, a otra P elegida al azar, robándole aproximadamente la mitad de su cola local de una sola vez (no solo una goroutine, lo que amortiza el costo del robo, reflejando la idea de "robar el trozo grande que queda" de ForkJoinPool). Elegir la víctima al azar evita que todas las P ociosas golpeen a la misma P ocupada a la vez, y mover la mitad de la cola en lugar de un solo elemento hace que no sea necesario robar de nuevo inmediatamente.

#ForkJoinPool de Java

ForkJoinPool es el hogar dedicado de Java para el paralelismo de divide y vencerás (RecursiveTask/RecursiveAction, y el motor detrás de los parallel streams). Cada ForkJoinWorkerThread posee un deque work-stealing; llamar a fork() sobre una subtarea la apila en el deque propio del hilo que llama, y llamar a join() sobre una subtarea que no ha terminado hace que el hilo que llama vaya a ayudar —ya sea ejecutando esa tarea específica si nadie más la ha tomado, o robando otro trabajo pendiente— en lugar de simplemente bloquearse, que es lo que hace que fork/join sea tan superior a un ExecutorService común para divisiones recursivas: el hilo que está "esperando" es él mismo un candidato a ladrón.

La lección más amplia para ingenieros de backend: cada vez que las tareas de tu carga de trabajo tengan una duración impredecible o muy variable —un ordenamiento paralelo recursivo, un job por lotes que reparte trabajo por registro con costos muy dispares, un manejador de solicitudes que bifurca subcómputos— un pool work-stealing mantendrá cada núcleo productivo mucho mejor que un diseño de partición fija o de cola única compartida, al costo de un planificador considerablemente más complejo de implementar (que es exactamente por lo que recurres a ForkJoinPool, rayon o el planificador integrado de Go en lugar de escribir uno tú mismo).