6 Sistema Operativo
6
6.1
6.2
6.3
6.4
6.5
6.6
6.7
Sistema Operativo
Generalità
Classificazioni e definizioni
Struttura generale
La gestione dei processi
La gestione della memoria
La gestione dell’I/O
File system e protezione
Unix - Windows
Architettura degli elaboratori 1 - A. Memo
283
6. Generalità
le macchine astratte 1
Offre un insieme di
istruzioni più strutlivello 5 : Macchina utente
turate che agevolano
livello 4 : Macchina programmatore
l’accesso e l’uso delle
risorse dei livelli 0 e 1.
livello 3 : Macchina Sistema Operativo Spesso nasconde cosa
c’è sotto o come funlivello 2 : Macchina hardware
ziona. Il linguaggio
utilizzato è quello dellivello 1 : Macchina microprogramma
le chiamate di sistema.
livello 0 : Macchina digitale
E’ prettamente software e indispensabile.
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
284
6. Generalità
le macchine astratte 2
Obiettivi del Sistema Operativo (OS):
 rendere il calcolatore più semplice da utilizzare
 ottimizzare l’utilizzo delle risorse
– il SO deve gestire la CPU, la memoria principale e
quella secondaria, le periferiche di I/O in maniera
efficiente, assicurandone l’accesso ai richiedenti e
regolandone la condivisione

gestire l’esecuzione dei programmi utente
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
285
6.1 Classificazioni e definizioni
storia 1
I SO nascono negli anni ‘50, con i primi
calcolatori elettronici a programma memorizzato
 i
programmi venivano inseriti tramite
interruttori binari frontali, o lettori di
schede perforate
 i dati venivano letti tramite led binari, testo
stampato o schede perforate
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
286
6.1 Classificazioni e definizioni
storia 2


negli anni ‘60 si sviluppa il software,
nascono compilatori per nuovi linguaggi e
tool di sviluppo
il costo elevato e la lentezza delle
periferiche (es. caricare un nuovo
compilatore) inducono il lavoro a lotti
(batch) gestito dall’operatore: un solo
programma alla volta, dati compresi
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
287
6.1 Classificazioni e definizioni
storia 3 (batch)

dai batch gestiti dall’operatore si passa al
monitor residente (RM) [S.O.batch]
– schedulatore sequenziale dei vari job controllato da schede perforate

le operazioni di I/O sono troppo lente (1001000 volte) [S.O. I/O off-line]
– direzionare l’I/O verso memorie a nastro
mediante sistemi intelligenti dedicati , e sovrapposizione tra esecuzione e gestione I/O
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
288
6.1 Classificazioni e definizioni
storia 4 (multiprogramming)

utilizzo del disco rigido come buffer di I/O
molto capiente [S.O. spooling]
– Simultaneus Peripheral Operation On-Line, è
più veloce e ad accesso diretto rispetto al nastro

utilizzo del disco anche per i programmi
[S.O. multi-programming]
– precarico nel disco un insieme di programmi,
appena il primo termina mando in esecuzione il
secondo, e così via.
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
289
6.1 Classificazioni e definizioni
storia 5 (time sharing)

multi-programming (segue)
– se un programma richiede I/O, posso assegnarlo
ad un esecutore meno importante, e continuare
con un altro programma

inizialmente c’era grande interattività e
poca efficienza, ora alta efficienza ma
scarsa interattività: [SO time-sharing]
– un quanto di tempo per utente, se lo scambio è
frequente, l’utente potrebbe non accorgersene
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
290
6.1 Classificazioni e definizioni
storia 6 (paralleli)

time-sharing (segue)
– esecuzione concorrente di più programmi
– condivisione della memoria
– schemi di protezione e controllo delle risorse

più CPU nello stesso sistema [SO paralleli]
– generalmente condividono memoria e I/O
– simmetrici, tutte le CPU hanno il medesimo SO
– asimmetrici, solo una CPU ha il SO
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
291
6.1 Classificazioni e definizioni
storia 7 (distribuiti e di rete)

più sistemi utilizzano il medesimo SO [SO
distribuiti]
– di solito operano su memorie ed I/O distinti
– ciascuno ha un’immagine coincidente del SO

più sistemi interconnessi [SO di rete]
– finalizzati alla condivisione delle risorse ed alla
comunicazione
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
292
6.1 Classificazioni e definizioni
storia 8 (real time e PC)

gestione prioritaria degli eventi esterni
rispetto alla loro elaborazione [SO real-time]
– impiegati nei controlli di processo e nei
calcolatori dedicati
– nuclei spesso ridotti

