Lucidi - Dipartimento di Informatica

Informatica Generale
Marzia Buscemi
[email protected]
Ricevimento: Giovedì ore 16.00-18.00,
Dipartimento di Informatica, stanza 306-PS
o per posta elettronica
Pagina web del corso:
http://www.di.unipi.it/~buscemi/IG07.htm
(sommario delle lezioni in fondo alla pagina)
1
Quali sono le parti di un SO ?
lato
utente
servizi richiesti dagli utenti
S
I
S
T
E
M
A
O
P
E
R
A
T
I
V
O
Interfaccia grafica
(desktop)
nucleo del SO (kernel)
Gestore dei
processi
Gestore dei
processori
Gestore della
memoria
HW
File system
Gestore dell’I/O
2
La scorsa volta abbiamo visto..
 Processo: parte statica (programma)
+ parte dinamica (dipende dallo stato di
esecuzione)
 Tabella dei processi: contiene
informazioni che servono per attivare,
sospendere l’esecuzione di un processo
(stato, PC, registri)
 Il gestore dei processi controlla la
sincronizzazione, interruzione e
riattivazione dei processi
3
Stati di un processo
selezione primo processo
pronto e sua esecuzione
inizio
esecuzione
processi
pronti
(coda)
processi in
esecuzione
termine
esecuzione
interruzione
completamento
operazione I/O
processi
in attesa
richiesta
operazione I/O
4
Transizioni di stato
 pronto  esecuzione:


il SO stabilisce quale dei processi pronti debba
essere mandato in esecuzione
la scelta è fatta dall’algoritmo di scheduling
(vedi dopo) che deve bilanciare efficienza e
fairness (tutti trattati allo stesso modo)
 esecuzione  attesa:


il processo chiede delle risorse di I/O o attende
un evento
il SO salva tutte le informazioni necessarie a
riprendere l’esecuzione e l’informazione relativa
all’evento atteso nella tabella del processo
5
Transizioni di stato
 attesa  pronto:
 si verifica l’evento atteso dal processo e il SO
sposta quel processo nella coda dei processi
pronti
 esecuzione  pronto:
 il processo in esecuzione viene interrotto dal SO
(es. perché termina il quanto di tempo a
disposizione) e lascia spazio a un altro processo
pronto
 il SO salva tutte le informazioni necessarie a
riprendere l’esecuzione del processo dal punto
in cui viene interrotta nella tabella del processo
 contemporaneamente un altro processo passa
da pronto a “in esecuzione”
6
Esercizio
 Consideriamo tre processi A, B e C
 Supponiamo:
il quanto di tempo t sia 0.25 msec
 Ad A servono 2 quanti per essere completato e a
metà del primo quanto A abbia bisogno di un input
(es. attesa di richiesta stampa per 0.20 msec)
 A B servono 2 quanti di CPU per essere completato e
a metà del secondo si metta in attesa di una risorsa
che non è disponibile
 A C serve un quanto
 Scrivere il diagramma temporale dell’esecuzione di A, B
eC
 Mostrare le transizioni di stato di tutto il sistema

7
Esecuzione in stato utente e in
stato supervisore
 A seguito di una system call o di un interrupt,
il SO può interrompere l’esecuzione di un
processo in stato utente (es. editor testo,
programma di email) e mandare in esecuzione
altri programmi o effettuare operazioni di
‘gestione’ della macchina
 Al termine della gestione dell’interrupt o
dell’esecuzione di processo del SO (in stato
supervisore), l’uso della CPU può passare di
nuovo all’esecuzione di un processo in stato
utente
 NB. Un processo in stato utente non può mai
passare allo stato supervisore (in stato
supervisore si ha accesso a tutte le risorse)! 8
Esercizio
 Considerando l’esercizio precedente,
spiegare quando l’esecuzione di un
programma in modalità utente viene
interrotta e il controllo della CPU passa
al SO e quando poi riprende
l’esecuzione in modalità utente.
9
Gestore dei processori
NB. A volte in letteratura non si distingue tra gestore dei
processori e gestore dei processi
10
Schedulatore (scheduler)
 Si occupa di stabilire quali processi
devono avvicendarsi nell’esecuzione
 riguarda la scelta tra i processi pronti
 cerca un “mix” ottimale di processi che
siano I/O bound (accedono soprattutto
alle periferiche) e CPU bound (usano
essenzialmente CPU).
 deve evitare che qualche processo
pronto non vada mai in esecuzione
(starvation)
11
Schedulatore 2
 Obiettivi:
 massimizzare l’uso della CPU
 massimizzare il numero di elaborazioni in un
certo intervallo di tempo
 terminare ciascuna esecuzione nel minor
tempo possibile
 garantire che il tempo di esecuzione di
ciascun processo sia “consistente”
 Tipi di schedulatori:


preemptive (un processo può essere
interrotto per prelazione)
non-preemptive (un processo non può essere
interrotto fino alla fine)
12
Schedulatore 3
 Criteri di efficienza:
 tasso di utilizzo della CPU
 throughput (numero di processi
eseguiti per unità di tempo)
 elapsed time (tempo di esecuzione per
ciascun processo)
 waiting time (tempo in coda)
 tempo di risposta (dalla richiesta
all’inizio dell’esecuzione)
13
Algoritmi di scheduling
 FIFO (first in first out): non-preemptive
 SJF (shortest job first): non-preemptive
 Round-robin (time slices + FIFO):
preemptive
 EDF (earliest deadline first): per
applicazioni real-time
 SRT (shortest remaining time):
versione preemptive di SJF
14
Algoritmi di scheduling: esercizi


1.
2.
3.
4.

Assumiamo 4 processi P1, P2, P3, P4

che arrivano nella coda di processi pronti in
quest’ordine: P1, P2, P3, P4

che hanno tempo di esecuzione: P1 30, P2 10,
P3 2, P4 8
Scrivere i diagrammi temporali seguendo gli
algoritmi
FIFO
SJF
Round-robin (con quanto t=5)
EDF (assumere deadline: P1 60, P2 10, P3 35, P4
20)
Confrontare l’efficienza degli algoritmi sopra
usando come parametro la somma dei tempi di di15
attesa in coda (waiting time)