Processi e Scheduling in Linux 2.6

Processi e Scheduling in Linux 2.6

Daniele Lacamera

1 Aprile 2005

Indice

0. Introduzione...pag. 4

1. Implementazione dei Processi...pag. 6

2. Progettazione dello Scheduler...pag. 14

3. Implementazione dello Scheduler...pag. 18

Conclusioni...pag. 25

Bibliografia...pag. 25

0. Introduzione

0.1 Multiprogrammazione

Tutti i moderni sistemi operativi sono in grado di fare piu` cose allo stesso tempo. Mentre la CPU esegue un'istanza di un programma, un computer e` in grado di leggere e scrivere dai dispositivi di I/O. Inoltre, in un sistema multiprogrammato, la CPU viene commutata da un programma all'altro, eseguendo ciascuno di essi per un limitato periodo di tempo.

Benche` in effetti la CPU sia in grado di eseguire un solo programma per volta, nel corso di un solo secondo essa puo` lavorare su piu` programmi, effettuando una rapida commutazione che fornisce all'utente una illusione di parallelismo di esecuzione degli stessi. A volte per indicare questa rapida rapida commutazione, si utilizza il termine di pseudoparallelismo, in diretto contrasto con il reale parallelismo offerto dai sistemi multiprocessore.

Come in ogni ambito in cui siano previste attivita` parallele con un numero limitato di risorse condivise, la gestione del modello del parallelismo di esecuzione in un sistema operativo risulta difficoltosa. I progettisti dei sistemi operativi hanno percio` sviluppato nel corso degli anni un modello a processi sequenziali.

0.2 Modello a processi

Nel modello a processi tutto il software eseguibile sul computer viene organizzato in un certo numero di processi sequenziali, o piu` semplicemente processi. Un processo rappresenta l'entita` attiva di un programma in esecuzione, comprensivo del valore corrente del program counter, dei valori dei registri interni alla CPU, di una serie di dati globalmente accessibili nell'ambito del programma e dell'insieme delle variabili locali a funzioni e procedure, che risiedono nello stack e nell'heap quando il processo e` in esecuzione.

0.3 Scheduling

Concettualmente, ogni processo possiede una sua CPU virtuale. In realta` la CPU reale viene rapidamente commutata tra i vari processi in esecuzione secondo un preciso schema di parallelismo. Il compito dello scheduler in un sistema operativo multiprogrammato e`

quello di fornire questo schema, agendo sui processi in esecuzione sulla macchina, decidendo quando, su quale processore e per quanto tempo ognuno di essi debba essere eseguito. Normalmente, lo scheduler stesso e` un processo costantemente eseguibile, che rimane sospeso per la maggior parte del tempo in attesa di un interrupt temporale, altrimenti e` invocato da un altro processo che desidera cedere il controllo della CPU. A ogni processo viene assegnato di volta in volta un quanto di tempo di esecuzione su una CPU. Quando questo termina, il controllo passa allo scheduler, che provvede a selezionare il processo successivo.

1. Implementazione dei Processi

1.1 Unita` di esecuzione

I thread sono degli oggetti attivi all'interno di un processo. Un thread e` in effetti il contenitore del program counter, dello stack del processo e dei valori dei registri del processore all'interno del processo stesso. Nei sistemi UNIX classici, ogni processo consiste in un unico thread. Nei moderni sistemi tuttavia, i programmi multithreaded sono di uso comune.

Prevedono l'esecuzione di piu` task che condividano un'area di memoria, e nel caso di sistemi multiprocessore permettono di ottenere un vero e proprio parallelismo.

Linux ha una implementazione molto originale dei threads. Il kernel non possiede la concezione di thread, tratta thread e processi allo stesso modo, ossia accedendo alle risorse che durante la creazione vengono assegnate e sono indicate nella task_struct.

Thread appartenenti allo stesso processo possono tuttavia condividere le risorse semplicemente poiche` possiedono lo stesso riferimento ad uno spazio di indirizzamento condiviso.

Questo approccio contrasta in maniera notevole con sistemi operativi quali Microsoft Windows e Sun Solaris, che hanno un supporto esplicito per i threads. In Linux i threads sono semplicemente un modo per condividere risorse tra due normali task in esecuzione.

Poiche` le risorse da condividere vengono consegnate al signolo task utilizzando COW, la velocita` nella creazione e gestione di nuove unita` di esecuzione risulta gia` la massima possibile, dunque non vi e` bisogno di implementare tecniche diverse per la creazione dei thread.

Se si richiede la condivisione di una o piu` risorse, viene incrementato per ognuna di esse un contatore di utilizzi, che memorizza il numero di processi che accedono alla risorsa.

Il kernel di Linux si occupa dello scheduling dei singoli thread come unita` di esecuzione.

I processi interagiscono con due entita` virtuali: un processore virtuale e una memoria virtuale. Il processore virtuale crea al processo l'illusione del monopolio della macchina reale. La memoria virtuale fornisce la possibilita` al singolo processo di allocare e gestire la propria memoria. Thread appartenenti allo stesso processo condividono tra loro la memoria virtuale, ma ciascuno di essi possiede un proprio processore virtuale.

