giovedì, ottobre 18, 2007

CFS per tutti - CFS for dummies - Completely Fair Scheduler

- post<li> - Permalink


Dopo il successo - inaspettato- (il post lo avevo scritto di getto senza revisionarlo, controllare i riferimenti, ecc...) dell'articolo "Rilasciato il kernel Linux 2.6.23 - la novità del nuovo schedulatore di processi CFS - Completely Fair Scheduler" ho deciso di tradurre dall'inglese le parole del progettista Ingo Molnar che spiegano in termini molto semplici, quasi discorsivamente, i principi di funzionamento di questo importate algoritmo.

--: Inizio Traduzione dal sito http://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt :--


Come funziona lo scheduler CFS.

L'80% dell'implementazione del CFS può essere riassunta in una singola frase: Il CFS fondamentalmente modella "una ideale e accurata CPU multi-tasking" sull'hardware reale.

"una ideale e accurata CPU multi-tasking" è una CPU (che non esiste :-)) che ha il 100% dell'occupazione e che può eseguire ogni task alla stessa velocità, in parallelo, ognuno alla velocità di 1/nr_running (nr_running = numero processi attivi NdT).
Per esempio: Se ci sono due processi attivi, li esegue ognuno al 50% delle proprie possibilità, completamente in parallelo.

Nell'hardware reale, possiamo eseguire un solo processo alla volta, quindi mentre questo viene eseguito, gli altri, che rimangono in attesa della CPU, sono in svantaggio, perchè il processo corrente si appropria ingiustamente del tempo di CPU.

Nel CFS, questo sbilanciamento è espresso e tracciato tramite un valore, associato ad ogni task, p->wait_runtime espresso in nanosecondi. "wait_runtime" è il tempo totale di CPU che il processo dovrebbe ancora ottenere affinchè il sistema ritorni perfettamente "giusto" e bilanciato.

(piccolo dettaglio: su un hardware 'ideale', il valore p->wait_runtime dovrebbe essere sempre a zero - nessun task dovrebbe trovarsi 'sbilanciato' rispetto al tempo 'ideale' di suddivisione del tempo di CPU totale 1/nr_running NdT)

La politica di scelta del prossimo processo da attivare è basata proprio sul valore p->wait_runtime ed è veramente semplice: il processo che ha il valore più alto di p->wait_runtime sarà quello scelto.

In altre parole, il CFS prova attivare il task che ha un bisogno urgente di altro tempo di CPU. Quindi il CFS cerca di dividere il tempo totale di CPU tra tutti i processi attivi, quanto più possibile, fedelmente a quello che accadrebbe in un 'ideale hardware multitasking'

La restante parte dell'implementazione del CFS, che non rientra in questa semplificazione, è relativa a poche aggiunte come i livelli di priorità, la gestione dei sistemi multiprocessore e alcune variazioni per il riconoscimento dei processi non attivi (sleepers)

In pratica funziona così: il sistema esegue il processo per un po', quando questo si sospende (o viene eseguito lo scheduler) l'uso della CPU viene accreditato al task: quel po' di tempo in cui ha usato la CPU fisica viene sotratto dal tempo totale che gli spettava p->wait_runtime [corretto del tempo ulteriore che comunque gli sarebbe spettato] (in pratica non viene sottratto esattamente dal p->wait_runtime il tempo di uso della CPU, ma un po' meno. NdT).

Appena il valore di p->wait_runtime diventa così basso che un altro processo diventa 'il prossimo task' tra quelli conservati nell'albero RN ordinato in base al tempo, (viene introdotta anche una certa -grana- distanza artificiale in modo da non sovra-schedulare i task e non sporcare la cache) (con trashing si intende quell'effetto, nei sistemi operativi, in cui il sistema passa più tempo a elaborare sè stesso che ha far eseguire i processi NdT) al processo corrente viene sotratta la CPU e concessa al nuovo task.

Il valore rq->fair_clock traccia il "tempo di CPU in cui il processo è stato in esecuzione rispetto al tempo che avrebbe ritenuto sufficiente ottenere". Usando questo valore si può misurare "il tempo di CPU atteso - sperato" da un task. (La traduzione di questo periodo non mi soddisfa completamente, lascio pertanto, finchè non me ne viene -anche suggerita- una migliore, la versione originale NdT)

The rq->fair_clock value tracks the 'CPU time a runnable task would have
fairly gotten, had it been runnable during that time'. So by using
rq->fair_clock values we can accurately timestamp and measure the
'expected CPU time' a task should have gotten.

Tutti i processi avviabili (runnable) sono ordinati nell'albero RN secondo la chiave
"rq->fair_clock - p->wait_runtime". Il CFS concede la CPU sempre al task più a 'sinistra'. Con il procedere del sistema, i processi che diventano avviabili vengo aggiunti via via da 'destra' - lentamente, ma sicuramente ad ogni processo viene data la possibilità di diventare quello più di 'sinistra' (inteso ovviamente come il prossimo a venir eseguito non come comunista NdT :D) e quindi di poter giungere alla CPU in un periodo di tempo deterministico.

--: Fine Traduzione dal sito http://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt :--

Per oggi può bastare se a qualcuno interessa anche la seconda parte dell'articolo "Some implementation details" - "Alcuni dettagli dell'implementazione" lo scriva nei commenti e se mi riesce provvederò ;D

Byez

"Il mezzo può essere paragonato a un seme, il fine a un albero; e tra mezzo e fine vi è esattamente lo stesso inviolabile nesso che c'è tra seme e albero. "

P.S. Come traduttore non sono molto bravo, ma lo faccio anche per migliorarmi, pertanto correggetemi pure dove ritenete opportuno, certi che non mi offenderò, anzi mi sentirò onorato! :D

2 commenti:

Articoli correlati divisi per etichetta



Widget by Hoctro