Vam tancar la lliçó anterior amb una pregunta oberta: hi ha deu processos en estat R i quatre nuclis, a quin se li dona la CPU i durant quant de temps? Aquesta decisió es pren a meteo-01 uns quants milers de vegades per segon, i d'ella depèn que una consulta a meteo-api respongui en 8 ms o en 400 ms, que l'ingestor no perdi lectures i que l'agregador acabi les seves mitjanes horàries abans de l'hora següent.

En aquesta lliçó entendràs per què cal planificar, quins criteris entren en conflicte (perquè no es poden optimitzar tots alhora), com funcionen els algorismes clàssics —calculant-los tu mateix sobre paper, que és l'única manera d'entendre'ls de debò— i què fa realment el planificador de Linux quan executes renice. En acabar sabràs decidir amb criteri quina prioritat mereix cada procés de Meteora i per què.

1. Per què cal planificar: el cicle de ràfegues
2. Processos limitats per CPU i per E/S
3. Els tres planificadors i el despatxador
4. Criteris d'avaluació i els seus compromisos
5. Planificació apropiativa davant de cooperativa
6. FCFS: primer a arribar, primer a servir-se
7. SJF i SRTF: la feina més curta primer
8. Planificació per prioritats, inanició i envelliment
9. Round Robin i l'efecte del quantum
10. Cues multinivell i cues amb realimentació
11. El planificador real de Linux: CFS, EEVDF i nice
12. Polítiques de temps real: SCHED_FIFO, SCHED_RR, SCHED_DEADLINE
13. Multiprocessador: afinitat i balanceig de càrrega

Cap procés no fa servir la CPU de manera contínua. Si observes el que fa l'ingestor, hi veuràs un patró que es repeteix:

Cada tram de càlcul és una ràfega de CPU i cada espera és una ràfega d'E/S. Tot procés alterna entre totes dues fins que acaba. Aquesta observació, que sembla trivial, és la base de tota la planificació:

• Si un procés només fes servir la CPU, n'hi hauria prou d'executar-lo fins al final. No caldria planificar res.
• Com que es bloqueja constantment esperant E/S, deixa la CPU lliure, i seria un malbaratament no donar-la a un altre mentrestant.

La distribució de les ràfegues de CPU en sistemes reals és molt característica: moltíssimes ràfegues curtes i poquíssimes de llargues. En una càrrega típica, el 70-80 % de les ràfegues dura menys de 8 ms. Això té una conseqüència enorme que veurem en parlar de Round Robin: si tries bé el quantum, la majoria de processos acaben la seva ràfega abans d'exhaurir-lo i es bloquegen sols, sense que calgui apropiar-los la CPU.

Els processos es classifiquen segons quin tipus de ràfega hi domina:

Aquesta classificació no és acadèmica: és la que dicta la decisió operativa. Tornem a les dades reals que vam veure a 02-01:

La lectura és directa:

• ingestor (1842): 94.013 bloquejos voluntaris davant de 118 apropiacions. Ràtio de 796 a 1. Fortament limitat per E/S: gairebé sempre està esperant paquets de les estacions.
• meteo-api (1901): ràtio de 4.792 a 1. Encara més extrem. Espera peticions HTTP.
• agregador (1877): ràtio de 63 a 1. Continua havent-hi E/S (llegeix fitxers de /var/lib/meteora/lectures/), però passa molt més temps calculant.

Un bon planificador afavoreix els processos limitats per E/S. Pot sonar contraintuïtiu —per què prioritzar el que menys CPU fa servir?—, però la lògica és sòlida: si dones la CPU a l'ingestor tan bon punt arriben dades, la fa servir 0,3 ms i es torna a bloquejar, alliberant-la gairebé de seguida. El cost d'atendre'l aviat és mínim i el benefici és que el dispositiu de xarxa torna a estar ocupat. Si en canvi dones la CPU a l'agregador, la reté mil·lisegons sencers mentre l'ingestor acumula lectures sense processar i les memòries intermèdies de xarxa s'omplen.

La regla general: prioritzar el que és curt manté tots els recursos ocupats en paral·lel.

Un sistema operatiu complet no pren una sola decisió de planificació, sinó tres, en escales de temps molt diferents:

• El de llarg termini ve dels sistemes per lots dels anys 60 (els vam veure a 01-02): amb memòria escassíssima, calia decidir quantes feines admetre simultàniament. En un Linux modern no existeix: qualsevol pot llançar un procés fins a exhaurir recursos. El més semblant són els límits de cgroups (mòdul 6) i els sistemes de cues tipus Slurm en supercomputació.
• El de mitjà termini sí que existeix: quan falta memòria, el nucli expulsa pàgines de processos inactius a swap. Ho veurem a Memòria Virtual i Paginació.
• El de curt termini és del qual parla aquesta lliçó. Actua cada pocs mil·lisegons, i per això el seu propi codi ha de ser extremadament ràpid: si trigués 1 ms a decidir, es menjaria el 25 % d'un quantum de 4 ms.

El despatxador (dispatcher) és el component que executa la decisió: fa el canvi de context que vam estudiar a 02-01, canvia a mode usuari i salta a la instrucció on el procés escollit s'havia quedat. El seu temps de feina s'anomena latència de despatx, i a Linux és de l'ordre d'1-3 µs.

Per comparar algorismes calen mètriques. Aquestes són les cinc clàssiques:

Les relacions entre ells:

El temps d'espera és la mètrica que es fa servir per comparar algorismes perquè és l'única part en què el planificador pot influir: el temps de CPU i el d'E/S els fixa la feina mateixa, no la planificació.

I aquí hi ha l'important: aquests criteris es contradiuen entre si. No existeix cap algorisme que els optimitzi tots.

A Meteora això és una decisió de negoci, no tècnica: si optimitzes la productivitat total, l'agregador acabarà abans però meteo-api respondrà amb pics de latència. Si optimitzes el temps de resposta, l'API va fina i l'agregador triga més a tancar l'hora. Cal triar, i triar requereix saber què fa més mal si falla.

Ja vam introduir totes dues a 01-03. Ara podem precisar quan pot actuar el planificador. Hi ha quatre moments:

1. El procés passa d'Executant a Bloquejat (demana E/S).
2. El procés passa d'Executant a Preparat (s'exhaureix el quantum, arriba una interrupció).
3. El procés passa de Bloquejat a Preparat (acaba la seva E/S).
4. El procés acaba.

Si el planificador només actua en els casos 1 i 4 —quan el procés amolla la CPU per voluntat pròpia—, és cooperatiu (o no apropiatiu). Si també actua en el 2 i el 3, és apropiatiu.

L'apropiació és el que fa possible que a meteo-01 un agregador amb un bucle mal escrit no bloquegi tota la màquina. El preu que s'ha de pagar és que les dades compartides entre processos poden quedar en estats inconsistents si se'ls interromp a mitges, i aquest preu és exactament el que estudiarem al mòdul 3.

El més simple: una cua FIFO. El primer que arriba és el primer que s'executa, i fins que no acaba la seva ràfega no n'entra un altre. És no apropiatiu.

Treballem amb aquest conjunt de processos, que reutilitzarem en tots els algorismes:

Diagrama de Gantt amb FCFS:

Càlcul pas a pas:

Ara invertim l'ordre d'arribada: que arribin primer P2 i P3, i P1 al final.

De 16 ms a 2 ms sense canviar l'algorisme, només l'ordre d'arribada. Aquesta sensibilitat extrema és el gran defecte de FCFS.

El fenomen té nom: efecte comboi. Un procés llarg limitat per CPU ocupa el processador, i al darrere s'hi acumula una filera de processos curts limitats per E/S que només necessitarien uns microsegons. Mentre esperen, els dispositius d'E/S estan ociosos, perquè els processos que els farien servir són a la cua.

En termes de Meteora: si l'agregador arrenca el seu càlcul horari de 24 ms i al darrere s'hi posen a la cua 40 peticions a meteo-api de 0,5 ms cadascuna, l'última espera 24 ms per fer una feina de mig mil·lisegon. I durant aquests 24 ms, la targeta de xarxa no té res per enviar.

La imatge mental és exacta: un camió lent en una carretera d'un sol carril amb 40 cotxes al darrere.

Si el problema és que els llargs bloquegen els curts, la solució òbvia és executar primer el més curt. Això és SJF (Shortest Job First).

Amb els nostres processos i suposant que tots han arribat en t=0:

Mitjana d'espera: 2,00 ms. I això no és casualitat:

SJF és demostrablement òptim: cap algorisme no pot donar un temps mitjà d'espera menor per a un conjunt donat de processos.