Il kernel di Linux si riferisce spesso ai singoli processi con il nome di task, che quindi

assumeremo come rappresentazione dell'unita` attiva di esecuzione in kernel space, per denominare indiscriminatamente thread e processi.

1.2 Strutture dati per la gestione dei processi

Il kernel memorizza i task in una lista double-linked circolare, chiamata task_list.

Ciascun elemento di questa lista e` un descrittore di processo di tipo task_struct.

Quest'ultima struttura e` molto grande, circa 1.7KB sulle architetture a 32 bit. In realta`

questa dimensione e` ridotta se si considera che all'interno di essa sono contenute tutte le informazioni relative allo specifico processo.

La lista circolare e linkata in entrambe le direzioni e` un oggetto molto usato nel kernel.

Includendo una struct di tipo list_head  all'interno della struct che si vuole utilizzare come elemento (in questo caso la task_struct), si ottiene una coppia di puntatori a list_head. Con apposite macro e` possibile creare una lista associandovi un nome, aggiungere e rimuovere elementi dalla lista e, specificando il tipo di struttura, ottenere uno specifico elemento della lista stessa.

In figura viene mostrato lo schema delle relazioni tra i puntatori delle list_head all'interno degli elementi:

La maggior parte dei sistemi operativi multiprogrammati gestisce un albero gerarchico di processi nel quale sono i processi stessi a generarne dei nuovi. Nella gran parte dei sistemi unix-like, un processo speciale denominato init viene eseguito subito dopo il caricamento in memoria del sistema operativo, e si occupa della generazione dei processi relativi ai programmi da eseguire all'avvio. Questi a loro volta possono avviare nuovi processi. Ogni processo e` dunque “figlio” di un altro processo in esecuzione sulla macchina, e puo` a sua volta generare zero, uno o piu` processi figli, ma ognuno di essi avra` uno e un unico genitore. Di conseguenza tutti i processi in esecuzione su una macchina sono nodi di un singolo albero, la cui radice e` il processo init.

L'implementazione di una lista di tutti i processi istanziati all'interno della macchina facilita l'accesso ad essi, ma non e` sufficiente a fornire un rapido accesso ai descrittori seguendo i criteri gerarchici, percio` ciascuno di essi e` vincolato tramite un apposito puntatore parent al processo che li ha generati, e a una lista children, che contiene puntatori ai descrittori degli evenuali figli.

Quando un processo viene creato, una nuova struttura di tipo thread_info viene allocata in fondo allo stack del kernel.

La struttura thread_info risulta cosi` definita per l'architettura x86 :

struct thread_info {

struct task_struct *task; /* main task structure */

struct exec_domain *exec_domain; /* execution domain */

unsigned long flags; /* low level flags */

unsigned long status; /* thread­synchronous flags */

__u32 cpu; /* current CPU */

__s32 preempt_count; /* 0 => preemptable, <0 => BUG */

mm_segment_t addr_limit; /* thread address space:

     0­0xBFFFFFFF for user­thead    0­0xFFFFFFFF for kernel­thread

*/

struct restart_block    restart_block;

unsigned long        previous_esp;   /* ESP of the previous stack in case    of nested (IRQ) stacks

*/

__u8 supervisor_stack[0];

};

Si noti come il primo membro di questa struttura sia un puntatore all'attuale task_struct relativa al thread.

Il sistema identifica i singoli processi attraverso un valore di identificazione del processo (PID), tipicamente intero, contenuto nella variabile pid_t. Per fornire un certo livello di compatibilita` con gli altri UNIX e le vecchie versioni di Linux stesso, il valore massimo della variabile pid_t e` fissato a 32767. Tuttavia e` possibile definire un diverso valore massimo utilizzando la sysctl kernel.pid_max.

Il kernel dovra` essere in grado di accedere alla task_struct relativa al processo corrente. Tuttavia questa operazione viene effettuata in modo diverso in base all'architettura della macchina.

Il campo state  del descrittore di processo contiene un valore associato a uno dei seguenti cinque stati:

TASK_RUNNING   –  Corrisponde allo stato “Runnable” e indica che il processo e`

attualmente in esecuzione, o sta attendendo di essere eseguito nell'apposita coda (runqueue);

TASK_INTERRUPTIBLE – Il processo e` sospeso, in attesa del verificarsi di determinate condizioni. Quando queste condizioni si verificano o viene inviato un segnale, il kernel modifica lo stato del processo in TASK_RUNNING.

TASK_UNINTERRUPTIBLE   –  Questo stato e` identico al precedente eccetto che il processo non ritornera` attivo quando riceve un segnale. Solitamente un processo si trova in questo stato quando e` necessario restare in attesa di un evento senza interruzioni;

