Paradigmi Concorrenti - Appunti

Paradigmi concorrenti

Lezione 1

Sistema concorrente

Sistema concorrente, caratteristiche:

• Competizione per l’accesso a risorse condivise.
• Cooperazione per uno scopo comune.
• Coordinamento di attività diverse.
• Sincronia (c’è un cronometro comune) / asincronia (no cronometro comune).

Sistema sequenziale: esegue un’azione alla volta.

Proprietà dei programmi concorrenti

• Safety: nulla di male potrà accadere (mai nessun processo sarà contemporaneamente nella stessa sezione critica).
• Liveness: qualcosa di buono prima o poi accadrà (prima o poi raggiungeremo uno stato desiderabile).
• Deadlock: situazione di blocco (processi in esecuzione bloccati, in attesa che un altro compia una certa azione).
• Livelock: ci possono essere dei processi bloccati, ma il sistema non è fermo; i processi cambiano continuamente di stato senza mai progredire realmente nell’elaborazione.
• Starvation: un processo pronto non viene mai eseguito.

Proprietà invarianti: proprietà vere costantemente.

Modello: rappresentazione semplificata della realtà; astrazione dei dettagli non rilevanti.

Notazione formale => tecniche e strumenti di analisi.

Thread: flusso (sequenziale) di controllo, processo sequenziale.

Programmi multithread: composti da più flussi di controllo paralleli.

Java Virtual Machine: programma multithreaded.

Ciclo di vita di un thread

Ciclo di vita di un thread: 1 – start BORN 2 – dispatch 1 3 – quantum expiration READY yield 6 10 interrupt 8 4 – complete 2 3 WAITING SLEEPING BLOCKED 5 – wait 6 - notify 7 9 5 notify All RUNNING 7 – sleep 4 8 – sleep interval expires DEAD 9 – issue I/O 1 10 – I/O completion.

Automi a stati finiti

Automi a stati finiti = sistemi di transizioni.

A = (S, E, T, s₀)

S = insieme di stati.

E = insieme delle etichette (nomi di azioni).

T = insieme delle transizioni di stato.

T ⊆ S x E x S.

Stato di partenza, stato d’arrivo.

s₀ ∈ S = stato iniziale.

0 1 a b c 2 d 3 5 b a 4 b a d b c.

Tracce di esecuzione: 1 5.

Un processo ha uno stato (che determina quali operazioni sono eseguibili) ed esegue delle operazioni (che determinano il comportamento di un processo).

Processi sequenziali

Rappresentati come Automi a stati finiti.

LTS (Labelled Transition Systems).

Stato “globale”.

Azione atomica.

Transizione di stato.

Es.: la lampadina accendi 0 = spento 0 1 1 = acceso spegni.

Es.: una lampadina che può guastarsi 0 = spento accendi guasto 1 = acceso 0 1 2 2 = guasto (si guasta solo quando la lampadina è accesa) spegni.

FSP (Finite State Processes): un linguaggio per specificare processi sequenziali e sistemi di processi sequenziali interagenti.

Elementi principali di FSP per la specifica dei processi:

• Alfabeto: insieme delle azioni atomiche che un processo può eseguire o alle quali “partecipa”.
• Strutture di controllo: operatori che esprimono il comportamento di un processo.
• Sequenza (action prefix) a -> P.
• Selezione (scelta non deterministica) | 2.
• Ricorsione (solo in coda: iterazione).
• STOP, ERROR => sono processi.
• Composizione parallela ||.

Es.: le lampadine.

L = (accendi -> (spegni -> L)).

L è il nome del processo. La lampadina può eseguire solo l’azione “accendi”; in seguito può eseguire “spegni”, poi può comportarsi come all’inizio.

LG = (accendi -> LA), chiamata di processo.

LA = (spegni -> LG | guasto -> STOP).

Lezione 2

Finite state processes (FSP)

Action prefix a -> P.

Scelta a -> P | b -> Q.

Ricorsione (il processo esegue a, poi b, e poi ricomincia).

P = (a -> b -> P).

STOP, ERROR.

STOP corrisponde alla terminazione per stato finale di un’esecuzione corretta; ERROR corrisponde alla terminazione di un’esecuzione errata.

Es.: P = (a -> (b -> (c -> STOP ))).

P = (a -> STOP | b -> STOP).

P = (a -> Q), ricorsione indiretta.

Q = (b -> P).

Composizione parallela

