Programmazione Concorrente e
Distribuita
Linguaggi e concorrenza
Programmazione Concorrente
e Distribuita
Bibliografia:
 Ancillotti- Boari. Principi e Tecniche di Programmazione
Concorrente. Utet Libreria
 Ben-Ari. Principles of concurrent and distributed programming.
Addison wesley (second edition)
 Raynal. Distributed Algorithms and Protocols. Wiley & Sons
 Lynch. Distributed Algorithms. Morgan Kaufman
PCD 2006-2007
Linguaggi e concorrenza
2
Programmazione Concorrente e
Distribuita
La programmazione concorrente nasce per gestire i Sistemi
Concorrenti cioe’ sistemi in grado di supportare piu’ utenti (o
programmi) contemporaneamente
Sistemi intrensecamente concorrenti
• Sistemi Real Time
• Sistemi operativi
• Gestione di basi di dati
Applicazioni potenzialmente concorrenti
• Uso di algoritmi paralleli per computazioni:
– su grandi quantita’ di dati
– con grande mole di calcolo
– vincoli di tempo reale
PCD 2006-2007
Linguaggi e concorrenza
3
Programmazione Concorrente e
Distribuita
Per sistema concorrente intendiamo:
 un sistema software
 implementato su vari tipi di hardware
 che porta avanti contemporaneamente una molteplicita’ di attivita’
diverse
 tra di loro correlate
possono cooperare ad un goal comune
possono competere per risorse condivise
PCD 2006-2007
Linguaggi e concorrenza
4
Programmazione Concorrente e
Distribuita
Algoritmi, Programmi, Processi
 Algoritmo:
procedimento logico che deve essere seguito per risolvere un
problema, solitamente specificato da una sequenza di passi che
l’esecutore dell’algoritmo deve seguire;
 Programma:
descrizione dell’algoritmo mediante un opportuno formalismo
(linguaggio di programmazione) che renda possibile l’esecuzione su un
particolare elaboratore;
 Processo:
sequenza di eventi cui dà luogo l’elaboratore quando opera sotto il
controllo di un particolare programma.
PCD 2006-2007
Linguaggi e concorrenza
5
Programmazione Concorrente e
Distribuita
Algoritmi, Programmi, Processi
ATT!
 Il programma è una unità statica
 il processo è una unità dinamica
 Se l’elaboratore e’ sequenziale
=>
il processo è sequenziale:
=>
la sequenza di eventi che costituisce il processo è
totalmente ordinata
=>
rappresentando il processo mediante il grafo orientato
dei suoi eventi (grafo di precedenza) il grafo risulterà
totalmente ordinato.
PCD 2006-2007
Linguaggi e concorrenza
9
Programmazione Concorrente e
Distribuita
Grafo di precedenza di un processo
 nodi del grafo rappresentano i singoli eventi
 archi del grafo rapprresentano le precedenze temporali
 se il processo è sequenziale, il grafo sarà a ordinamento totale: cioè ogni
nodo avrà un predecessore (eccetto il nodo iniziale) ed un successore
(eccetto il nodo finale).
PCD 2006-2007
Linguaggi e concorrenza
10
Programmazione Concorrente e
Distribuita
Grafo di precedenza ad ordinamento totale del
processo che valuta l'espressione:
(3 * 4) + (2 + 3) * (6 - 2)
INIZIO
3 * 4 = 12
2+3=5
6-2=4
5 * 4 = 20
12 + 20 = 32
FINE
PCD 2006-2007
Linguaggi e concorrenza
11
Programmazione Concorrente e
Distribuita
Processi Concorrenti
 L’ ordinamento totale del grafo è solo in parte dovuto alla natura del
problema da risolvere, in parte è dovuto alla natura sequenziale del
calcolatore.
 La natura del problema cioè impone di fatto solo un ordinamento parziale
tra gli eventi.
PCD 2006-2007
Linguaggi e concorrenza
12
Programmazione Concorrente e
Distribuita
Grafo di precedenza ad ordinamento parziale
INIZIO
3*4 = 12
6–2=4
2+3=5
5 * 4 = 20
12+20 = 32
FINE
PCD 2006-2007
Linguaggi e concorrenza
13
Programmazione Concorrente e Distribuita
INIZIO
L1
E1
S1
Ln
En
Sn
FINE
PCD 2006-2007
Linguaggi e concorrenza
14
Programmazione Concorrente e
Distribuita
INIZIO
L1
E1
S1
L2
E2
S2
L3
E3
S3
Ln
En
Sn
FINE
PCD 2006-2007
Linguaggi e concorrenza
15
Programmazione Concorrente e
Distribuita
Abbiamo visto che:
alcuni problemi possono essere risolti mediante processi di calcolo non
sequenziali cioè rappresentati da un grafo ad ordinamento parziale

