Corso di Informatica

(1)

28/09/2013 M. Malatesta 3-Schedulazione-0

1

Modulo T3

3-Schedulazione

Corso di Informatica

Prerequisiti

Concetto di media

Concetto di varianza

(2)

3

Introduzione

Come sappiamo, l’assegnazione della CPU ai processi viene gestita dal nucleo, attraverso un meccanismo detto schedulazione. Si tratta di algoritmi speficatamente studiati per massimizzare l’efficienza del sistema.

Quali requisiti deve rispettare un algoritmo di schedulazione?

Come può funzionare uno schedulatore?

Come gestisce il nucleo interi lotti di lavori?

A queste domande diamo una risposta in questa Unità.

Obiettivi della schedulazione

La schedulazione è un algoritmo del nucleo che ha il compito di ordinare le richieste da parte dei processi (di avanzare e di ottenere risorse).

Per fare ciò deve lo schedulatore tenere conto di due obiettivi:

tempi di esecuzione

utilizzo delle risorse

(3)

5

Obiettivi della schedulazione

- tempi di esecuzione

Per questo parametro, possiamo valutare:

tempo di completamento (turnaround time): indica l’intervallo di tempo compreso fra l’inizio del processo e il suo completamento;

tempo di risposta: indica intervallo di tempo tra l’invio di una richiesta e la prima risposta prodotta;

tempo di attesa: indica la somma degli intervallo di tempo trascorsi in attesa nella ready list;

tasso di servizio, indica il numero medio di processi serviti nell’unità di tempo.

Obiettivi della schedulazione

- tempi di esecuzione

Per cui, da un lato occorre:

garantire l’avanzamento di tutti i processi, (condizione detta fairness) senza tempi di attesa eccessivi o indefiniti;

dall’altro occorre:

minimizzare il tempo di completamento

minimizzare i tempi di attesa: fare in modo che sia massimo il numero di utenti interattivi che nell’esecuzione dei comandi abbiano risposte in tempi accettabili;

minimizzare la varianza dei tempi di attesa: far sì che il tempo di attesa medio degli utenti nell’eseguire i comandi sia prevedibile;

massimizzare il tasso di servizio dei processi (throughput);

(4)

7

Obiettivi della schedulazione

- utilizzo delle risorse

Il requisito di utilizzo delle risorse richiede:

utilizzo teorico CPU al 100%;

garanzia di assegnazione (assunzione di progresso finito).

In pratica, occorre:

stabilire priorità tra le risorse, ossia un ordine di importanza di queste in base al loro pregio (CPU, memoria centrale e memoria secondaria);

favorire un utilizzo uniforme, evitando il sovraccarico di alcune risorse a vantaggio di altre in certi intervalli di tempo;

minimizzare il costo della schedulazione, ossia evitare algoritmi di scheduling complessi al punto da assorbire eccessivamente le risorse, come tempo o quantità (scheduling overhead).

Tipi di schedulazione

La schedulazione dei processi avviene di solitto su un modello gerarchico a due livelli:

basso livello (breve termine )

alto livello (lungo termine)

Il livello indica il tipo di risorsa gestita, per cui il primo tipo di

schedulazione riguarda i processori, quello di alto livello riguarda i job.

Possiamo anche considerare un terzo livello intermedio che riguarda la

memoria, ma per semplicità ci riferiamo solo ai primi due.

(5)

9

Tipi di schedulazione

- a basso livello

Come sappiamo, viene detto anche schedulatore a breve termine (Short Term Scheduler o Dispatcher) e serve a gestire in modo ottimale i processori. Dato un processo P in esecuzione, questo schedulatore agisce nelle seguenti transizioni:

esecuzione blocco (P prerilascia la CPU poichè richiede I/O)

rilascio volontario della CPU da parte di P (P termina o abortisce)

esecuzione pronto (P prerilascia la CPU poichè termina il quanto)

esecuzione di un processo P’ in luogo di P (P’ priorità maggiore di P)

Tipi di schedulazione

- a basso livello

L’algoritmo di scheduling viene eseguito con un frequenza molto alta (anche migliaia di volte al secondo) pertanto deve essere:

molto efficiente

svolto interamente dal nucleo

Occorre tenere presente che il tempo di assegnazione della CPU:

non deve essere troppo breve, per evitare troppi context switch con conseguente riduzione di efficienza della CPU;

non deve essere troppo lungo, per non appesantire i tempi di risposta,

specialmente con processi interattivi.

(6)

11

Tipi di schedulazione

- a basso livello (round robin)

Illustriamo, in ordine evolutivo, le tre tecniche utilizzate per lo schedulatore a basso livello nel caso di sistemi interattivi:

round robin

foreground-background

multilevel feedback

Tipi di schedulazione

- a basso livello (round robin)

La tecnica round robin utilizza il prerilascio, tipica del time-sharing.

Ad ogni processo è assegnato a turno un quanto di tempo (time slice). Se un

