Scheduling
A. Ferrari
Terminato
Nuovo
interruzione
ammissione
Coda Pronti
uscita
in
esecuzione
Pronto
assegnazione
evento verificato
attesa evento (es. I/O)
bloccato
Code di Attesa
Tipi di processi
CPU Bound
Processi che sfruttano pesantemente le risorse
computazionali del processore, ma non richiedono servizi di
ingresso/uscita dati al sistema operativo in quantità
rilevanti.
Es. i programmi di calcolo matematico, i quali necessitano
spesso di un'enorme potenza di calcolo, ma sfruttano l'I/O
solo all'inizio della loro vita (per caricare gli input) ed alla
fine di essa (per produrre gli output).
I/O Bound
molti accessi alle periferiche, il processo è spesso interrotto
per attendere il completamento delle richieste di I/O.
P1 (CPU bound)
P2 /I/O bound)
P1
Lungo burst di CPU
Attesa completamento I/O
Corto burst di CPU
P2
tempo
In esecuzione
In attesa
Classi di scheduling
Nella gestione delle risorse di un elaboratore, il
fattore tempo porta a identificare tre tipi di
scheduling:
Scheduling a breve termine
Scheduling a medio termine
Scheduling a lungo termine
Scheduling
a lungo termine
E’ impiegato nella scelta dei programmi, presenti in
memoria secondaria, da caricare in memoria centrale
per la creazione dei corrispondenti processi
individua i programmi da ammettere all’esecuzione
regola la presenza in memoria centrale di processi I/O
bound e CPU bound
controlla il livello di multiprogrammazione
Scheduling
a medio termine
Gestisce la permanenza in memoria dei processi non
in esecuzione
coordina le operazioni di trasferimento temporaneo
dei processi in memoria secondaria (swap out):
interviene nella gestione dei processi in attesa di
eventi da lungo tempo
Scheduling
a breve termine
Si occupa della selezione del nuovo processo da eseguire,
quando
il processo in esecuzione passa allo stato di attesa o ritorna
allo stato di pronto oppure termina
un processo passa dallo stato di attesa allo stato di pronto
si verificano eventi particolari (interruput, chiamate al S. O.)
Quando la CPU rimane inattiva, il process scheduler
(modulo del kernel) seleziona dalla ready queue (coda dei
processi pronti) il prossimo processo a cui assegnare la
CPU e decide da quale momento e per quanto tempo farlo
eseguire.
Context switch
Il context switch (commutazione di contesto) è la fase in
cui l’uso della CPU passa da un processo pi al suo
successivo pi+1
Nella fase di passaggio il SO realizza, in sequenza, le
seguenti operazioni:
Salvataggio dello stato del processo pi uscente
Selezione del nuovo processo pi+1
Ripristino dello stato del processo pi+1 entrante
Si modifica, in questo modo, il contesto in cui lavora il
processore.
Durata del
context switch
Il tempo utilizzato dal SO per le operazioni di context
switch, in rapporto al time-slice (quanto di tempo di
CPU), non deve essere causa di
riduzione dell’efficienza della CPU
lunghi tempi di risposta
A tal fine, il tempo di context switch non deve
superare il 25% del time-slice (solitamente di circa 100
ms)
Dispatcher
L’effettiva assegnazione della CPU al processo
prescelto per l’esecuzione è affidata al dispatcher,
modulo del kernel che gestisce
il context switch
il passaggio al modo utente
il salto alla giusta posizione del programma utente
(impostazione del program counter)
Politiche di scheduling:
obiettivi
massimizzare
il throughput (numero di processi utente completati nell’unità di tempo)
l’utilizzo della CPU (percentuale media di utilizzo della CPU nell’unità di
tempo)
minimizzare
l’overhead (numero di processi di sistema completati nell’unità di tempo)
il tempo di turnaround (tempo di permanenza di un processo nel sistema)
il tempo di risposta (tempo trascorso tra l’immissione di un comando e
l’emissione della prima risposta)
il tempo di attesa (tempo totale trascorso da un processo nello stato di
pronto)
garantire
fairness (equità) (imparzialità nell’attribuzione dei time-slice ai processi)
Tipi di sistemi
Ogni algoritmo di scheduling della CPU è finalizzato
al raggiungimento di alcuni obiettivi.
Nei sistemi batch (elaborazione a lotti) si cerca di
massimizzare il throughput e di minimizzare
l’overhead.
Nei sistemi interattivi (tempi di risposta immediati) è
essenziale minimizzare i tempi di risposta e di attesa
dei processi.
Parentesi storica
IBM 7094
IBM 7094
The 7094 was IBM's most powerful scientific computer in
1963. It could perform 500,000 logical decisions, 250,000
additions or subtractions, 100,000 multiplications, or
62,500 divisions in one second. It had hardware to do
double-precision floating-point arithmetic.
The computer gained considerable I/O bandwidth from its
separate data channels with direct memory access, and so
it was also used to run business and general-purpose
applications. The 7094 had an operating system called
IBSYS, and FORTRAN and COBOL compilers.
A typical system cost $3,134,500. IBM stopped selling them
in 1969.
Dati tecnici
Manufacturer:
IBM
Memory technology:
magnetic core
First introduced:
1963
Memory size:
32K 36-bit words
CPU technology:
transistor
Cycle time:
2 microseconds (0.5 MHz)
Sfruttare al massimo la
potenza di calcolo
Sistemi batch
Non interattività dei programmi
Esecuzione non immediata ma rimandata nel tempo dei
programmi
Il termine batch risale all'epoca della programmazione per
schede perforate. In quel contesto, i programmatori
solitamente non avevano accesso diretto al computer, bensì
preparavano i propri programmi "off-line" e li passavano a un
amministratore di sistema, il quale aveva il compito di mandarli
in esecuzione quando possibile (accodandoli rispetto ad altri
programmi in esecuzione e spesso accorpando più programmi
in un'unica unità di esecuzione), restituendo poi in seguito i
risultati dell'elaborazione agli interessati.
Sistemi interattivi
Nei 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.
Classificazione delle
politiche di scheduling
Le politiche di scheduling della CPU si
differenziano in base a tre criteri di
classificazione:
senza prelazione/con prelazione
senza priorità/con priorità
statiche/dinamiche
Prelazione (pre-rilascio)
Politiche senza prelazione
(non pre-emptive)
una volta che la CPU è stata
assegnata ad un processo,
essa non può più essergli
tolta se non quando il
processo ha esaurito il suo
tempo di servizio o
necessita di un'operazione
di I/O.
Politiche con prelazione
(pre-emptive)
la CPU può essere
forzatamente tolta al
processo in corso di
esecuzione per essere
assegnata ad un altro
processo.
Priorità
Politiche senza priorità
pongono i processi sullo
stesso piano, dal punto
di vista dell’urgenza di
esecuzione.
Politiche con priorità
distinguono e suddividono
in classi i processi in stato di
pronto, a secondala della
loro importanza o urgenza
di esecuzione. Sono
necessarie nei sistemi realtime e interattivi.
Statiche/dinamiche
Politiche statiche
Politiche dinamiche
un processo conserva nel
tempo i suoi diritti di
accesso all’unità centrale
(priorità)
i processi modificano nel
tempo i propri diritti di
accesso all’unità centrale.
Politiche di
schedulazione
FCFS: First Come First Served
SJF: Shortest Job First -> (SRTF)
Per priorità
Round Robin
FCFS: First Come First
Served
La CPU è assegnata ai singoli processi in base al loro
ordine nella coda dei processi pronti (ready queue),
stabilito in base al tempo di arrivo oppure dal
numero identificativo (PID)
La ready queue è gestita in modalità FIFO (First In
First Out)
al processo che giunge nella ready queue viene
attribuito l’ultimo posto della coda
la CPU è assegnata al processo situato alla testa alla
ready queue
FCFS: caratteristiche
E’ senza prelazione: il processo in esecuzione trattiene la
CPU sino al termine del suo tempo di servizio o fino a
quando non necessita di un’operazione di I/O
Tende a penalizzare i processi I/O bound e quelli di breve
durata, poiché costretti a lunghe attese dietro processi
CPU bound
Tempi di attesa molto variabili e generalmente lunghi. La
gestione dei dispositivi è poco efficiente ed è adeguata
per sistemi batch (mancanza di interattività).
SJF: Shortest Job First
La CPU è assegnata al processo il cui intervallo di
tempo previsto per l’utilizzo della CPU è più breve
Nel caso in cui più processi pronti presentino gli
stessi tempi di servizio, la scelta viene fatta secondo
la politica FCFS
SJF: due casi
SJF senza prelazione
il processo in esecuzione trattiene la CPU sino al
termine del suo tempo di servizio o fino a quando non
necessita di un’operazione di I/O.
SJF con prelazione
se, ad un certo istante, nella coda dei processi pronti
giunge un processo con un tempo di servizio più breve
di quello che rimane (da completare) al processo in
esecuzione, la CPU viene rilasciata e ceduta al processo
appena arrivato (Shortest Remaining Time First - SRTF)
Scheduling per priorità
A ciascun processo, in fase di generazione, viene
attribuito un livello di priorità, espresso da un
numero intero
La CPU è assegnata al processo che presenta la
massima priorità.
A parità di priorità, si ricorre alla politica FCFS
Per priorità: due casi
Senza prelazione
il processo in esecuzione trattiene la CPU sino al
termine del suo tempo di servizio o fino a quando non
necessita di un’operazione di I/O.
Con prelazione
se nella coda dei processi pronti arriva un processo con
priorità maggiore di quella del processo in esecuzione,
questo rilascia la CPU, cedendola al processo appena
arrivato.
Determinare la priorità
Priorità definite dal S. O. (p. interna)
Priorità definite dall’utente (p. esterna)
Priorità statica
una volta stabilita, non varia nel tempo
Priorità dinamica
varia nel tempo per evitare che alcuni processi possano
essere bloccati per un tempo indefinito (starvation), a
causa della costante presenza nella ready queue di
processi a più elevata priorità
Starvation
(attesa indefinita)
Una possibile soluzione allo starvation è data dalla
procedura di aging (invecchiamento): la priorità di un
processo può
aumentare al crescere del suo tempo di attesa
diminuire al crescere del tempo di CPU già utilizzato
Round Robin
La CPU viene assegnata, a turno, ad ogni processo
per un certo periodo q di tempo massimo (time-slice
o quanto di tempo)
Se, alla fine di tale periodo, il processo in esecuzione
non è terminato, esso viene ricondotto nella coda dei
processi pronti, all’ultima posizione
Alla messa in esecuzione, il S. O. avvia un dispositivo
timer, trascorso l’intervallo q, il timer genera
un’interruzione che provoca il prerilascio della CPU
time-slice
Un time-slice troppo grande rischia di far tendere la
politica Round Robin a quella FCFS.
Un time-slice troppo piccolo consente tempi di
risposta brevi ma impegna eccessivamente la CPU
per le operazioni di context switch, con conseguente
calo della produttività e dell’efficienza del sistema.
Nei sistemi reali il valore del time-slice che garantisce
buone prestazioni è compreso tra 20 e 50
millisecondi.