Modulo sulla concorrenza
Gabriella Pasi e Carla Simone (dai
lucidi tratti dal sito del libro di
Jeff Magee e Jeff Kramer)
Concurrency: introduction
1
©Magee/Kramer
Libro di testo
Concurrency:
State Models &
Java Programs
Jeff Magee &
Jeff Kramer
WILEY
Concurrency: introduction
2
©Magee/Kramer
Obbiettivi di questo modulo
In questo modulo di lezioni sono presentano i concetti
fondamentali relativi alla definizione di specifiche
(modelli) di programmi concorrenti. NON sono
presentati aspetti di programmazione concorrente in
Java, che saranno affrontati nel corso di sistemi
operativi.
Gli aspetti di modellazione sono di estrema
importanza per una corretta comprensione e
definizione di sistemi concorrenti, e per ragionare in
termini di concorrenza
Concurrency: introduction
3
©Magee/Kramer
Programma
 Concetti
 si presenta un approccio modellistico alla specifica e alla
costruzione di programmi concorrenti
 Modelli
 Labelled Transition Systems (LTS)
 Reti di Petri SA (ad automi sovrapposti)
 Finite State Process (FSP)
Costrutti grafici
notazione algebrica
 Esempi
Concurrency: introduction
4
©Magee/Kramer
Cos’è un programma concorrente?
Un programma sequenziale ha un
singolo “thread” di controllo.
Un programma concorrente ha più
“thread” di controllo che permettono
sia la realizzazione di computazioni
multiple sia il controllo di attività
esterne che si presentano
contemporaneamente.
Concurrency: introduction
5
©Magee/Kramer
Thread
Thread: filone, filo del discorso
Thread:
[1] Una delle parti di un processo (applicazione in fase di
esecuzione). Ogni thread dispone di una parte di memoria e di un
gruppo di registri della CPU. Quando il thread termina (quando
cioè termina la singola fase all'interno dell'esecuzione
dell'applicazione) la memoria e gli oggetti di sistema che
utilizzava vengono liberati. Quando termina l'ultimo thread di un
processo, termina anche il processo, e quindi l'applicazione. Il
termine multithreading denota l’esecuzione contemporanea di più
thread
[2] In un newsgroup Usenet (in Internet) identifica i messaggi con
Concurrency:
introductionargomento.
6
un medesimo
©Magee/Kramer
Perché la Programmazione Concorrente?
 Migliori prestazioni in caso di hardware multiprocessore
parallelismo
 Applicazioni distribuite
 Incremento velocità di trasferimento dati (throughput)
tra applicazioni
 Incremento dei tempi di risposta delle applicazioni
thread di alta priorità per le richieste utenti.
 Strutturazione
nel caso di programmi che interagiscono con l’ambiente,
Concurrency: introduction
7
controllo di attività multiple e gestione di eventi multipli.
©Magee/Kramer
modelli
Un modello è una rappresentazione semplificata della
realtà.
 focalizzazione su un aspetto di interesse - concorrenza
 animazione dei modelli per verificare un comportamento
 verifica di proprietà (ad esempio sicurezza & vivezza)
Concurrency: introduction
8
©Magee/Kramer
modelli
In questo contesto i modelli sono descritti per mezzo di automi
a stati finiti.
Diversi metodi di rappresentazione grafica:
•Labelled Transition Systems LTS.
•Reti di Petri
Da un punto di vista notazionale in
alcuni casi un processo non è ben
distinto dal suo comportamento
Da un punto di vista notazionale
un processo è sempre ben
distinto dal suo comportamento
Un modello grafico può essere descritto linguisticamente
mediante il linguaggio FSP (finite state processes) e, se
denotato mediante LTS, può essere visualizzato e analizzato
Concurrency: introduction
9
per mezzo dello strumento di analisi LTSA.
©Magee/Kramer
Materiale su Web
http://www-dse.doc.ic.ac.uk/concurrency/
 esempi in Java
 esempi di modelli a stati
 Il tool “Labelled Transition System Analyser
(LTSA)” per animare i modelli LTS e per verificarne
le proprietà.
Concurrency: introduction
10
©Magee/Kramer
Capitolo 2
Processi & Thread
Concurrency: introduction
11
©Magee/Kramer
Processi concorrenti
I sistemi complessi sono strutturati
come insiemi di attività semplici
ognuna rappresentata come processo
sequenziale. I processi possono
sovrapporsi o essere concorrenti. La
concorrenza può essere intrinseca al
mondo fisico, oppure introdotta per
ottimizzare i tempi di esecuzione o
per
gestire
comunicazioni.
La
programmazione
concorrente
è
complessa
e
può
facilmente
introdurre errori. Un approccio
rigoroso è essenziale
Concurrency: introduction
Processo come sequenza
di azioni
Modellazione di processi
come macchine a stati
finiti
A livello di
programmazione:
thread in Java.
12
©Magee/Kramer
Modellazione di Processi
Modelli descritti mediante macchine a stati, quali
Reti di Petri e Labelled Transition Systems LTS.
Queste possono essere descritte
linguisticamente per mezzo di una notazione
algebrica, detta finite state processes (FSP)
Notazioni con espressività diversa!
Vedremo perchè
 LTS - Reti di Petri forma grafica
 FSP - forma algebrica
Concurrency: introduction
13
©Magee/Kramer
Modellazione di Processi
Un processo è l’esecuzione di un programma sequenziale.
E’ modellato come una macchina a stati finiti che transita
da stato a stato per mezzo dell’esecuzione di azioni
atomiche.
Un interruttore
on
0
LTS
Reti di Petri
on
1
off
off
onoffonoffonoff ……….
Concurrency: introduction
Una sequenza di azioni o “trace” 14
©Magee/Kramer
comportamento
FSP - azioni e processi
Se x è un’azione e P un processo (x-> P) descrive un
processo che inizialmente esegue l’azione x e poi si
comporta esattamente come P.
ATTIVAZIONEUNICA = (unavolta -> STOP).
once
0
1
Convenzione: le azioni hanno lettera iniziale minuscola
i PROCESSI hanno lettera iniziale maiuscola
Concurrency: introduction
15
©Magee/Kramer
FSP - ricorsione
Un comportamento ripetitivo si modella mediante ricorsione:
on
ATTIVAZIONE = OFF,
OFF
= (on -> ON),
ON
= (off -> OFF).
0
Definizione più sintetica:
1
off
ATTIVAZIONE = OFF,
OFF
= (on -> (off -> OFF)).
E ancora:
ATTIVAZIONE = (on -> off -> ATTIVAZIONE).
Concurrency: introduction
16
©Magee/Kramer
Animazione per mezzo del “tool” LTSA
Il programma LTSA può
essere usato per produrre
una “trace”.
Nella rappresentazione LTS
associata, l’ultima azione è
evidenziata in rosso.
on
0
Concurrency: introduction
1
off
17
©Magee/Kramer
FSP - action prefix
modello FSP di un semaforo :
SEMAFORO = (rosso->giallo->verde->giallo->SEMAFORO).
LTS :
Reti di Petri
rosso
red
0
giallo
orange
1
Trace:
verde
green
2
giallo
orange
rosso
3
giallo
verde
giallo
rossogialloverdegiallorossogialloverde
Concurrency: introduction
18
©Magee/Kramer
…
FSP - costrutto di selezione
Se x e y sono azioni, (x-> P | y-> Q) descrive un
processo che inizialmente realizza una delle due azioni
x o y. Dopo l’esecuzione della prima azione, il
comportamento successivo è descritto da P se la prima
azione è stata x, da Q se la prima azione è stata y.
Chi o che cosa compie la scelta?
C’è una differenza tra azioni di input e output?
Concurrency: introduction
19
©Magee/Kramer
FSP - scelta
Modello FSP di una macchina distributrice di bevande:
DISTRIBUTORE = (rosso->caffè->DISTRIBUTORE
|blu-> thè-> DISTRIBUTORE).
Reti di Petri
blublue
LTS
red
rosso
rosso
0
1
blu
2
caffè
coffee
caffè
thè
tea
thè
Concurrency: introduction
20
©Magee/Kramer
Scelta non deterministica Lanciare una moneta
Il processo (x-> P | x -> Q) descrive un’azione iniziale x e
un comportamento successivo modellato da P o Q.
LANCIOMONETA = (lancio->TESTA|lancio->CROCE),
TESTA = (vistesta->LANCIOMONETA),
TAILS= (viscroce->LANCIOMONETA).
Concurrency: introduction
21
©Magee/Kramer
Lanciare una moneta
Scelta non deterministica
Reti di Petri
LTS :
lancio
toss
lancio
A)
toss
lancio
vistesta
0
1
2
heads
vistesta
tails
viscroce
B)
lancio
vistesta
Concurrency: introduction
viscroce
lancio
viscroce
22
©Magee/Kramer
Modellare errori (eccezioni)
Come si può modellare un canale di comunicazione
inaffidabile che accetta un input (in) e produce un
output solo nel cas in cui non si presenti un errore?
Uso del non-determinismo ...
LTS :
CHAN = (in->CHAN
|in->out->CHAN).
Reti di Petri
in
in
0
in
Concurrency: introductionout
1
error
out
23
©Magee/Kramer
FSP - processi e azioni indicizzati
Buffer che prende in input un valore nell’intervallo 0 .. 3
e restituisce in output quel valore:
BUFF = (in[i:0..3]-> out[i]-> BUFF).
equivalente a:
BUFF = (in[0]->out[0]->BUFF
|in[1]->out[1]->BUFF
|in[2]->out[2]->BUFF
|in[3]->out[3]->BUFF
).
O, usando un parametro di processo con valore di default:
BUFF(N=3) = (in[i:0..N]->out[i]-> BUFF).
Concurrency: introduction
24
©Magee/Kramer
FSP - selezione su condizione
La selezione (when B x -> P | y -> Q) significa che
quando la condizione B è verificata allora è possibile
scegliere sia l’azione x sia l’azione y, altrimenti se B
non è verificata l’azione x non può essere scelta.
COUNT (N=3)
= COUNT[0],
COUNT[i:0..N] = (when(i<N) inc->COUNT[i+1]
|when(i>0) dec->COUNT[i-1]
).
inc
0
1
dec
Concurrency: introduction
inc
inc
2
dec
3
dec
25
©Magee/Kramer
FSP - selezione su condizione
Valore 0
inc
Valore 1
dec
inc
Valore 2
dec
inc
Valore 3
dec
Concurrency: introduction
26
©Magee/Kramer