TASK_ZOMBIE – Il task e` terminato, ma il padre del processo non ha ancora effettuato una chiamata alla syscall wait4(). Il descrittore del processo viene conservato nel caso in cui il padre desideri accedervi. Nel momento in cui viene chiamata wait4()  il descrittore del processo viene deallocato;

TASK_STOPPED – L'esecuzione del processo e` stata sospesa. Il processo non risulta in esecuzione ne` e` selezionabile per e ssere eseguito. Cio` accade quando il processo riceve un segnale di tipio SIGSTOP, SIGTSTP, SIGTIN e SIGTTOU o quando riceve qualsiasi segnale in fase di debugging del programma.

1.3 Creazione dei processi

Tradizionalmente, effettuando la chiamata alla syscall fork() ci si aspetta che tutte le risorse del processo che la effettua siano copiate in un nuovo spazio di indirizzamento e che la copia sia consegnata al processo appena creato. Questo approccio risulta molto inefficiente, specie nel caso in cui le risorse allocate dal processo chiamante siano dell'ordine di decine di megabytes. Poiche` la filosofia stessa dei sistemi unix incoraggia la scelta di rapidita` di esecuzione dei processi, i programmatori di Linux hanno deciso di implementare la primitiva fork() utilizzando pagine “copy-on-write” (COW). Questo meccanismo prevede che i due processi condividano la stessa area di memoria. I dati pero` sono marcati in modo che se il processo appena generato tenta una scrittura su di

essi ne ottiene una copia unica su cui effettuare l'operazione. Di conseguenza, la duplicazione delle risorse avviene soltanto quando quando si tenta la scrittura; prima di allora essi sono condivisi in sola lettura.

Una chiamata a fork() produce una particolare chiamata alla syscall clone(), analoga a quella utilizzata un userspace per la creazione dei thread.

Tra i parametri della syscall clone() possono essere specificate le risorse che il task chiamante vuole condividere attraverso specifiche flags, definite in include/linux/sched.h :

/*

 * cloning flags:

 */

#define CSIGNAL 0x000000ff /* signal mask to be sent at exit */

#define CLONE_VM 0x00000100 /* set if VM shared between processes */

#define CLONE_FS 0x00000200 /* set if fs info shared between processes */

#define CLONE_FILES 0x00000400 /* set if open files shared between processes */

#define CLONE_SIGHAND 0x00000800 /*   set   if   signal   handlers   and   blocked   signals shared */

[..]

L'elenco completo delle flags definite per la syscall clone() si trova nel file include/linux/sched.h.

Una normale fork() puo` essere implementata con una chiamata a clone()effettuata con i parametri:

clone(SIGCHLD,0);

1.4 Terminazione dei processi

La terminazione di un processo puo` avvenire esplicitamente attraverso la chiamata alla syscall exit() o implicitamente se il processo non riesce a ignorare un segnale o gestire una eccezzione. In ognuno di questi casi, il lavoro di chiusura del processo e` affidato alla procedura do_exit(), definita in kernel/exit.c.

La procedura do_exit() effettua una serie di operazioni in sequenza:

__exit_mm(tsk);

Rilascia il controllo della mm_struct associata al processo, e se nessun altro processo stava condividendo quell'area di memoria, essa viene deallocata.

exit_sem(tsk);

Se il processo che sta terminando era in attesa a un semaforo, viene rimosso dalla coda associata.

__exit_files(tsk);

__exit_fs(tsk);

exit_namespace(tsk);

exit_thread();

Queste routine decrementano il valore del contatore di utilizzatori associate alle rispettive risorse. Quando un contatore raggiunge zero, la risorsa associata viene rimossa.

tsk­>exit_code = code;

Memorizza l'exit code del task nell'apposito campo della task_struct.

exit_notify(tsk);

Chiamando exit_notify() invia appositi segnali al task padre e a eventuali task figli, cosi` come ai task dei thread dello stesso gruppo, dopodiche` porta il task nello stato TASK_ZOMBIE.

schedule();

Il controllo viene restituito allo scheduler, poiche` nessun task che si trovi nello stato TASK_ZOMBIE puo` essere eseguito. Questa e` l'ultima istruzione in assoluto che il task esegue.

Il processo in questione e` a questo punto terminato, ma la sua task_struct rimane allocata nello stack del kernel, poiche` le tracce della sua esistenza sono utili per il processo padre. Il processo terminato rimane nello stato TASK_ZOMBIE finche` non viene deallocato il suo descrittore. Questa operazione e` la diretta conseguenza di una chiamata alla syscall wait() da parte del processo padre, che implica una chiamata alla procedura release_task(), anch'essa definita in kernel/exit.c.

Questa procedura si occupa inizialmente di decrementare il contatore dei processi aperti

dall'utente proprietario del processo attraverso la chiamata a free_uid(). Linux mantiene una cache contenente informazioni su processi e files aperti per ogni utente, e quando il contatore dei processi raggiunge 0, la cache viene deallocata.

In seguito la release_task() effettua la chiamata a unash_process(), routine in cui il processo viene eliminato dalla pidhash e dalla task_list.

A questo punto, tramite la chiamata a put_task_struct(), vengono deallocate tutte le zone di memoria in cui erano stati precedentemente allocati il descrittore task_struct e la struttura thread_info.

2. Progettazione dello Scheduler

