Scheduling in Windows e Linux

Partiamo col definire il termine preemptive: questa modalità consiste nella capacità del sistema operativo di interrompere l’esecuzione di qualsiasi thread o processo in qualsiasi istruzione e ripristinarlo in qualsiasi punto del programma. Sia Windows che Linux hanno funzionalità preemptive, ed è una condizione essenziale del loro funzionamento.

Vediamo come funziona nei vari sistemi operativi.

Windows

– le code di esecuzione sono solo thread (minimo 1 thread per processo);

– ogni thread ha un livello di priorità (1-15 per i processi normali, il cui valore può essere modificato dallo scheduler, 16-31 per i processi ad alta priorità): valore più alto significa più alta priorità;

– i thread hanno gli stati ready, wait, run

– all’inizio del quanto lo scheduler sceglie il primo thread di priorità più alta. Se non ci sono altri thread alla conclusione del quanto il thread viene rimesso in coda con la stessa priorità;

– se durante il quanto si inserisce un thread con priorità più alta, windows sospende il thread, lo rimette in coda e fa partire un nuovo quanto col thread a priorità più alta;

– se durante un quanto un thread chiede una risorsa, va in wait;

– al termine di ogni quanto la priorità di tutti i thread in stato ready aumenta di 1 (fino a 15);

– i quanti foreground (finestre attive) sono più lunghi dei quanti di background (questo per garantire la reattività del sistema).

Come si vede il sistema è articolato, e tiene conto sia della starvation, sia della reattività con l’utente.

Linux 

– le code di esecuzione possono essere processi o thread (per comodità li chiamiamo task)

– le priorità vanno da 0-99 (real time) e 100-139 (normali): numero più basso significa maggiore priorità;

– finché i task real time (urgenti) restano attivi inibiscono l’esecuzione dei processi normali;

– all’interno dei processi real time, c’è la categoria FIFO (First In First Out) che non può essere mai interrotta in modo preemptive (si tratta di processi kernel che goverano l’intero sistema, in genere manutenzione), e la categoria RR (Round Robin) che invece ha una schedulazione divisa in quanti di tempo: in ogni quanto viene eseguito un task, al termine del task il processo viene messo in coda; la coda è data dalla priorità dei processi;

– all’interno dei processi normali, si applica l’algoritmo CFS (Completeley Fair Scheduler): in pratica ad ogni processo viene garantito lo stesso tempo di cpu (se ci sono 20 processi, si divide il tempo di cpu per 20). Il quanto è quindi determinato dinamicamente da una costante (detta time limit, tipicamente 0,2 secondi, dipende dalla versione del kernel) divisa per il numero di processi. Al termine di ogni quanto lo scheduler mette il processo che ha usato la cpu meno tempo. Quindi se ci sono pochi processi avremo quanti lunghi, se ci sono molti processi avremo quanti brevi.

– il limite di CFS è che se sono attivi molti processi il costo del context switch può diventare significativo. Per questo si introduce un limite minimo (min_granularity).di lunghezza del quanto. 

Esempio:

ipotizziamo un sistema Linux con questi due processi:

PID	priorità	durata (ms)
1	105	150
2	120	300
3	110	400

Calcolare la sequenza dei quanti.

Risposta:

siccome ci sono 3 processi, abbiamo un quanto pari a 200ms/3= 66 ms, finchè sono attivi 3 procssi, poi diventa 100ms ed infine 200ms. Si segue quindi un ordine di priorità.

quanto	PID	durata quanto	tempo rimanente
#1	1	66	150-66=84
#2	2	66	300-66=234
#3	3	66	400-66=334
#4	1	66	84-66=22
#5	2	66	234-66=168
#6	3	66	334-66=268
#7	1	22	0
#8	2	100	234-100=134
#9	3	100	334-100=234
#10	2	100	134-100=34
#11	3	100	234-100=234
#12	2	34	0
#13	3	200	234-200=34
#14	3	34	0

Struttura della risposta: