Paradigmi Concorrenti - Appunti

Paradigmi Concorrenti

Lezione 1

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à 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: 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 completation

Automi a stati finiti = sistemi di transizioni

A = (S, E, T, s ) S = insieme di stati

0 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 badbc

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)

o stato “globale”

o azione atomica

o 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) . 3

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: ||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

00 10

spA

acB spB spB acB

acA 11

01 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. 4

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

00 10 dormeB

dormeA compitiB compitiB

compitiA dormeB

01 11 12

dormeA

21 gioco compitiA

compitiB 20 22 02

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

00 10 22 32

b e e

d d

01 11 23 33

a c

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”);

} 5

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). 6

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

00 10

a.inc

b.rileva b.inc b.inc b.rileva

a.rileva

01 11

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);

}

}

} 7

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();

} 8

Lezione 4

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

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 nuovo valore del

può essere svolta 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);

}

}

} 9

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;

}

}

} 10

Lezione 5

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:

1 - aggiungendo il prefisso a[1..N]

2 - modificando il nome delle azioni

3 - 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