La intuïció de la demostració: si un procés llarg va abans que un de curt, intercanviar-los redueix molt l'espera del curt i augmenta poc la del llarg. Repetint l'intercanvi s'arriba a l'ordre ascendent.

SRTF (Shortest Remaining Time First) hi afegeix apropiació: si arriba un procés la ràfega del qual és menor que el que li queda a l'actual, se li treu la CPU.

Un exemple amb arribades esglaonades:

Simulació instant a instant:

• t=0: només A. Executa A (li'n queden 8).
• t=1: arriba B amb 4 < 7 restants d'A. Apropiació: entra B.
• t=2: arriba C amb 9 > 3 restants de B. Continua B.
• t=3: arriba D amb 5 > 2 restants de B. Continua B.
• t=5: B acaba. Candidats: A (7), C (9), D (5). Entra D.
• t=10: D acaba. Candidats: A (7), C (9). Entra A.
• t=17: A acaba. Entra C.
• t=26: C acaba.

Comparat amb FCFS sobre el mateix conjunt (que donaria 7,75 ms) és millor, i SRTF és òptim entre els apropiatius.

Requereix conèixer la durada de la ràfega següent, que és el futur. No hi ha manera de saber-la.

La solució pràctica és estimar-la a partir de l'historial, amb una mitjana exponencial:

on t(n) és la durada real de l'última ràfega, τ(n) l'estimació anterior i α un pes entre 0 i 1 (típicament 0,5).

Exemple numèric amb α = 0,5 i estimació inicial τ = 10:

Observa el comportament: l'estimació convergeix suaument i reacciona davant del canvi brusc de l'última ràfega sense disparar-se del tot. Amb α = 1 només comptaria l'última ràfega (molt reactiu, molt inestable); amb α = 0 no canviaria mai.

Segon problema de SJF: inanició. Un procés llarg pot no executar-se mai si no paren d'arribar processos curts. En un sistema amb meteo-api rebent peticions constants, l'agregador podria no arrencar mai.

S'assigna un número de prioritat a cada procés i es tria el de prioritat més alta. SJF és en realitat un cas particular: la prioritat és la inversa de la durada de la ràfega.

Amb aquest conjunt (menor número = major prioritat, convenció habitual):

Les prioritats es poden assignar per criteris interns (mida de memòria, ràtio d'E/S, temps consumit) o externs (importància de l'usuari, diners pagats, criticitat del servei).

El problema és el mateix que a SJF: un procés de prioritat baixa pot esperar indefinidament. L'anècdota clàssica —potser apòcrifa, però molt il·lustrativa— explica que en apagar l'IBM 7094 de l'MIT el 1973 hi van trobar una feina de prioritat baixa enviada el 1967 que mai no va arribar a executar-se.

La solució és l'envelliment (aging): incrementar gradualment la prioritat dels processos que fa molt de temps que esperen.

Amb aquesta regla, cap procés no espera més de 14 segons per molt baixa que sigui la seva prioritat. L'envelliment converteix una garantia impossible ("tots s'executen") en una d'acotada ("ningú no espera més de X"), que és la mena de garantia amb què sí que es pot treballar.

Round Robin és FCFS amb apropiació per temps: cada procés rep un quantum fix; si no acaba, torna al final de la cua.

Amb els nostres tres processos originals (P1=24, P2=3, P3=3) i quantum = 4 ms:

Pitjor que SJF (2,00 ms), però moltíssim millor que FCFS (16,00 ms). I, sobretot, amb una propietat que els altres no tenen: el temps de resposta està acotat. Amb n processos i quantum q, cap no espera més de (n−1)·q per al seu primer torn. Amb 10 processos i q=4 ms, la pitjor espera és de 36 ms. Això és una garantia útil per a un sistema interactiu.

Triar q és un compromís directe:

Amb el cost de canvi de context de 5 µs que vam calcular a 02-01:

La regla pràctica: el quantum ha de ser prou gran perquè el 80 % de les ràfegues de CPU acabin dins seu. Com que la majoria de ràfegues duren menys de 8 ms, un quantum d'aquesta magnitud aconsegueix que la majoria de processos es bloquegin sols i que l'apropiació sigui l'excepció, no la norma.

Un matís important: el temps de retorn no millora monòtonament en reduir el quantum. Pot empitjorar, perquè un procés que necessitaria 7 ms seguits amb q=7 acaba d'una tirada, i amb q=2 necessita quatre torns repartits.

Els algorismes anteriors tracten tots els processos igual. A la realitat no ho són: un procés interactiu i un procés per lots necessiten polítiques diferents.

A les cues multinivell, la cua de preparats es divideix en diverses cues, cadascuna amb el seu propi algorisme:

Entre cues es planifica normalment per prioritat absoluta: no s'executa res de la cua 2 si hi ha alguna cosa a la 0 o a la 1. Això és ràpid però causa inanició. L'alternativa és repartir percentatges de CPU: 60 % a la cua 0, 25 % a la 1, 10 % a la 2 i 5 % a la 3.

El problema de les cues multinivell pures: un procés queda fixat a la seva cua per sempre, i la seva naturalesa pot canviar. L'agregador és limitat per CPU mentre calcula, però limitat per E/S mentre llegeix fitxers.

Les cues multinivell amb realimentació (multilevel feedback queue) resolen això permetent que els processos pugin i baixin de cua segons el seu comportament observat:

La lògica és elegant:

• Tot procés comença a dalt, amb la màxima prioritat i el quantum més curt.
• Si exhaureix el seu quantum sense bloquejar-se, és senyal que està limitat per CPU: baixa una cua, on tindrà menys prioritat però un quantum més llarg (que és el que li convé).
• Si es bloqueja per E/S abans d'exhaurir-lo, és interactiu: es manté o puja.
• L'envelliment puja els processos que fa molt que esperen a baix, evitant la inanició.

Aquest esquema dedueix del comportament el que no pot saber per endavant: aproxima SJF sense necessitat d'endevinar el futur. Va ser el disseny dels planificadors dels UNIX tradicionals, de Windows NT i del planificador O(1) de Linux fins al 2007.

Linux va abandonar l'enfocament de cues amb realimentació a la versió 2.6.23 (2007) pel CFS (Completely Fair Scheduler), i des de la 6.6 (2023) per EEVDF (Earliest Eligible Virtual Deadline First), que refina la mateixa idea.

El punt de partida del CFS és diferent i molt potent: en lloc de quàntums fixos i cues, modela quanta CPU li correspondria a cada procés en una màquina ideal i corregeix la desviació.

• Si hi ha n processos executables, cadascun hauria de tenir 1/n de la CPU.
• CFS porta el compte del temps virtual d'execució (vruntime) de cada procés: el temps de CPU que ha consumit, ponderat per la seva prioritat.
• Sempre tria el procés amb el vruntime més baix, és a dir, el que va més endarrerit respecte a la seva part justa.
• Els processos s'emmagatzemen en un arbre roig-negre ordenat per vruntime, així que triar el següent és agafar el node de més a l'esquerra: O(1) a la pràctica, O(log n) en inserir.

La conseqüència bonica: un procés que es bloqueja per E/S no acumula vruntime mentre espera, així que quan es desperta té el vruntime més baix de tots i s'executa immediatament. Els processos interactius obtenen bona resposta sense cap heurística especial: surt de franc del model.

El valor nice va de −20 (màxima prioritat) a +19 (mínima), amb 0 per defecte. El nom ve de "com d'amable ets amb els altres": un nice alt significa que cedeixes el pas.

A CFS, nice no dona torns extra: modifica el ritme al qual avança el vruntime.

Cada unitat de nice canvia el pes en un factor d'aproximadament 1,25, cosa que es tradueix en una regla molt fàcil de recordar:

Cada punt de nice canvia la quota de CPU al voltant d'un 10 %.

Aplicat a Meteora:

Què fa cada ordre:

• renice -n 10 -p 1877 rebaixa l'agregador a nice 10. Ara, competint amb meteo-api (nice 0), rebrà aproximadament un 9,7 % de la CPU quan tots dos vulguin executar-se. Quan meteo-api estigui bloquejat esperant peticions —que és gairebé sempre—, l'agregador farà servir el 100 %. Aquesta és la clau que molta gent no capta: nice no limita el consum, només decideix qui cedeix en cas de conflicte. Per limitar de debò calen cgroups (06-02).
• nice -n 15 ... llança el reprocessament històric amb prioritat mínima. És l'ordre correcta per a feines pesades que no han de molestar: consumirà tota la CPU sobrant i s'apartarà a l'instant tan bon punt arribi una petició.
• Abaixar el nice (valors negatius) requereix privilegis de root, perquè altrament qualsevol usuari podria monopolitzar el sistema.

Un avís important sobre nice que gairebé sempre agafa desprevingut: només afecta la CPU. Si l'agregador satura el disc llegint /var/lib/meteora/lectures/, renice no arreglarà res. Per a això existeix ionice, que veurem a Gestió d'Emmagatzematge.

Linux implementa diverses polítiques de planificació que conviuen. nice només s'aplica a la primera:

Regla d'or: qualsevol procés de temps real desplaça tots els normals. Un SCHED_FIFO de prioritat 1 s'executa abans que un SCHED_OTHER de nice −20.

Amb això l'ingestor passa a SCHED_FIFO amb prioritat 10: tan bon punt tingui un paquet per processar, desplaça agregador i meteo-api immediatament.

És bona idea? Amb matisos. SCHED_FIFO és adequat aquí perquè l'ingestor està limitat per E/S: fa servir la CPU 0,3 ms i es bloqueja. Però comporta un perill real: un SCHED_FIFO que entri en un bucle infinit bloqueja el seu nucli per complet, i no podràs ni obrir un intèrpret d'ordres per matar-lo. Linux es protegeix parcialment amb:

Els processos de temps real poden fer servir com a màxim 950.000 µs de cada 1.000.000 µs, és a dir el 95 %. El 5 % restant queda reservat perquè el sistema continuï sent administrable. És una xarxa de seguretat dissenyada exactament per a l'escenari del bucle infinit.

SCHED_DEADLINE és més modern i més segur: en lloc d'una prioritat, declares "necessito 2 ms de còmput cada 10 ms, amb termini als 8 ms" i el nucli rebutja la petició si no ho pot garantir. El detall d'aquestes garanties correspon a Sistemes Operatius Mòbils i de Temps Real.

meteo-01 té 4 nuclis, així que en realitat cal decidir quin procés i en quin nucli.

Linux manté una cua d'execució per nucli, no una de global. És una decisió deliberada: una cua global necessitaria un forrellat compartit per tots els nuclis, i aquest forrellat es convertiria en el coll d'ampolla del sistema amb 64 o 128 nuclis.

Dos conceptes governen el repartiment:

Afinitat de processador. Quan un procés fa una estona que és al nucli 2, les memòries cau L1 i L2 d'aquest nucli són plenes de les seves dades. Migrar-lo al nucli 3 significa començar en fred: centenars de fallades de memòria cau a ~100 ns cadascuna. Per això el planificador prefereix mantenir cada procés on era (afinitat tova), i només el migra quan el desequilibri ho justifica.

L'afinitat dura es fixa a mà:

Amb això has particionat la màquina: l'agregador només pot fer servir els nuclis 2 i 3, i l'ingestor el 0 i l'1. Ni tan sols competeixen. És una tècnica vàlida quan coneixes bé la càrrega, i es fa servir molt en sistemes de baixa latència, però té un cost: si l'ingestor està ociós, els seus dos nuclis es malbaraten perquè l'agregador no els pot tocar. L'afinitat dura canvia flexibilitat per previsibilitat.

Balanceig de càrrega. Periòdicament, el nucli comprova si unes cues estan molt més carregades que d'altres i migra processos. Ho fa tenint en compte la topologia: migrar entre dos nuclis que comparteixen memòria cau L3 és barat; migrar entre dos sòcols NUMA diferents és car, perquè a més de la memòria cau freda, el procés quedaria accedint a memòria d'un altre sòcol.

Interpretació: la columna %nice mesura el temps consumit per processos amb nice positiu. Aquest 16,8 % al nucli 2 és exactament l'agregador amb el seu nice 10, i confirma que l'afinitat està fent el que li demanem. El %iowait baix indica que el disc no és el coll d'ampolla avui.

Creure que nice limita el consum de CPU. No ho fa. Un procés amb nice 19 farà servir el 100 % de la CPU si ningú més no la vol. nice només decideix qui cedeix en cas de conflicte. Per posar-hi un sostre real necessites cgroups (CPUQuota a systemd), tema de 06-02.

Posar processos en SCHED_FIFO "per si de cas". És la manera més ràpida de deixar una màquina inaccessible. Només té sentit per a processos que es bloquegen amb freqüència i de manera demostrada. I abans de fer-ho, prova amb nice -20: gairebé sempre n'hi ha prou.

Confondre la prioritat PRI amb NI. NI és el que tu demanes; PRI és el que el nucli calcula a partir d'això. A més, ps mostra PRI amb una escala invertida respecte a la interna del nucli, cosa que despista molt. Per saber què passa, mira NI i la política (chrt -p).

Aplicar el diagrama de Gantt de l'examen a la realitat. Els exercicis assumeixen una ràfega per procés i cap E/S. A la realitat cada procés alterna desenes de ràfegues, entren i surten processos nous i hi ha diversos nuclis. Els càlculs serveixen per entendre els algorismes, no per predir temps reals.

Buscar l'algorisme òptim. No existeix. SJF minimitza l'espera mitjana però causa inanició i necessita endevinar el futur. Round Robin acota la resposta però empitjora la mitjana. La pregunta correcta mai no és "quin és millor", sinó "què em fa més mal si va malament: la latència de meteo-api o el retard de l'agregador".

Oblidar que un procés bloquejat no competeix. És l'error de raonament més freqüent en analitzar càrrega real. Si meteo-api està el 99 % del temps esperant peticions, donar-li nice -10 gairebé no canvia res, perquè quan vol CPU normalment està lliure.

Consell pràctic: abans de tocar prioritats, comprova que la CPU és de debò el problema. Mira %iowait a mpstat i la columna b de vmstat: si hi ha processos bloquejats i %iowait alt, el coll d'ampolla és el disc i cap prioritat de CPU no ho arreglarà.

A meteo-01 arriben aquestes quatre feines:

Calcula el diagrama de Gantt i el temps mitjà d'espera per a: (a) FCFS, (b) SJF no apropiatiu, (c) SRTF, (d) Round Robin amb quantum 3 ms. Després indica quin algorisme triaries per a Meteora i per què.

A meteo-01 (4 nuclis) tens aquesta situació durant el pic de les 8:00, quan les estacions envien la seva ràfega matinal:

• ingestor: rep 800 lectures/segon. Si la seva memòria intermèdia de socket s'omple, es perden lectures irrecuperablement.
• meteo-api: 40 peticions/segon, amb un objectiu de servei de 200 ms al percentil 99.
• agregador: calcula les mitjanes de l'hora anterior. Ha d'acabar abans de les 9:00.
• backup-diari: comprimeix /var/lib/meteora/lectures/ cap a un altre servidor. Triga 25 minuts i no té termini estricte.

Decideix política i prioritat per a cadascun, escriu les ordres concretes i justifica cada decisió. Indica també quin risc introdueix la teva configuració.

Un sistema té 12 processos executables. El cost del canvi de context és de 6 µs. El 75 % de les ràfegues de CPU dura menys de 5 ms.

1. Calcula el sobrecost percentual i el temps màxim de resposta amb quantum de 500 µs, 5 ms i 50 ms.
2. Quin triaries per a un servidor on meteo-api ha de respondre per sota de 200 ms?
3. Si la màquina passés a tenir 200 processos executables, canviaria la teva resposta?

Solució 1

(a) FCFS — per ordre d'arribada: P1, P2, P3, P4.

(b) SJF no apropiatiu — en triar, s'agafa el més curt dels que ja han arribat.

• t=0: només P1. Executa P1 fins a t=10 (no apropiatiu).
• t=10: han arribat P2 (2), P3 (4), P4 (6). El més curt és P2 → fins a t=12.
• t=12: P3 (4) davant de P4 (6). Entra P3 → fins a t=16.
• t=16: P4 → fins a t=22.

Coincideix amb FCFS per casualitat, perquè P1 va acaparar el començament:

Aquest resultat és instructiu: SJF no apropiatiu no ajuda si la feina llarga arriba primer. El seu avantatge només apareix quan hi ha elecció real.

(c) SRTF (apropiatiu):

• t=0: P1 (10). Executa P1.
• t=1: arriba P2 (2) < 9 restants de P1. Apropiació → P2.
• t=2: arriba P3 (4) > 1 restant de P2. Continua P2.
• t=3: P2 acaba. Candidats: P1 (9), P3 (4), P4 (6). Entra P3.
• t=7: P3 acaba. Candidats: P1 (9), P4 (6). Entra P4.
• t=13: P4 acaba. Entra P1.
• t=22: P1 acaba.

(d) Round Robin, q=3 ms. Cua inicial: P1. S'hi van incorporant al final a mesura que arriben.

• t=0-3: P1 (li'n queden 7). En acabar el torn ja han arribat P2, P3, P4 → cua: P2, P3, P4, P1.
• t=3-5: P2 (necessita 2, acaba abans del quantum). Cua: P3, P4, P1.
• t=5-8: P3 (li'n queda 1). Cua: P4, P1, P3.
• t=8-11: P4 (li'n queden 3). Cua: P1, P3, P4.
• t=11-14: P1 (li'n queden 4). Cua: P3, P4, P1.
• t=14-15: P3 acaba.
• t=15-18: P4 acaba.
• t=18-22: P1 acaba.

Comparació final:

Què triaria per a Meteora: cap dels quatre purs, sinó Round Robin amb prioritats, que és essencialment el que fa CFS. El raonament:

• SRTF guanya en la mitjana, però és inaplicable: no es coneix la durada de les ràfegues i, sobretot, condemnaria l'agregador a la inanició quan meteo-api rebés peticions contínues.
• FCFS provocaria l'efecte comboi: els 10 ms de l'agregador bloquejarien totes les peticions a l'API.
• Round Robin pur tracta igual els quatre, quan ingestor i agregador tenen necessitats oposades.

La configuració pràctica seria Round Robin amb nice diferenciat: ingestor a −5, meteo-api a 0, agregador a 10 i neteja a 19. Cal notar a més que aquests càlculs suposen un sol nucli; amb els 4 de meteo-01 els quatre processos correrien gairebé en paral·lel i l'espera mitjana cauria dràsticament en tots els algorismes.

Solució 2

Anàlisi prèvia. El primer és classificar per cost del retard, no per importància percebuda:

Configuració proposada:

Justificació de cada decisió:

1. ingestor a nice −10, no a SCHED_FIFO. Amb nice −10 obté un 90 % de la CPU davant d'un procés normal en cas de conflicte, més que suficient per a un procés que només fa servir 0,3 ms per lectura. SCHED_FIFO donaria una garantia més forta però introduiria el risc de bloquejar un nucli sencer si l'ingestor tingués una fallada. La regla és no fer servir temps real si nice en té prou, i aquí en té prou amb folgança.

2. meteo-api a nice −3. Necessita respondre ràpid, però està limitat per E/S: passa gairebé tot el temps bloquejat, i quan es desperta CFS ja li dona preferència per tenir el vruntime més baix. Una empenta moderada és suficient i evita que competeixi amb l'ingestor.

3. agregador a nice 10 i confinat a 2 nuclis. És l'únic limitat per CPU i el que pot fer mal als altres. Amb nice 10 rep un ~10 % en conflicte i el 100 % quan els altres dormen, que és gairebé sempre. Confinar-lo als nuclis 2 i 3 garanteix que els nuclis 0 i 1 estiguin sempre disponibles per al pic de les 8:00. Com que ha d'acabar en una hora i el seu càlcul real dura minuts, té marge de sobres.

4. backup-diari a nice 19 i ionice -c 3. Aquí hi ha la clau que sempre s'oblida: el backup comprimeix i transfereix, així que competeix per CPU i per disc. renice només resol el primer. ionice -c 3 (classe idle) fa que només faci servir el disc quan ningú més no el demana, i això protegeix les lectures de /var/lib/meteora/lectures/ de l'agregador.

Riscos que introdueix aquesta configuració:

• L'afinitat dura malbarata capacitat. Si ingestor i meteo-api estan ociosos a les 3 de la matinada, els nuclis 0 i 1 queden sense fer servir mentre l'agregador es limita a dos. Seria millor aplicar l'afinitat només a la franja de pic, amb un temporitzador, o eliminar-la si l'agregador comença a apurar el termini.
• ionice -c 3 pot provocar inanició del backup en un servidor amb activitat de disc contínua. Si el backup deixa de completar-se, cal apujar-lo a -c 2 -n 7 (millor esforç, prioritat mínima), que sí que garanteix progrés.
• Res d'això no limita la memòria. Si l'agregador consumeix tota la RAM, l'OOM killer podria matar meteo-api amb independència de les prioritats de CPU. Aquest front es cobreix amb cgroups, a 06-02.

Solució 3

1. Càlculs. Amb 12 processos i canvi de context de 6 µs, la pitjor espera per al primer torn és (n−1)·(q + cost) = 11·(q + 6 µs).

2. Elecció per a meteo-api amb objectiu de 200 ms: quantum de 5 ms.

• 500 µs es descarta encara que el seu temps de resposta sigui excel·lent, perquè el 75 % de les ràfegues dura menys de 5 ms i amb q=500 µs una ràfega típica necessitaria fins a 10 torns. Cada torn intercalat significa reentrar amb les memòries cau contaminades pels altres 11 processos: el sobrecost real és molt més gran que l'1,19 % nominal, que només compta el canvi de context i no les fallades de memòria cau.
• 50 ms es descarta directament: 550 ms de pitjor cas supera de bon tros l'objectiu de 200 ms. N'hi hauria prou amb un pic de càrrega per incomplir-lo.
• 5 ms és el punt correcte: sobrecost menyspreable (0,12 %), 55 ms de pitjor resposta —amb un marge de 3,6× sobre l'objectiu— i coincideix amb el llindar en què el 75 % de les ràfegues acaben soles, que és justament la regla pràctica de l'apartat del quantum.

3. Amb 200 processos executables: sí, canviaria, i de manera dràstica.

Gairebé cinc vegades l'objectiu de 200 ms. Per tornar-lo a complir:

Caldria abaixar el quantum a 1 ms, acceptant cinc vegades més sobrecost de canvis de context.

I aquí hi ha l'observació més valuosa de l'exercici: aquesta és exactament la raó per la qual CFS no fa servir un quantum fix. Linux defineix una latència objectiu (sched_latency_ns, 6 ms per defecte) que és el període en què tot procés executable ha de rebre CPU almenys una vegada, i calcula el quantum dividint-la entre el nombre de processos executables. Amb un terra de granularitat mínima (sched_min_granularity_ns, ~0,75 ms) perquè no degeneri:

És a dir: el planificador manté la latència objectiu mentre pot, i quan hi ha massa processos prefereix estirar-la abans que arruïnar el rendiment amb quàntums minúsculs. Aquesta degradació controlada és una decisió de disseny conscient, i explica per què un servidor amb 2.000 processos executables se sent lent encara que la CPU no estigui al 100 %: no li falta CPU, li falta torn.

Cal planificar perquè els processos alternen ràfegues de CPU i d'E/S, i quan un es bloqueja la CPU quedaria malbaratada. La distinció entre processos limitats per CPU i limitats per E/S és la que guia tota decisió pràctica, i es llegeix directament en la proporció de canvis de context voluntaris davant d'involuntaris de /proc/<pid>/status. Afavorir els curts no és caritat: és el que manté tots els recursos ocupats alhora.

Els criteris es contradiuen: no hi ha cap algorisme que optimitzi alhora productivitat, temps de retorn i temps de resposta. FCFS és trivial però pateix l'efecte comboi; SJF/SRTF són òptims en espera mitjana però requereixen endevinar el futur i causen inanició; les prioritats necessiten envelliment per no condemnar ningú; Round Robin sacrifica la mitjana a canvi d'acotar la resposta, amb el quantum com a comandament central; i les cues amb realimentació dedueixen del comportament el que no poden saber per endavant.

Linux resol tot això amb CFS/EEVDF, que substitueix cues i quàntums per un temps virtual i tria sempre el més endarrerit respecte a la seva part justa. Aquí encaixa nice: no reparteix torns, sinó que canvia el ritme del rellotge virtual, amb la regla d'un ~10 % de quota per punt. I nice només actua en cas de conflicte i només sobre la CPU, dos límits que cal tenir sempre presents. Per damunt hi ha les polítiques de temps real, potents i perilloses a parts iguals, i per sota el repartiment entre nuclis amb afinitat i balanceig.

Fins aquí hem repartit la CPU donant per fet que cada procés té la seva memòria i no trepitja la dels altres. És hora de preguntar-se com s'aconsegueix això: com diversos processos comparteixen una memòria física limitada sense envair-se, què converteix l'adreça 0x400000 d'ingestor i la 0x400000 d'agregador en dos llocs físics diferents, i què fa exactament el maquinari per impedir que un llegeixi les dades de l'altre. És el que veurem a Gestió de Memòria.