[Sistemi Operativi] Dispatching: scheduling dei processi

Win Mac Linux

[Sistemi Operativi] Dispatching: scheduling dei processi

0

L’ obbiettivo dello scheduling  del processore è quello di assegnare al processore i processi da eseguire.

Normalmente questa attività viene divisa in tre parti: Long-term schedling, medium-term scheduling e short-term sceduling.

Long-Term scheduling

Questo scheduler si occupa di ammettere o meno i processi al sistema di processamento.

Questo contiene quindi anche la chiave del multitasking: infatti il Long-Term Scheduler deve ammettere o meno dei processi a seconda anche dalle capacità del sistema e al livello di multiprogrammazione che vogliamo raggiungere.
Ad esempio, ammettendo troppi processi, ognuno poi potrebbe venire eseguito per un lasso di tempo breve rallentando tutto il sistema.

Medium-Term scheduling

In questo scheduler troviamo le funzioni di swapping: ovvero si occupa di gestire i trasferimenti dalla memoria principale a quella seconda e viceversa (lo vedremo meglio più avanti).

Short-Term Scheduling

Il Long-term scheduler viene eseguito relativamente raramente, il medium-term potrebbe ipoteticamente non venire eseguito o comunque non frequentemente. Lo Short-Term scheduler invece, aka (also known as) dispatcher, viene eseguito più frequentemente anche perchè è lui che ha la capacità di assegnare priorità per un processo rispetto che un’altro.
Vediamo quindi di analizzare questo dispatcher

Algoritmi di scheduling

Come in tutte le cose, quando scegliamo un algoritmo di scheduling ci troviamo davanti a problemi di ottimizzazione.
Questo vuol dire che,dato un insieme di punti che vedremo fra poco, ottimizzarne uno vuol dire peggiorare un’altro e via dicendo.
Nello specifico, un algoritmo di scheduling deve prevedere:

  • Turnaround Time: Questo è l’intervanno fra la sottomissione del processo e il completamento della sua esecuzione.
  • Response Time: Per i processi interattivi questo è il tempo che passa fra l’ invio di una richiesta e la sua risposta.
  • Scadenza: Quando il completamento di un processo ha una scadenza, il dispatcher dovrebbe impegnarsi nel riuscire a rispettarla o quanto meno ad avvicinarsi il più possibile (es: se più processi hanno tempi di scadenza brevi)
  • Predicibilità: Un processo dovrebbe esseguire nello stesso lasso di tempo e allo stesso costo senza considerare il tempo richieesto dal sistema (overhead).
  • Throughput: Concetto che abbiamo visto anche a reti, il throughput è la quantita di processi risolti per unità di tempo. In pratica una misura di quanto lavoro è stato eseguito.
  • Utilizzo del processore: La percentuale di tempo in cui il processore è al lavoro. In un sistema multi-utente, questo è un fatto molto importante.
  • Giustizia: Già l’avevamo vista in passato: a parità di priorità due processi dovrebbero essere trattati allo stesso modo, e nessuno dovrebbe essere lasciato “morire di fame” (starvation, suona meglio in inglese)
  • Prima le priorità: I processi con priorità maggiore devono essere eseguiti per primi.
  • Bilanciare le risorse: La politica di scheduling dovrebbe mantenere le risorse di sistema il più occupate possibile.

L’ uso delle priorità

Un sistema di scheduling di solito utilizza più code: se sono i, con Q0 intendiamo quella con priorità più alta e Qi quella con priorità più bassa allora il dispatcher si occuperà prima di quelle con priorità più alta.
Un algoritmo che sfrutta un sistema di priorità assoluta però, non è ottimo: questo perchè lascerebbe morire di starvation le code più basse in caso ci sia troppo lavoro “ai piani alti”.
Vediamo quindi alcune politiche di scheduling.

Politiche di scheduling

Una funzione di selezione è quella che sceglie quale processo, fra quelli nello stato ready, vanno prossimamente eseguiti.
Una decisione mode, specifica in che istante deve essere utilizzata la funzione di selezione e si divede in:
Nonpreemptive: Il processo nello stato Running si blocca o perchè và nello stato exit, o perchè richiede un accesso I/O;
Preemptive: Il SO decidere di interrompere il processo e lo manda nello stato ready; e può farlo per diversi motivi.

Vediamo quindi un po di politiche:

First-Come-First-Served

Questa politica è molto semplice: sfrutta il concetto di coda, e tutti i processi che entrano nello stato ready entrano in una coda ready, dove il più vecchio viene servito per primo (First In First Out).

Round Robin

Questa l’avevamo già vista in precedenza parlando dei processi: anche conosciuta come time-slicing, questa politica consiste nell’ assegnare slot temporali ad ogni processo prima di fare il preemptive.

Shortest Process Next

Questa politica ricalca un pò quella di First-Come-First-Served. Shortes process next, tradotto il prossimo processo da eseguire è quello più corto, consiste appunto nell’ eseguire i processi più corti per prima che vengono infatti mandati davanti alla coda rispetto ai processi più lunghi.

Shortest Remaining Time

Una versione preemptive della politica precedente, consiste nel eseguire il processo più rapido prima, e di interrompere quello in esecuzione se un processo che entra nello stato ready impiega meno tempo ad essere eseguito.

About the Author

Federico Ponzi

Studente, Webmaster ed appassionato di tutto ciò che è informatico con una spruzzata di scienza.

View all posts by Federico Ponzi

Leave a Reply