in questo caso il problema puo’ essere risolto da alcuni moduli
sequenziali che lavorano in parallelo.

Occorre quindi un elaboratore parallelo, in grado cioe’ di eseguire un
numero arbitrario di operazioni contemporaneamente.

Occorre quindi un linguaggio di programmazione con il quale poter
descrivere questi algoritmi non sequenziali.
Lo studio di questi linguaggi, dei loro compilatori e delle loro
applicazioni prende il nome di Programmazione Concorrente.
PCD 2006-2007
Linguaggi e concorrenza
16
Programmazione Concorrente e
Distribuita
Hardware
Sist. Operativi
Sist. Real Time
Sist. Di Rete
Software
Di base
Programmazione
concorrente
Sist. Distribuiti
Linguaggi di
Programm.
PCD 2006-2007
Linguaggi e concorrenza
17
Programmazione Concorrente e
Distribuita
Hardware per sistemi concorrenti
uniprocessore
Nuove architetture
dataflow e
macch. funzionali
CPU unica
+ processori
dedicati
LAN
Local internet
Vector e
Array processor
PCD 2006-2007
Multiprocessori
Memoria condivisa
Linguaggi e concorrenza
Sistemi
LAN/WAN
18
Programmazione Concorrente e
Distribuita
Architetture per sistemi concorrenti
 SISD: Single instruction stream, single data stream
Modello uniprocessore convenzionale (macchina di von Neumann)
 SIMD: Single instruction stream, multiple data stream
Piu’ processori che eseguono la stessa istruzione su dati diversi
(array o vector instruction)
 MIMD: Multiple instruction stream, multiple data stream
Piu’ processori che eseguono istruzioni diverse; possiamo ulteriormente
distinguere tra:
Sistemi multiprocessori con memoria comune
Sistemi a rete (senza memoria comune)
PCD 2006-2007
Linguaggi e concorrenza
19
Programmazione Concorrente e
Distribuita
La macchina su cui un programma concorrente deve andare in
esecuzione deve quindi essere in grado di :
 eseguire un certo numero n di processi sequenziali (n > 1) => la sua
architettura deve essere quella di un multielaboratore
 permettere ai processi di sincronizzarsi => deve fornire meccanismi
primitivi di sincronizzazione e/o di comunicazione, sfruttati dal
compilatore per tradurre i costrutti linguistici di sincronizzazione fornite
dal linguaggio ad alto livello.
PCD 2006-2007
Linguaggi e concorrenza
20
Programmazione Concorrente e
Distribuita
Un po’ di terminologia:
 sistema parallelo: sistema in cui l’esecuzione dei programmi si
sovrappone nel tempo (parallelismo reale )
 sistema concorrente: sistema in cui l’esecuzione dei programmi può
(ma non necessariamente deve) sovrapporsi nel tempo
(parallelismo apparente)
La concorrenza è una forma di astrazione del parallelismo e permette
di trattare in maniera uniforme varie situazioni:
 Multitasking di sistemi mono –processori
 Sistemi fortemente connessi (multiprocessori)
 Sistemi di rete
