Scheduler: differenze tra le versioni

Versione delle 09:53, 15 gen 2021

Versione delle 19:52, 14 mar 2021

Riga 1:

{{NN|informatica|gennaio 2015}}

{{U|Dispatcher|informatica|agosto 2017}}

[[Immagine:Scheduler.png|thumb|right|Schema di uno Scheduler''scheduler'']]

Lo '''scheduler''scheduler' (dall'[[lingua inglese|inglese]] ''to schedule'' letteralmente "mettere in lista", ovvero "pianificare", (in italiano '''''schedulatore''pianificatore''' o '''gestore didei processi'''), in [[informatica]], è un componente di un [[sistema operativo]] ovvero un [[programma]] che implementa un [[algoritmo]] di ''scheduling (''detto (in italiano algoritmo di schedulazione''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;

* cercare l'ordinamento di richieste che minimizza il rapporto tra tempo di servizio (ovvero il tempo che una richiesta impiega per essere soddisfatta) e tempo di "turnaround" (il lasso di tempo che intercorre tra l'istante in cui la richiesta è generata e quello in cui la richiesta è soddisfatta);

Riga 13:

* dare all'utente del sistema la percezione che le richieste vengano soddisfatte contemporaneamente.

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 gestisono 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''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 e implementati a sua volta attraverso vari tipi di algoritmi di scheduling.

Generalmente infatti [[computer]] con un [[processore]] sono in grado di eseguire un programma per volta, quindi per poter far convivere più task è necessario usare uno ''scheduler''. Nel dettaglio lo scheduler si occupa di fare avanzare un processo interrompendone temporaneamente un altro, realizzando così quellouna che è chiamato "cambiamento[[commutazione di contesto" (''[[context switch]]'') all'interno del [[ciclo del processore]]. Esistono vari [[algoritmo|algoritmi]] di ''scheduling'' che permettono di scegliere nella maniera più efficiente possibile quale task far proseguire: ad esempio il [[kernel]] [[linux]] nella versione 2.4 ha uno scheduler [[teoria della complessità algoritmica|O(n)]], mentre dalla versione 2.6 ha un algoritmo di complessità [[teoria della complessità algoritmica|O(1)]], ossia in grado di determinare in un tempo costante quale processo debba essere eseguito, indipendentemente dal numero di processi in attesa.

Ci sono vari modelli di schedulazione:

* Modello a macchina singola.

* Flow-shop (modello di Johnson).

* Algoritmo euristico di Campbell, Dudek e Smith.

* ''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.

Riga 41:

Per analizzare gli algoritmi che verranno successivamente presentati verrà utilizzato il criterio del tempo d'attesa medio dei processi presi in considerazione.

==== Obiettivi dello ''scheduling'' ====

Un algoritmo di scheduling si pone i seguenti obiettivi:

*''Fairness'' (equità): processi dello stesso tipo devono avere trattamenti simili

Riga 48:

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 Macchinaa Singolamacchina singola (modello di Karg e Thompson)==

Passi dell'Algoritmoalgoritmo:

#Selezionare Casualmentecasualmente due jobs''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., Altrimentialtrimenti finetermina.

===FCFS===

L'algoritmo FCFS (''First Comecome, Firstfirst Servedserved'') è 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:

Riga 128:

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.

===MultilevelRetroazione Feedbackmultilivello===

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 Feedbackretroazione secondo il quale si penalizzano i processi che hanno speso più tempo nel sistema. Lo ''scheduling'' Multilevela Feedbackretroazione multilivello (o '''Feedbackretroazione 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''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:

Riga 136:

===FSS===

L'algoritmo FSS (''Fair Shareshare Schedulingscheduling'') raccoglie i processi in gruppi, così è possibile avere un controllo sulla distribuzione delle risorse computazionali più ampio.

==Scheduling nelle reti==