2.1 Task CPU-bound e I/O-bound

I task in esecuzione tendono ad essere classificati in base al loro utilizzo delle risorse. Vi sono processi che impiegano molto tempo a effettuare calcoli su un processore, e vengono detti CPU-bound, mentre altri restano per lunghi periodi in attesa di input da periferiche esterne, percio` sono denominati I/O-bound. Uno dei primi problemi nell'implementazione di uno scheduler e` effettuare questo tipo di classificazione in modo da fornire un livello di priorita` piu` elevato ai processi I/O-bound, in maniera da migliorare la risposta del sistema alle richieste dirette di interazione dell'utente con l'applicazione, e allo stesso tempo per ottimizzare i tempi morti dei processi che rimangono in attesa di eventi esterni prima di rientrare in esecuzione.

2.2 Cambio di contesto

Il cambio di contesto e` una operazione che consiste nel passare l'esecuzione da un processo ad un altro. In effetti questo avviene due volte ogniqualvolta un processo finisce il suo quanto temporale, poiche` il controllo passa prima dal processo iniziale allo scheduler, il quale eseguira` il codice necessario a scegliere il processo successivo e infine consegnera` il controllo del processore a quest'ultimo. Dal punto di vista pratico, un cambio di contesto implica inoltre il salvataggio dello stato dei registri del processore, il caricamento di un nuovo stato, la cancellazione della cache, e il cambio della mappa della memoria virtuale. I cambi di contesto sono dunque delle operazioni molto dispendiose, da limitare il piu` possibile per mantenere alte le performance della macchina. Queste operazioni, essendo molto legate al tipo di architettura sul quale vengono eseguite, sono costituite da routine interamente scritte in assembler, differenziate per tipo di processore.

Ad esempio su PowerPC il puntatore all'attuale task_struct si trova nel registro r2 del processore. Su x86 invece, l'attuale task_struct viene ottenuta mascherando i 13 bit meno significativi dello stack pointer del processore attraverso una macro in assembler. I programmatiori del cambio di contesto del PowerPC sono di fatto stati avvantaggiati dall'avere a disposizione molti registri di processore, al contrario del i386, dove e` stato necessario ricorrere alla suddetta macro, che penalizza le prestazioni generali dello scheduler, se si considera quanto spesso questo codice viene eseguito.

2.3 Obiettivi dello scheduler di Linux

La progettazione dello scheduler di un sistema operativo e` fortemente legata al tipo di mercato a cui punta. La discriminazione della tipologia d'uso richiesta per il sistema operativo da implementare porta alla valutazione della scala di importanza tra gli obiettivi dello scheduler, e in diretta conseguenza alle scelte che determinano l'algoritmo di scheduling da utilizzare. Linux e` stato inizialmente creato da uno studente per essere utilizzato sul suo computer, ma in breve e` divienuto un sistema operativo server. Cio` ha portato in breve alla complessa e indefinita interfaccia grafica costruita su Linux, se confrontata alla pari con altri sistemi WYSIWYG (what you see is what you get) come i sistemi operativi proprietari di largo uso di marca Apple o Microsoft. Tuttavia cio` non ha frenato l'attuale tendenza di considerare i sistemi GNU/Linux una valida alternativa per l'utenza Desktop, oltre che utilizzi specifici da server. Lo scheduler di Linux 2.6 e` stato riscritto da Ingo Molnar con l'esplicita volonta` di soddisfare entrambi i mercati, riuscendo a fornire migliori prestazioni all'utenza desktop delle distribuzioni di GNU basate su Linux 2.6. L'obiettivo di soddisfare piu` tipologie di utenza contemporaneamente ha caricato l'implementazione dello scheduler di Linux 2.6 di pesanti aspettative, rendendo questa parte di Linux un interessante caso per studiare come soddisfare due mercati cosi` diversi con successo.

Un obiettivo importante per uno scheduler e` la sua efficienza. Il sistema operativo deve tentare di utilizzare il piu` possibile i processori per produrre del “vero” lavoro mentre le applicazioni sono in attesa di altri eventi. Ad esempio, poiche` come abbiamo visto i cambi di contesto sono operazioni dispendiose, fornire quanti di tempo piu` lunghi aumenta l'efficienza poiche` il codice per il cambio del contesto viene eseguito piu` raramente.

Anche aumentare la rapidita` di esecuzione del cambio di contesto, ottimizzandone l'implementazione, puo` apportare notevoli miglioramenti all'efficienza dello scheduler.

Un altro obiettivo importante da considerare e` l'interattivita`, specie nell'ottica di ottimizzare Linux per l'utenza Desktop, poiche` un utente si aspetta una pronta risposta dai processi I/O-bound, specialmente quando le periferiche in questione sono la tastiera e il mouse. L'interattivita` tuttavia richiederebbe cambi di contesto frequenti, a discapito dell'efficienza, e percio` e` giusto trovare il giusto equilibrio tra efficienza e interattivita`.

