Work Stealing y la eficiencia del scheduler de Go

El scheduler de Go opera bajo el modelo G-M-P. En este modelo, las G (Goroutines) se ejecutan sobre M (Machines, hilos del sistema operativo) mediante un intermediario llamado P (Processors, contextos lógicos que representan la capacidad de ejecución). Para evitar que los hilos del sistema operativo queden ociosos mientras hay trabajo pendiente, el runtime implementa un mecanismo de work stealing (robo de trabajo).

Cada P mantiene su propia local run queue (LRQ), una cola local de goroutines lista para ejecutarse. Cuando un P termina sus tareas, no se queda esperando; primero revisa la global run queue (GRQ) y, si esta también está vacía, busca a otro P para “robarle” la mitad de sus goroutines de su LRQ. Este diseño busca minimizar la contención, ya que si todas las goroutines estuvieran en una única cola global, cada cambio de contexto requeriría un bloqueo de mutex masivo, convirtiendo el scheduler en un cuello de botella.

El scheduler de Go es híbrido: es cooperativo porque las goroutines ceden el control en puntos de llamadas a funciones, pero también es preemptivo [disponible desde Go 1.14] mediante señales asíncronas, lo que permite que el runtime interrumpa un bucle infinito que no haga llamadas a funciones. Este mecanismo garantiza que una goroutine con un cálculo intensivo no deje morir de inanición (starvation) al resto de las tareas en el sistema.

Si el scheduler no implementara el robo de trabajo, verías núcleos de tu CPU al 0% de utilización mientras otros están al 100% con colas de goroutines interminables, destruyendo el paralelismo real que ofrece Go.

package main

import (
	"fmt"
	"runtime"
	"sync"
	"time"
)

// Representa una carga de trabajo intensiva para CPU.
func heavyWork(id int, wg *sync.WaitGroup) {
	defer wg.Done()
	
	// Simulamos una tarea que consume ciclos de CPU de forma continua.
	// En versiones antiguas de Go (<1.14), un bucle como este sin llamadas
	// a funciones podría causar starvation, pero el scheduler moderno 
	// lo puede interrumpir mediante preemption asíncrona.
	start := time.Now()
	for i := 0; i < 1e9; i++ {
		if i%1000000 == 0 {
			// Un punto de llamada que facilita la cooperación
			_ = i 
		}
	}
	fmt.Printf("Tarea %d completada en %v\n", id, time.Since(start))
}

func main() {
	// Ajustamos GOMAXPROCS para tener un número fijo de Ps.
	// En un entorno real, esto suele ser igual al número de cores lógicos.
	numCPUs := runtime.NumCPU()
	runtime.GOMAXPROCS(numCPUs)

	fmt.Printf("Ejecutando con %d Ps (Logical Processors)\n", numCPUs)

	var wg sync.WaitGroup

	// Lanzamos un número de goroutines significativamente mayor a los Ps.
	// Esto obliga al scheduler a gestionar LRQs y, potencialmente, a realizar
	// work stealing cuando algunos Ps terminen sus tareas más rápido que otros.
	numGoroutines := 50
	wg.Add(numGoroutines)

	for i := 0; i < numGoroutines; i++ {
		go func(id int) {
			// Mezclamos tareas pesadas con tareas cortas para crear
			// desequilibrio en las run queues locales.
			if id%5 == 0 {
				heavyWork(id, &wg)
			} else {
				// Tareas muy rápidas que se agotan pronto,
				// dejando al P con necesidad de robar trabajo.
				time.Sleep(10 * time.Millisecond)
				wg.Done()
			}
		}(i)
	}

	wg.Wait()
	fmt.Println("Todas las tareas han finalizado.")
}

Desglose del mecanismo

En el código anterior, al lanzar 50 goroutines con tiempos de ejecución tan dispares, forzamos al scheduler a trabajar.

1. Cuando las goroutines con time.Sleep terminan, sus respectivos P vacían sus local run queue casi instantáneamente.
2. Esos P que terminan pronto no se quedan ociosos. El runtime detecta que su LRQ está vacía y activa el work stealing.
3. El P ocioso buscará a otro P que todavía tenga goroutines de heavyWork en su cola local.
4. Una vez que el P ocioso “roba” una parte de la cola del P ocupado, la carga de trabajo se redistribuye, aprovechando los núcleos de la CPU que de otro modo estarían en reposo esperando a que la global run queue les asigne algo.
5. El uso de runtime.GOMAXPROCS define cuántos de estos contextos de ejecución (P) existen. Si intentas ejecutar tareas intensivas con GOMAXPROCS(1), el work stealing no tendrá a quién robarle, y la ejecución será estrictamente secuencial para esas goroutines, sin importar cuántos cores tengas.

El error frecuente

Un error conceptual común es asumir que crear miles de goroutines para tareas intensivas de CPU mejorará el rendimiento por el simple hecho de “hacer más trabajo”.

// MAL: Esto causa un exceso de contención y overhead de scheduling
for i := 0; i < 1000000; i++ {
    go func() {
        // Un cálculo matemático pesado
        _ = math.Sqrt(float64(i))
    }()
}

Aunque el scheduler es extremadamente eficiente, el work stealing tiene un costo. Intentar manejar un número de goroutines que sobrepase por órdenes de magnitud la capacidad de procesamiento de CPU no solo genera un overhead masivo en el scheduler (al intentar equilibrar las colas constantemente), sino que también aumenta la presión sobre el Garbage Collector debido a la asignación de memoria para los stacks de cada goroutine. El scheduler está diseñado para manejar la concurrencia, pero el paralelismo está limitado por el hardware y la gestión de los P.

N° 168