Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Domenico Cotroneo » 5.Scheduling nei sistemi mono-processore


Sommario della lezione

  • Schedulatore
  • Algoritmi di scheduling
  • Tipologie di schedulatori
  • Scheduling a Priorità
  • Starvation
  • Preemption
  • Tipi di algoritmi di scheduling

Schedulatore dei processi


Schedulatore

Lo schedulatore (o scheduler) è quella parte del S.O. preposta all’assegnazione di risorse a favore dei processi.

La selezione di un processo in una coda può avvenire mediante differenti criteri, a seconda dell’algoritmo di scheduling che implementa uno schedulatore.

Tipologie di Scheduler

  • Schedulatore a breve termine o scheduler della CPU.
  • Schedulatore a medio termine o schedulatore di swap (swapper).
  • Schedulatore a lungo termine o schedulatore di job.

Tipologie di Scheduler


Lo scheduler di lungo termine

Determina quale programma caricare nella coda dei processi pronti del sistema.

Pertanto controlla il grado di multiprogrammazione del sistema.

Ogni volta che un processo termina, lo scheduler di lungo termine dovrà sceglierne uno nuovo da caricare. La decisione è fatta secondo uno o più criteri:

  • FIFO;
  • priorità;
  • tempo di esecuzione presunto;
  • requisiti di I/O;
  • tempo presunto di CPU.

Lo scheduler di lungo termine

Caso tipico: al fine di aumentare l’efficienza d’utilizzo delle risorse, lo scheduler di lungo termine tenta di mantenere nel sistema un numero comparabile di processi CPU-bound e I/O bound.

Lo scheduler di medio termine

Rappresenta quella funzione del SO che ha il compito di trasferire temporaneamente processi (o parte di essi) dalla memoria centrale alla memoria di massa (swap-out) e viceversa (swap-in).
Viene utilizzato:

  • per liberare parte della memoria centrale, oppure
  • per rendere possibile il caricamento di altri processi.

Il suo obiettivo è quello di migliorare l’efficienza nell’utilizzo della risorsa memoria.

Lo scheduler di breve termine

Conosciuto anche con il nome di Dispatcher, è lo scheduler che viene attivato più frequentemente nel sistema.
Ha il compito di scegliere a quale tra i processi pronti assegnare la CPU.

Lo scheduler di breve termine viene invocato all’occorenza di un evento che comporta la sospensione del processo in esecuzione. Tra gli eventi si possono annoverare:

  • interruzioni del Clock (timer);
  • interruzioni di I/O;
  • system call;
  • segnali (ad esempio semafori).

Algoritmo di scheduling

L’obiettivo dell’algoritmo di scheduling del Dispatcher è quello di allocare il processore in maniera tale da ottimizzare uno o più aspetti del comportamento del sistema.

I criteri più utilizzati sono:

  • User-oriented. Si riferiscono al comportamento del sistema così come percepiti dall’utente o da un processo (ad es. tempo di risposta).
  • System-oriented. L’obiettivo è quello di utilizzare in modo efficiente il processore (ad es. il throughput).

Parametri User-Oriented

Tempo di turnaround: è l’intervallo di tempo che trascorre dall’istante in cui un processo è sottomesso al sistema e l’istante della sua terminazione. Tiene conto del tempo effettivo di esecuzione e del tempo speso in attesa delle risorse (CPU inclusa). E’ un parametro significativo per i processi batch.

Tempo di risposta: per un processo interattivo, indica il tempo che trascorre dall’istante della sottomissione di una richiesta fino all’istante in cui la risposta inizia ad essere ricevuta, anche se il processo potrebbe continuare l’esecuzione.

Deadlines: nel caso in cui si possa specificare il termine di completamento di un processo (deadline), la disciplina di scheduling ha l’obiettivo di massimizzare la percentuale di scadenze raggiunte.

Parametri System-Oriented

