Concetto di processo - didattica-2000.archived.uniroma2.it

1

Sistemi e Tecnologie Informatiche 1

Sistema Operativo:

Gestione dei Processi


Concetto di processo

� Processo: programma in esecuzione

� Un processo include:• program counter

• stack

• data section

2


Processo in memoria


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


Diagramma FSM di un processo


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


Process Control Block (PCB)


CPU Switch From Process to

Process

5


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


Esempi di code di processi pronti e di

code dei dispositivi

6


Rappresentazione dello

scheduling dei processi


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


Scheduling a lungo termine


Algoritmi di scheduling

8


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


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


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)


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


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


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


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


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


Time Quantum and Context Switch

Time


Multilevel Queue Scheduling

13


Sistema Operativo:

Gestione della memoria


Registro di base e registro

limite

� Una coppia di registri base e limite definiscono lo spazio di

indirizzamento logico

14


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


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


Rilocazione dinamica utilizzando un

registro di rilocazione


Vista schematica dello

Swapping

16


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


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


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


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


Architettura della paginazione


Modello di paginazione per la

memoria logica e fisica

19


Esempio di paginazione

32-byte di memoria e pagine di 4 byte


Lista dei frame liberi

Prima dell’allocazione Dopo l’allocazione

20


Memoria virtuale: tavola delle pagine con

alcune pagine non presenti nella memoria

centrale

Concetto di processo - didattica-2000.archived.uniroma2.it

Documents

Transcript of Concetto di processo - didattica-2000.archived.uniroma2.it