1. El árbol rojinegro
CFS mantiene los procesos listos en un árbol rojinegro (red-black tree) ordenado por vruntime. El proceso con el menor vruntime está en el extremo izquierdo del árbol. La selección del siguiente proceso es O(1): basta con tomar el mínimo (el nodo más a la izquierda).
Un árbol rojinegro es un árbol binario de búsqueda balanceado. Garantiza que la altura del árbol es O(log n), donde n es el número de procesos. Esto asegura que la inserción y eliminación son O(log n).
El árbol se mantiene en la estructura struct cfs_rq (CFS runqueue) de cada CPU. Cada nodo del árbol es un struct sched_entity que representa a un proceso (o a un grupo de procesos).
El árbol rojinegro tiene un buen equilibrio entre simplicidad de implementación y garantías de rendimiento. Es auto-balanceado: después de cada inserción o eliminación, el árbol se rebalancea en O(log n). Es el mismo tipo de árbol que usan los mapas ordenados de muchos lenguajes de programación.
2. Por qué un árbol y no una cola
Una cola FIFO (como en FCFS) no funciona para CFS porque:
- Los procesos tienen vruntimes distintos: no se pueden ordenar por llegada.
- El vruntime cambia: cada vez que un proceso se ejecuta, su vruntime aumenta y cambia de posición.
- Se necesita buscar el mínimo eficientemente: el proceso con menor vruntime debe encontrarse en O(1) o O(log n).
Un árbol rojinegro permite:
- Búsqueda del mínimo en O(1): el mínimo está en el extremo izquierdo.
- Inserción en O(log n): al añadir un proceso.
- Eliminación en O(log n): al quitar un proceso (termina o se bloquea).
- Actualización eficiente: cuando el vruntime cambia, el nodo se reinserta en O(log n).
La alternativa (una lista ordenada) tendría inserción y eliminación en O(n), lo que sería demasiado lento con muchos procesos.
3. La latencia objetivo
La latencia objetivo (target latency) es el tiempo que CFS intenta que pase entre dos ejecuciones consecutivas del mismo proceso. Es el tiempo que un proceso debería esperar para recibir la CPU de nuevo.
Si hay n procesos listos y la latencia objetivo es T, cada proceso recibe T/n de tiempo de CPU. Por ejemplo, con 4 procesos y una latencia objetivo de 20 ms, cada proceso recibe 5 ms.
La latencia objetivo por defecto en Linux es de 6 ms (para sistemas de escritorio) y 12 ms (para servidores). Se puede ajustar con el parámetro sched_latency_ns en /proc/sys/kernel/.
La latencia objetivo determina el equilibrio entre respuesta y overhead:
- Latencia corta: mejor respuesta, más cambios de contexto, más overhead.
- Latencia larga: peor respuesta, menos cambios de contexto, menos overhead.
4. La granularidad mínima
La granularidad mínima (min granularity) es el tiempo mínimo que un proceso puede ejecutarse antes de ser preemptado. Evita que el tiempo de ejecución sea tan corto que el overhead de cambios de contexto sea excesivo.
Si la latencia objetivo dividida por el número de procesos es menor que la granularidad mínima, se usa la granularidad mínima. Por ejemplo, con 100 procesos y una latencia objetivo de 20 ms, cada proceso recibiría 0,2 ms. Si la granularidad mínima es 0,75 ms, cada proceso recibe 0,75 ms y la latencia real es 75 ms.
La granularidad mínima por defecto en Linux es de 0,75 ms (para sistemas de escritorio) y 1,5 ms (para servidores). Se ajusta con sched_min_granularity_ns.
Sin la granularidad mínima, con muchos procesos, el tiempo de ejecución sería tan corto que el overhead de cambios de contexto dominaría. La granularidad mínima asegura que cada proceso reciba al menos un tiempo mínimo de CPU.
5. Cómo se calcula el tiempo de ejecución
El tiempo de ejecución de un proceso en CFS se calcula así:
- Calcular el tiempo ideal: tiempo_ideal = latencia_objetivo / número_de_procesos. ideal
- Aplicar la granularidad mínima: si tiempo_ideal < granularidad_mínima, usar granularidad_mínima. granularidad
- Ajustar por peso: el tiempo real se ajusta por el peso del proceso (a través del vruntime). peso
El tiempo de ejecución no es un quantum fijo: se recalcula cada vez que cambia el número de procesos (cuando uno llega o termina). Esto hace que CFS se adapte automáticamente a la carga.
6. Un ejemplo desarrollado
4 procesos listos, latencia objetivo = 20 ms, granularidad mínima = 0,75 ms:
- Tiempo ideal = 20 / 4 = 5 ms.
- 5 ms > 0,75 ms, así que se usa 5 ms.
- Cada proceso recibe 5 ms.
Si llega un quinto proceso:
- Tiempo ideal = 20 / 5 = 4 ms.
- 4 ms > 0,75 ms, así que se usa 4 ms.
- Cada proceso recibe 4 ms.
Si hay 100 procesos:
- Tiempo ideal = 20 / 100 = 0,2 ms.
- 0,2 ms < 0,75 ms, así que se usa 0,75 ms.
- Cada proceso recibe 0,75 ms. La latencia real es 100 × 0,75 = 75 ms.
La latencia objetivo (20 ms) no se cumple con 100 procesos: la latencia real es 75 ms. Esto es un trade-off: con muchos procesos, la latencia real aumenta porque no se puede dar a cada uno menos que la granularidad mínima.
7. Plazos y garantías
CFS no ofrece garantías de plazo como los sistemas de tiempo real. No hay plazos explícitos ni verificación de planificabilidad. Sin embargo, la latencia objetivo proporciona una garantía informal: cada proceso recibirá la CPU al menos cada T unidades de tiempo (donde T es la latencia objetivo o la latencia real, lo que sea mayor).
Esta garantía es «blanda»: no es formal ni verificable, pero en la práctica proporciona una respuesta razonable para los procesos interactivos.
8. El camino hacia EEVDF
En 2023, Linux introdujo EEVDF (Earliest Eligible Virtual Deadline First) como sucesor de CFS. EEVDF mantiene la idea del vruntime pero añade el concepto de plazo virtual (virtual deadline).
En CFS, el planificador solo mira el vruntime para elegir el siguiente proceso. En EEVDF, mira tanto el vruntime (para equidad) como el plazo virtual (para latencia). Esto permite que EEVDF ofrezca mejores garantías de latencia sin sacrificar la equidad.
EEVDF es una evolución de CFS, no un reemplazo completo. Mantiene la misma estructura (árbol rojinegro, vruntime) pero añade información adicional a cada nodo.
9. Qué es EEVDF
EEVDF (Earliest Eligible Virtual Deadline First) es un algoritmo de planificación que combina la equidad de CFS (vruntime) con la garantía de latencia de EDF (plazos). Cada proceso tiene un vruntime (para equidad) y un plazo virtual (para latencia). El planificador elige el proceso elegible (vruntime ≤ vruntime mínimo) con el plazo virtual más cercano.
El concepto de «elegibilidad» es clave: un proceso es elegible si su vruntime es ≤ el vruntime mínimo de todos los procesos. Esto garantiza que un proceso no se ejecute antes de que le toque (equidad). Entre los procesos elegibles, se elige el que tiene el plazo virtual más cercano (latencia).
EEVDF resuelve un problema de CFS: en CFS, un proceso con vruntime muy bajo (porque esperó mucho) puede acaparar la CPU, perjudicando a otros. EEVDF limita esto con el plazo virtual: un proceso solo puede ejecutarse hasta su plazo virtual.
10. CFS vs EEVDF
| Aspecto | CFS | EEVDF |
|---|---|---|
| Criterio de selección | Menor vruntime | Menor plazo virtual (entre elegibles) |
| Equidad | Sí (vruntime) | Sí (vruntime + elegibilidad) |
| Latencia | Informal (latencia objetivo) | Formal (plazo virtual) |
| Complejidad | Media | Mayor |
| Uso en Linux | Hasta 6.6 | Desde 6.6 |
EEVDF es una evolución, no un reemplazo. Mantiene las mismas estructuras y conceptos, pero añade el plazo virtual para mejorar la latencia.
11. Observar en Linux
# Ver la latencia objetivo
$ cat /proc/sys/kernel/sched_latency_ns
6000000
# Ver la granularidad mínima
$ cat /proc/sys/kernel/sched_min_granularity_ns
750000
# Ver si se usa EEVDF
$ uname -r
6.6.87-microsoft-standard-WSL2
# Ver el vruntime de un proceso
$ grep vruntime /proc/self/sched
vruntime : 12345.6712. Resumen
- CFS mantiene los procesos en un árbol rojinegro ordenado por vruntime.
- La latencia objetivo determina cuánto tiempo se ejecuta cada proceso.
- La granularidad mínima evita cambios de contexto excesivos.
- El tiempo de ejecución se calcula dinámicamente: latencia / n, con mínimo.
- EEVDF es el sucesor de CFS: añade plazos virtuales para mejorar la latencia.
- EEVDF mantiene la equidad (vruntime) y añade latencia (plazo virtual).
- Linux 6.6+ usa EEVDF; versiones anteriores usan CFS.
13. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué estructura de datos usa CFS?
Un árbol rojinegro (red-black tree) ordenado por vruntime.
2. ¿Qué es la latencia objetivo?
El tiempo que CFS intenta que pase entre dos ejecuciones consecutivas del mismo proceso.
3. ¿Qué es la granularidad mínima?
El tiempo mínimo que un proceso puede ejecutarse antes de ser preemptado.
4. ¿Cómo se calcula el tiempo de ejecución?
latencia_objetivo / número_de_procesos, con mínimo de granularidad.
5. ¿Qué es EEVDF?
Earliest Eligible Virtual Deadline First: combina equidad (vruntime) con latencia (plazo virtual).
6. ¿Qué añade EEVDF a CFS?
El concepto de plazo virtual y elegibilidad.
7. ¿Cuándo se usa la granularidad mínima?
Cuando la latencia objetivo / n es menor que la granularidad mínima.
8. ¿Qué parámetro controla la latencia objetivo en Linux?
sched_latency_ns en /proc/sys/kernel/.
9. ¿Qué versión de Linux introdujo EEVDF?
Linux 6.6.
10. ¿Es EEVDF un reemplazo completo de CFS?
No, es una evolución. Mantiene las mismas estructuras y conceptos.
Para practicar
- Calcula el tiempo de ejecución para 4 procesos con latencia 20 ms y granularidad 0,75 ms.
- Explica qué ocurre con 100 procesos.
- Verifica la latencia objetivo de tu sistema con /proc/sys/kernel/sched_latency_ns.
- Investiga cómo se implementa el árbol rojinegro en el código del núcleo.
- Explica la diferencia entre CFS y EEVDF.
- Investiga qué cambios introdujo EEVDF en el código de Linux.