CFS i EEVDF
vruntime i el slice de CFS amb els pesos reals del kernel.| Versió | Any | Planificador | Idea clau |
|---|---|---|---|
| 2.4 | 2001 | O(n) | Èpoques; a cada decisió es recorren tots els preparats |
| 2.6.0 | 2003 | O(1) | 140 cues de prioritat i heurístiques d’interactivitat |
| 2.6.23 | 2007 | CFS | Repartiment proporcional amb vruntime; apareixen les classes de planificació |
| 3.14 | 2014 | SCHED_DEADLINE |
Temps real per terminis |
| 6.6 | 2023 | EEVDF | Substitueix la selecció de CFS; es completa a la 6.12 |
| 6.12 | 2024 | sched_ext |
Planificadors escrits en BPF |
SCHED_FIFO i SCHED_RR existeixen des de molt abans i conviuen amb tots aquests planificadors.SCHED_FIFO i SCHED_RRSCHED_FIFO: s’executa fins que es bloqueja, acaba o arriba un procés de prioritat més alta. No té quantum.SCHED_RR: igual, però amb quantum entre processos de la mateixa prioritat (per defecte 100 ms).Un procés SCHED_FIFO sí que pot ser expulsat, per un procés de temps real més prioritari. El que no té és quantum: entre processos de la mateixa prioritat, no cedeix la CPU per temps.
nice −20 → 100, nice 19 → 139).Quantum segons la prioritat estàtica: nice −20 → 800 ms · nice 0 → 100 ms · nice 19 → 5 ms.
Prioritat dinàmica segons el temps que el procés passa dormint (sleep_avg):
\[\text{prioritat} = \text{estàtica} - (\text{bonus} - 5), \qquad \text{bonus} \in [0, 10]\]
És una MLFQ: prioritat que puja o baixa segons el comportament. I té els mateixos problemes: les heurístiques es poden enganyar (com l’Othello) i és difícil ajustar-les.
vruntime: el temps de CPU rebut, ponderat pel pes.vruntime = pass de l’stride. Triar el vruntime mínim = triar el pass mínim. La diferència: CFS mesura temps real executat (en nanosegons), no quanta.
vruntime i pesosCada vegada que un procés s’executa durant \(\Delta t\):
\[v_i \mathrel{+}= \Delta t \cdot \frac{1024}{w_i}\]
vruntime només avança mentre el procés s’executa: dormint o esperant no canvia.nice 0: per a un procés de nice 0, el vruntime avança com el temps real.nice |
−10 | −5 | 0 | 1 | 5 | 10 | 19 |
|---|---|---|---|---|---|---|---|
| Pes \(w\) | 9548 | 3121 | 1024 | 820 | 335 | 110 | 15 |
| \(1024/w\) | 0.11 | 0.33 | 1 | 1.25 | 3.06 | 9.31 | 68.3 |
nice multiplica el pes per ≈ 1.25: ≈ 10 % de CPU respecte d’un veí.nice 5 no fa avançar el vruntime el doble de ràpid: el fa avançar 3.06 vegades més ràpid. Feu servir sempre la taula de pesos.
nice 0, \(w = 1024\))nice 5, \(w = 335\)).| Tick | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(v_A\) | 0 | 1 | 1 | 2 | 3 | 4 | 4 | 5 | 6 | 7 | 7 | 8 |
| \(v_B\) | 0 | 0 | 3.06 | 3.06 | 3.06 | 3.06 | 6.11 | 6.11 | 6.11 | 6.11 | 9.17 | 9.17 |
| Executa | A | B | A | A | A | B | A | A | A | B | A | A |
CFS no assigna prioritats dinàmiques com O(1), sinó que utilitza un comptador que permet comparar el servei rebut per cada procés.
CFS no té un quantum fix. Fixa un període (latència objectiu) i el reparteix proporcionalment:
\[\text{slice}_i = \text{període} \cdot \frac{w_i}{\sum_j w_j}, \qquad \text{període} = \max\!\left(\text{sched_latency},\ n \cdot \text{min_granularity}\right)\]
sched_latency: latència objectiu per donar oportunitat d’execució als processos.
min_granularity: temps mínim d’execució.
n: nombre de processos preparats.
Valors base: sched_latency = 6 ms i min_granularity = 0.75 ms (el kernel els escala segons el nombre de CPU).
Amb molts processos, el període creix: cap slice baixa de min_granularity, per limitar els canvis de context.
nice 0, 0 i 5Si un procés nou comencés amb vruntime = 0, executaria fins a atrapar tots els altres.
min_vruntime: el mínim de la cua, que mai no decreix.min_vruntime i, a més, se li suma un slice (START_DEBIT): s’incorpora al final de la ronda.És una referència global del progrés dels processos de la cua de planificació. Representa el valor mínim de vruntime i serveix per evitar que els processos nous o que es desperten comencin en una posició excessivament avantatjosa.
Si fos així, n’hi hauria prou amb fer fork() repetidament per monopolitzar la CPU.
Dos paràmetres independents: el pes (quanta CPU) i la mida de la petició (cada quant temps). És exactament el que separa WF²Q: el pes del flux i la mida dels paquets.
Stoica i Abdel-Wahab (1995). Linux el fa servir des de la 6.6 (completat a la 6.12).
\[vd_i = ve_i + \frac{r_i}{w_i}\]
Un procés és elegible si \(ve_i \le V(t)\). D’entre els elegibles, s’executa el de \(vd\) mínim.
\[ \operatorname{lag}_i(t) = \underbrace{S_i^{\mathrm{ideal}}(t)}_{\text{servei a la CPU ideal}} - \underbrace{s_i(t)}_{\text{servei rebut}} \]
| Situació | Regla |
|---|---|
| Ritme del temps virtual | \(dV/dt = 1/\sum w_{\text{actius}}\) |
| Arribada d’un procés a l’instant \(t\) | \(ve = V(t)\) |
| Nova petició en acabar-ne una | \(ve_{nou} = vd_{anterior}\) |
| Deadline | \(vd = ve + r/w\) |
| Elecció | \(vd\) mínim entre els que tenen \(ve \le V(t)\) |
L’error més freqüent és triar directament el \(vd\) mínim. Primer descarta els processos amb \(ve > V(t)\).
Suposa:
Fes la planificació de \(t=0\) fins a \(t=5\).
A (\(w = 1\), \(r = 1\)) i B (\(w = 3\), \(r = 1\)) arriben a \(t = 0\) i fan peticions contínuament. Empats: B.
| \(t\) | \(V\) | A: \(ve\) | A: \(vd\) | B: \(ve\) | B: \(vd\) | Elegibles | Executa |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 1/3 | A, B | B |
| 1 | 1/4 | 0 | 1 | 1/3 | 2/3 | A | A |
| 2 | 1/2 | 1 | 2 | 1/3 | 2/3 | B | B |
| 3 | 3/4 | 1 | 2 | 2/3 | 1 | B | B |
| 4 | 1 | 1 | 2 | 1 | 4/3 | A, B | B |
| 5 | 5/4 | 1 | 2 | 4/3 | 5/3 | A | A |
Mateix pes, peticions diferents. B (càlcul, \(r = 4\) ms) s’està executant: \(ve_B = 8\), \(vd_B = 12\). A \(V = 10\) es desperta A, amb lag 0: \(ve_A = V = 10\).
| Petició d’A | \(vd_A = 10 + r_A\) | Comparació amb \(vd_B = 12\) | Què passa |
|---|---|---|---|
| \(r_A = 1\) ms | 11 | 11 < 12 | A va primer |
| \(r_A = 4\) ms | 14 | 14 > 12 | A espera que B acabi la petició |
| Paper | Kernel de Linux (6.6+) |
|---|---|
| \(V(t)\) integrat | Mitjana dels vruntime ponderada pels pesos (avg_vruntime) |
| \(ve_i\) | vruntime del procés; elegible si vruntime \(\le V\) |
| \(vd_i = ve_i + r_i/w_i\) | deadline = vruntime + slice \(\cdot 1024/w_i\) |
| Mida de la petició \(r_i\) | Slice: per defecte ≈ 0.75 ms (escalat segons el nombre de CPU) |
| Arribada amb \(ve = V\) | Un procés nou comença a avg_vruntime (lag 0) |
| Lag conservat en dormir | El lag es guarda en dormir i es restaura en despertar (acotat) |
sched_setattr() (camp sched_runtime, entre 0.1 i 100 ms).| CFS | EEVDF | |
|---|---|---|
| Model | Repartiment proporcional (stride) | Repartiment proporcional + deadlines (WF²Q) |
| Tria | vruntime mínim |
Deadline virtual mínim entre els elegibles |
| Quanta CPU | Pes | Pes |
| Cada quant | Pes (i heurístiques de despertar) | Mida de la petició |
| Justícia | Sense cota formal | Lag acotat |
| Processos que dormen | Crèdit de mitja latència | Es conserva el lag |
EEVDF continua sent un planificador de repartiment proporcional per a processos normals. Les garanties de temps real a Linux són SCHED_FIFO, SCHED_RR i SCHED_DEADLINE.
Quan el kernel ha de triar, pregunta a les classes per ordre. La primera que té un procés preparat, guanya.
| Ordre | Classe | Polítiques |
|---|---|---|
| 1 | stop | Fils interns del kernel (migració entre CPU) |
| 2 | deadline | SCHED_DEADLINE |
| 3 | rt | SCHED_FIFO, SCHED_RR |
| 4 | fair | SCHED_OTHER (= SCHED_NORMAL), SCHED_BATCH, SCHED_IDLE → CFS / EEVDF |
| 5 | ext | SCHED_EXT (6.12+, planificadors en BPF) |
| 6 | idle | Fil ociós de la CPU |
sched_ext.nice i prioritat dinàmica per heurística. És una MLFQ i en té els problemes.vruntime mínim; els nous comencen a min_vruntime.sched_ext.