SMP: una cola de ejecución por núcleo y el arte de reequilibrar

Un servidor de 2026 apila fácilmente doscientos núcleos lógicos. Imagina una única lista global de tareas listas protegida por un solo lock: cada tick, cada despertar, cada cambio de contexto en cualquiera de esos doscientos núcleos tendría que tomar ese candado. El lock —no la CPU— sería la máquina. Linux resuelve el problema con el mismo instinto del nivel 26: particionar. Cada CPU tiene su propia cola de ejecución y su propio lock, y decide a solas a quién correr. Pero partir crea un problema nuevo y simétrico: el trabajo se acumula desigual. El balanceo de carga es el contrapeso que reparte sin destruir la localidad.

Una cola de ejecución por núcleo

El planificador no guarda una lista de tareas listas: guarda una por CPU. La estructura es struct rq (runqueue), y es una variable per-CPU —exactamente la técnica del nivel 26— alineada a línea de caché para que dos núcleos nunca compartan la suya:

/* kernel/sched/core.c */
DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

/* kernel/sched/sched.h */
#define cpu_rq(cpu)   (&per_cpu(runqueues, (cpu)))
#define this_rq()     this_cpu_ptr(&runqueues)
#define task_rq(p)    cpu_rq(task_cpu(p))

Cada rq lleva su propio candado, rq->__lock, un raw_spinlock (nivel 15). La consecuencia es enorme: planificar en el núcleo 7 no toca ninguna estructura del núcleo 8, así que doscientos núcleos toman doscientas decisiones en paralelo, sin contención. El precio es que una tarea “vive” en la rq de un núcleo concreto, y moverla a otro exige tomar los dos locks en orden —double_rq_lock— y actualizar task_cpu(p). Esa migración no es gratis, y de encarecerla brota todo el resto del nivel.

El planificador es modular: la cadena de clases

Dentro de cada rq no hay un algoritmo único sino varias políticas apiladas por prioridad absoluta. Cada una es un struct sched_class, y el kernel las encadena de la más urgente a la más laxa mediante una sección del enlazador:

/* orden real de mayor a menor prioridad (kernel/sched/) */
/*   stop_sched_class   -> migracion y hotplug, por encima de todo   */
/*   dl_sched_class     -> SCHED_DEADLINE (EDF), nivel 47.3          */
/*   rt_sched_class     -> SCHED_FIFO y SCHED_RR, nivel 47.3         */
/*   fair_sched_class   -> SCHED_NORMAL, hoy EEVDF                   */
/*   idle_sched_class   -> la tarea ociosa, cuando no hay nada mas   */

static struct task_struct *__pick_next_task(struct rq *rq, ...)
{
	const struct sched_class *class;

	for_each_class(class) {                 /* de dl a idle, en orden */
		struct task_struct *p = class->pick_next_task(rq);
		if (p)
			return p;                   /* la primera clase con algo, gana */
	}
	BUG();                                  /* idle siempre devuelve la idle task */
}

for_each_class recorre las clases en orden fijo: si hay una tarea SCHED_DEADLINE lista, corre antes que cualquier SCHED_FIFO; si hay una SCHED_FIFO, corre antes que cualquier tarea normal. Las tareas corrientes —el 99% del sistema— caen en fair_sched_class, que desde el kernel 6.6 implementa EEVDF (Earliest Eligible Virtual Deadline First), sucesor de CFS: cada entidad acumula vruntime y recibe un plazo virtual que decide su turno, buscando repartir la CPU con justicia y baja latencia. La estructura de árbol y el detalle de EEVDF los abre el nivel de scheduling justo; aquí basta con retener que SCHED_NORMAL es la clase fair, y que las clases de tiempo real la pisan siempre.

Balanceo de carga: migrar sin desbalancear

Si cada núcleo elige de su propia cola, ¿qué impide que ocho tareas caigan en el núcleo 0 mientras el 1 duerme ocioso? Nada, salvo el balanceador de carga. Corre en dos momentos. En el despertar de una tarea, select_task_rq_fair elige de entrada un buen núcleo destino —idealmente uno ocioso y cercano en caché al que la despierta—. Y de forma periódica, el tick del planificador dispara un softirq que reequilibra:

/* kernel/sched/fair.c, esquema del camino periodico */
void sched_tick(void)               /* en cada tick de este CPU */
{
	/* ...contabilidad de la tarea en curso... */
	trigger_load_balance(rq);   /* si toca, levanta SCHED_SOFTIRQ */
}

/* el softirq acaba en: */
static int load_balance(int this_cpu, struct rq *this_rq,
			struct sched_domain *sd, ...)
{
	struct sched_group *group = find_busiest_group(&env);
	if (!group)
		return 0;                       /* ya esta equilibrado */

	struct rq *busiest = find_busiest_queue(&env, group);
	/* detach_tasks() del busiest -> attach_tasks() aqui */
	/* respetando afinidad, cache-hotness y limites de carga */
}

La clave está en cómo decide a quién robar tareas, y ahí entran los dominios de scheduling (struct sched_domain). El kernel modela la topología del hardware como una jerarquía: hilos SMT que comparten núcleo físico, núcleos que comparten caché L3, sockets, nodos NUMA (nivel 26). Balancear entre dos hilos SMT es baratísimo y se hace muy a menudo; balancear entre dos nodos NUMA es carísimo —mueve datos lejos de su memoria— y se hace rara vez y con histéresis. La medida de “cuánto pesa” una tarea no es un contador ingenuo sino PELT (Per-Entity Load Tracking), una media geométrica que estima la demanda reciente de cada tarea y cada rq.

flowchart TD
N[Nodo NUMA: balanceo caro y raro] --> L3a[Dominio LLC socket 0]
N --> L3b[Dominio LLC socket 1]
L3a --> Ca[Nucleo fisico 0]
L3a --> Cb[Nucleo fisico 1]
Cb --> T0[Hilo SMT 0: balanceo barato y frecuente]
Cb --> T1[Hilo SMT 1: balanceo barato y frecuente]
style N fill:#f38ba8,color:#11111b
style T0 fill:#a6e3a1,color:#11111b
style T1 fill:#a6e3a1,color:#11111b