1. Qué es CFS
CFS (Completely Fair Scheduler) es el planificador de la clase fair de Linux (desde el núcleo 2.6.23). Su objetivo es repartir la CPU de forma completamente equitativa entre todos los procesos listos, según sus pesos (prioridades). No usa colas multinivel ni quantums fijos: usa un árbol ordenado por tiempo virtual (vruntime).
CFS fue diseñado por Ingo Molnár para reemplazar al planificador O(1) de Linux, que usaba colas multinivel con 140 prioridades. CFS simplificó el diseño: en lugar de 140 colas, usa un solo árbol ordenado por vruntime.
La idea central de CFS es que cada proceso debería recibir una fracción de la CPU proporcional a su peso. Si dos procesos tienen el mismo peso, cada uno recibe el 50 %. Si uno tiene el doble de peso, recibe el 67 %.
CFS no usa un quantum fijo como Round Robin. En su lugar, calcula dinámicamente cuánto tiempo debe ejecutarse cada proceso para que el vruntime sea equitativo. El tiempo de ejecución depende del número de procesos y de la latencia objetivo.
2. La idea central: reparto equitativo
La idea de CFS es simple: si hay n procesos listos, cada uno debería recibir 1/n de la CPU. Si los procesos tienen pesos distintos, el reparto es proporcional a los pesos.
El problema es que los procesos llegan y salen en momentos distintos, y sus ráfagas son de duraciones distintas. CFS resuelve esto con el tiempo virtual: cada proceso acumula vruntime a medida que se ejecuta, y el proceso con menos vruntime se ejecuta primero.
El vruntime es una medida del «tiempo que el proceso ha recibido, ajustado por su peso». Un proceso que ha recibido mucha CPU tiene mucho vruntime; uno que ha recibido poca tiene poco. El planificador siempre elige el proceso con menos vruntime, lo que garantiza que todos reciban una cantidad equitativa (ajustada por peso).
3. El tiempo virtual (vruntime)
El vruntime (virtual runtime) es un contador que cada proceso acumula a medida que se ejecuta. La velocidad de acumulación depende del peso del proceso: un proceso con mayor peso (nice más bajo) acumula vruntime más lentamente, lo que significa que se ejecuta más antes de que su vruntime alcance el del siguiente proceso.
El vruntime se mide en nanosegundos y se almacena en la PCB del proceso. Se actualiza cada vez que el proceso se ejecuta o se bloquea.
La clave es que el vruntime no es el tiempo real de ejecución: es el tiempo real ajustado por el peso. Un proceso con peso alto «envejece» más lentamente en términos de vruntime, lo que le permite ejecutarse más.
4. La fórmula del vruntime
La fórmula del vruntime es:
vruntime += tiempo_real × (peso_base / peso_proceso)
Donde:
- tiempo_real es el tiempo que el proceso se ejecutó en la CPU.
- peso_base es el peso de referencia (nice 0 = 1024).
- peso_proceso es el peso del proceso (según su nice).
Si el proceso tiene peso 1024 (nice 0), el factor es 1024/1024 = 1: el vruntime aumenta a la misma velocidad que el tiempo real. Si el proceso tiene peso 3121 (nice -5), el factor es 1024/3121 = 0,33: el vruntime aumenta a un tercio de la velocidad del tiempo real. Si el proceso tiene peso 335 (nice +5), el factor es 1024/335 = 3,06: el vruntime aumenta 3 veces más rápido.
Esto significa que un proceso con nice -5 acumula vruntime 3 veces más lento que uno con nice 0, por lo que se ejecuta 3 veces más antes de que su vruntime alcance el del siguiente proceso.
5. Cómo el peso afecta al vruntime
El peso afecta al vruntime de forma inversamente proporcional:
| Nice | Peso | Factor (1024/peso) | Velocidad de acumulación de vruntime |
|---|---|---|---|
| -20 | 88761 | 0,0115 | Muy lenta (acumula poco vruntime) |
| -10 | 9548 | 0,107 | Lenta |
| -5 | 3121 | 0,328 | Lenta |
| 0 | 1024 | 1,000 | Normal (base) |
| +5 | 335 | 3,057 | Rápida |
| +10 | 110 | 9,309 | Muy rápida |
| +19 | 15 | 68,267 | Extremadamente rápida |
Un proceso con nice -20 acumula vruntime 87 veces más lento que uno con nice 0. Esto significa que recibe aproximadamente 87 veces más CPU (en proporción a su peso).
La relación es inversamente proporcional: si el peso se duplica, la velocidad de acumulación se divide por 2, y el proceso recibe el doble de CPU.
6. Un ejemplo desarrollado
Dos procesos, P1 (nice 0, peso 1024) y P2 (nice -5, peso 3121), ambos con ráfaga 6, llegando en 0:
CFS ejecuta el proceso con menos vruntime. Al principio, ambos tienen vruntime 0. Se ejecuta P1 (o P2, desempate por llegada/pid). Supongamos que se ejecuta P1 durante 3 ms:
- P1: vruntime += 3 × (1024/1024) = 3. vruntime = 3.
- P2: vruntime = 0.
Ahora P2 tiene menos vruntime, así que se ejecuta. Se ejecuta P2 durante 3 ms:
- P2: vruntime += 3 × (1024/3121) = 0,98. vruntime = 0,98.
- P1: vruntime = 3.
Ahora P1 tiene más vruntime, así que se ejecuta P2 de nuevo (0,98 < 3). Y así sucesivamente. P2 recibe más tiempo de CPU porque su vruntime crece más lento.
El resultado es que P2 (nice -5) termina antes que P1 (nice 0), aunque ambos tengan la misma ráfaga. P2 recibió más CPU en cada «turno».
7. Cómo se selecciona el siguiente proceso
CFS selecciona el proceso con el menor vruntime. Para hacer esto eficientemente, mantiene los procesos en un árbol rojinegro (red-black tree) ordenado por vruntime. El proceso con el menor vruntime está en el extremo izquierdo del árbol (el mínimo).
La selección del siguiente proceso es O(1): basta con tomar el mínimo del árbol. La inserción y eliminación son O(log n).
Cuando un proceso se ejecuta, su vruntime aumenta. Si su vruntime supera el del siguiente proceso en el árbol, el planificador puede interrumpirlo (si se le acaba el tiempo de ejecución calculado) y seleccionar el siguiente.
El tiempo de ejecución se calcula dinámicamente para que el vruntime sea equitativo: si hay n procesos y la latencia objetivo es T, cada proceso recibe T/n de tiempo de CPU. Si T/n es menor que la granularidad mínima, se usa la granularidad mínima.
8. Propiedades de CFS
| Propiedad | ¿La cumple? | Comentario |
|---|---|---|
| Reparto equitativo | Sí | Proporcional a los pesos. |
| Sin quantum fijo | Sí | El tiempo de ejecución se calcula dinámicamente. |
| Eficiencia | Sí | O(log n) para inserción/eliminación, O(1) para selección. |
| Sin inanición | Sí | Todo proceso con vruntime finito se ejecuta eventualmente. |
| Adaptabilidad | Sí | Se adapta automáticamente al número de procesos. |
| Necesita conocer ráfagas | No | No predice ráfagas. |
9. Ventajas
- Reparto equitativo: todos los procesos reciben una fracción de CPU proporcional a su peso.
- Sin quantum fijo: el tiempo de ejecución se adapta al número de procesos.
- Eficiencia: O(log n) para inserción/eliminación.
- Sin inanición: el vruntime garantiza que todos se ejecuten.
- Simplicidad conceptual: un solo árbol, una sola métrica (vruntime).
- Uso real: es el planificador de la clase fair de Linux.
10. Simulador interactivo
Este simulador muestra cómo CFS reparte la CPU entre dos procesos con nice distintos. Observa cómo el vruntime crece a diferente velocidad:
Simulador · CFS (vruntime)
| Proceso | Nice | Peso | vruntime acumulado | Tiempo de CPU | Fracción |
|---|
11. Resumen
- CFS reparte la CPU de forma equitativa según los pesos de los procesos.
- El vruntime es el tiempo virtual: se acumula a velocidad inversamente proporcional al peso.
- El proceso con menos vruntime se ejecuta primero.
- Los procesos se mantienen en un árbol rojinegro ordenado por vruntime.
- El tiempo de ejecución se calcula dinámicamente según el número de procesos y la latencia objetivo.
- Sin quantum fijo: se adapta automáticamente.
- Sin inanición: el vruntime garantiza que todos se ejecuten.
- CFS es el planificador de la clase fair de Linux desde 2.6.23.
12. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué es CFS?
Completely Fair Scheduler: el planificador de la clase fair de Linux que reparte la CPU de forma equitativa según los pesos.
2. ¿Qué es el vruntime?
El tiempo virtual: un contador que se acumula a medida que el proceso se ejecuta, a velocidad inversamente proporcional a su peso.
3. ¿Cómo afecta el peso al vruntime?
Mayor peso = acumulación más lenta = más CPU. vruntime += tiempo_real × (1024 / peso).
4. ¿Qué proceso se ejecuta primero en CFS?
El que tiene menos vruntime.
5. ¿Qué estructura de datos usa CFS?
Un árbol rojinegro (red-black tree) ordenado por vruntime.
6. ¿Tiene CFS un quantum fijo?
No. El tiempo de ejecución se calcula dinámicamente.
7. ¿Por qué un proceso con nice -5 «envejece» más lento?
Porque su peso es mayor, así que su vruntime crece más lentamente. Acumula menos vruntime por unidad de tiempo real.
8. ¿Cómo se calcula el tiempo de ejecución en CFS?
latencia_objetivo / número_de_procesos, con un mínimo (granularidad mínima).
9. ¿CFS sufre inanición?
No. El vruntime garantiza que todo proceso con vruntime finito se ejecuta eventualmente.
10. ¿Qué reemplazó CFS?
El planificador O(1) de Linux (que usaba colas multinivel con 140 prioridades).
Para practicar
- Calcula el vruntime de un proceso con nice -5 que se ejecuta 10 ms.
- Explica por qué CFS no tiene quantum fijo.
- Compara el vruntime de dos procesos con nice 0 y nice 10 tras ejecutarse 5 ms cada uno.
- Investiga cómo se implementa el árbol rojinegro en CFS.
- Explica cómo la latencia objetivo afecta al tiempo de ejecución.
- Modifica el simulador para añadir un tercer proceso con nice distinto.