Composizione parallela: ||S = (P || Q).

Es.: lampadina.

L = (accendi -> spegni -> L).

La = (acA -> spA -> La).

Lb = (acB -> spB -> Lb).

||S = (La || Lb).

L La Lb accendi acA acB 0 0 1 0 1 1 spegni spA spB.

Per costruire ||S devo operare con il prodotto fra stati di La e Lb.

2.

Quanti stati ha ||S? La e Lb hanno 2 stati, quindi 2² = 4 stati.

acA 0 0 1 0 spA acB spB spB acB acA 1 1 0 1 spA.

Alfabeto = insieme di tutti i nomi delle azioni che compaiono nella specifica del processo.

Alfabeto(La) = {acA, spA}.

Alfabeto(Lb) = {acB, spB}.

Alfabeto(S) = {acA, spA, acB, spB}.

Azioni locali = azioni che un processo compie da solo.

Es.: comportamento di due bambini.

A = (compitiA -> gioco -> dormeA -> A). compitiA.

B = (compitiB -> gioco -> dormeB -> B). 0 1.

||S = (A || B). gioco dormeA 2 compitiA 0 0 1 0 dormeB dormeA compitiB compitiB compitiA dormeB 0 1 1 1 1 2 dormeA 2 1 gioco compitiA compitiB 2 0 2 2 0 2 dormeB dormeA.

Es.: P = (a -> b -> c -> STOP).

Q = (d -> b -> e -> STOP).

||S = (P || Q). a b c 0 1 2 3 d e b 0 1 2 3.

3.

||S = 2 processi, 3 stati, quindi 2³ = 8 stati.

a c 0 0 1 0 2 2 3 2 b e e d d 0 1 1 1 2 3 3 3 a c.

Thread in Java

THREAD -> è una classe “attiva”, quindi in Java si traduce in un thread.

La = (acA -> spA -> La).

Lb = (acB -> spB -> Lb).

||S = (La || Lb).

public class La extends Thread {
private boolean accesa;
private int id;
public La(int id) {
this.id = id;
accesa = false;
}
private void acA() { private -> perché è un metodo eseguito solo all’interno di questa classe
accesa = true;
System.out.println(id + “ accesa”);
}
public void run() { -> cosa fa il thread una volta invocato
while(true) {
acA(); ciclo infinito
spA();
}
}
}

public static void main(String[] args) {
La lamp = new La(1);
lamp.start(); run -> provoca la chiamata del metodo e si interrompe immediatamente
}

main che crea 2 lampadine:

La lamp_1 = new La(1);

La lamp_2 = new La(2);

lamp_1.start(); lamp_1, -> viene avviato il thread corrispondente all’oggetto il secondo.

lamp_2.start(); lamp_2 oggetto però non aspetta che l’altro finisca la sua esecuzione, quindi andranno contemporaneamente.

Se prima (con una sola lampadina) l’output era:

accesa, spenta, accesa, spenta, …

ora l’esecuzione contemporanea è:

accesa, accesa, spenta, spenta, accesa, spenta, accesa, …

(gli stati si mischiano, e non sempre in modo omogeneo).

Lezione 3

Es.: Due tornelli ogni volta che passa un visitatore girano e incrementano una variabile.

T = (rileva -> inc -> T).

V = (inc -> stampa -> V).

||A = (a:T || b:T).

a, b = identificatori; “:” è un operatore che trasforma un processo, quindi si ottiene:

T = (a.rileva -> a.inc -> a.T)

a.rileva 0 0 1 0 a.inc b.rileva b.inc b.inc b.rileva a.rileva 0 1 1 1 a.inc.

V = (a.inc -> stampa -> V | b.inc -> stampa -> V).

a.inc a.inc 0 1 b.inc stampa 0 1 b.inc stampa stampa 2.

||S = (A || V).

||S = (a:T || b:T || V).

Nell’implementazione in Java, per ogni processo distinto nel modello ci sarà una classe.

Ogni azione si traduce in metodo.

public class Tornello extends Thread {
private Var var;
private int id;
public Tornello(int id) {
this.id = id;
}
public void rileva() {
System.out.println(“Rilevata una persona”);
}
public void run() {
while(true) {
rileva();
Var.inc(id);
}
}
}

public class Var {
private int valore;
Object lock = new Object();
public Var() { valore = 0; }
synchronized(lock) interferenza -> si utilizza
public void inc(int id) {
synchronized(lock) { per regolare l’accesso a una sezione critica
valore = valore+1;
System.out.println(id + “ “ + valore);
}
}
}

