Processi e Thread
Meccanismi di IPC
Problemi classici di IPC
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 principalmente ai processi
– maccanismi simili sono disponibili per i thread
2
Comunicazioni fra processi
Race Condition (Interferenza)
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 esterno
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)
• 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
7
Mutua Esclusione con attesa attiva
(busy waiting) (2)
• Soluzioni software
– alternanza stretta
– soluzione di Peterson
• Soluzioni hardware-software
– l’istruzione TSL
8
Mutua Esclusione con attesa attiva (3)
Alternanza stretta
Processo 0
Processo 1
Una soluzione non soddisfacente per il problema della ME
– 0 può bloccare 1 quando si trova fuori dalla SC
9
Mutua Esclusione con attesa attiva (4)
Soluzione di Peterson (semplificata)
10
Mutua Esclusione con attesa attiva (5)
Ingresso ed uscita dalla sezione critica utilizzando
l’istruzione TSL
11
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
– wakeup(P) :: sveglia il processo P
12
Sol. Errata al problema del produttore–consumatore (con race condition)
13
Semafori (1)
• Problema con sleep e wakeup : una wakeup non
utilizzata immediatamente viene persa
• Semafori : variabili intere
– contano il numero di wakeup pendenti
– il valore è 0 se non ci sono wakeup pendenti e > 0 altrimenti
• Due operazioni atomiche standard Up e Down (P e V)
– down(S)
• se S > 0 allora S= S - 1 ed il processo continua l’esecuzione
• se S==0 ed il processo si blocca senza completare la primitiva
– up(S)
• se ci sono processi in attesa di completare la down su quel semaforo (e
quindi necessariamente S == 0) uno di questi viene svegliato e S
rimane a 0, altrimenti S viene incrementato;
• in caso contrario (S > 0), allora S=S + 1
14
Semafori (2)
Soluzione del Produttore/Consumatore con semafori
15
Mutex (1)
• Semaforo con solo due stati aperto (unlocked) o chiuso
(locked)
• Popolare nei thread user-level
• Due primitive :
– mutex_lock(), corrisponde alla down()
– mutex_unlock(), corrisponde alla up()
• Utilizzato per realizzare sezioni critiche su dati condivisi
• Puo essere implementato efficientemente senza passare
in stato kernel (se è disponibile la TSL)
16
Mutex (2)
Implementazione delle primitive di mutex_lock e
mutex_unlock
17
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)
18
Monitor (2)
Un esempio di monitor
19
Monitor (3)
• Schema di soluzione Produttore/Consumatore
– ad ogni istante solo una procedura del monitor è in esecuzione
– il buffer ha N posizioni
20
Monitor (4)
• Caratteristiche principali dei monitor Java
–
–
–
–
ME nell’esecuzione dei metodi synchronized
non ci sono variabili di condizione
wait(), notify() simili a sleep() , wakeup()
è possibile svegliare tutti i processi in attesa
21
Monitor (5)
Soluzione per Produttore/Consumatore in Java (parte 1)
22
Monitor (6)
Soluzione per Produttore/Consumatore in Java (parte 2)
23
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
24
Scambio Messaggi (2)
Sol. Produttore/Consumatore con N messaggi
25
I filosofi a cena (1)
• I filosofi mangiano e
pensano
• Per mangiare servono due
forchette
• Ogni filosofo prende una
forchetta per volta
• Come si può prevenire il
deadlock
26
I filosofi a cena (2)
Una falsa soluzione al problema dei filosofi
27
I filosofi a cena (3)
Una soluzione corretta al problema (parte 1)
28
I filosofi a cena (4)
Una soluzione corretta al problema (parte 2)
29
Il problema dei lettori e scrittori (1)
• Un database molto esteso (db)
– es. prenotazioni aeree …
• Un insieme di processi che devono leggere o scrivere
in db
• Più lettori possono accedere contemporaneamente a db
• Gli scrittori devono avere accesso esclusivo a db
• I lettori hanno precedenza sugli scrittori
– se uno scrittore chiede di accedere mentre uno o più lettori
stanno accedendo a db, lo scrittore deve attendere che i lettori
abbiano finito
30
Il problema dei lettori e scrittori (2)
Una soluzione al problema dei lettori e scrittori
31
Il barbiere sonnolento (1)
32
Il barbiere sonnolento (2)
Soluzione al problema del barbiere.
33