Scheduler: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Collegamenti esterni: Aggiunto il template "Garzanti" |
fix |
||
Riga 1:
{{NN|informatica|gennaio 2015}}
{{U|Dispatcher|informatica|agosto 2017}}
[[
Lo '''''scheduler''''' (in italiano '''pianificatore''' o '''gestore dei processi'''), in [[informatica]], è un componente di un [[sistema operativo]] ovvero un [[programma]] che implementa un [[algoritmo]] di ''scheduling'' (in italiano algoritmo di pianificazione) il quale, dato un insieme di richieste di accesso ad una [[risorsa informatica|risorsa]] (tipicamente l'accesso al [[processore]] da parte di un [[processo (informatica)|processo]] da [[esecuzione (informatica)|eseguire]]), stabilisce un ordinamento temporale per l'[[esecuzione (informatica)|esecuzione]] di tali richieste, privilegiando quelle che rispettano determinati parametri secondo una certa politica di ''scheduling'', in modo da ottimizzare l'accesso a tale risorsa e consentire così l'espletamento del servizio/istruzione o processo desiderato.
L'attenzione posta su alcuni parametri piuttosto che su altri differenzia la cosiddetta politica di scheduling all'interno della gestione dei processi dando vita a [[coda di priorità|code di priorità]]: ad esempio lo scheduler può eseguire le richieste in base al loro ordine di arrivo ([[FIFO]]), oppure dare precedenza a quelle che impegnano per meno tempo la risorsa ([[SNPF]]); possono esistere politiche che si basano su principi statistici o sulla predizione per individuare un ordinamento delle richieste che si avvicini il più possibile a quello ottimale.
== Descrizione ==
Generalmente l'obiettivo dello ''scheduling'' è quello di:
* massimizzare il ''[[throughput]]'', ovvero la produttività dell'intero sistema, minimizzando i tempi in cui la risorsa è inutilizzata;
Line 15 ⟶ 16:
Esistono in realtà molti requisiti che possono essere presi in considerazione, dipendenti anche dal problema specifico che lo ''scheduler'' deve gestire: esistono scheduler che si occupano di suddividere il tempo di uso del processore da parte di un processo, ''scheduler'' che gestiscono richieste di lettura/scrittura da una periferica, anche gli [[memoria virtuale|algoritmi di sostituzione delle pagine]] della memoria sono da considerarsi ''scheduler''.
=== ''Scheduler'' a breve termine del processore (''dispatcher'') ===
È un componente fondamentale dei [[Sistema operativo|sistemi operativi]] [[multitasking|multiprocesso]], e sicuramente l'esempio più diffuso e critico di ''scheduler''. È in grado di far eseguire, al [[processore]] di un [[computer]], attraverso l'omonima operazione di scheduling, più [[processo (informatica)|processi]] (''task'') concorrentemente attraverso varie politiche di scheduling. Esso rappresenta dunque il gestore del multitasking attraverso criteri di assegnazione delle risorse di memorizzazione/elaborazione ai vari processi, implementati a loro volta attraverso vari tipi di algoritmi di scheduling.
Line 26 ⟶ 27:
* ''Job-shop''.
=== ''Scheduling'' della CPU ===
{{
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.
Line 33 ⟶ 35:
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:
* Utilizzo del processore: la [[CPU]] (ovvero il processore) deve essere attiva il più possibile, ovvero devono essere ridotti al minimo i possibili tempi morti.▼
* Throughput: il numero di processi completati in una determinata quantità di tempo.▼
▲*Utilizzo del processore: la [[CPU]] (ovvero il processore) deve essere attiva il più possibile, ovvero devono essere ridotti al minimo i possibili tempi morti.
* Tempo di
▲*Throughput: il numero di processi completati in una determinata quantità di tempo.
*
* Tempo
▲*Tempo di risposta: il tempo che trascorre tra la sottomissione del processo e l'ottenimento della prima risposta.
Per analizzare gli algoritmi che verranno successivamente presentati verrà utilizzato il criterio del tempo d'attesa medio dei processi presi in considerazione.
Line 44 ⟶ 45:
==== Obiettivi dello ''scheduling'' ====
Un algoritmo di scheduling si pone i seguenti obiettivi:
* ''Fairness'' (equità): processi dello stesso tipo devono avere trattamenti simili
* ''Balance'' (bilanciamento): tutte le parti del sistema devono essere sfruttate
Inoltre bisogna effettuare un distinguo tra i [[Batch|sistemi batch]] e i [[Interattività|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 a macchina singola (modello di Karg e Thompson) ==
Passi dell'algoritmo:
# Selezionare casualmente due ''job''.
# Selezionare un nuovo ''job'' e provare a disporlo nella sequenza corrente.
# Per ogni posizione provata calcolare il ''set-up'' complessivo.
# Allocare il ''job'' nella posizione che garantisce i più bassi tempi di ''set-up''.
# Se vi sono ancora ''job'' da allocare vai al passo 2, altrimenti termina.
=== 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.
Line 71 ⟶ 72:
Tuttavia se i processi sono [[CPU-bound]] e lunghi, il [[FCFS]] rimane l'algoritmo migliore.
=== RR ===
{{vedi anche|Schedulazione round robin}}
L'algoritmo di scheduling RR (''round-robin'') è un particolare algoritmo con prelazione (preemptive) che esegue i processi nell'ordine d'arrivo, come il FCFS, ma esegue la prelazione del processo in esecuzione, ponendolo alla fine della coda dei processi in attesa, qualora l'esecuzione duri più della "quantità di tempo" stabilita, e facendo proseguire l'esecuzione al successivo processo in attesa.
Line 98 ⟶ 100:
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 (Tempo di attesa).
=== SJF ===
{{
Gli algoritmi SJF (''[[shortest job first]]''), possono essere sia non-preemptive (SNPF) sia preemptive (SRTF).
Line 110 ⟶ 113:
*<math>\alpha = 1 \Rightarrow \tau_{n+1} = t_n</math> (conta solo l'ultimo valore reale del CPU burst)
==== 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
Line 125 ⟶ 128:
Una tecnica comunemente usata è quella di utilizzare la [[Media mobile|media mobile esponenziale]]: <math>\tau_{n+1} = \alpha t_n + (1-\alpha) \tau_n</math> dove <math>\tau_n</math> è la stima dell'n-esima esecuzione del processo, <math>\tau_{n+1}</math> la stima attuale e <math>\alpha</math>∈<math>[0,1]</math> è il peso che deve essere assegnato al passato del processo e in genere per <math>\alpha=1/2</math> si ha una discreta approssimazione del comportamento del processo e un risultato accettabile.
==== SRTF ====
L'algoritmo SRTF (''Shortest Remaining Time First'') si differenzia per il fatto che, quando viene sottomesso un nuovo processo la cui durata è minore del tempo necessario al processo in esecuzione per portare a terminare la propria sessione, lo scheduler provvede ad effettuare un [[context switch]] e assegna l'uso della CPU al nuovo processo (prelazione - algoritmo preemptive). Il vantaggio è una gestione ottimale del [[tempo di attesa]] medio, in quanto processi dalla durata di esecuzione ridotta vengono eseguiti molto velocemente. Tra gli svantaggi potenziali, come avviene per l'SRT, vi è il fenomeno della [[starvation]] dei processi in quanto processi con tempi di esecuzione rimanenti lunghi potrebbero rimanere in attesa indefinitamente nel caso venissero continuamente aggiunti processi di durata rimanente inferiore.
==== HRRN ====
L'algoritmo HRRN (''Higher Responsive Ratio Next'') viene utilizzato per prevenire l'aging, ossia l'attesa eccessiva dei processi molto lunghi scavalcati da quelli più corti tramite SNPF e SRTF e si basa sul tempo di attesa di un processo utilizzando la formula <math>Ratio=(W+S)/S</math> dove <math>W</math> è il tempo di attesa e <math>S</math> il prossimo CPU-burst (consumo della [[CPU]]) stimato.
=== Retroazione multilivello ===
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 retroazione secondo il quale si penalizzano i processi che hanno speso più tempo nel sistema. Lo ''scheduling'' a retroazione multilivello (o retroazione 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 ''running'' finisce il suo quanto di tempo, viene spostato in una coda con un quanto di tempo più grande ma con una priorità minore.
Line 138 ⟶ 141:
*Con alcuni accorgimenti è possibile evitare condizioni di [[starvation]].
=== FSS ===
L'algoritmo FSS (''Fair share scheduling'') raccoglie i processi in gruppi, così è possibile avere un controllo sulla distribuzione delle risorse computazionali più ampio.
== Scheduling nelle reti ==
Nell'ambito delle [[rete di telecomunicazioni|reti di telecomunicazioni]] in maniera molto simile al contesto informatico il termine "''scheduling''" indica il processo, messo in atto dallo scheduler in uscita ad un [[nodo (informatica)|nodo]] di [[commutazione a pacchetto]], per selezionare e assegnare secondo varie possibili classi di priorità il diritto di [[trasmissione (telecomunicazioni)|trasmissione]] alle varie possibili code ([[buffer]]) di [[pacchetto (reti)|pacchetti]] in situazione di [[congestione (reti)|congestione]] garantendo il rispetto dei parametri di [[qualità di servizio]] (QoS) da offrire all'utente per le varie tipologie di traffico in ingresso.
| |||