E` inoltre fondamentale che uno scheduler ben costruito tenga conto di un certo grado di

tempo troppo lungo o che si verifichi starvation, perche` la sua priorita` e` molto piu`

bassa di quella degli altri task eseguibili con cui compete. Per questo scopo, lo scheduler di Linux 2.6 prevede che i task che si avvicinano a una soglia di starvation, scelta a priori dagli sviluppatori dello scheduler, ricevano un significativo incremento di grado di priorita`

o eventualmente una prelazione immediata. Il parametro dell'equita` non deve portare a pensare che task simili che hanno la stessa priorita` debbano ricevere un uguale trattamento da parte dello scheduler, ma semplicemente che sia garantito che non si verifichino starvation e che non ci sia la possibilita` per una applicazione di manomettere il sistema di scelta dei processi nello scheduler per guadagnare piu` risorse di quelle che l'algoritmo gli assegnerebbe.

2.4 Tecnologie di parallelismo reale

Con Linux e` possibile eseguire parallelamente piu` task in contemporanea, sfruttando i sistemi a multiprocessore SMP (Symmetric Multi Processing) o il supporto per Hyperthreading presente sui processori di ultima generazione con SMT (Symmetric Multi threading) o ancora utilizzare sistemi di calcolo distribuito sfruttando NUMA (Non-Uniform Memory Access).

Il supporto per SMP e` presente in Linux gia` dalla versione 2.4, e si occupa di far girare parallelamente piu` task eseguibili contemporaneamente su una macchina che ha piu` di un processore, occupandosi tra l'altro dell'accesso esclusivo ai dispositivi e che un processo abbia a disposizione al massimo un processore per una unita` di tempo. Poiche`

piu` processori sulla stessa macchina utilizzano alle stessa memoria e alle stesse risorse di sistema, il compito primario di SMP e` di utilizzare al meglio possibile il tempo di tutti i processori. Per questo motivo lo scheduler considera alcuni parametri legati alle performances quando ha a che fare con sistemi multiprocessore. Ad esempio tende ad assegnare un task sempre allo stesso processore in quanti di tempo successivi, in modo che si possa usufruire al meglio della rapidita` di accesso alla cache di primo livello delle CPU.

Con la tecnologia Hyperthreading, alcuni processori realizzano il parallelismo in maniera virtuale, condividendo tra i singoli chip SMT alcune risorse come la cache e alcuni registri.

Per questo motivo i processori “virtuali” non possono essere trattati con gli stessi schemi

con cui si realizza la SMP.

NUMA permette di far eseguire l'immagine di un singolo sistema tra piu` nodi. Ogni nodo e` definito da una scheda madre, sulla quale possono essere presenti piu` processori, e puo` agire come parte del sistema. Cio` e` possibile solo se tra i nodi vi e` una interconnessione ad alta velocita` che lo consente, connettendo gli host a livello di scheda madre piuttosto che attraverso una semplice rete IP. E` possibile per lo scheduler in questo caso, allocare la memoria necessaria all'esecuzione di un processo anche su un nodo diverso da quello in cui e` presente il processore che lo sta eseguendo, ma per i thread che richiedono efficienza maggiore e` possibile specificare anche che la memoria sia allocata sullo steso nodo. NUMA rende possibile ampliare il concetto di multiprogrammazione parallela estendendo il limite dei 2-8 processori di SMP fino a 512 processori un un sistema distribuito che utilizza questa tecnologia.

Lo scheduler di Linux 2.6 puo` supportare anche un meccanismo real-time leggero, programmando l'esecuzione di processi che abbiano richieste molto precise sui tempi di esecuzione. Sebbene sia possibile che le deadline vengano rispettate, non vi e` garanzia che cio` avvenga. I processi real-time sono trattati in maniera speciale da parte dello scheduler, utilizzando una coda FIFO per discriminare la scelta dei processi in esecuzione.

3. Implementazione dello Scheduler

3.1 Punto di partenza: lo scheduler di Linux 2.4

Durante il periodo di sviluppo del kernel 2.5, la riscrittura dell'algoritmo di scheduling e`

stata uno dei piu` importanti cambiamenti nel passaggio a Linux 2.6. Sebbene lo scheduler esistente in Linux 2.4 fosse gia` largamente usato e affidabile, aveva una serie di caratteristiche che ne limitavano la scalabilita`.

Diamo una breve descrizione dell'algoritmo di scheduling di Linux 2.4 per poter meglio comprendere i motivi che hanno portato alla riscrittura dello scheduler.

Il tempo e` diviso in “epoche”, ossia degli intervalli in cui tutti i processi, a turno, eseguono nel loro intervallo temporale (timeslice). All'inizio di ogni epoca tuttavia, l'algoritmo si occupa di calcolare la lunghezza delle timeslice di ciascun processo, iterando dunque tra i vari processi all'interno della task_list. Ogni task ha una timeslice di base che gli viene assegnata durante la creazione a partire dal valore “nice” del processo a cui appartiene. Un valore di nice pari a 0 fornisce al task una timeslice di base di 200ms. La durata di questa timeslice viene poi ritoccata in base a quanto il processo sia I/O-bound.