SO per personal computer
– in corrispondenza alla diminuzione dei costi
– via via inglobano le prestazioni degli altri SO
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
293
6.1 Classificazioni e definizioni
definizione di SO
Definizione di SO:
un Sistema Operativo è un insieme di
programmi che assolvono al duplice
compito di far vedere all’utente una
macchina virtuale semplificata e di gestire
in maniera ottimiz-zata le risorse del
calcolatore
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
294
6.1 Classificazioni e definizioni
componenti di un SO

gestore processi

gestore risorse
–
–
–
–
processore/i
memoria principale
memoria secondaria
dispositivi di I/O
Sistema Operativo

file system

interfaccia utente

sicurezza e protezione
Architettura degli elaboratori 1 - A. Memo
295
6.1 Classificazioni e definizioni
definizioni di processo

un processo è l’insieme ordinato degli stati
che il sistema assume durante l’esecuzione
di un particolare programma o parte di esso,
a partire da uno specifico stato iniziale
oppure

un processo è l’insieme ordinato delle
azioni (operazioni) che il sistema esegue
durante lo svolgimento di un particolare
programma o insieme di istruzioni
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
296
6.1 Classificazioni e definizioni
caratteristiche dei processi





un programma può determinare più processi
in un sistema coesistono processi utente e
processi di sistema
i processi vengono creati, sospesi o terminati
i processi devono poter comunicare tra loro e
sincronizzarsi
i processi avanzano concorrentemente
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
297
6.1 Classificazioni e definizioni
gestore dei processi

è il cuore del SO, viene detto anche kernel
– deve cambiare di stato i processi, scegliendo
quello o quelli da mandare in esecuzione
(scheduling) e ponendo in attesa quelli che
richiedono una risorsa occupata
– deve assicurare a tutti i processi la possibilità di
avanzare, senza privilegiarne o penalizzarne
alcuno
– assicurare un meccanismo di sincronizzazione
tra i vari processi
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
298
6.1 Classificazioni e definizioni
definizioni di risorsa


una risorsa è qualsiasi elemento di natura
hardware o software condiviso dai processi,
necessario alla loro creazione o al loro
avanzamento
le risorse possono essere:
– riutilizzabili o consumabili
– pre-rilasciabili e non
– a molteplicità unaria o multipla
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
299
6.1 Classificazioni e definizioni
la risorsa processore



è l’unica risorsa (hardware o software)
indispensabile per l’avanzamento di tutti i
processi
a livello hardware può essere associato alla
CPU
a livello software in un sistema monoprocessore il SO può virtualizzarne molti
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
300
6.1 Classificazioni e definizioni
la risorsa memoria principale



è una risorsa riutilizzabile, pre-rilasciabile a
molteplicità unitaria se in scrittura, multipla
se in lettura
il SO la condivide tra i vari processi, di
volta in volta attribuendola e liberandola
la gestione della memoria principale risulta
più veloce se viene effettuata a livello
hardware
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
301
6.1 Classificazioni e definizioni
la risorsa memoria secondaria


è una risorsa riutilizzabile, pre-rilasciabile a
molteplicità unitaria se in scrittura, multipla
se in lettura
il SO ne regola le richieste di accesso, e la
può attribuire o recuperare parzialmente ai
vari processi
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
302
6.1 Classificazioni e definizioni
le risorse gestione dell’I/O



sono generalmente risorse riutilizzabili, a
molteplicità unaria e non pre-rilasciabili
il SO ne virtualizza l’impiego nascondenone le caratteristiche hardware e omogeneizzandone il trattamento
il SO ne regola e condivide l’accesso,
richiamando le relative routine proprietarie
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
303
6.1 Classificazioni e definizioni
file system



il file system è la componente del SO che
gestisce i file e le directory
il SO garantisce una visione logica della
struttura fisica della memoria secondaria
il SO gestisce la creazione, la cancellazione
e la modifica delle proprietà dei file
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
304
6.1 Classificazioni e definizioni
l’interfaccia utente



è l’insieme delle modalità con cui l’utente
può accedere ai servizi offerti dal SO
l’accesso per l’operatore è basato su un
interprete dei comandi, che li acquisisce, li
decodifica e li esegue
l’accesso per i programmi utente avviene
tramite chiamate standard (system call e/o
API)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
305
6.1 Classificazioni e definizioni
sicurezza e protezione

la sicurezza di un SO è la capacità di
svolgere correttamente le sue funzioni
anche in presenza di guasti (tolleranza ai
guasti) o tentativi di effrazione (protezione
e controllo degli accessi)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
306
6.2 Struttura generale
possibili architetture




Sistema Operativo
S.O. monolitici
S.O. a livelli
S.O. a macchine virtuali
S.O. client server
Architettura degli elaboratori 1 - A. Memo
307
6.2 Struttura generale
sistemi operativi monolitici