si può scrivere anche:

public synchronized void inc(…){ … }

public static void main(String[] args) {
Var v = new Var();
Tornello a = new Tornello(1);
Tornello b = new Tornello(2);
a.start();
b.start();
}

Lezione 4

Produttore – Consumatore

Es.: Produttore – Consumatore.

3 processi:

• Processo Produttore (produce risorse e le deposita nel buffer).
• Processo Consumatore (preleva le risorse dal buffer e le elabora).
• Processo Buffer (riceve risorse dal produttore e le dà al consumatore, coordina le azioni).

P = (produce -> deposita -> P).

C = (preleva -> elabora -> C).

B = (deposita -> preleva -> B).

||S = (P || C || B). produce produce deposita preleva B.

Bvuoto = (deposita -> Bpieno), Bpieno = (preleva -> Bvuoto).

Bisogna stabilire le condizioni per la quale il buffer esegue “deposita” o “preleva” in base al suo stato:

B[0] = buffer vuoto, B[1] = buffer pieno -> stato iniziale del processo.

B = B[0],

B[i:0..1] = ( when i == 0 deposita -> B[1] | when i == 1 preleva -> B[0] ).

guardia = indica quando l’azione può essere svolta.

nuovo valore del parametro.

i = nome del parametro; 0..1 = possibili valori del parametro.

Produttore e Consumatore sono due processi “attivi”, quindi in Java si tradurranno in thread; Buffer invece è un processo “passivo” (le azioni che contiene infatti appartengono a Produttore e Consumatore), quindi non è un thread.

public class Produttore extends Thread {
private Buffer buffer;
private Object item;
private Object produce() { … }
public void run() {
while(true) {
item = produce();
buffer.deposita(item);
}
}
}

public class Consumatore extends Thread {
private Buffer buffer;
private Object item;
private void elabora(Object item) { … }
public void run() {
while(true) {
item = buffer.preleva();
elabora(item);
}
}
}

public class Buffer {
private Object item;
private boolean pieno = false;
synchronized(lock) {
wait(); Il thread che sta eseguendo queste azioni viene sospeso.
}
Uno dei thread sospesi sull’oggetto lock si “risveglia”, synchronized(lock) { lock diventa pronto.
notify() notifyAll() invece risveglia tutti i thread sospesi.
}

public void deposita(Object x) {
synchronized(this) {
if(pieno) condizione per la quale non si possono più depositare
wait(); oggetti (dovranno rimanere in attesa finché non si libera
item = x; spazio nel buffer)
pieno = true;
notify(); si risveglia un processo in attesa
}
}

public Object preleva() {
synchronized(this) {
if(!pieno)
wait();
pieno = false;
notify();
return item;
}
}
}

Lezione 5

Posteggio con numero di posti limitato

Es.: Posteggio con numero di posti limitato, numero automobili > numero posti.

-> costante che indica il numero di macchine.

const N = 6

-> costante che indica il numero di posti.

const M = 3

AUTO = (arriva -> parte -> AUTO). arriva parte.

||A = (a[1..N] : AUTO). a.2.arriva a.2.parte.

POSTEGGIO = P[0],

P[occ:0..M] = ( when occ < M arriva -> P[occ+1] | when occ > 0 parte -> P[occ-1] ).

||S = (A || POSTEGGIO). arriva arriva arriva POSTEGGIO: 0 1 2 3 parte parte parte.

Bisognerebbe modificare il nome delle azioni del processo POSTEGGIO per indicare azioni differenti.

Tre possibili soluzioni:

• Aggiungendo il prefisso a[1..N].
• Modificando il nome delle azioni.
• Rinominando tutte le azioni “arriva” e “parte” in “a.1.arriva”, “a.1.parte”, e così via.

Soluzione 1

Modifichiamo S in:

||S = (A || a[1..N]::POSTEGGIO).

“::” è un operatore che permette di aggiungere il prefisso “a*1..N+” a tutte le azioni del processo POSTEGGIO.

a.6.arriva…

a.2.arriva

POSTEGGIO: a.1.arriva a[1..6].arriva a[1..6].arriva 0 1 2 3 a.1.parte a[1..6].parte a[1..6].parte.

a.2.parte…

a.6.parte

Soluzione 2

Modifichiamo il processo POSTEGGIO in:

POSTEGGIO