Ogni task ha un contatore il cui valore e` impostato alla timeslice base all'inizio della prima epoca di vita del processo, e viene decrementato in base a quanto tempo il processo rimane in esecuzione. Se alla fine dell'epoca il processo non ha utilizzato tutta la sua timeslice significa che si e` sospeso per attendere un segnale da un'altra risorsa, per cui la sua timeslice nella prossima epoca sara` la timeslice base incrementata della meta` del tempo rimanente nel contatore. In questo modo si consegna ai processi piu` I/O-bound una timeslice piu` lunga, ma si garantisce che qualora uno di essi cambiasse il suo comportamento utilizzando la sua timeslice per intero, tornerebbe alla sua timeslice base all'inizio della prossima epoca.

Durante il cambio di contesto, la funzione schedule() effettua la scelta del prossimo processo utilizzando iterativamente su tutti i processi eseguibili la funzione goodness(), e scegliendo quello che nella chiamata restituisce il valore piu` alto.

Quest'ultima routine, chiamata su un task restituisce in genere la somma del valore nice del processo con il tempo rimanente all'interno del contatore del tempo rimasto nella timeslice. Se il contatore di un processo raggiunge 0, goodness() restituira` 0. Se un processo e` etichettato come real-time, il valore della goodness() risultera`

incrementato di una costante, 1000, che lo rende in genere il migliore tra i processi candidati. Sono inoltre previsti altri bonus nella goodness(), ad esempio per i task che condividono la stessa area di memoria del task precedente, in modo da favorire i cambi di contesto che non prevedano riallocazione delle pagine in cache, oppure in SMP viene assegnato un grosso bonus (+15) sul processore che sta attualmente effettuando il cambio di contesto all'ultimo processo che ha eseguito, per scoraggiare la migrazione dei processi da una CPU all'altra.

E` chiaro che il limite piu` invalidante di questo algoritmo di scheduling risiede nella scalabilita`. Benche` sia un discreto algoritmo e funzioni bene su sistemi che prevedono pochi processi, inizia a mostrare i suoi limiti quando il numero di task in esecuzione aumenta. Cio` accade perche` ad ogni cambio di contesto e` necessario iterare tra tutti i processi, cosi` come alla fine di ogni epoca viene effettuato l'aggiornamento dei contatori di ognuno dei processi da eseguire.

Queste due operazioni hanno una complessita` che dipende linearmente dal numero di processi in esecuzione, per cui l'algoritmo di scheduling di Linux 2.4 risulta O(n).

Un altra caratteristica negativa e` stata sottolineata da alcuni tra i piu` autorevoli studiosi del kernel di Linux, ossia un inadeguato valore per le timeslice di base di default, che risulterebbe troppo alta e potrebbe portare delle lunghissime attese per l'esecuzione di un processo, dell'ordine di decine di secondi, nel caso in cui il sistema sia molto carico e siano presenti molti processi CPU-bound.

3.2 Nuove strutture dati

La caratteristica piu` innovativa del nuovo scheduler e` di riuscire ad eseguire tutte le operazioni critiche, come il cambio di contesto, in un tempo costante e indipendente dal numero di processi presenti sulla macchina. Il nuovo algoritmo di scheduling e` dunque O (1) poiche` la sua complessita` nel caso peggiore non e` una funzione del numero di processi. Questo risolve definitivamente il problema di scalabilita` di Linux 2.4.