Throughput: misura la produttività di un sistema in termini di numero di processi terminati per unità di tempo. Questo parametro dipende fortemente dalla lunghezza media di un processo ma è anche influenzato dalla particolare politica adottata per la schedulazione.

Utilizzo della CPU: rappresenta la percentuale di tempo per cui il processore risulta occupato.

Fairness: salvo contrarie indicazioni da parte dell’utente, tutti i processi dovrebbero essere trattati allo stesso modo e nessuno di essi dovrebbe potersi trovare in situazioni di attesa indefinita.

Esiste un alg. PERFETTO?

Naturalmente NO!

I parametri prima definiti sono interdipendenti ed alcuni sono persino in contrasto tra loro.
Ad esempio fornire un tempo di risposta minimo richiede un algoritmo che esegue un context switch molto frequente. Ciò accresce l’overhead del sistema, abbassando notevolmente il throughput.

\Downarrow

Il progetto e l’implementazione di una politica di scheduling implica sempre un compromesso tra vari requisiti contrastanti. La scelta dovrà essere fatta tenendo conto “per cosa dovrà essere utilizzato il sistema“.

L’utilizzo delle Priorità

Lo Scheduler può scegliere i processi in base alla loro priorità.

Le priorità possono essere:

  • statiche, se non si modificano durante il periodo di vita dei processi;
  • dinamiche, se durante il loro ciclo di vita i processi possono modificare la loro priorità in base ad alcuni parametri (tempo di CPU, tempo di I/O).

I processi tipicamente sono raggrupati in classi di priorità: l’algoritmo di scheduling dovrà scegliere un processo pronto che appartiene alla classe di priorità più alta.

Starvation

L’utilizzo di un algoritmo di scheduling a priorità può indurre situazioni di attesa indefinita di processi a priorità più bassa (starvation).

Per far fronte a siffatte situazioni si utilizzano schemi di priorità dinamiche (es. aumento graduale della priorità dei processi che si trovano in attesa nel sistema da lungo tempo (Aging)).

Preemption

Lo scheduler di breve termine può essere

Nonpreemptive

  • Una volta che il processo è nello stato di Esecuzione, esso continuerà in tale stato fin quando non si sospenderà (ad es per una system call o per una op. di I/O etc…).

Preemptive

  • Un processo in stato di esecuzione può essere interotto e spostato nello stato Pronto dal SO.
  • Tale scheduler previene situazioni in cui un processo può monopilazzare l’uso del processore.

Un esempio di riferimento

Per illustrare i vari algoritmi ci riferiremo al seguente esempio:

\begin{tabular}{|c|c|c|}\toprule Process&Arrival Time&Service Time \\A&0&3 \\ B&2&6 \\ C&4&4 \\ D&6&5 \\E&8&2 \\ \bottomrule \end{tabular}

Parametri utilizzati:

  • FinishTime per ogni processo;
  • Tempo di Tournaround Tr;
  • Il rapporto Tr/Ts è un indicatore del ritardo relativo di ogni processo (più è grande il service time, Ts, più alto è il ritardo tollerabile del processo).

First-Come-First-Served (FCFS)

Quando il processo cessa la sua esecuzione, viene scelto il processo che attende da più tempo.

FinishTime TA=3, TB= 9, TC=13, TD=18, TE=20
Tournaround TrA=3, TrB= 7, TrC=9, TrD=12, TrE=12
TrA/TsA=1, TrB/TsB=1.17, TrC/TsC=2.25
TrD/TsD=2.40, TrE/TsE=6.00

Il processo E spende nel sistema un tempo che è 6 volte quello di esecuzione.


First-Come-First-Served (FCFS)

Un processo con tempo di esecuzione corto può aspettare un tempo molto lungo prima di essere eseguito.

Favorisce i processi CPU-bound.

  • I processi I/O-bound devono attendere il completamento di quelli CPU-bound (effetto convoglio).

