Scheduler: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Annullate le modifiche di 79.13.32.15 (discussione), riportata alla versione precedente di 193.203.232.31 |
Nessun oggetto della modifica |
||
Riga 29:
Lo scheduling è un'operazione molto importante per il corretto ed efficiente funzionamento del calcolatore. Infatti non solo consente di eseguire più programmi concorrentemente, ma consente anche di migliorare l'utilizzo del processore. Ad esempio, quando è necessario eseguire un'operazione di I/O, il processore non può proseguire l'elaborazione del processo attualmente in esecuzione fino al completamento della stessa. Dato che le operazioni di I/O sono molto più lente del processore sarebbe un inutile spreco di risorse se il processore rimanesse bloccato fino al completamento delle stesse. Per evitare questo le operazioni di I/O vengono gestite unicamente dal [[Sistema operativo]] che, nel frattempo, assegna l'uso del processore ad un altro processo. In questo modo si massimizza l'uso delle risorse del sistema.
È importante la distinzione tra scheduling con diritto di [[prelazione]] (scheduling ''preemptive'') e scheduling senza diritto di prelazione (scheduling ''non-preemptive'' o ''cooperative''). Nel primo caso lo scheduler può sottrarre il possesso del processore al processo anche quando questo potrebbe proseguire nella propria esecuzione. Nel secondo caso, invece, lo scheduler deve attendere che il processo termini o che cambi il suo stato da quello di esecuzione a quello di attesa o di pronto, a seguito, ad esempio, di una richiesta di I/O oppure a causa di un segnale di interruzione ([[interrupt]]).
Esistono vari algoritmi di scheduling che tengono conto di varie esigenze e che possono essere più indicati in alcuni contesti piuttosto che in altri. La scelta dell'algoritmo da usare dipende da cinque principali criteri:
Line 47 ⟶ 46:
*''Balance'' (bilanciamento): tutte le parti del sistema devono essere sfruttate
Inoltre bisogna effettuare un distinguo tra i [[sistemi batch]] e i [[sistemi interattivi]]. Nei primi il ''throughput'' deve essere massimizzato e il ''Tempo di Turnaround'' deve essere minimizzato. Nei secondi, i sistemi interattivi, il tempo di risposta deve essere il minimo possibile per dare l'idea di continuità all'utente e la proporzionalità deve essere rispettata, ossia il tempo di risposta deve essere proporzionale alla complessità dell'azione.
==Modello Macchina Singola (modello di Karg e Thompson)==
Line 59 ⟶ 57:
===FCFS===
L'algoritmo FCFS (''First Come First Served'') è un tipo di algoritmo [[FIFO]]: esegue i processi nello stesso ordine in cui essi vengono sottomessi al sistema. Il primo processo ad essere eseguito è esattamente quello che per primo richiede l'uso della CPU. Quelli successivi vengono serviti non appena questo ha terminato la propria esecuzione, e così avviene successivamente per tutti gli altri posti in coda. Questo tipo di algoritmo è molto semplice da implementare ma solitamente è anche poco efficiente, almeno considerando il tempo medio d'attesa.
Infatti, prendiamo ad esempio la sottomissione nell'ordine dei seguenti processi con la seguente durata espressa in millisecondi:
Line 69 ⟶ 66:
Verranno eseguiti nello stesso ordine: p1 → p2 → p3
Il processo p1 non attende nulla, perché entra immediatamente in esecuzione. Il processo p2 attende 10 millisecondi, e p3 14. Il tempo medio d'attesa quindi è (0+10+14)/3=8 millisecondi. Si ha allora un effetto convoglio, caratterizzato dal fatto che più processi brevi attendono la terminazione di un unico processo più corposo. Un risultato decisamente diverso da quello ottenibile, in forma teorica, dall'algoritmo ottimale SJF (Shortest Job First) pari a (0+2+6)/3=8/3 millisecondi solamente.
Tuttavia se i processi sono [[CPU-bound]] e lunghi, il [[FCFS]] rimane l'algoritmo migliore.
Line 97 ⟶ 92:
Le prestazioni di quest'algoritmo sono dunque influenzate dal tempo medio d'attesa sebbene consenta a tutti i processi di ottenere il controllo della CPU ed evita quindi il problema dell'attesa indefinita ([[starvation]]).
È inoltre da tenere in considerazione l'impatto dovuto ai frequenti [[context switch]] effettuati. È necessario quindi calcolare correttamente la durata ottimale della quantità di tempo per far sì che l'incidenza dei cambi di contesto sia abbastanza limitata come anche i tempi di attesa. Si può stabilire che, per un funzionamento ottimale, le sequenze di operazioni di CPU dovrebbero essere più brevi della quantità di tempo stabilita in circa l'80 per cento dei casi.
Interessante in questo caso il discorso della media, in quanto risulta molto più stabile di come appare nelle altre strategie. In questo caso, la media va calcolata sommando le 4 differenze tra istante finale di esecuzione del processo e relativo burst. Andando quindi a rappresentare graficamente l'andamento dei processi da p1 a p4, notiamo che p1 termina all'istante 85, p2 all'istante 35, p3 all'istante 145, p4 all'istante 150. Sommando le differenze avremo [(85-30)+(35-15)+(145-60)+(150-45)]/4. La media risultante è 66,25 ms.
Line 114 ⟶ 108:
====SNPF====
L'algoritmo SNPF (''Shortest Next Process First'') prevede che venga eseguito sempre il processo con il tempo di esecuzione più breve tra quelli in attesa. Prendiamo ad esempio che siano stati sottomessi contemporaneamente i seguenti processi, con la rispettiva durata di esecuzione in millisecondi:
*p1: 10
*p2: 2
Line 123 ⟶ 116:
I processi vengono eseguiti nel seguente ordine: p2 → p4 → p3 → p1
Non tenendo in considerazione il tempo necessario per il [[context switch]], il processo p2 non attende nulla, perché entra subito in esecuzione, p4 attende 2 millisecondi, perché entra in esecuzione subito dopo p2, quindi p3 attende 6 millisecondi e p1 ne attende 12. Il tempo medio d'attesa è pari a (0+2+6+12)/4= 5 millisecondi.
Si può dimostrare che questo algoritmo è ottimale, in quanto consente di ottenere sempre il valore più basso di tempo d'attesa medio. Sfortunatamente non è possibile applicarlo, in quanto non è possibile conoscere anticipatamente quanto durerà l'esecuzione del processo. Tuttavia si può provare a predirlo, in quanto è probabile che sia simile ai precedenti.
Line 137 ⟶ 129:
===Multilevel Feedback===
Non potendo stimare con precisione il tempo di esecuzione di un processo nel momento in cui entrerà nel sistema, vi è la possibilità di stimare il tempo trascorso. Viene introdotto il concetto di Feedback secondo il quale si penalizzano i processi che hanno speso più tempo nel sistema. Lo scheduling Multilevel Feedback (o '''Feedback con code multiple''') è uno scheduling basato su quanti di tempo ed utilizza un meccanismo di priorità dinamica. Quando un processo entra nel sistema gli viene assegnata una priorità secondo criteri prefissati e viene inserito in una coda con un quanto di tempo fissato. Se il processo che si trova in stato di Running, finisce il suo quanto di tempo, viene spostato in una coda con un quanto di tempo più grande ma con una priorità minore.
Ogni coda è gestita attraverso l'algoritmo di [[round-robin]], tutte tranne l'ultima che è servita tramite FCFS. Caratteristiche:
*Favorisce processi più corti;
*Con alcuni accorgimenti è possibile evitare condizioni di [[starvation]].
| |||