PCD 2006-2007
Linguaggi e concorrenza
23
Programmazione Concorrente e
Distribuita
Concorrenza come “interleaving” di istruzioni atomiche
Definizione:
Un programma concorrente consiste di un insieme finito di processi
sequenziali. I processi sono scritti usando un insieme finito di
istruzioni atomiche. L’esecuzione di un programma concorrente è
ottenuta interfogliando in maniera arbitraria le istruzioni dei
processi. Il risultato di questo interleaving viene detto
computazione.
PCD 2006-2007
Linguaggi e concorrenza
24
Programmazione Concorrente e
Distribuita
Istruzioni atomiche
Un’ istruzione atomica viene eseguita completamente senza
possibilita’ di interruzioni.
Proprieta’ delle istruzioni atomiche:
Il risultato ottenuta dall’esecuzione “simultanea” di due istruzioni
atomiche e’ lo stesso che si otterrebbe dalla loro esecuzione
sequenziale (in un qualsiasi ordine).
PCD 2006-2007
Linguaggi e concorrenza
25
Programmazione Concorrente e
Distribuita
Istruzioni atomiche
E’ importante specificare con precisione quali siano le istruzioni
atomiche.
Es. lo statement di assegnazione e’ atomico:
n := 0
n := n + 1
n := 0
n := n + 1
temp := n
n:= temp +1
PCD 2006-2007
Linguaggi e concorrenza
temp := n
n:= temp +1
26
Programmazione Concorrente e
Distribuita
Correttezza
Nei programmi concorrenti alcune computazioni possono essere corrette altre no,
ma le normali tecniche di debugging non funzionano poiche’ diverse esecuzioni
dello stesso programma possono dare risultati diversi!!.
Ci sono due tipi di proprieta’ di correttezza:
 Proprieta’ di “safety”:
La proprieta’ P deve sempre essere vera
(P e’ vera in ogni stato della computazione)
 Proprieta’ di “liveness”:
La proprieta’ P prima o poi sara’ vera
(in ogni computazione esiste uno stato in cui P e’ vera)
PCD 2006-2007
Linguaggi e concorrenza
27
Programmazione Concorrente e
Distribuita
Fairness
Ogni possibile interleaving di iststruzioni e’ considerato essere una computazione di
un programma concorrente, pero’ questo comporta che in alcune computazioni ci
siano statement che non sono mai eseguiti. La proprieta’ di “fairness” esclude queste
computazioni.
Proprieta’ di “fairness”:
una computazione e’ fair se per ogni suo stato e’ vero che uno
statement sempre abilitato, prima o poi sara’ eseguito
n := 0
flag := false
while flag = false
n := n + 1
PCD 2006-2007
flag := true
Linguaggi e concorrenza
28
Programmazione Concorrente e
Distribuita
 Le interazioni tra i processi possono essere classificate:
 cooperazione: interazione prevedibile e desiderata
(sincronizzazione diretta o esplicita)
scambio di segnali temporali
scambio di informazione
 competizione: interazione prevedibile e non desiderata, ma
necessaria
(sincronizzazione indiretta o implicita)
mutua esclusione
PCD 2006-2007
Linguaggi e concorrenza
29
Programmazione Concorrente e
Distribuita
Programma sorgente
scritto nel
linguaggio
L
Compilatore
Programma tradotto
nel linguaggio
oggetto per
la macchina M
Compilazione di programmi concorrenti
PCD 2006-2007
Linguaggi e concorrenza
30
PCD
Architettura di una macchina concorrente
La macchina concorrente M in realta’ e’ una macchina virtuale o
astratta aventi la caratteristiche funzionali desiderate, ma
realizzata con tecniche software, basandosi su una macchina
fisica M’ molto piu’ semplice.
In particolare M’:
 puo’ avere un numero molto inferiore di processori (anche uno
solo)
 puo’ essere priva di primitive di sincronizzazione/comunicazione:
queste saranno data da uno strato di software che funzionalmente
rappresenta il nucleo (kernel) del SO e che viene chiamato
supporto run time del compilatore del linguaggio concorrente.
Un nucleo fornisce sempre due meccanismi basilari:
 meccanismo di multiprogrammazione
 meccanismo di sincronizzazione/comunicazione
PCD 2006-2007
Linguaggi e concorrenza
31
PCD
Architettura di una macchina concorrente
Meccanismo di multiprogrammazione
Meccanismo di sincronizzazione
Macchina fisica M’
Macchina virtuale e macchina fisica
PCD 2006-2007
Linguaggi e concorrenza
32
PCD
Architettura di una macchina concorrente
Due diverse organizzazioni logiche:
 gli elaboratori sono collegati ad una unica
memoria comune (modello a memoria comune)
 gli elaboratori sono collegati da una sottorete di
comunicazione, ma non condividono memoria (modello
a rete)
PCD 2006-2007
Linguaggi e concorrenza
33
Programmazione concorrente e distribuita
Esprimere la concorrenza
In un linguaggio per la concorrenza occorrono
costrutti linguistici per:
dichiarare, creare, attivare, terminare processi
sequenziali che lavorino in parallelo;
permettere l’interazione (comunicazione e
sincronizzazione) tra processi concorrenti.
PCD 2006-2007
Linguaggi e concorrenza
35
Programmazione concorrente e distribuita
Esprimere la concorrenza
Costrutti linguistici per la concorrenza:
Coroutines
Processi
Fork/ Join
Cobegin/Coend
Task
PCD 2006-2007
Linguaggi e concorrenza
36
Programmazione concorrente e distribuita
Esprimere la concorrenza
Coroutines
costrutto presente nei linguaggi Simula (68), BLISS,
Modula, ec..
utile per simulare l’elaborazione non sequenziale in
ambiente monoprocessore
meccanismo di passaggio di controllo simile al go to
realizza un trasferimento di controllo non locale, cioè
tra contesti diversi
PCD 2006-2007
Linguaggi e concorrenza
37
Programmazione concorrente e distribuita
Esprimere la concorrenza
 La coroutine è costituita da:
un insieme di dati locali
insieme di istruzioni (body)
 Nel body ci può essere l’istruzione : resume X
