Processi e Thread
• Processi
• Thread
• Meccanismi di comunicazione fra processi (IPC)
• Problemi classici di IPC
• Scheduling
• Processi e thread in Unix
• Processi e thread in Windows
1
Comunicazioni fra processi/thread
• Processi/thread eseguiti concorrentemente hanno bisogno
di interagire per comunicare e sincronizzarsi :
– scambiare dati
– utilizzare correttamente strutture dati condivise
– eseguire azioni nella sequenza corretta
• Molti meccanismi proposti
• Per semplicità ci riferiremo sempre ai processi
– maccanismi simili sono disponibili per i thread
2
Comunicazioni fra processi
Race Condition
(Interferenza, gara, corsa critica)
Due processi accedono alla memoria condivisa contemporaneamente
l’esito dipende dall’ordine in cui vengono eseguiti gli accessi
3
Sezioni/Regioni Critiche (1)
Regione Critica : porzione di un processo che
accede a strutture dati condivise
– punti potenziali di interferenza
Obiettivo : fare in modo che le regioni critiche di
due processi non vengano mai eseguite
contemporaneamente (mutua esclusione)
4
Sezioni/Regioni Critiche (2)
4 condizioni per assicurare la mutua esclusione




un solo processo per volta esegue la sezione critica
non viene fatta nessuna assunzione sulla velocità
relativa dei processi
nessun processo che sta eseguendo codice esetrno
alla sezione critica può bloccare un altro processo
nessun processo attende indefinitamente di entrare
nella sezione critica
5
Sezioni/Regioni Critiche (3)
Mutua esclusione con sezioni critiche
6
Mutua Esclusione con attesa attiva
(busy waiting) (1)
• Attenzione: il processo e' in stato “running”
ma e' in busy waiting (loop)
7
Mutua Esclusione con attesa attiva
(busy waiting) (2)
• Disabilitare le interruzioni
– impedisce che un altro processo vada in
esecuzione
– non utilizzabile in modo utente
– utilizzabile per poche istruzioni in modo kernel
– non risolve il problema se il sistema ha più di
una CPU
8
Mutua Esclusione con attesa attiva
(busy waiting) (3)
• Soluzioni software
– alternanza stretta
– soluzione di Peterson
• Soluzioni hardware-software
– l’istruzione TSL
9
Mutua Esclusione con attesa attiva (3)
Alternanza stretta (1)
Processo 0
Processo 1
Una soluzione non soddisfacente per il problema della ME
– 0 può bloccare 1 quando si trova fuori dalla SC
10
Mutua Esclusione con attesa attiva (3)
Alternanza stretta (2)
Garantisce la proprieta' di mutua esclusione
MA HA DUE PUNTI DEBOLI:
a) i due processi devono osservare un'alternanza stretta per l'uso
della sezione critica
la velocita' di esecuzione e' data dal processo piu'
lento
11
Mutua Esclusione con attesa attiva (3)
Alternanza stretta (2)
Garantisce la proprieta' di mutua esclusione
MA HA DUE PUNTI DEBOLI:
a) i due processi devono osservare un'alternanza stretta per l'uso
della sezione critica
la velocita' di esecuzione e' data dal processo piu'
lento
b) se un processo fallisce, l'altro viene bloccato per sempre
12
Mutua Esclusione con attesa attiva (4)
Soluzione di Peterson (semplificata) 1981
13
Mutua Esclusione con attesa attiva (5)
TEST & SET LOCK
TSL RX, LOCK
RX<= (LOCK)
LOCK <= #1
Ingresso ed uscita dalla sezione critica utilizzando
l’istruzione TSL (TEST AND SET LOCK)
14
Soluzioni senza attesa attiva
Le primitive Sleep e Wakeup (1)
• Idea di base : un processo viene bloccato finché non è in
grado di entrare nella sezione critica (in modo da non
sprecare cicli di CPU)
• Due primitive realizzate come system call
– sleep() :: blocca il processo che la invoca (P va in stato
“BLOCCATO”)
– wakeup(P) :: sveglia il processo P
15
Le primitive Sleep e Wakeup (2)
Sol. errata al problema del produttore–consumatore (con race condition)
16
Semafori
Dijkstra (1965) (1)
• Problema con sleep e wakeup : una wakeup non
utilizzata immediatamente viene persa
• Dijkstra (1965): due o piu' processi possono cooperare
attraverso semplici segnali in modo che un processo si
fermi ad una locazione ben precisa finche' non riceve un
segnale specifico
• Semafori : variabili intere
– contano il numero di wakeup pendenti
– il valore è 0 se non ci sono wakeup pendenti e > 0 altrimenti
17
Semafori (2)
• Due operazioni atomiche (= non interrompibili)
standard Up e Down (P e V)
– down(S) [riceve segnale]
• se S > 0 allora S= S – 1 ed il processo continua l’esecuzione
• se S==0 il processo viene bloccato senza completare la primitiva (il
processo viene aggiunto alla lista dei processi in attesa al semaforo e
poi viene invocato lo scheduler)
– up(S)
[trasmette segnale]
• se S > 0 allora S= S + 1
• se S==0 e ci sono processi in attesa di completare la down su quel
semaforo, uno di questi viene svegliato (viene messo nello stato di
pronto) e S rimane a 0, altrimenti S viene incrementato
18
Semafori (3)
• Ogni risorsa e' protetta da un semaforo. Quando un
semaforo viene creato gli viene assegnato un numero
che denota quanti utilizzi concorrenti della risorsa sono
ammessi
• Semafori binari (per mutua eclusione)
MUTEX (MUTual EXclusion)
per protezione risorse
mutex=1;
inizializzato a 1
processo
...
down (&mutex)
<regione critica>
up (&mutex)
....
19
mutex
Semafori (4)
sincronizzazione
Soluzione del Produttore/Consumatore con semafori
20
Semafori (5)
Schema di cosa accade nei livelli bassi dell’OS
quando viene rilevata una interruzione
1. Salvataggio PC, PSW e qualche RG sulla pila (hw)
2. L’interrupt vector viene caricato nel PC (hw)
3. Salvataggio delle info sullo stack e di tutti i registri
nella tabella dei processi (assembler)
4. L’SP punta a una nuova pila (assembler)
5. Esecuzione
del gestore delle interru-
zioni (C)
6. Esecuzione dello scheduler per decidere il nuovo
processo da eseguire (C)
7. Caricamento dei registri e di tutte le informazioni
relative al nuovo processo da eseguire (assembler)
MODELLO A
SEMAFORO
semaphore s=0;
processo P (device
driver)
starts i/o device;
down (s); si blocca
.....
interrupt handler
~~> interrupt
up (s); P pronto
21
Monitor (1)
•
•
•
•
Oggetti (Strutture dati + procedure per accedervi)
Mutua esclusione nell’esecuzione delle procedure
Variabili di Condizione + wait() e signal()
wait(X)
– sospende sempre il processo che la invoca in attesa di una
signal(X)
• signal(X)
– sveglia uno dei processi in coda su X
– se nessun processo è in attesa va persa
– deve essere eseguita solo come ultima istruzione prima di
uscire dal monitor (il processo svegliato ha l’uso esclusivo del
monitor)
22
Monitor (2)
Un esempio di monitor
23
Monitor (3)
pseudoPascal
procedure
• Schema di soluzione Produttore/Consumatore
– ad ogni istante solo una procedura del monitor è in esecuzione
– il buffer ha N posizioni
24
Scambio Messaggi (1)
• Non richedono accesso a supporti di
memorizzazione comune
• primitive base
– send(destination,&msg)
– receive(source, &msg)
• decine di varianti, nel nostro caso :
– la receive blocca automaticamente se non ci sono
messaggi
– i messaggi spediti ma non ancora ricevuti sono
bufferizzati dal SO
25
Scambio Messaggi (2)
send (destination, & message)
receive(source, &message)
Sol. Produttore/Consumatore con N messaggi
26
I filosofi a cena (1)
Dijkstra (1965)
• I filosofi mangiano e
pensano
• Per mangiare servono due
forchette
• Ogni filosofo prende una
forchetta per volta
• Come si può prevenire il
deadlock
27
I filosofi a cena (2)
Una falsa soluzione al problema dei filosofi
28
I filosofi a cena (3)
<---down (mutex);
<--up(mutex);
Una falsa soluzione al problema dei filosofi
29
LN R
512
123
234
345
451
I filosofi a cena (4)
“%” = modulo
Una soluzione corretta al problema (parte 1)
30
I filosofi a cena (5)
(int i)
libera il sx
libera il dx
(int i)
Una soluzione corretta al problema (parte 2)
31
Il problema dei lettori e scrittori
Una soluzione al problema dei lettori e scrittori (1971)
32
Il barbiere sonnolento (1)
33
Il barbiere sonnolento (2)
Soluzione al problema del barbiere.
34