mercoledì, ottobre 10, 2007

Rilasciato il kernel Linux 2.6.23 - la novità del nuovo schedulatore di processi CFS - Completely Fair Scheduler

- post<li> - Permalink


E' stato rilasciato il Kernel 2.6.23, ma quali sono le principali novità?

Per chi non ha seguito un corso all'università di Sistemi Operativi queste notizie possono lasciare abbastanza indifferenti e comunque il variare della terza cifra ( .23 ) può lasciare il tempo che trova per chiunque.

Questa volta però volevo segnalare che "qualcosina" di nuovo c'è :D

In particolare mi ha colpito (mi perdonino i hardcore kernel hackers se non me ne sono accorto prima) che è stato cambiato il PS ovvero il Process Scheduler.

Il Process Scheduler
Il Process Scheduler è una delle componenti fondamentali di ogni sistema operativo tanto da pregiudicarne il successo o l'insuccesso. Da esso dipende infatti come un sistema "risponde" sotto diversi punti di osservazione: uso della CPU e della memoria, riposta all'interattività, tempi di soddisfazione delle richieste di Input / Output.

I processi -principalmente- si dividono in CPU bound (uso intensivo della CPU) e I/O bound (lettura/scrittura frequente da/per dispositivi esterni). Per fare un esempio, i primi sono soprattutto i processi server che elaborano molti dati in background, mentre i secondi sono tipicamente i processi interattivi: quando muovete il mouse qualcuno deve leggere dal mouse la nuova posizione e disegnarla sul monitor, per fare questo serve la CPU, ma se questa è impegnata per fare altro la vostra freccetta rimane ferma e pensate "cavolo" che cosa sta facendo il mio PC perchè non "risponde"?.

Bene gli algoritmi di decisione di quale processo premiare e concedendogli la CPU sono quelli implementati nel Process Scheduler. Sarebbe molto bello se questi schemi decisionali fossero implementati anche nella vita reale, mentre, quando siete in coda, state sopportando tutte le inefficenze del FIFO -primo arrivato-primo servito-

Il problema
Va detto subito che l'algoritmo perfetto non esiste perchè dovrebbe avere facoltà divinatorie, cioè prevedere la futura evoluzione dei processi. Tuttavia si può prevedere come si comporterà un processo in futuro analizzando come si è comportato in passato e sperando che continui nello stesso modo. Alcuni di questi algoritmi possono favorire i processi CPU bound rispetto a quelli I/O e viceversa, la maggior parte cerca di accontentare tutti.

Le soluzioni moderne
Bene dopo queste chiacchere da bar posso dire che una delle maggiori innovazioni che hanno fatto fare il salto dal kernel 2.4 a quello 2.6 è stata l'introduzione di un algoritmo di schedulazione con O(1) ovvero con complessità asintottica 1 o in altre parole riusciva a schedulare i processi con un numero finito di passi, indipendentemente del numero degli stessi. Per capire la portata di queste innovazione basta pensare se nella vita reale potessimo ordinare tutte le figurine in un sacchetto indipendentemente dal numero sempre, che ne so, in 10 mosse!

Nel mondo linux questa innovazione è stata così importante che è stata una di quelle più soggette a backport ovvero è stata portate anche nelle distribuzioni commerciali che giravano sul kernel 2.4 come ad esempio la RHEL 4. Sempre per fare un parellelo è stato fatto lo stesso con le cinture di sicurezza. L'innovazione è stata tale che le cinture sono state montate anche sulle auto che inizialmente non le prevedevano.

Questo algoritmo è stato implementato da "Ingo Molnar" che ci ritroviamo anche qui.

Infatti il PS con O(1) da lui inventato ha mostrato dei limiti nella gestione dei processi "interattivi" ovvero mentre navighi con firefox si potrebbe percepire una mancanza di risposta oppure mentre si ascolta della musica questa potrebbe "saltare" +incavolato+

Per ovviare a questo inconveniente erano in gara due pretendenti il CFS (Completely Fair Scheduler - Lo schedulatore completamente giusto :D ) sempre di Molnar e il RSDL (Rotating Staircase Deadline Scheduler Lo scheduler organizzato a scale mobili a scadenza :D ) messo a punto da Con Kolivas.

Queste due implementazioni non hanno inventanto molto di nuovo ma nel mix di strutture dati usate, modo di assegnare le priorità, modo di determinare o NON determinare l'interattività di un processo hanno fatto progredire la teoria (e la pratica) dei Sistemi Operativi.

In questa specie di "gara" ha prevalso ancora una volta il mix di Molnar e quindi il CFS.

In questo algoritmo:
  1. Non vengono usare code ( runqueues ) ;
  2. Viene usata come struttura dati un RedBlack Tree (rbtree) - Albero Rosso Nero;
  3. Gestisce l'accounting (la storia passata) dei processi mediante conteggio a livello di nanosecondi di uso della CPU senza contare nessuna altra variabile;
  4. Non c'è quindi il concetto di timeslice - slot di tempo-;
  5. C'è un solo parametro di configurazione /proc/sys/kernel/sched_granularity_ns
    dove impostare il comportamento della macchina:
    • CPU bound o server (good batching - buona elaborazione);
    • I/O bound o desktop (low latency - bassi tempi di risposta - alta interattività: il mouse si muove subito, la musica non salta, firefox saltella proprio come una volpe, ecc... :D ) [da KernelTrap "Linux: The Completely Fair Scheduler"]
Conclusioni
Innanzitutto complimenti, se siete arrivati a leggere queste righe siete pronti per affrontare la vostra prima lezione di Sistemi Operativi! B-) poi la prossima volta che vedrete il vostro PC che non "risponde" come vorreste pensate a che sforzo sta facendo per accontentarvi e dategli un po' di tempo per respirare e magari fatelo anche voi!

Riferimenti:

CFS
Gli alberi Rosso Nero
RSDS
Immagine tratta da Linux Process Scheduler Improvements in Version 2.6.0

Aggiornamento del 12/10/2007

Questo articolo è stato segnalato da Fabio Boneschi su "Nuovo kernel linux 2.6.23 con Process Scheduler rivisto". Grazie ai commenti di

"La coda è la più lunga da scorticare."
Proverbio Italiano

4 commenti:

Articoli correlati divisi per etichetta



Widget by Hoctro