First-Come-First-Served(FCFS): effetto convoglio

Un processo CPU-bound e molti processi I/O bound.

Via via che fluiscono i processi nel sistema si può riscontrare come il processo CPU-bound occupi la CPU (i processi I/O occupano la CPU per un periodo breve a favore del processo CPU-bound).

L’effetto è che tutti i processi attendono che un lungo processo liberi la CPU, causando una riduzione dell’utilizzo della CPU stessa e dei dispositivi rispetto alla situazione che si avrebbe se si eseguissero per primi i processi più brevi.

Round-Robin

Nasce dalla trasformazione preemptive del FCFS mediante l’impiego di un timer.

Le prestazioni dell’algoritmo sono dipendenti dalla durata del periodo del timer che definisce il quanto di tempo di massimo utilizzo della risorsa o time slice (valori tipici da 10 a 100 msec).

Aumentando il time slice tende a trasformarsi in FCFS, mentre diminuendolo aumentano i salvataggi e ripristini di stato dei processi e quindi l’overhead del S.O.

Round-Robin

TA=4, TB= 18, TC=17, TD=20, TE=15
TrA=4, TrB= 16, TrC=13, TrD=14, TrE=7
TrA/TsA=1.33, TrB/TsB=2.67, TrC/TsC=3.25
TrD/TsD=2.80, TrE/TsE=3.50
Con il round-robin il processo E dimezza il suo ritardo relativo.


Round-Robin: scelta del quanto di tempo

A. Il quanto di tempo q dovrebbe essere leggermente superiore del tempo s richiesto per una tipica interazione.

B. Se inferiore, la maggior parte dei processi richiederà almeno due quanti di tempo!


Shortest Process Next

Può avere sia uno schema non-preemptive sia preemptive (chiamato Short Remaining Time).

Vengono selezionati i Processi con il minor tempo di esecuzione stimato.

Uno scheduling progettato al fine di rendere minimo il tempo medio di attesa per un dato insieme di processi

…al costo di rendere i tempi di risposta medi più lunghi (specialmente per i processi lunghi).

Shortest Process Next

TA=3, TB= 9, TC=15, TD=20, TE=11
TrA=3, TrB= 7, TrC=11, TrD=14, TrE=3
TrA/TsA=1, TrB/TsB=1.17, TrC/TsC=2.75
TrD/TsD=2.80, TrE/TsE=1.50

Possibilità di starvation per i processi più lunghi (ad es., il processo D).


SPN: stima del tempo di servizio

SPN richiede di conoscere, o almeno stimare, il tempo di servizio di ciascun processo.

In un sistema batch, questa stima potrebbe essere richiesta al programmatore, o effettuata dal SO su basi statistiche (in base alle esecuzioni passate del job).

In un sistema interattivo, il SO può stimare il tempo di servizio (n+1)-mo di ciascun processo come media dei “burst” di esecuzione passati (da 1 a n):

S_{n+1}=\frac 1 n \sum_{i=1}^n T_i=\frac 1 n T_n + \frac{n-1}n S_n

dove:

  • S_{n+1} è il tempo di esecuzionedel burst i-mo;
  • T_i è il valore predetto per il burst (n+1)-mo;
  • S_n è il valore predettoper il burst n-mo.

SPN: stima del tempo di servizio

Questa stima da ugual peso ad ogni Ti.

… e se la stima del tempo di esecuzione è non corretta, l’algoritmo può andare in crisi.

Un’alternativa è dare un peso maggiore ai Ti più recenti, in quanto più rappresentativi del comportamento futuro del processo.

A tal scopo, viene utilizzata una stima basta su media esponenziale:

S_{n+1}=\alpha T_n+(1-\alpha) S_n \;\;\;\;\; 0<\alpha<1

SPN: valori dei coefficienti di stima

S_{n+1}=\alpha T_n+(1-\alpha)\alpha T_{n-1}+\;\;\;+(1-\alpha^i \alpha T_{n-i})+\;\;\;+(1-\alpha)^n S_1