insieme paritetico di
tutte le componenti che
possono richiamarsi liberamente
paragonabile alla programmazione spaghetti
esempi: MS-DOS ed il
primo UNIX
Sistema Operativo
prog. 1
prog. 2
MS DOS
BIOS
Periferica 1
Architettura degli elaboratori 1 - A. Memo
Periferica 1
308
6.2 Struttura generale
sistemi operativi a livelli 1



suddivisione delle funzionalità del SO in
livelli, in modo che ogni componente di un
livello possa utilizzare solo le funzioni
offerte dal livello sottostante
assicurano modularità e facilità di controllo
non sempre la suddivisione a livelli è facile
o definibile
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
309
6.2 Struttura generale
sistemi operativi a livelli 2
superisore
applications
risorse
API
nucleo
kernel
device drivers
generale
OS/2
La tendenza attuale è di avere un numero contenuto di
livelli e spostare più funzioni possibile verso l’alto.
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
310
6.2 Struttura generale
sistemi operativi a macchine virtuali 1


sviluppato in IBM nel ‘79, distingue tra
multi-programmazione e interfacciamento
alle risorse
sopra al livello hardware opera il Virtual
Machine Monitor, che offre al livello
superiore più macchine virtuali complete,
ciascuna dotata del proprio livello hardware
(virtuale) indipendente
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
311
6.2 Struttura generale
sistemi operativi a macchine virtuali 2
IBM/370
virtuale
IBM/370
virtuale
IBM/370
virtuale
Conversational Conversational Conversational
Monitor
Monitor
Monitor
System
System
System
VM/370 Virtual Machine Monitor
system
call
I/O
instr.
livello hardware reale
VM/370 IBM
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
312
6.2 Struttura generale
sistemi operativi client-server


la tendenza odierna è di avere un kernel minimo e
di implementare tutte le altre funzioni nei processi
utente
nel client-server il kernel trasferisce solo i
messaggi tra i vari processi
processo processo
client
server
file
server
processo
client
kernel
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
313
6.2 Struttura generale
caricamento del SO 1
Il SO può risiedere
 permanentemente su ROM
– controllori industriali e sistemi dedicati

su disco ed essere caricato all’accensione
(bootstrap)
– adatto a sistemi complessi o gestiti da più
sistemi operativi
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
314
6.2 Struttura generale
caricamento del SO 2


all’accensione viene eseguito un piccolo
programma presente in ROM (Initial
Program Loader) che legge la routine di
caricamento (OS Loader) presente in una
zona predefinita del disco.
questa routine carica il modulo Real Time
Executive del SO, che fornisce i principali
servizi offerti dal SO
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
315
6.2 Struttura generale
sistema operativo elementare 1

analizziamo brevemente il nucleo di un SO
uniprocessor multiprogramming con time
sharing, organizzato a livelli:
– supervisor, con funzione di verifica dei diritti e
attribuzione delle risorse
– gestione delle risorse, escluso il processore
– nucleo o kernel, per la gestione dei processi
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
316
TERMINATO
ATTIVATO
crea()
termina()
livello
supervisor
dispatcher()
ESECUZIONE
PRONTO
livello
kernel
time_out()
wait()
signal()
BLOCCATO
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
317
6.2 Struttura generale
sistema operativo elementare 3
ATTIVATO
il supervisore lo attiva, e richiama la system call
(sc) per creare il nuovo PCB
PRONTO
il processo è pronto ad andare in esecuzione e
rimane in attesa del suo turno
ESECUZIONE
al processo selezionato è stato attribuito il
processore, e sta avanzando
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
318
6.2 Struttura generale
sistema operativo elementare 4
BLOCCATO
il processo è sospeso in attesa di una risorsa
attualmente non disponibile
TERMINATO
il processo ha concluso regolarmente le sue
operazioni e si predispone ad “uscire” dal SO
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
319
6.2 Struttura generale
sistema operativo elementare 5
crea()
immette un nuovo processo nel kernel, aggiornando la ready-list, o lista dei processi pronti
dispatcher()
manda in esecuzione il primo processo della
ready-list
time_out()
il processo in esecuzione esaurisce il quanto di
tempo a sua disposizione e ritorna nella ready-list
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
320
6.2 Struttura generale
sistema operativo elementare 6
wait()
il processo richiede l’uso di una risorsa, e se
questa è occupata il processo viene sospeso
signal()
il processo corrente ha liberato la risorsa attesa dal
processo bloccato, che passa nella ready-list
termina()
il processo in esecuzione termina regolarmente il
suo lavoro e rilascia il PCB
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
321
6.2 Struttura generale
sistema operativo elementare 7
I compiti del livello kernel sono quindi:
– gestire la transizione da PRONTO ad
ESECUZIONE
– gestire le interruzioni esterne causate da eventi
di I/O o da situazioni critiche rilevate da altri
processi o componenti del SO
– fornire ai livelli superiori le primitive per la
gestione dei processi (creazione, terminazione
e sincronizzazione)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
322
6.3 La gestione dei processi








definizione (vista in precedenza)
stati di un processo (visti in precedenza)
descrittore dei processi
schedulazione dei processi
operazioni sui processi
i thread (LWP)
Inter Process Comunications
deadlock
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
323
6.3 La gestione dei processi
PCB

ogni processo è caratterizzato da un descrittore di
processo (Process Control Block) composto da:
–
–
–
–
–
–
–
–
identificatore del processo
contesto interno della CPU (registri)
stato di avanzamento
priorità iniziale ed attuale
diritti di accesso alle risorse
processo padre ed eventali processi figli
puntatore alla lista delle risorse assegnate
puntatore alla coda messaggi in arrivo
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
324
6.3 La gestione dei processi
passaggio tra processi

se in un sistema possono avanzare concorrentemente
più processi, occorre un metodo per decidere quando
passare da uno all’altro
– scambio cooperativo (co-operative o non pre-emptive
switching), in cui è il processo in esecuzione che decide
quando passare il controllo al processo successivo [Win 3.1]
– scambio a pre-rilascio in cui il processo in esecuzione
viene scalzato o da un processo in attesa a priorità maggiore
(priority pre-emptive switching) o quando ha esaurito il
tempo a sua disposizione (time-sharing pre-emptive
switching) [UNIX e Win NT]
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
325
6.3 La gestione dei processi
schedulazione dei processi
I processi possono essere schedulati
 dalla ready list per mandarli in esecuzione ,
dispatcher, (short-term scheduler)
 dalla job list, lista dei processi in attesa di
attivazione (long-term scheduler)
 dalle liste in coda alle risorse di I/O (gestore
delle risorse)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
326
6.3 La gestione dei processi
dispatcher 1



il dispatcher è lo schedulatore più critico in
quanto viene richiamato ad ogni scambio
il dispatcher deve cambiare il contesto e
ritornare il controllo all’utente
i criteri di valutazione di un dispatcher sono
– percentuale di utilizzazione della CPU
– numero di processi completati nell’unità di tempo
– durata dell’attesa nella ready list
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
327
6.3 La gestione dei processi
dispatcher 2

la tecnica più semplice di gestione della
ready list è la FCFS
– il primo processo ad arrivare nella coda sarà il
primo ad essere estratto per mandarlo in
esecuzione, e vi rimarrà fino a che non chiede
una risorsa o termina
– ottimizza i tempi di scelta ed è facilmente
implementabile, ma si blocca se un processo si
blocca, non minimizza i tempi di attesa e
attribuisce implicitamente priorità maggiore ad
un tipo di processi
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
328
6.3 La gestione dei processi
dispatcher 3

Dati tre processi A, B e C con tempi di esecuzione
rispettivamente 2, 5 e 10 mS, i tempi di attesa
medi dipendono dall’ordine di esecuzione:
ABC
BAC
ACB

t = 9/3 = 3 mS
t = 12/3  4 mS
t = 14/3  4,6 mS
B C A t = 20/3  6,6 mS
C A B t = 22/3  7,3 mS
C B A t = 25/3  8,3 mS
l’attesa media minore si ha eseguendo prima quelli
con tempi di esecuzione minori (SJF, short job
first), o in pre-emption SRTF, shortest remainingtime first
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
329
6.3 La gestione dei processi
dispatcher 4


un processo è generalmente costituito da una
sequenza di attività_CPU intervallate da
attività_I/O
i processi si possono classificare in
– CPU_bound se richiedono poche attività_CPU di
durata molto lunga
– I/O_bound se richiedono molte attività_CPU di
breve durata intervallate da attività_I/O molto
lunghe

la tecnica
I/O_bound
Sistema Operativo
FCFS
penalizza
Architettura degli elaboratori 1 - A. Memo
i
processi
330
6.3 La gestione dei processi
dispatcher 5


le politiche SJF ed SRTF sono complesse ed
onerose da implementare
si possono attribuire priorità diverse ai vari
processi (SJF si può considerare a priorità in
base al tempo di esecuzione)
– i criteri di priorità influiscono le prestazioni
– si possono minimizzare i tempi di attesa medi, ma
penalizzare fortemente qualche processo (con il preemption si può arrivare anche al blocco)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
331
6.3 La gestione dei processi
dispatcher 6
introducendo il concetto di time-sharing, dalla
politica FCFS si deriva la tecnica round-robin
Dati tre processi A, B e C con tempi di esecuzione
di 2, 5 e 10 mS ed un quanto di tempo di 2 mS:


A
C1

B3
B2
B1
C2
C3
C4
C5
il tempo medio di attesa vale (0+6+7)/3  4,3 mS +
(9/3 =) 3 cambi di contesto (che devono essere rapidi)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
332
6.3 La gestione dei processi
dispatcher 7

attribuendo ad ogni processo una propria
priorità si ottiene la tecnica Multi-level
Queue Scheduling
– i processi vengono posti in code distinte, uno
per ogni livello di priorità
– ogni coda viene gestita con la propria politica
– c’è una politica di scheduling tra le varie code
– una semplice implementazione è la round-robin
a due livelli: quelli CPU_bound ed I/O_bound
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
333
6.3 La gestione dei processi
creazione di un processo 1

il programmatore UNIX, per creare un processo, utilizza la funzione fork() delle API
val fork()
val = -1
= 0
> 0
Sistema Operativo
attiva un nuovo processo figlio simile
al padre, ma con un proprio PID
operazione fork non riuscita
identifica il processo figlio
identifica il padre, e gli restituisce il
PID del figlio generato
Architettura degli elaboratori 1 - A. Memo
334
6.3 La gestione dei processi
creazione di un processo 2
#include <stdio.h>
#include <sys/types.h>
int main(void) {
pid_t pid;
pid = fork();
if (pid == -1) {
fprintf(stderr, "fork() non riuscita\n");
exit(1);
}
if (pid == 0) {
printf("Sono il figlio\n");
exit(0);
}
if (pid > 0) {
printf("Sono il padre del figlio n.%d\n", pid);
exit(0);
}
}
/* si noti l’ordine casuale dei messaggi */
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
335
6.3 La gestione dei processi
processi e thread
modello a processi
• ogni processo ha il proprio spazio di indirizzabilità
• schemi di sicurezza e
protezione semplificati
• scambio di contesto
oneroso
heavy-weight process
Sistema Operativo
modello a thread
• il thread ha una parte di
stato proprio contenuto
ed una parte condivisa
con tutti i thread dello
stesso programma,
risorsa o altro
• la creazione e lo
scambio di contesto
sono più snelle
light-weight process
Architettura degli elaboratori 1 - A. Memo
336
6.3 La gestione dei processi
thread 1




un thread può essere pensato come una
sequenza di istruzioni finalizzate ad un
compito elementare specifico
un processo generalmente è scomponibile in
più thread
il passaggio da programma a processo/i
viene effettuato dal SO
la scomposizione del programma in thread è
compito del programmatore
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
337
6.3 La gestione dei processi
thread 2


lo stato interno di un processo è
contraddistinto dai valori assunti dai registri
della CPU e dalle informazioni presenti
nell’area di stack del processo
un thread (o light process) è spesso visto
come un processo il cui stato interno è
contraddistinto da un numero inferiore di
valori, al minimo il solo IP e lo stack
contenente l’indirizzo di ritorno
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
338
6.3 La gestione dei processi
thread 3
class Azione implements Nucleo {
Object oggetto;
Azione(Object a) { oggetto = a; }
public void esegui() {
// esegue qualcosa su oggetto
}
}
class Programma {
static public void main(String args[]) {
Object ogg_1 = new Object();
Nucleo Azione_1 = new Azione(ogg_1);
Thread t1 = new Thread(Azione_1);
Nucleo Azione_2 = new Azione(ogg_1);
Thread t2 = new Thread(Azione_2);
t1.esegui(); t2.esegui();
// e così via ...
}
}
6.3 La gestione dei processi
thread 4


un thread in Java è caratterizzato dai valori
di tutti i registri della CPU e dalle variabili
locali della procedura thread, e non dagli
oggetti, che vengono assimilati a variabili
globali
nei SO multi-threading lo scambio tra i vari
thread avviene solo per termine o rilascio
spontaneo del thread in esecuzione
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
340
6.3 La gestione dei processi
avanzamento dei processi 1
I processi possono avanzare in maniera
 sequenziale, nei sistemi uni-processore con un


solo contatore di programma; tipico nei SO
monolitici
parallela, nei sistemi multi-processore, per
ottenere il massimo delle prestazioni ma con scarsa
efficenza
alternata, nei sistemi uni-processore con più
contatori di programma, SO a massima efficenza
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
341
6.3 La gestione dei processi
avanzamento dei processi 2
A
A
B
B
sequenziale
C
A1
A2
A3
B
C
C1
parallela
alternata
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
C2
342
6.3 La gestione dei processi
avanzamento dei processi 3


