Post on 13-May-2022
1
Sistemi e Tecnologie Informatiche 1
Sistema Operativo:
Gestione dei Processi
Sistemi e Tecnologie Informatiche 2
Concetto di processo
� Processo: programma in esecuzione
� Un processo include:• program counter
• stack
• data section
2
Sistemi e Tecnologie Informatiche 3
Processo in memoria
Sistemi e Tecnologie Informatiche 4
Stato di un processo
� Possibili stati di un processo
• new: creazione del processo
• running: esecuzione istruzioni
• waiting: attesa evento
• ready: attesa di essere assegnato al processore
• terminated: fine dell’esecuzione
3
Sistemi e Tecnologie Informatiche 5
Diagramma FSM di un processo
Sistemi e Tecnologie Informatiche 6
Process Control Block (PCB)
Informazioni associate ad ogni processo:
� Stato
� Program counter
� Registri CPU
� CPU scheduling information
� Memory-management information
� Accounting information
� I/O status information
4
Sistemi e Tecnologie Informatiche 7
Process Control Block (PCB)
Sistemi e Tecnologie Informatiche 8
CPU Switch From Process to
Process
5
Sistemi e Tecnologie Informatiche 9
Code di scheduling dei processi
� Coda dei processi pronti – insieme
di tutti I processi che risiedono nella
memoria principale e pronti
all’esecuzione
� Coda dei dispositivi – insieme dei
processi in attesa di un dispositivo di
I/O
Sistemi e Tecnologie Informatiche 10
Esempi di code di processi pronti e di
code dei dispositivi
6
Sistemi e Tecnologie Informatiche 11
Rappresentazione dello
scheduling dei processi
Sistemi e Tecnologie Informatiche 12
Schedulers
� scheduler a lungo termine (or job
scheduler) – seleziona quali
processi inserire nella coda dei
processi pronti
� scheduler a breve termine (or
CPU scheduler) – seleziona I
processi che saranno eseguiti dalla
CPU
7
Sistemi e Tecnologie Informatiche 13
Scheduling a lungo termine
Sistemi e Tecnologie Informatiche 14
Algoritmi di scheduling
8
Sistemi e Tecnologie Informatiche 15
First-Come, First-Served (FCFS)
Scheduling
Process Burst Time
P1 24
P2 3
P3 3
� Ordine di arrivo dei processi: P1 , P2 , P3
� Tempo di attesa P1 = 0; P2 = 24; P3 = 27
� Tempo di attesa medio: (0 + 24 + 27)/3 = 17
P1 P2 P3
24 27 300
Sistemi e Tecnologie Informatiche 16
FCFS Scheduling (Cont.)
Supponiamo che l’ordine di arrivo sia:
P2 , P3 , P1
� Il diagramma di Gantt sarà:
� Tempo di attesa P1 = 6; P2 = 0; P3 = 3
� Tempo di attesa medio: (6 + 0 + 3)/3 = 3
� Molto migliore del caso precedente
P1P3P2
63 300
9
Sistemi e Tecnologie Informatiche 17
Shortest-Job-First (SJF)
Scheduling
� Associa ad ogni processo la durata del prossimo burst di CPU
(tempo di utilizzo della CPU). Utilizza dunque queste lunghezze
per programmare l’esecuzione del processo con il tempo
inferiore
� Due schemi possibili:
• Senza prelazione – una volta che la CPU è assegnata al
processo non può essere interrotta fino a quando con
completa il burst
• Con prelazione – se viene creato un nuovo processo con
lunghezza di CPU burst inferiore a al tempo rimanente di
quello in esecuzione, il primo processo viene sostituito.
Questo schema è anche noto come Shortest-Remaining-
Time-First (SRTF)
Sistemi e Tecnologie Informatiche 18
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
� SJF (non-preemptive)
� Average waiting time = (0 + 6 + 3 + 7)/4 = 4
Esempio di Non-Preemptive SJF
P1 P3 P2
73 160
P4
8 12
10
Sistemi e Tecnologie Informatiche 19
Esempio di Preemptive SJF
Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
� SJF (preemptive)
� Average waiting time = (9 + 1 + 0 +2)/4 = 3
P1 P3P2
42 110
P4
5 7
P2 P1
16
Sistemi e Tecnologie Informatiche 20
Priority Scheduling
� Un numero di priorità è associato ad ogni processo
� La CPU è allocata al processo con la più alta priorità
• Preemptive (con prelazione)
• Nonpreemptive (senza prelazione)
� SJF è un priority scheduling dove la priorità è pari alla stima
della durata del prossimo burst di CPU
� Probelmi: attesa indefinita: processi a gbassa priorità
potrebbero non essere mai eseguiti
� Soluzione ≡ Invecchiamento – incrementare la priorità sulla
base del tempo di permanenza in coda
11
Sistemi e Tecnologie Informatiche 21
Round Robin (RR)
� Ad ogni processo è assegnato un quanto di tempo di
CPU, tipicamente 10-100 millisecondi. Scaduto questo
tempo, il processo è prelazionato ed aggiunto in fondo
alla coda dei processi pronti
� Se ci sono n processes nella coda dei processi pronti ed il
quanto è pari a q, allora ogni processo prende 1/n of the
CPU time in porzioni al massimo di q unità di tempo alla
volta. Nessun processo aspetta più di (n-1)q time units.
� Performance
• q molto grande ⇒ FIFO
• q molto piccolo ⇒ q deve essere grande rispetto al
context switch
Sistemi e Tecnologie Informatiche 22
Example of RR with Time
Quantum = 20
Process Burst Time
P1 53
P2 17
P3 68
P4 24
� Diagramma di Gantt:
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
12
Sistemi e Tecnologie Informatiche 23
Time Quantum and Context Switch
Time
Sistemi e Tecnologie Informatiche 24
Multilevel Queue Scheduling
13
Sistemi e Tecnologie Informatiche 25
Sistema Operativo:
Gestione della memoria
Sistemi e Tecnologie Informatiche 26
Registro di base e registro
limite
� Una coppia di registri base e limite definiscono lo spazio di
indirizzamento logico
14
Sistemi e Tecnologie Informatiche 27
Collegamento tra istruzioni e indirizzi
Il collegamento tra istruzioni o dati e indirizzi di memoria può
avvenire in tre diverse fasi
• compilazione: se la posizione in memoria è nota a
priori è possibile generare del codice assoluto. E’
necessario ricompilare il codice se cambia la
posizione in memoria
• Caricamento: è possibile generare del codice
rilocabile se la locazione di memoria non è nota al
momento della compilazione
• Esecuzione: il collegamento è ritardato fino al
momento dell’esecuzione. In questo caso il processo
può essere spostato da un segmento o pagina di
memoria ad un altro. E’ necessario dell’hardware di
supporto
Sistemi e Tecnologie Informatiche 28
Memory-Management Unit (MMU)
� E’ il dispositivo hardware che mappa gli indirizzi fisici e quelli
logici
� Nello schema della MMU, il volore nel registro di rilocazione
è aggiunto a ciascun indirizzo generato da un processo
utente nel momento in cui il processo è inviato in memoria
� Il programma utente vede solo gli indirizzi logici (mai quelli
fisici)
15
Sistemi e Tecnologie Informatiche 29
Rilocazione dinamica utilizzando un
registro di rilocazione
Sistemi e Tecnologie Informatiche 30
Vista schematica dello
Swapping
16
Sistemi e Tecnologie Informatiche 31
Problema dell’allocazione
dinamica della memoria
� First-fit: Alloca il primo buco abbastanza capiente
� Best-fit: Alloca il più piccolo buco abbastanza grande da contentere il processo; è necessario fare una ricerca su tutta la lista a meno che essa non sia ordinata per dimensione
� Worst-fit: Alloca il buco più grande; anche in questo caso la ricerca va fatta su tutta la lista
Come soddisfare la richiesta di dimensione n tra una lista di buchi
(hole) liberi
First-fit e best-fit forniscono prestazioni migliori di worst-
fit in termini di velocità e di utilizzo di memoria
Sistemi e Tecnologie Informatiche 32
Frammentazione
� Frammentazione Esterna– lo spazio di memoria totale per
soddisfare una richiesta esiste ma non è contiguo
� Internal Fragmentation – la memoria allocata può essere
abbastanza più grande della memoria richiesta; questa
differenza è interna ad una partizione (es. Pagina) ma non è
usata
� E’ possibile ridurre la frammentazione esterna attraverso la
compattazione
• Solo se la rilocazione è dinamica ed avviene durante
l’execution time
• Sposta I contenuti di memoria per disporre tutte le parti
libere di memoria in un unico blocco contiguo
17
Sistemi e Tecnologie Informatiche 33
Paginazione
� Divide la memoria fisica in blocchi di grandezza fissa chiamati
frame (dimensione pari a una potenza di 2, tra 512 bytes e
8,192)
� Divide la memoria logica in blocchi della stessa dimensione
chiamati pagine
� Mantiene traccia di tutti i frame liberi
� Per eseguire un programma di n pagine è necessario trovare
n frame liberi e caricare il programma
� Predispone una tabella delle pagine per tradurre gli indirizzi
logici in indirizzi fisici
� Frammentazione interna
Sistemi e Tecnologie Informatiche 34
Schema di traduzione degli
indirizzi
� L’indirizzo generato dalla CPU è diviso in:
• Numero di pagina (p) – utilizzato come un indice per
una tabella delle pagine che contiene l’indirizzo di base
per ogni pagina della memoria fisica
• Scostamento (d) – si combina con l’indirizzo di base
per definire l’indirizzo di memoria fisica che sarà inviato
all’unità di memoria
Spazio degli indirizzi logici di 2m byte e dimensione della
pagina di 2n
Numero di pagina scostamento
p d
m - n n
18
Sistemi e Tecnologie Informatiche 35
Architettura della paginazione
Sistemi e Tecnologie Informatiche 36
Modello di paginazione per la
memoria logica e fisica
19
Sistemi e Tecnologie Informatiche 37
Esempio di paginazione
32-byte di memoria e pagine di 4 byte
Sistemi e Tecnologie Informatiche 38
Lista dei frame liberi
Prima dell’allocazione Dopo l’allocazione
20
Sistemi e Tecnologie Informatiche 39
Memoria virtuale: tavola delle pagine con
alcune pagine non presenti nella memoria
centrale