SPN: confronto tra media semplice e media esponenziale


Shortest Remaining Time

E’ la versione Preemptive dell’alg. Shortest Process Next.

La prelazione della CPU avviene quando entra in coda un nuovo processo con tempo di servizio inferiore al tempo di servizio rimanente al processo running.

Nell’esempio tutti i processi più piccoli non hanno ritardo.

TrA/TsA=1, TrB/TsB=2.17, TrC/TsC=1
TrD/TsD=2.80, TrE/TsE=1


Shortest Remaining Time

Come per SPN, c’è il problema della stima del tempo di servizio.

Ci può essere starvation per i processi lunghi.

Prestazioni comparabili al Round Robin:

  • RR genera più interruzioni dovute alla scadenza del quanto di tempo _ maggiore overhead per i context switch;
  • d’altra parte, SRT introduce un overhead dovuto alla memorizzazione e gestione dei tempi di servizio.

Feedback

Motivazioni

  • Se non si hanno indicazioni sulla lunghezza relativa dei vari processi risulta difficile, se non impossibile, utilizzare gli algoritmi SPN, SRT.
  • Se non è possibile avere una stima sul tempo di esecuzione sicuramente però sarà possibile avere informazioni sul tempo speso da un processo nel sistema.
  • Pertanto si possono penalizzare i processi che hanno speso più tempo nel sistema.

Multilevel Feedback

Lo scheduling è di tipo preemptive basato su quanto di tempo, code multiple, e priorità
… è utilizzato un meccanismo di priorità dinamico (se un processo usa “troppo” tempo di CPU, viene spostato in una coda con priorità minore).

  • Quando un processo entra nel sistema si pone nella coda a più alta priorità (RQ0).
  • Dopo la prima prelazione il processo ritorna nello stato di ready nella coda RQ1
  • …così via fino ad arrivare alla coda a minima priorità (RQn).

Mantiene i processi con prevalenza di I/O e i processi interattivi nelle code a priorità più elevata.

Scheduler a Priorità


Multilevel Feedback

E’ caratterizzato da i seguenti parametri:

  • numero di code;
  • alg. di scheduling per ciascuna coda;
  • criteri per lo spostamento dei processi tra le varie code.

Costituisce il più generale criterio di scheduling della CPU, che nella fase di progettazione si può adeguare a un sistema specifico.

E’ anche l’algoritmo più complesso da implementare.

Multilevel Feedback

Favorisce i processi più corti.

Il tempo di tournaround dei processi lunghi può crescere sensibilmente. Può esserci anche starvation per particolari condizioni di carico.

Per minimizzare la probabilità del verificarsi di situazioni di starvation viene adottato il seguente schema:

  • ad un processo contenuto nella coda RQi vengono assegnati 2i quanti di tempo.

Per evitare completamente la starvation si può anche permettere ad un processo contenuto nella coda RQn di transitare nuovamente nella coda RQ0.

Multilevel Feedback


Multilevel Feedback

Caratteristiche delle differenti politiche di schedulazione
w= tempo di attesa; e= tempo di esecuzione; s= tempo di servizio, incluso e

Caratteristiche delle differenti politiche di schedulazione w= tempo di attesa; e= tempo di esecuzione; s= tempo di servizio, incluso e


Multilevel Feedback


I materiali di supporto della lezione

P. Ancilotti, M.Boari, A. Ciampolini, G. Lipari, “Sistemi Operativi”, Mc-Graw-Hill (Cap.2)

Dispense fornite tratte dallo Stallings

Testi di Approfondimento

W. Stallings, “Operating Systems : Internals and Design Principles (6th Edition) ”, Pearson Education (Cap. 9)

A. Silbershatz, G. Gagne, "Sistemi Operativi" (sesta edizione), Addison-Wesley

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion