Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
Struttura di un SO
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
Dal problema all’algoritmo
Chiamiamo problema una qualsiasi
situazione per cui è necessario elaborare
una strategia per identificare una sua
soluzione, ovvero una serie azioni da
compiere per raggiungere il risultato.
Algoritmo
Un algoritmo è un insieme di istruzioni chiare
e non ambigue, effettivamente calcolabili,
che eseguito fornisce un risultato in una
quantità di tempo finita.
L’algoritmo descrive le istruzioni da eseguire
per giungere alla soluzione di un problema.
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
Proprietà principali di un algoritmo
La sequenza di istruzioni che compone un algoritmo deve
essere:
• finita : l’esecutore deve arrivare prima o poi al risultato
richiesto, quindi le azioni descritte sono un numero
finito e ciascuna azione deve essere eseguita un
numero finito di volte.
• non ambigua : ciascuna istruzione deve essere
descritta chiaramente ed interpretata univocamente,
di modo che l’azione descritta sia effettuata allo stesso
modo da qualsiasi esecutore.
• eseguibile - effettivamente calcolabili ciascuna azione
deve rientrare nelle effettive capacità dell’esecutore.
L’esecutore di un algoritmo non dev’essere
necessariamente un automa ma può essere anche un
sistema biologico.
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
Dall’algoritmo al programma
Il Blocco di Input
Leggi A
Può essere tradotto in un linguaggio con l’istruzione
Read A;
ISTRUZIONE
La struttura condizionale
F
A>10
A=A+1
può essere tradotta nelle seguenti istruzioni:
if (A>10) THEN A=A-1
ELSE A=A+1
V
A=A-1
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
Per tradurre un programma scritto in un linguaggio di
programmazione (programma sorgente) nel linguaggio macchina
comprensibile all’esecutore è necessaria la compilazione.
La compilazione consiste nel tradurre l’intero programma sorgente
prima di eseguirlo.
La compilazione traduce ogni singola istruzione del programma
sorgente in istruzioni nel linguaggio macchina equivalenti.
Il risultato della compilazione crea un codice in linguaggio macchina
detto codice oggetto.
CODICE SORGENTE
COMPILATORE
CODICE OGGETTO
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
Dal linguaggio di programmazione al
linguaggio macchina
Traduciamo un semplice programma, che effettua la somma di
due numeri
A=5;
// alla variabile A è assegnato il valore 5
READ(B); // la variabile B è assegnato un valore in INPUT
C=A+B; // la variabile C contiene la somma A + B
COMPILAZIONE
Mostriamo una traduzione possibile nel linguaggio macchina (in realtà è un
linguaggio detto assembly) del programma
MOV R0, #5
MOV Rn, 5
ADD R0,Rn
STA 7
Non preoccupatevi se risulta incomprensibile al momento , lo
dettaglieremo di seguito
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
ISTRUZIONI MACCHINA
MOV R0, #5
MOV Rn, 5
ADD R0,Rn
STA 7
Le istruzioni del programma, cosi come le variabili usate dal
programma sono memorizzate in memoria.
1
2
3
4
5
6
7
MOV R0,#5
MOV Rn.5
ADD R0,Rn
STA 7
VALORE DI B
VALORE DI C
Rappresentazione della
memoria che contiene
istruzioni e dati del
programma
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
1
2
3
4
5
6
7
MOV R0,#5
MOV Rn,5
ADD R0,Rn
STA 7
Le istruzioni del
programma sono
memorizzate dalla
locazione 1 alla
locazione 4
VALORE DI B
VALORE DI C
BUS
I dati su cui operano le
istruzioni sono
contenute nella
locazione di indirizzo 5
e nella locazione di
indirizzo 7
CPU
E’ la CPU l’esecutore delle istruzioni, quindi sono previsti meccanismi
per cui le istruzioni da eseguire sono trasferite dalla memoria
all’UNITA’ CENTRALE DI ELABORAZIONE
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
1
2
3
4
5
6
7
MOV R0,#5
MOV Rn,5
Il programma caricato
in memoria prende il
nome di Processo.
ADD R0,Rn
STA 7
VALORE DI B
VALORE DI C
Un processo pronto
per l’esecuzione ,
attende che la risorsa
CPU sia disponibile per
poter eseguire le
proprie istruzioni.
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
Nei sistemi operativi MULTITASKING sono presenti più processi in
esecuzione che competono per l’uso delle risorse.
E’ indispensabile che ci sia una politica di assegnazione delle risorse
necessarie, tale politica va sotto il nome di SCHEDULING.
La risorsa principale è la CPU che deve essere assegnata in modo che
tutti i processi siano eseguiti senza che nessuno venga penalizzato .
Il modulo del SO che si occupa della esecuzione, della terminazione,
della attivazione e della sincronizzazione dei processi prende il
nome di GESTORE DEI PROCESSI.
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
Il SO tiene traccia dei processi presenti attraverso il PCB
(Process Control Block)
Il PCB è una struttura dati che memorizza lo stato dei processi.
Tra le informazioni principali esso conserva:
• Program Counter (l’indirizzo della prossima istruzione da
eseguire)
• Area salvataggio registro di stato
• Stato corrente di avanzamento del processo (Pronto, In
Esecuzione, Bloccato)
• Identificatore unico del processo
• Livello di priorità
• Informazioni per il memory management(Gestione della
memoria in particolare per la memoria virtuale)
• Informazioni per lo scheduling (gestione) del processo, come il
tempo di run (esecuzione) o wait (attesa) accumulato
• Informazioni sullo stato di I/O del processo
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
Come descritto nelle informazioni conservate dal PCB, un processo
può trovarsi in 3 stati possibili
RUN(esecuzione)
Un processo si trova nello stato RUN quando ha tutte le risorse
necessarie per poter svolgere il proprio compito ed è in quel
momento in esecuzione avendo la CPU a disposizione per potere
eseguire le proprie istruzioni
WAIT(Sospeso)
Un processo si trova nello stato WAIT quando non ha tutte le
risorse di cui necessita per avanzare , oppure , è in attesa di un
completamento di un’istruzione di I/O.
Ready(Pronto per l’esecuzione)
Un processo si trova nello stato READY quando dispone di tutte le
risorse necessarie al suo avanzamento ed è in attesa
dell’assegnazione della CPU
Nella slide successiva vedremo il diagramma di transizioni degli
stati di un processo
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
DIAGRAMMA DI TRANSIZIONE DEGLI STATI
RUN
READY
WAIT
Un processo passa dallo stato RUN allo stato WAIT quando
Un
processo
transitaildallo
stato READYdiallo
stato RUN , quando
richiede
e attende
completamento
un’operazione
di I/O. gli
viene assegnata la risorsa CPU è può eseguire le proprie istruzioni.
Unprocesso
processotorna
transita
stato
RUNquando
allo stato
READY, quando
o di
Un
nellodallo
stato
READY
l’operazione
richiesta
è scaduto
il time-slice,
sistemaaha
richiesto per competere
I/O
stata completata
e haoppure
tutte leil risorse
disposizione
l’esecuzione
di un
INTERRUPT
per cui necessità della CPU per
all’
assegnazione
della
CPU.
«servire» la gestione dell’interrupt.
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
DIAGRAMMA DI TRANSIZIONE DEGLI STATI
RUN
Richiesta I/O
READY
Completamento
I/O
WAIT
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
La lista dei processi PRONTI la Ready List
Tra tutti i processi che si trovano nello stato READY (PRONTO) lo
scheduler deve scegliere attraverso opportune politiche di
scheduling il processo a cui sarà assegnata la CPU.
I processi in questo stato sono inseriti in una ready list (lista dei
processi pronti).
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
L’algoritmo di scheduling Round-Robin
L’algoritmo che già conosciamo va sotto il nome di Round-Robin
Tale algoritmo assegna una stessa quantità di tempo ad ogni processo
nell’utilizzo della CPU, allo scadere di questo tempo (quanto o timeslice) la CPU viene associata a un altro processo e il processo fino a
quel momento in esecuzione viene riaccodato nella lista dei processi
pronti (READY-LIST).
L’algoritmo di Round-Robin non fa differenza tra processi Utente e
processi di S.O. e questo tipo di scheduling potrebbe compromettere
le prestazioni del sistema.
Nella realtà si utilizzano più LISTE dei processi pronti considerando
anche il concetto di priorità di un processo per l’utilizzo della CPU.
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
La lista dei processi PRONTI la Ready List
Ad ogni processo è assegnata una priorità di utilizzo della CPU.
Esistono tantissimi parametri nell’assegnazione del valore di
priorità a un processo, qui illustriamo quelli più significativi.
Una prima considerazione è quella di classificare i processi rispetto
al numero di operazioni di I/O e all’utilizzo della CPU.
Si parla di processi CPU BOUND se essi prevedono un elevato uso
della CPU (elevata quantità di computazioni)
Si parla di processi I/O BOUND se essi prevedono prevalentemente
operazioni di I/O.
Contrariamente a quanto uno potrebbe essere portato a pensare ,
conviene assegnare priorità più alta ai processi I/O BOUND. Infatti
una volta assegnati al processore (Schedulati) essi lascerebbero al
risorsa processore libera per eseguire altri processi.
Se invece assegnassimo una priorità alta a un processo
CPU/BOUND questo userà molto probabilmente la CPU per tutta la
durata del time-slice.
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
La lista dei processi PRONTI la Ready List
Nei sistemi operativi reali, spesso si combinano
diversi algoritmi di scheduling.
Esempio: Multiple Level Feedback Queues
più code, ognuna associata a un tipo di job diverso (batch,
interattivi (I/O-BOUND), CPU-bound, etc.)
ogni coda ha una diversa priorità: scheduling delle code con
priorità
ogni coda viene gestita con scheduling FCFS o Round Robin
i processi possono muoversi da una coda all’altra, in base alla loro
storia:
• passaggio da priorità bassa ad alta: processi in attesa da molto
tempo (feedback positivo)
• passaggio da priorità alta a bassa: processi che hanno già
utilizzato molto tempo di CPU (feedback negativo)
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
Come funzionano gli INTERRUPT
Un’interruzione è un evento di natura asincrona, cioè può verificarsi
in qualsiasi istante indipendentemente dalle azioni che sta svolgendo
il processore.
Esempi di eventi asincroni sono : la fine di un processo di stampa, la
pressione di un tasto della tastiera o del mouse, etc…
Un’interruzione sincrona invece è in corrispondenza di un evento di
clock, ad esempio lo scadere del time-slice assegnato a un processo.
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
Come funzionano gli INTERRUPT
Quando la CPU rileva la presenza di una richiesta di INTERRUPT deve
necessariamente eseguire le seguenti azioni:
1. Completare l’esecuzione dell’istruzione che sta eseguendo
2. Salvare le informazioni relative al processo in quel momento in
esecuzione
3. Eseguire la particolare procedura(ROUTINE) di gestione relativa al
segnale di INTERRUPT
4. Terminata la ROUTINE di gestione dell’interruzione, recuperare le
informazioni relative al processo interrotto e riprendere
l’esecuzione del processo interrotto dall’istruzione successiva
all’ultima eseguita prima di gestire l’interruzione.
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
Schema di funzionamento degli INTERRUPT
MEMORIA
Istruzione 1
INTERRUZIONE
Istruzione 2
IR
Istruzione 3
PC
CPU
STATO
PROCESSO
REGISTRI
STATUS
Il processore sta eseguendo l’istruzione 2
quando arriva un segnale di INTERRUPT
Il processore termina l’esecuzione
dell’istruzione 2 e salva le informazioni
sullo stato del processo in memoria.
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
Schema di funzionamento degli INTERRUPT
MEMORIA
Istruzione 1
Istruzione 2
IR
Istruzione 3
PC
CPU
STATO
PROCESSO
Istruzione 1
Istruzione 2
Istruzione 3
REGISTRI
STATUS
Al termine della routine
di gestione dell’interrupt
Vengono ricaricate le
Routine di interrupt informazioni sul
processo interrotto e
l’esecuzione riprende
Il processore esegue
la routine successiva
dall’istruzione
dell’interrupt
a quella
precedentemente
interrotta.
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
TECNICHE DI RICONOSCIMENTO DEGLI INTERRUPT
La CPU ha un piedino INT dove riceve i segnali per la richiesta degli
interrupt (INTERRUPT REQUEST).
Essendo l’unica linea sorge il problema di identificare il
dispositivo che ha sollevato l’interruzione.
Esistono 2 tecniche :
1. POLLING
2. INTERRUZIONI VETTORIZZATE
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
GESTORE DEI PROCESSI
TECNICHE DI RICONOSCIMENTO DEGLI INTERRUPT
POLLING
La tecnica del POLLING richiede che la CPU interroghi tutti i
dispositivi finché non trova quello che ha generato l’interruzione.
Siccome tale tecnica potrebbe impegnare la CPU in modo
considerevole, si preferisce la tecnica dell’interrupt vettorizzato.
INTERRUPT VETTORIZZATO
Il dispositivo che ha generato l’interrupt invia sul BUS un codice di
riconoscimento che contiene l’indirizzo di un vettore (VETTORE
DEGLI INTERRUPT) che contiene l’indirizzo di memoria iniziale della
routine di gestione dell’interrupt.
MEMORIA
D
VETTORE
I
DEGLI
S
INTERRUPT
P
300
0
O
1
50
100
S
2
100
2
I
3
ROUTINE
T
4
I
5
V
6
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
… e il nostro programmino???
1
2
3
4
5
6
7
MOV R0,#5
MOV Rn,5
ADD R0,Rn
STA 7
VALORE DI B
A=5;
// alla variabile A è assegnato il
valore 5
READ(B); // la variabile B è assegnato un
valore in INPUT
C=A+B; // la variabile C contiene la
somma A + B
VALORE DI C
MOV R0,#5 carica il valore 5 nel registro R0
Rn,5due
carica
il contenuto
della
locazione
memoria
R0 EMOV
Rn sono
registri
della CPU,
i registri
sonodidelle
di indirizzo
5 nel registro
Rn
(VALORE
DI B)
memorie
ad accesso
veloce
(nella
gerarchie
ADD R0,Rn
somma
i contenuti
dei
registridelle
R0 e memorie
Rn e salva
sono
al
primo
livello)
che
possono
contenere
o
dati
o un
il risultato in un altro registro detto ACCUMULATORE
istruzione
contenuti
in unanella
locazione
di memoria.
STA 7 Salva
il risultato
locazione
di memoria di
Prima
di effettuare
operazioni
aritmetiche
la CPU carica i
indirizzo
7 ( VALORE
DELLA logico
VARIABILE
C)
dati su cui operare all’interno dei registri.
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
… e il nostro programmino???
1
2
3
4
5
6
7
MOV R0,#5
In nero l’istruzione da eseguire
MOV Rn,5
ADD R0,Rn
Carica 5 nel registro R0
STA 7
VALORE DI B
VALORE DI C
R0
5
Rn
PC
2
IR
MOV R0,#5
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
… e il nostro programmino???
1
2
3
4
5
6
7
MOV R0,#5
In nero l’istruzione da eseguire
MOV Rn,5
ADD R0,Rn
Carica il valore della locazione
di indirizzo 5 nel registro Rn
STA 7
VALORE DI B
Carica il valore dalla locazione
5 in Rn
VALORE DI C
R0
5
B
Rn
PC
3
IR
MOV Rn, 5
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
… e il nostro programmino???
1
2
3
4
5
6
7
MOV R0,#5
In nero l’istruzione da eseguire
MOV Rn,5
ADD R0,Rn
STA 7
SOMMA IL CONTENUTO DI R0 E Rn
e il risultato è memorizzato nel
registro accumulatore.
VALORE DI B
VALORE DI C
ACC
B+5
R0
5
B
Rn
PC
4
IR
ADD R0,Rn
Menu
•
•
•
•
•
Struttura SO
Algoritmo
Programma
Processo
Gestione dei
Processi
… e il nostro programmino???
1
2
3
4
5
6
7
MOV R0,#5
In nero l’istruzione da eseguire
MOV Rn,5
Memorizza il contenuto del registro
accumulatore nella locazione di
memoria di indirizzo 7
ADD R0,Rn
STA 7
VALORE DI B
Abbiamo eseguito C=5+B
4 istruzioni macchina
VALORE DI C
ACC
B+5
R0
5
B
Rn
IR
STA 7
Sistemi Operativi : Gestore dei processi
FINE PRESENTAZIONE
A cura di Alberto Landi