X è il nome della coroutine chiamata
l’esecuzione della resume X trasferisce il controllo dalla
coroutine chiamante alla coroutine X, previo salvataggio di
contesto;
X viene attivata a partire dall’inizio (se è la prima volta che
viene chiamata) oppure a partire dall’istruzione successiva
all’ultimo resume da lei eseguito
PCD 2006-2007
Linguaggi e concorrenza
42
Programmazione concorrente e distribuita
Esprimere la concorrenza
Coroutine X
<dich. dati locali>
Coroutine Y
<dich. dati locali>
Coroutine Z
<dich. dati locali>
begin
….
….
resume Y
….
….
….
begin
….
resume Z
….
resume X
….
….
begin
….
….
resume Y
….
…..
….
end
end
end
PCD 2006-2007
Linguaggi e concorrenza
43
Programmazione concorrente e distribuita
Esprimere la concorrenza
Oltre all’istruzione resume, occorrono altre
istruzioni per:
creare: co-id:= co-create (name, start-address, stack-size)
cancellare: kill (co-id)
chiamare: call (co-id)
sospendere: suspend
una coroutine
PCD 2006-2007
Linguaggi e concorrenza
44
Programmazione concorrente e distribuita
Esprimere la concorrenza
Caratteristiche delle coroutines:
in ogni istante una sola coroutine è attiva
l’ordine di esecuzione è controllato dal
programmatore
sono utili per specificare particolari strategie di
esecuzione in ambiente monoprocessore
non sono adatte per programmare algoritmi
concorrenti per ambienti multiprocessore
PCD 2006-2007
Linguaggi e concorrenza
45
Programmazione Concorrente e
Distribuita
1 programma
1 programma
1 processo
1 processo
Codice per
una procedura
Codice per una
procedura
Codice per gestire procedure separate
Sistema runtime
Sistema runtime
del linguaggio
del linguaggio
Supporto runtime
Gestione dello stack e
dello heap
Kernel del SO
Linguaggio di programmazione
sequenziale: attività diverse nel
codice utente
PCD 2006-2007
Linguaggi e concorrenza
46
Programmazione Concorrente e
Distribuita
1 programma
1 programma
1 processo
1 processo
Codice
coroutine
Codice
coroutine
Codice
coroutine
Codice creazione e gestione coroutine
Sistema runtime
Sistema runtime
del linguaggio
del linguaggio
sistema runtime
Kernel del SO
Linguaggio di programmazione
sequenziale: attività diverse nel
codice utente
PCD 2006-2007
Linguaggi e concorrenza
47
Programmazione concorrente e distribuita
Esprimere la concorrenza
Codice di una
coroutine
Codice di una
coroutine
Codice di una
coroutine
Codice per la creazione di coroutine e per il passaggio di controllo
Sistema runtime
Gestione della memoria
heap
PCD 2006-2007
Uno stack
ed un
blocco di
controllo
per
ciascuna
coroutine
Supporto per la creazione e
il trasferimento di
controllo:
co-create
kill
call
suspend
resume
Linguaggi e concorrenza
48
Programmazione concorrente e distribuita
Esprimere la concorrenza
Consideriamo i seguenti problemi:
Un file server per una rete gira su una macchina dedicata. Riceve
richieste
dai
clienti
e
lavora
a
più
richieste
contemporaneamente.
Un SO controlla un certo numero di periferici e l’insieme delle
routine di gestione.
Il sistema computerizzato di un impianto chimico
periodicamente preleva ed esamina dati da sensori e gestisce le
situazioni critiche
Un sistema multiprocessre è utlizzato per ricerche parallele su
grandi quantità di dati.
PCD 2006-2007
Linguaggi e concorrenza
49
Programmazione concorrente e distribuita
Esprimere la concorrenza
Il file server.
Una possibile implementazione di questo problema con le coroutines si
può ottenere creando una coroutine per ogni cliente del file server. Il server,
in un loop, decide quale coroutine servire, il codice delle coroutine termina
con una suspend.
Questa soluzione va bene se il SO offre dell system call non bloccanti e se
non è necessaria una risposta immediata agli eventi.
Coroutine A
Main
suspend
Call A
Call B
Coroutine B
suspend
PCD 2006-2007
Linguaggi e concorrenza
50
Programmazione concorrente e distribuita
Esprimere la concorrenza
Controllo Periferici.
Una possibile implementazione di questo problema con le coroutines si
può ottenere creando una coroutine per ogni periferico. Il main è costituito da
un polling loop in cui le routine dei periferici sono chiamate l’una dopo
l’altra in un ordine prefissato.
Questa soluzione va bene se non ci sono tempi critici di risposta ai devices.
Altri Problemi
Il problema del controllo computerizzato di un impianto chimico non si
può realizzare per problemi di tempo reale, mentre quello dell’elaborazione
parallela per mancanza di parallelismo effettivo!
PCD 2006-2007
Linguaggi e concorrenza
51
Programmazione Concorrente e
Distribuita
1 programma
1 programma
1 processo
più processi
Codice per un
processo
...
Codice per un
processo
Codice per gestire la creazione di processi e
il passaggio di controllo
Sistema runtime
Sistema runtime
del linguaggio
del linguaggio
Supporto runtime
Kernel del SO
heap
Gestione dei processi
Supporto per la
creazione e lo
scheduling dei
processi
Linguaggio di programmazione
concorrente: processi gestiti dal
linguaggio
PCD 2006-2007
Linguaggi e concorrenza
52
Programmazione concorrente e distribuita
Esprimere la concorrenza
Specifica, creazione e cancellazione di processi.
Fork/Join
Espressione linguistica proposta da Conway [63], Dennis[66]:
L’istruzione fork ha un comportamento analogo ad una chiamata di
procedura (call), ma il programma chiamante prosegue assieme al
programma chiamato:
A
A:
B:
fork X
<istruzione
successiva alla fork>
X:
<prima istruzione
procedura invocata fork>
PCD 2006-2007
B
Linguaggi e concorrenza
X
53
Programmazione concorrente e distribuita
Esprimere la concorrenza
Specifica, creazione e cancellazione di processi.
Fork/Join
per congiungere più flussi di controllo si usa l’istruzione join:
var cont: integer
:
join cont
l’istruzione join in forma indivisibile esegue queste azioni;
cont := cont -1
if cont = 0 then <terminazione del processo>
PCD 2006-2007
Linguaggi e concorrenza
54
Programmazione concorrente e distribuita
Esprimere la concorrenza
Specifica, creazione e cancellazione di processi.
Fork/Join
Esempio
begin
cont := 3
A
fork E1
B
fork E2
D
go to E3
E1: C
F
go to E3
E2: E
E3: join cont
G
end
PCD 2006-2007
A
C
B
F
D
E
G
Linguaggi e concorrenza
55
Programmazione concorrente e distribuita
Esprimere la concorrenza
Specifica, creazione e cancellazione di processi.
Fork/Join
Alternativa al join con contatore:
 la fork restituisce un valore
 tale valore è utilizzato per specificare lóperando della join
X
P:= fork X
P:= fork X
begin
join P
end
join P
PCD 2006-2007
Linguaggi e concorrenza
56
Programmazione concorrente e distribuita
Esprimere la concorrenza
var P1, P2:process
procedure E1
begin
C
F
end
procedure E2
begin
E
end
begin
A
P1 :=fork E1
B
P2:=fork E2
D
join P1
join P2
G
end
PCD 2006-2007
Linguaggi e concorrenza
57