processo presente nella ready list (che è gestita con disciplina FIFO,

quindi come una coda) richiede un’operazione di I/O di durata superiore

al quanto, esso abbandona la ready list.

(7)

13

Tipi di schedulazione

- a basso livello (round robin)

L’avvicendamento dei vari processi alla coda può avvenire con provenienze diverse, come mostrato dallo schema sottostante.

Tipi di schedulazione

- a basso livello (foreground-background)

La tecnica foreground-background è un miglioramento della tecnica precedente e consiste nel far sì che i processi che richiedono I/O siano favoriti rispetto a quelli che richiedono computazione.

Ciò è realizzato ripartendo i due tipi di processi in due code con differente priorità:

coda background, per priorità più basse

coda foreground, per priorità più alte

Per evitare che processi con

una priorità alta vengano

eseguiti indefinitamente, lo

scheduler decrementa la

priorità del processo in

esecuzione ad ogni interrupt

(8)

15

Tipi di schedulazione

- a basso livello (multilevel feedback)

La tecnicamultilevel feedback, considerata la migliore, consiste nel decomporre lo stato di pronto in tante code (classi di priorità) quante sono le priorità dei processi presenti. Il nucleo selezionerà il processo da porre in esecuzione, partendo dalla coda con priorità massima.

Tipi di schedulazione

- a basso livello (multilevel feedback)

La coda Q1 è quella a priorità massima. Se un processo utilizza

esclusivamente il quanto T1, allo scadere di questo terminerà, altrimenti verrà inserito in Q2 e riceverà, al momento opportuno, un quanto T2 (T2>T1). Se esaurisce anche il quanto T2, passerà in Q3 e riceverà un quanto T3 e così via.

In molti casi si ha T

_i+1

=2*T

_i

, per agevolare i processi più pesanti.

Il quanto T

_i

viene assegnato

comunque in time sharing,

(9)

17

Tipi di schedulazione

- a basso livello (multilevel feedback)

Ad esempio. Windows 2000 adotta una strategia di scheduling a code multiple con priorità, in modo da agevolare, da un lato, i processi che richiedono I/O rispetto a quelli che richiedono la sola computazione, ma dall’altro anche cercando di favorire l’interattività.

Ad esempio, supponiamo:

di avere due processi P1 e P2 con la stessa priorità;

che T sia il quanto di tempo;

che P1 sia in esecuzione;

se P2 termina un’operazione di I/O, Windows agisce in modo che P1 prerilasci il processore, in favore di P2, favorendo quindi un buon livello di interattività.

Tipi di schedulazione

- ad alto livello

Nel caso di sistemi a lotti (batch) la tecnica utilizzata consiste nel multiprogrammare gruppi di processi su processori diversi.

Il sistema valuta con cadenza costante le percentuali di utilizzo dei processori da parte dei processi e:

seleziona quelli che usano maggiormente tempo di CPU, rispetto a quelli che usano maggiormente processori di I/O;

diminuisce la priorità dei processi del primo tipo e aumenta quella dei

processi del secondo tipo, in modo che essi risultino favoriti a beneficio

della produttività del sistema.

(10)

19

Tipi di schedulazione

- ad alto livello

Lo schedulatore ad alto livello, detto anche schedulatore a lungo termine (Long Term Scheduler o Job Scheduler) è tipico dei sistemi a lotti in cui occorre gestire i vari job presenti.

Ovviamente, affinchè lo scheduler possa operare, i vari job devono prevedere:

le risorse necessarie, indicate nelle apposite schede iniziali del job;

le operazioni richieste sulle risorse (montare volumi a disco o nastro, caricare carta speciale sulla stampante, ecc) che possono coinvolgere l’intervento dell’operatore e che comportano quindi tempi lunghi (dell’ordine dei minuti).

Tipi di schedulazione

- ad alto livello

Le operazioni sui vari job possono coivolgere:

uso di periferiche: in questo caso l’operatore assegna al job le risorse richieste agendo con comandi di console;

uso di risorse privilegiate (memoria, spazio su disco): in questo caso l’operazione è svolta da processi di sistema.

Anche in questo tipo di schedulazione il nucleo è responsabile

dell’assegnazione delle risorse ai vari job e deve essere in

grado di attuare il prerilascio delle risorse da parte di un job

nel caso se ne presenti uno con priorità maggiore, curando il

(11)

21

Altre tecniche di schedulazione

- FCFS

Nella tecnica FCFS (First Came First Served), i processi vengono gestiti con una coda, in base all’ordine di arrivo.

Esempio:

Si può calcolare il tempo medio di attesa con:

T

_ma

= (0 + 30 + 48) / 3 = 26 msec P3 P2

P1

40 msec 48 msec

30 msec

Altre tecniche di schedulazione

- SJF

La tecnica SJF (Shortest Job First) dà la precedenza ai processi più brevi (in genere usato per lo scheduling ad alto livello).