l’avanzamento parallelo e quello alternato
comportano l’esecuzione concorrente (reale
o simulata) dei processi
in tal modo si possono condividere le
risorse, aumentare la velocità di esecuzione
globale e implementare il software secondo
tecniche modulari
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
343
6.3 La gestione dei processi
avanzamento dei processi 4
L’avanzamento concorrente di più processi
può portare a risultati indeterminati. Esempio:
il processo P1 è composto da 2 azioni sequenziali, A e B:
(supponiamo A: x=0 e B: y= x+2)
il processo P2 è composto da 2 azioni sequenziali, C e D
(supponiamo C: x=10 e D: y= x-1)
Le possibili sequenze di un avanzamento concorrente sono:
A B C D (x=10, y=9)
C A B D (x=0, y=-1)
A C D B (x=10, y=12)
C A D B (x=0, y=2)
A C B D (x=10, y=9)
C D A B (x=0, y=2)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
344
6.3 La gestione dei processi
sincronizzazione dei processi 1



se due processi non condividono lo stesso
stato possono operare concorrentemente
se non soddisfano le condizione di Bernstein
non possono operare concorrentemente
conviene limitare la non-concorrenza solo in
quei punti in cui effettivamente viene
condiviso lo stato, mediante utilizzo di
segnali o primitive di sincronizzazione
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
345
6.3 La gestione dei processi
sincronizzazione dei processi 2





supponiamo che A e B siano due processi che hanno
in comune la variabile X, e che inizialmente X valga
10
il processo A deve incrementarla di 2 unità
il processo B deve decrementarla di 4 unità
entrambi accedono contemporaneamente ad X,
vedono che vale 10: il processo A scrive in X il suo
risultato (12), mentre B scrive il suo (6)
alla fine X vale o 12 o 6, in base a chi termina prima,
ma il risultato corretto (8) non lo scriverà nessuno
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
346
6.3 La gestione dei processi
sincronizzazione dei processi 3


per evitare questo problema dobbiamo far si
che i due processi accedano in maniera mutuamente esclusiva alla variabile condivisa
il metodo più semplice sembra essere quello
di utilizzare una variabile lucchetto (flag)
che indichi quando la variabile condivisa
(X) è in uso ad un altro processo (è detta
anche mutex, da mutual exclusion)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
347
6.3 La gestione dei processi
sincronizzazione dei processi 4
- il processo A avanza
- // deve accedere ad X
- test (flag == 0) ?
- se SI
// X è in uso
ritorno al test //aspetto
- altrimenti // X è libera
flag = 0
// occupo X
- uso la variabile X
- flag = 1
// libero X
- il processo B avanza
- // deve accedere ad X
- test (flag == 0) ?
- se SI
// X è in uso
ritorno al test //aspetto
- altrimenti // X è libera
flag = 0
// occupo X
- uso la variabile X
- flag = 1
// libero X
altro esempio: lock file di UNIX
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
348
6.3 La gestione dei processi
sincronizzazione dei processi 5
Questa soluzione ha due problemi:
 in time sharing non funziona perché il
processo può essere interrotto dopo aver
controllato la variabile flag, ma prima di
averla modificata (sezione critica)
 il processo in attesa consuma risorsa CPU
(attesa attiva)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
349
6.3 La gestione dei processi
sincronizzazione dei processi 6

per assicurare la mutua esclusione in sezione critica si possono
adottare due tecniche:
– disabilitare gli interrupt all’ingresso in sezione critica e
riabilitarli in uscita: in tal modo nessuno potrà sospendere
le attività del processo; è pericoloso perché si possono
perdere interrupt importanti, non va bene nei sistemi multiprocessor, è troppo generalizzato e penalizzante
– ricorrere ad una sola istruzione in linguaggio macchina
(atomicità del comando) che acquisisca il valore di una
variabile e ne forzi successi-vamente il valore ad 1
(istruzione test-and-set) (o con analoga xchg)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
350
6.3 La gestione dei processi
sincronizzazione dei processi 7
ancora: TSL reg,flag
CMP reg,0
JNZ ancora
// sezione critica
MOV flag,0
TSL reg,flag legge il valore
di flag, lo pone nel registro
reg, e poi porta flag a 1
XCHG reg,flag scambia i
valori di flag con reg
Sistema Operativo
flag a 0 indica risorsa
disponibile, ad 1 indica
risorsa già in uso.
MOV reg,1
ancora: XCHG reg,flag
CMP reg,0
JNZ ancora
// sezione critica
MOV flag,0
Architettura degli elaboratori 1 - A. Memo
351
6.3 La gestione dei processi
sincronizzazione dei processi 8

per evitare di dover programmare in LM, si utilizzano
due primitive e la variabile semaforo:
– il semaforo utilizza una variabile globale intera S
che non può essere utilizzata direttamente, ma solo
tramite due primitive pubbliche atomiche wait() e
signal(); per S>0 la risorsa è accessibile, inizialmente S=1
void wait (int S) {
void signal (int S) {
S ++;
}
Sistema Operativo
while (S<=0)do;
S --;
}
Architettura degli elaboratori 1 - A. Memo
352
6.3 La gestione dei processi
sincronizzazione dei processi 9
Se un processo vuole accedere alla risorsa R
comune, regolata dalla variabile semaforo sem:
processo
{ // avanzamento
wait(sem);
// usa risorsa R
signal(sem);
// avanzamento
}
Sistema Operativo
wait(s) viene usata per
richiedere l’accesso alla risorsa, e signal(s)
per rilasciare la risorsa
Architettura degli elaboratori 1 - A. Memo
353
6.3 La gestione dei processi
sincronizzazione dei processi 10
Se il processo A vuole sincronizzarsi con B, ed
essere sicuro di avanzare solo quando B ha già
raggiunto un certo punto (all’inizio sem=0) :
processo A
{ // avanzamento
wait(sem);
// avanzamento
}
Sistema Operativo
processo B
{ // avanzamento
signal(sem);
// avanzamento
}
Architettura degli elaboratori 1 - A. Memo
354
6.3 La gestione dei processi
sincronizzazione dei processi 11



Per evitare di avere attesa attiva, la funzione wait()
può bloccare il processo che trova il semaforo
occupato, e la funzione signal() può recuperare da
una lista FIFO i processi in attesa (se ce ne sono)
Per assicurare l’atomicità di wait() e signal(), si
devono disabilitare le interruzioni durante
l’esecuzione delle due funzioni
Se il semaforo può assumere solo due valori
numerici (0 ed 1) lo si chiama semaforo binario,
altrimenti è un semaforo a contatore
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
355
6.3 La gestione dei processi
sincronizzazione dei processi 12
void wait(struct sem){
sem.valore -- ;
if (sem.valore < 0){
ora il semaforo è
add (sem.lista, coda);
una struttura comsleep(chiamante);
posta da un campo
}
intero valore e da
}
un campo lista
con tutti i processi void signal(struct sem){
sem.valore ++ ;
in attesa su quel
if (sem.valore < 0)
semaforo
wakeup(estrai(coda));
}
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
356
6.3 La gestione dei processi
sincronizzazione dei processi 13

per offrire strumenti di sincronizzazione accessibili a linguaggi più astratti, sono stati
introdotti i monitors
– contengono sia la struttura dati, non accessibile
dall’esterno, che le funzioni per gestirla
(analoghi agli oggetti)
– includono anche la coda dei processi in attesa
– assicurano la mutua esclusione
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
357
6.3 La gestione dei processi
InterProcess Communication 1

adesso che abbiamo stabilito come
possiamo condividere l’accesso ad una
risorsa, e quindi anche alla memoria,
vediamo quali strumenti possono utilizzare i
processi per comunicare tra loro:


pipe (condotto)
stream (flusso)
Sistema Operativo


socket (porta)
signal (messaggio)
Architettura degli elaboratori 1 - A. Memo
358
6.3 La gestione dei processi
InterProcess Communication 2

il pipe è come un canale (buffer) unidirezionale tra due processi: al suo ingresso
un processo può scrivere informazioni ed alla
sua uscita un altro processo le può leggere
– un pipe può essere non identificabile, se
condiviso tra processo padre e figlio
– un pipe è identificabile se ha un ID che lo
contraddistingue, e viene utilizzato da processi tra
loro indipendenti, solo tramite il suo ID
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
359
6.3 La gestione dei processi
InterProcess Communication 3



uno stream è analogo al pipe, ma trasferisce
informazioni strutturate
un socket rappresenta una porta di comunicazione tra due processi
il messaggio è il sistema più diretto per far
interagire due processi, ed è l’unico che
opera correttamente in ambienti a memoria
non condivisa
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
360
6.3 La gestione dei processi
InterProcess Communication 4
Il modello a messaggi utilizza due primitive
send (destinazione, messaggio)
receive (mittente, messaggio)
ed una struttura di interconnessione costituita da
canali simmetrici (1 a 1)
canali asimmetrici (1 a N) o (N a 1)
mailbox (N a M)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
361
6.3 La gestione dei processi
produttore - consumatore 1