Questo obiettivo e` stato raggiunto riscrivendo le strutture dati che contengono i descrittori dei processi nelle operazioni di scheduling. In particolare e` definita una runqueue (coda di esecuzione) per ogni processore presente sulla macchina. Ogni runqueue a sua volta contiene due priority array (vettori di priorita`), un tipo di struttura

che rappresenta, come vedremo, la vera innovazione nell'implementazione dell'algoritmo.

La struttura della runqueue e` definita in kernel/sched.c, non in kernel/sched.h come si potrebbe immaginare. Cio` e` stato fatto appositamente per una scelta progettuale di separare le interfacce dello scheduler accessibili dai kernel threads dalle caratteristiche implementative interne dello scheduler stesso. La runqueue tiene traccia di alcuni elementi puramente statistici riguardanti l'utilizzo del processore, il suo carico medio, il numero di processi in coda ecc. E` presente anche un puntatore all'ultimo task che e` stato eseguito sul processore, un altro che indica l'area di memoria virtuale utilizzata dall'ultimo processo. Un vettore di due elementi di tipo prio_array_t e`

definito quando la runqueue viene associata al processore. I due puntatori active e expired indicano quale dei due array contiene i processi che devono ancora consumare la loro timeslice in questa epoca. Ogniqualvolta un task viene eseguito, l'istanza del task presente nel vettore di priorita` attivo viene spostato in quello expired. Alla fine di ogni epoca, tutti i task si troveranno all'interno del vettore di priorita` puntato da expired. A questo punto i due array vengono scambiati, semplicemente scambiando i due puntatori active e expired, in modo tale che sia di nuovo pieno il vettore di priorita` attivo che contiene i descrittori dei processi da eseguire in questa epoca.

Ciascun priority array contiene le informazioni necessarie per eseguire lo scheduling del prossimo processo in un tempo costante, poiche` consente la classificazione dei task in base alla loro priorita` durante l'inserimento del descrittore all'interno di questo particolare vettore. In effetti il priority array consiste essenzialmente in un array di puntatori a liste bidirezionali di processi aventi priorita` uguali. Sono previsti 140 livelli di priorita`, a ciascuno dei quali e` associata una lista bidirezionale. Le liste bidirezionali sono chiaramente dello stesso tipo di quelle analizzate in 1.2. Il priority array mantiene una mappa di bit che discrimina i livelli di priorita` che contengono almeno un processo attivo, ad esempio se sono presenti tre processi, due dei quali con priorita` 3 e uno con priorita`

7, i bit 3 e 7 della bitmap saranno accesi, e le due liste associate ai livelli

di priorita` 3 e 7 conterranno rispettivamente 2 e 1 processo. In figura sono mostrate le relazioni fra le strutture dati. Per semplificare la rappresentazione dei priority array sono visualizzati solo 8 livelli di priorita`.

3.3 Assegnamento di priorita` e timeslice

Quando un task viene creato, gli viene assegnato un valore detto priorita` statica, che dipende dal valore nice che l'utente puo` specificare durante la creazione del processo o del thread che genera il task. A partire da questo valore, ogniqualvolta che il processo finisce la sua timeslice e viene spostato da un vettore di priorita` all'altro, viene ricalcolata la sua priorita` effettiva, o dinamica, con opportuni vantaggi per i processi I/O bound e opportune penalita` per i processi piu` CPU bound. Nelle attuali versioni di Linux 2.6, il massimo incremento o penalita` rispetto alla priorita` statica e` fissato a 5. La priorita`

viene calcolata dalla routine effective_prio()  ogniqualvolta un processo finisce di utilizzare il processore, prima dello scambio dei due priority array che determina la fine di un'epoca. Al contrario di Linux 2.4, esiste un complesso schema che effettua delle statistiche sul tempo effettivamente utilizzato dal processo per compiere operazioni sul processore rispetto a quanto esso resta in attesa di eventi esterni, determinando cosi` il

suo bonus di priorita`. Allo stesso modo le timeslice dei task sono calcolate ogniqualvolta un processo finisce la propria timeslice, quando sta per essere inserito nel vettore di priorita` expired, utilizzando appositi valori discreti associati ai livelli di priorita` dinamica:

un task con priorita` piu` alta otterra` una timeslice piu` lunga rispetto agli altri processi, sempre nell'ottica di favorire i processi interattivi. La timeslice minima che puo` essere assegnata a un processo molto “affamato” di CPU e` di 10ms, mente un processo interattivo puo` ottenere una timeslice di durata molto maggiore, il cui massimo e` fissato a 200ms. E` inoltre prevista ad una variabile per ogni task, chiamata interactive_credits, che tiene conto del numero di interazioni del processo con le periferiche, discriminando cosi` i processi in base alla loro “interattivita`” ricavata statisticamente. Questo serve per evitare che un task altamente interattivo, alla fine di una serie di interazioni, cominci a usare la CPU per un tempo maggiore e possa cosi` perdere troppo in fretta priorita` e durata della timeslice. Un'altra eccezione che riguarda i processi interattivi e` la possibilita` che essi siano reinseriti nel vettore di priorita` attivo quando ha finito la sua timeslice, se cio` non comporta starvation dei processi in attesa della fine dell'epoca nell'array expired.

3.4 Cambio di contesto

Quando il controllo passa alla funzione schedule(), direttamente o indirettamente, la scelta del prossimo processo da eseguire viene fatta visitando la lista associata al livello di priorita` piu` alto e selezionando il primo descrittore di quella lista. Questo garantisce che se esistono processi aventi lo stesso livello di priorita` si alternino attraverso un meccanismo round-robin, altrimenti viene sempre selezionato il processo con priorita` piu`

alta. Poiche` come abbiamo visto le priorita` e le timeslice sono calcolate ogniqualvolta il processo finisce la sua timeslice, non c'e` bisogno di iterare tra i processi durante il cambio di contesto. La nuova versione della funzione schedule() lavora con tempi costanti, dovendo soltanto identificare il primo bit acceso nella bitmap del priority array dei processi attivi, attraverso una chiamata alla funzione sched_find_first_set(). Una volta che un nuovo task e` stato selezionato, la funzione context_switch() viene invocata, e a sua volta richiama la routine switch_mm() che cambia la mappatura della memoria virtuale da quella del processo che ha appena concluso il suo ciclo di esecuzione

con quella del nuovo processo. In seguito viene chiamata la procedura switch_to() che si occupa di cambiare lo stato dei registri del processore e lo stack, ripristinando quelli relativi al processo selezionato.

3.5 Code di attesa e prelazione

Accade spesso che un task non sia piu` eseguibile perche` rimane in attesa di un evento esterno, ossia si mette in uno stato di attesa. In questo caso viene inserito in una apposita coda di attesa e rimosso dalla coda di esecuzione. Quando il task prova a risvegliarsi, per il verificarsi di un evento o la ricezione di un segnale, la funzione try_to_wake_up() riporta il processo nella runqueue. Se il processo che tenta di risvegliarsi ha una priorita`

dinamica maggiore del processo attualmente in esecuzione, il kernel ha la possibilita` di effettuare un cambio immediato di contesto per mettere a disposizione la CPU al processo che si e` appena risvegliato. Questo meccanismo detto di pre-emption o prelazione, assicura una risposta ancora piu` pronta ai processi interattivi, e viene realizzata grazie a un interrupt software che, per ogni millisecondo, grazie alla chiamata alla procedura schedule_tick(), controlla che non si siano risvegliati dei task con priorita` maggiore di quello attualmente in esecuzione.

3.6 Bilanciamento del carico nei sistemi SMP

Come abbiamo osservato in precedenza, il kernel utilizza una runqueue per ogni processore presente nel sistema. Per questo motivo puo` capitare che una delle runqueue abbia piu` processi delle altre. Da un sistema con piu` processori ci si aspetta che il carico sia il piu` possibile distribuito tra le varie CPU. Per questo motivo, se una runqueue e`

vuota, o comunque ogni 200 ms con un interrupt software, viene invocato l'algoritmo di bilanciamento del carico. La routine invocata per bilanciare le runqueues e`

load_balance(), la quale, attraverso la chiamata a find_busiest_queue(), identifica la runqueue piu` carica, e ne restituisce il puntatore alla load_balance(). Se nessuna delle runqueue ha un carico superiore del 25% rispetto a quella corrente, find_busiest_queue() restituisce NULL e load_balance() termina. In caso contrario, avviene la migrazione dei processi in eccesso dalla runqueue piu` carica a quella

corrente, attraverso successive chiamate a pull_task() fino a quando la find_busiest_queue()  non restituisce NULL. I processi da migrare sono scelti preferibilmente dal priority array expired, poiche` sono quelli che attendono da piu`

tempo che si liberi il processore, altrimenti, se l'array expired e` vuoto, vengono prelevati dal priority array active. La load_balance() tende a far migrare i task con priorita`

maggiore che sono in attesa da piu` tempo, qualora essi non siano marcati in maniera da non potere lasciare la runqueue corrente, per via di affinita` con i processi su quella runqueue, per motivi di performances, ad esempio condivisione della stessa area di memoria da parte di thread dello stesso gruppo, che lo scheduler tende a lasciare in coda di esecuzione sullo stesso processore per utilizzare al meglio la cache.

3.7 Miglioramento del supporto Real Time

Linux 2.6 e` in grado di utilizzare politiche differenti per lo scheduling dei processi real time. Quando un processo real time viene inserito in coda di esecuzione non viene calcolato un valore di priorita` dinamica, poiche` il sistema per l'assegnamento delle priorita` statiche dei processi real time e` sufficiente per garantire una priorita` maggiore a questo tipo di processi rispetto ai normali processi della macchina. Grazie alla preemption e a due diverse politiche di scheduling per i processi Real Time, le prestazioni inerenti la gestione di tali processi risulta molto migliorata dalla versione precedente di Linux. Generalmente, se si utilizza la politicha di scheduling SCHED_FIFO, i processi real time possono essere eseguiti ininterrottamente fino all'esaurimento della loro timeslice. E`

tuttavia possibile utilizzare la politica SCHED_RR per fornire comunque un meccanismo di round robin a timeslices per gestire l'esecuzione di tali processi. Benche` il supporto Real Time sia “leggero” anche in Linux 2.6, ossia non sia possibile garantire il rispetto dei tempi di esecuzione, le prestazioni misurate per il nuovo algoritmo di scheduling Real Time sono risultate eccellenti.

Conclusioni

Il bisogno di riscrivere da zero i meccanismi per lo scheduling dei processi durante il passaggio all'attuale versione di Linux, e` stato dettato da necessita` eterogenee. Ingo Molnar e` riuscito egregiamente nel compito di fornire una implementazione versatile ed efficiente, cancellando, con lo sviluppo di uno scheduler O(1), i problemi di scalabilita`

inaccettabili per un sistema operativo cosi` popolare e stimato come Linux, ma anche perfezionando le caratteristiche esistenti analizzando a fondo il vecchio scheduler, attraverso l'introduzione di una serie di algoritmi innovativi e efficienti.

Bibliografia

– The Linux Cross Reference http://lxr.linux.no

– Andrew S.Woodhul, Andrew S.Tanenbaum, “Operating Systems Design and Implementation”, 2^nd Edition, Prentice Hall International.

– Robert J. Love, “Linux Kernel Development”, Developers's Library.

– Daniel P. Bovet, Marco Cesati, “Understanding the Linux Kernel”,2^nd Edition, O'Reilly.

– Josh Aas, “Understanding the Linux 2.6.8.1 CPU Scheduler”, Silicon Graphics Inc. 17 Febbraio 2005.