un processo produce dati ed un’altro li legge
per elaborarli, entrambi con tempi variabili
si utilizzano tre semafori ed un buffer
– int buffer, contenente N slot di dati (liberi)
– sem vuoto, contenente il numero di slot vuoti
nel buffer, inizializzato ad N
– sem pieno, contenente il numero di slot con dati
del buffer, inizializzato a 0
– sem mutex, per impedire l’accesso simultaneo
al buffer
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
362
6.3 La gestione dei processi
produttore - consumatore 2
void produttore(){
// produrre dato
wait(vuoto);
wait(mutex);
// invia dato
// in buffer
signal(mutex);
signal(pieno);
}
Sistema Operativo
void consumatore(){
wait(pieno);
wait(mutex);
// leggi dato
// dal buffer
signal(mutex);
signal(vuoto);
// consumare dato
}
Architettura degli elaboratori 1 - A. Memo
363
6.3 La gestione dei processi
produttore - consumatore 3
si può risolvere anche con il modello a messaggi
void produttore(){
int dato, mess
do {
// produrre dato
receive(consID,mess);
mess=dato;
send(consID,mess);
} while (!finito);
}
NN N
Sistema Operativo
void consumatore(){
int dato, mess
init_buffer();
do {
receive(prodID,mess);
dato=mess;
// consumare dato
send(prodID,NULL);
} while (!finito);
}
Architettura degli elaboratori 1 - A. Memo
364
6.3 La gestione dei processi
stallo 1





i processi A e B hanno entrambi bisogno delle due
risorse R e Q
A chiede l’accesso alla risorsa R e poiché è libera
ne ottiene l’utilizzo esclusivo
B chiede l’accesso alla risorsa Q e poiché è libera
ne ottiene l’utilizzo esclusivo
A chiede l’accesso alla risorsa Q, ma poiché è
occupata si pone in attesa
B chiede l’accesso alla risorsa R, ma poiché è
occupata si pone in attesa
(altro esempio: incrocio stradale e precedenza)
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
365
6.3 La gestione dei processi
stallo 2
Conzioni di stallo (o deadlock) necessarie e
sufficienti:
– accesso esclusivo alla risorsa
– presenza dello stato di blocco nel SO
– non ricorso alla tecnica del pre-rilascio
– lista circolare chiusa tra processi e risorse
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
366
6.3 La gestione dei processi
stallo 3
Ci sono almeno tre modi per affrontare lo stallo:
 prevenirlo,
cercando che almeno una delle
condizioni precedenti non si verifichi mai
 ripristinarlo, ammettendo che si possa verificare
lo stallo ma essere in gardo di riconoscerlo ed
avere a disposizione una procedura di recupero
 ignorarlo, sapendo che la probabilità di stallo è
molto bassa, non prendere alcuna cautela contro di
esso; se succede, pazienza.
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
367
6.3 La gestione dei processi
stallo 4

Prevenzione sulle cause
– accesso esclusivo alla risorsa

per alcune risorse non ci sono alternative
– stato di blocco

impossibile da eliminare
– no pre-emption

per alcune risorse non è possibile
– attesa circolare

Sistema Operativo
difficile ed onerosa da valutare
Architettura degli elaboratori 1 - A. Memo
368
6.3 La gestione dei processi
stallo 5

Prevenzione sulla richiesta di accesso
– ad ogni richiesta di accesso, verificare se questa
porta allo stallo
– in caso affermativo però non si sa bene cosa fare
– è oneroso valutare la possibilità di stallo ad ogni
richiesta
– un’altra possibilità è di richiedere all’inizio a
tutti i processi quali risorse richiederanno e
schedularne l’attività in maniera controllata
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
369
6.3 La gestione dei processi
stallo 6

Riconoscimento
– riconoscere lo stallo è molto oneroso: con una
certa frequenza (ogni secondo?) si deve
bloccare l’avanzamento del sistema, analizzare
lo stato di tutti i processi attivi e verificare se
quelli in attesa costituiscono una lista circolare
chiusa
– il ripristino da uno stato di blocco può essere
effettuato solo terminando uno dei processi
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
370
6.3 La gestione dei processi
stallo 7
Il problema dei cinque filosofi affamati
Cinque filosofi sono seduti ad un tavolo
circolare, e ciascuno ha davanti un piatto di
spaghetti ed una forchetta alla sua destra. Per
mangiare gli spaghetti hanno bisogno di due
forchette. I filosofi alternano momenti di
meditazione a momenti di alimentazione.
Sistema Operativo
Architettura degli elaboratori 1 - A. Memo
371
6.3 La gestione dei processi
stallo 8
soluzione con stallo
5
4
5
1
1
2
4
3
3
Sistema Operativo
2
void filosofo_i_esimo(){
while (1) {
// medita
forchetta_on(i);
forchetta_on((i++)%5);
// mangia
forchetta_off(i);
forchetta_off((i++)%5);
}
}
Architettura degli elaboratori 1 - A. Memo
372