Programmazione

concorrente

COURTESY OF PROF. LUCIANO BARESI.

 Parallelismo = “multitasking”

• Possiamo scrivere un programma in cui

diverse attività (task) evolvono in parallelo
• Parallelismo fisico
– Ogni attività parallela ha a disposizione un
processore fisico
• Processori condivisi
– Secondo modalità decise da uno scheduler non
controllabile dal programmatore

COURTESY OF PROF. LUCIANO BARESI.

 Multitasking su singolo processore

• Processore esegue i diversi task sotto il

controllo dello scheduler
• Il processore sembra lavorare sui diversi
task concorrentemente
• Il passaggio avviene
– Nei momenti di inattività
– Per esaurimento della finestra temporale (time
sharing)

COURTESY OF PROF. LUCIANO BARESI.

 Task singolo
o doppio

COURTESY OF PROF. LUCIANO BARESI.

 Processo

• Ha un suo spazio di indirizzi (variabili e

strutture dati in memoria)
• Ogni processo esegue un diverso
programma
• I processi comunicano via memoria
condivisa, file, rete
• Può contenere più thread

COURTESY OF PROF. LUCIANO BARESI.

 Thread

• Attività logica sequenziale

• Spazio di indirizzi condiviso con gli altri
thread del processo e comunica via variabili
condivise
• Ha un suo contesto di esecuzione (program
counter, variabili locali)
• Si parla spesso di processo “leggero”

COURTESY OF PROF. LUCIANO BARESI.

 Metodo 1
public class MyThread extends Thread {
private String message;

public MyThread(String m) {message = m;}

public void run() {
for (int r=0; r<20; r++)
[Link](message);
}
}

public class ProvaThread {

public static void main(String[] args) {
MyThread t1, t2;

t1 = new MyThread("primo thread");

t2 = new MyThread("secondo thread");

[Link]();
[Link]();
}
COURTESY OF PROF. LUCIANO BARESI. }
 Classe Thread

start avvia il thread (eseguendo il metodo run)

mette in attesa il thread in esecuzione fino a quando il

join
thread su cui è stato invocato il metodo join() non termina

controlla se il thread è vivo (in esecuzione, in attesa o

isAlive
bloccato)

sleep(int ms) sospende l’esecuzione del thread

mette temporaneamente in pausa il thread corrente e

yield
consente ad altri thread in attesa di essere eseguiti

COURTESY OF PROF. LUCIANO BARESI.

class A extends Thread {
public void run() {
for (int i=0; i<=5; i++) [Link]("From Thread A: i= "+i);
[Link]("Exit from A");
}
} Esempio
class B extends Thread {
public void run() {
for (int j=0; j<=5; j++) [Link]("From Thread B: j= "+j);
[Link]("Exit from B");
}
}

class C extends Thread {

public void run() {
for (int k=0; k<=5; k++) [Link]("From Thread C: k= "+k);
[Link]("Exit from C");
}
}

public class ProvaThread {

public static void main(String[] args) {
new A().start();
new B().start();
new C().start();
}
}
 Possibili esecuzioni

COURTESY OF PROF. LUCIANO BARESI.

 Metodo 2

• La classe Thread implementa l’interfaccia

Runnable
• Runnable definisce un solo metodo run che
contiene il codice del thread

COURTESY OF PROF. LUCIANO BARESI.

 Metodo 2
public class MyThread implements Runnable {
private String message;

public MyThread(String m) {message = m;}

public void run() {

for (int r=0; r<20; r++) [Link](message);
}
}

public class ProvaThread {

public static void main(String[] args) {
Thread t1, t2;
MyThread r1, r2;

r1 = new MyThread("primo thread");

r2 = new MyThread("secondo thread");
t1 = new Thread(r1);
t2 = new Thread(r2);

[Link]();
[Link]();
}
}

COURTESY OF PROF. LUCIANO BARESI.

 Stile funzionale

public class ProvaThread {

public static void main(String[] args) {
Runnable r1 = () -> {for (int r=0; r<20; r++)
[Link]("primo thread");};
Runnable r2 = () -> {for (int r=0; r<20; r++)
[Link]("secondo thread");};

new Thread(r1).start();
new Thread(r2).start();
}
}

COURTESY OF PROF. LUCIANO BARESI.

 Quale metodo utilizzare?

• Thread
– Più intuitivo, permette di istanziare un solo
oggetto
– Poco flessibile
• Runnable
– Permette di avere classi che estendono altre
classi
– Esistono meccanismi più avanzati per la
schedulazione che preferiscono oggetti di tipo
Runnable
– È un metodo più articolato

COURTESY OF PROF. LUCIANO BARESI.

 Dati condivisi

• Può essere necessario imporre che certe

sequenze di operazioni che accedono a dati
condivisi vengano eseguite dai task in mutua
esclusione
class ContoCorrente {
private float saldo;
public ContoCorrente(float saldoI){
saldo=saldoI;
}
public void deposito(float soldi){
saldo += soldi;
}
public void prelievo (float soldi){
saldo -=soldi;
}
...
COURTESY OF PROF. LUCIANO BARESI.
 Interferenza

• Fenomeno causato dall’interazione di

operazioni di due o più thread
• Esecuzione concorrente di x+=y e x-=y

COURTESY OF PROF. LUCIANO BARESI.

 Sequenze “atomiche”

• Generalizzazione del problema

– a volte si vuole che certe sequenze di istruzioni
vengano eseguite in isolamento, senza
interleaving con istruzioni di altre sequenze
parallele che altri thread potrebbero eseguire
– si parla di “sequenze atomiche”

COURTESY OF PROF. LUCIANO BARESI.

 Operazioni non
Operazioni nonatomiche
atomiche
Saldo iniziale = 100
Thread1 Thread2
deposito(50) prelievo(50)
read(saldo) -> 100
read(saldo) -> 100
sum(50+100) -> 150
sub(100-50) -> 50
write(saldo) -> 50
write(saldo) -> 150

Saldo finale = 150

COURTESY OF PROF. LUCIANO BARESI.

 Operazioni atomiche
Operazioni atomiche
Saldo iniziale = 100
Thread1 Thread2
deposito(50) prelievo(50)
read(saldo) -> 100
sum(50+100) -> 150
write(saldo) -> 150
read(saldo) -> 150
sub(150-50) -> 100
write(saldo) -> 100

Saldo finale = 100

COURTESY OF PROF. LUCIANO BARESI.

 synchronized
class ContoCorrente {
private float saldo;

public ContoCorrente(float saldoI){

saldo = saldoI;
}
public synchronized void deposito(float soldi){
saldo += soldi;
}
public synchronized void prelievo(float soldi){
saldo -= soldi;
}
...

COURTESY OF PROF. LUCIANO BARESI.

 Esempio

public class SynchronizedCounter {

private int c = 0;

public synchronized void increment() {

c++;
}
public synchronized void decrement() {
c--;
}
public synchronized int value() {
return c;
}
}

COURTESY OF PROF. LUCIANO BARESI.

 Metodi synchronized

• Java associa un lock a ciascun oggetto

– Solo un thread alla volta può eseguire il codice
dell’oggetto
• Quando il metodo synchronized viene
invocato
– Se nessun metodo synchronized è in esecuzione,
l'oggetto viene acquisito (locked) e quindi il
metodo viene eseguito
– Se l'oggetto è acquisito, il task chiamante viene
sospeso e messo in coda fino a quando il task
bloccante libera il lock

COURTESY OF PROF. LUCIANO BARESI.

 Metodi synchronized (II)

• Quando un metodo synchronized viene

invocato da un altro metodo synchronized
sullo stesso oggetto, il thread chiamante non
deve competere per il lock, in quanto già
acquisito durante l’invocazione del primo
metodo (reentrant lock)
• L’accesso mutuamente esclusivo vale solo
per i metodi dichiarati synchronized
– L’accesso attraverso gli altri metodi può avvenire
anche mentre un thread ha acquisito il lock

COURTESY OF PROF. LUCIANO BARESI.

 Commenti sul lock

• Diverse invocazioni di metodi synchronized

sullo stesso oggetto non sono soggette a
interleaving
• I costruttori non possono essere
synchronized
– Solo il thread che crea l’oggetto deve avere
accesso ad esso mentre viene creato
• Eventuali dati final possono essere letti con
metodi non synchronized
– I dati sono comunque in sola lettura e non
possono essere modificati

COURTESY OF PROF. LUCIANO BARESI.

 Ulteriori commenti sul lock

• L’intrinsic lock viene acquisito

automaticamente all’invocazione del metodo
synchronized e rilasciato al ritorno
• Se il metodo synchronized fosse static
– Il thread acquisisce l’intrinsic lock per il Class
object associato alla classe
– Pertanto l’accesso ai campi static è controllato da
un lock speciale, diverso da quelli associati alle
istanze della classe

COURTESY OF PROF. LUCIANO BARESI.

 Synchronized statements

• Devono specificare l’oggetto a cui applicare

il lock
• Si rilascia il lock all’oggetto prima di invocare
un metodo che potrebbe a sua volta
richiedere di attendere il rilascio di un lock

public void addName(String name) {

synchronized(this) {
lastName = name;
nameCount++;
}
[Link](name);
}

COURTESY OF PROF. LUCIANO BARESI.

 Blocco synchronized

• Per controllare l’accesso concorrente a

porzioni di codice con una granularità più
fine del metodo
– Più grande è la porzione di codice sincronizzata,
minore sarà il parallelismo
– È possibile impiegare il blocco synchronized (obj)
{codice critico}
• Il lock viene acquisito per l’esecuzione del
blocco e non per l’intero metodo

COURTESY OF PROF. LUCIANO BARESI.

 Controllo “fine” della concorrenza

public class TestBlock {

private long c1 = 0;
private long c2 = 0;
private Object lock1 = new Object();
private Object lock2 = new Object();

public void inc1() {

synchronized(lock1) {c1++;}
}

public void inc2() {

synchronized(lock2) {c2++;}
}
}

COURTESY OF PROF. LUCIANO BARESI.

 Alcune regole pratiche

• Usare lock per la modifica degli attributi

dell’oggetto
– Per essere certi di avere uno stato consistente
• Usare lock per l’accesso a campi
dell’oggetto probabilmente modificati
– Per evitare di leggere valori “vecchi”
• Non usare lock quando si invoca un metodo
su altri oggetti
– Per evitare deadlock
• Non c’è bisogno di lock per accedere alle
parti “stateless” di un metodo

COURTESY OF PROF. LUCIANO BARESI.

 Altro problema di concorrenza

• Ordinamenti particolari nell’esecuzione di

operazioni
• Per esempio, l’operazione A eseguita da un
thread deve essere sempre eseguita prima
dell’operazione B di un altro thread
• Di solito ciò deriva dal fatto di voler garantire
certe proprietà di consistenza dei dati

COURTESY OF PROF. LUCIANO BARESI.

 Liveness

• È una proprietà molto importante in pratica

• Significa che un’applicazione concorrente
viene eseguita entro accettabili limiti di
tempo
• Le situazioni da evitare attraverso un’attenta
progettazione sono deadlock, starvation e
livelock

COURTESY OF PROF. LUCIANO BARESI.

 Deadlock

• Due o più thread sono bloccati per sempre,

in attesa l’uno dell’altro
– Esempio: Anna e Giacomo sono amici e credono
nel galateo, che dice che se una persona si
inchina a un amico, deve restare inchinata fino a
che l’amico restituisce l’inchino
– Problema: inchino reciproco allo stesso tempo

COURTESY OF PROF. LUCIANO BARESI.

 Starvation

• Situazione in cui un thread ha difficoltà ad

accedere a una risorsa condivisa e quindi ha
difficoltà a procedere
– Task “greedy” che molto frequentemente invocano
metodi lunghi ritardano costantemente il thread
– Uno scheduler che usa priorità dà sempre la
precedenza ai task greedy

COURTESY OF PROF. LUCIANO BARESI.

 Livelock

• Errore di progetto che genera una sequenza

ciclica di operazioni inutili ai fini dell’effettivo
avanzamento della computazione
– Esempio: la sequenza infinita di “vada prima lei”
– Diverso dal deadlock: la computazione non è
bloccata, qualcosa viene fatto ma mai niente di
utile

COURTESY OF PROF. LUCIANO BARESI.

public class Friend {
private final String name;

public Friend(String name) {

[Link] = name;
}
public String getName() {
return [Link];
}

public synchronized void bow(Friend bower) {

[Link]("%s: %s" + " has bowed to me!%n",
[Link], [Link]());
[Link](this);
}
public synchronized void bowBack(Friend bower) {
[Link]("%s: %s" + " has bowed back to me!%n",
[Link], [Link]());
}
}
public class ThreadTest {
public static void main(String[] args) {
final Friend anna = new Friend("Anna");
final Friend giacomo = new Friend("Giacomo");

new Thread(new Runnable() {

public void run() {[Link](giacomo);}
}).start();

new Thread(new Runnable() {

public void run() {[Link](anna);}
}).start();
}
}
 Precondizioni per metodi synchronized

• Come evitare il prelievo se il conto va in

rosso?
• Wait rilascia il lock e sospende il thread!
public class ContoCorrente {
private float saldo;

public synchronized void prelievo (float soldi) {

while (saldo-soldi<0) wait();
saldo -= soldi;
}
}

COURTESY OF PROF. LUCIANO BARESI.

 Come risvegliare un task in wait?
• Notify risveglia un task (scelto a caso) in
sospeso da wait su questo oggetto, se
esiste
public class ContoCorrente {
private float saldo;

public ContoCorrente (float saldoI) {

saldo = saldoI;
}

synchronized public void deposito (float soldi) {

saldo += soldi;
notify();
}

public synchronized void prelievo (float soldi) {

while (saldo-soldi < 0) wait();
saldo -= soldi;
COURTESY OF PROF. LUCIANO BARESI.
}
 Primitive di sincronizzazione
• Le primitive di sincronizzazione wait, notify e
notifyAll sono associate a ogni oggetto, in quanto
definite nella classe Object
• Consentono a un thread di sospendersi (wait), e di
risvegliare uno (notify) o tutti (notifyAll) i thread
sospesi
• Tali primitive operano sul lock associato
all’oggetto, pertanto possono essere invocate
all’interno di un thread solo dopo che esso ha
acquisito il lock
– Solo se all’interno di un blocco o metodo synchronized
– Se si invoca una di queste primitive su un oggetto per cui
non si è acquisito il lock si ottiene una
IllegalMonitorStateException

COURTESY OF PROF. LUCIANO BARESI.

 Esempio: una coda FIFO condivisa

• Operazione di inserimento di elemento

– Sospende task se coda piena
• while (codaPiena()) wait()
– Al termine
• notify()/notifyAll()
• Operazione di estrazione di elemento
– Sospende task se coda vuota
• while (codaVuota()) wait()
– Al termine
• notify()/notifyAll()

COURTESY OF PROF. LUCIANO BARESI.

public class FIFO {
private boolean empty;
private String message;

public synchronized String take() {

while (empty) {
try {wait();}
catch (InterruptedException e) {}
}
empty = true;
notifyAll();
return message;
}

public synchronized void put(String message) {

while (!empty) {
try {wait();}
catch (InterruptedException e) {}
}
empty = false;
[Link] = message;
notifyAll();
}
}
 Priorità e scheduling

• È possibile assegnare una priorità (1-10) ai

task (setPriority); default è 5
• Alcune piattaforme supportano il "time
slicing"
• In assenza, un thread viene eseguito fino al
completamento, a meno che non diventi
"blocked", "waiting" o "dead"
• Compito dello scheduler è mandare in
esecuzione il thread con priorità più alta

COURTESY OF PROF. LUCIANO BARESI.

 Ciclo di vita di un thread

born
start

notify ready
notifyAll
schedule
fine I/O
r fine lock
wait running I/O

waiting lock
blocked

dead

COURTESY OF PROF. LUCIANO BARESI.

 Concetti avanzati

• I concetti di base potrebbero essere

inadeguati a un’effettiva programmazione
concorrente
• Alcuni elementi avanzati di
[Link].*
– Oggetti “lock”
– Esecutori
– Collezioni concorrenti
– Variabili atomiche

COURTESY OF PROF. LUCIANO BARESI.

 Oggetti lock

• Il codice synchronized definisce un caso

elementare di lock (implicito), ma esistono
meccanismi più sofisticati
• Un lock, definito dall’interfaccia Lock, può
essere acquisito da un solo thread, come nel
caso degli “implicit lock” associati a codice
synchronized

COURTESY OF PROF. LUCIANO BARESI.

 ReentrantLock

• Simile al lock implicito fornito da

synchronized
• Funzionalità aggiuntive
– lock() acquisisce il lock in modo esplicito
– tryLock() acquisisce il lock solo se non è già in
possesso di un altro thread
– unlock() rilascia il lock

COURTESY OF PROF. LUCIANO BARESI.

 Classe BowLoop
import [Link];

public class BowLoop implements Runnable {

private Friend bower;
private Friend bowee;

public BowLoop(Friend bower, Friend bowee) {

[Link] = bower;
[Link] = bowee;
}

public void run() {

Random random = new Random();
for (;;) {
try {
[Link]([Link](10));
} catch (InterruptedException e) {}
[Link](bower);
}
}
}
COURTESY OF PROF. LUCIANO BARESI.
public class Friend {
private final String name;
private final Lock lock = new ReentrantLock();

public Friend(String name) {

[Link] = name;
}
public String getName() {
return [Link];
}
public boolean impendingBow(Friend bower) {
Boolean myLock = false;
Boolean yourLock = false;
try {
myLock = [Link]();
yourLock = [Link]();
} finally {
if (! (myLock && yourLock)) {
if (myLock) [Link]();
if (yourLock) [Link]();
}
}
return myLock && yourLock;
}
public void bow(Friend bower){
if (impendingBow(bower)){
try {
[Link]("%s: %s has” + " bowed to me!%n",
[Link], [Link]());
[Link](this);
} finally {
[Link]();
[Link]();
}
} else {
[Link]("%s: %s started” +
" to bow to me, but saw that” +
" I was already bowing to” +
" him.%n”, [Link], [Link]());
}
}

public void bowBack(Friend bower) {

[Link]("%s: %s has" + " bowed back to me!%n",
[Link], [Link]());
}
public class ThreadTest {
public static void main(String[] args) {
final Friend giacomo = new Friend("Giacomo");
final Friend anna = new Friend("Anna");

new Thread(new BowLoop(giacomo, anna)).start();

new Thread(new BowLoop(anna, giacomo)).start();
}
}
 Esecutori

• Gli strumenti finora disponibili impongono

una stretta relazione tra il compito che deve
essere eseguito da un thread (definito
dall’oggetto Runnable) e il thread stesso,
definito dall’oggetto Thread
• I due concetti possono essere tenuti distinti
in applicazioni complesse
– Gli esecutori sono predefiniti e consentono una
gestione efficiente che riduce il pesante overhead
dovuto alla gestione dei thread

COURTESY OF PROF. LUCIANO BARESI.

 Esecutori

• Sono una famiglia di classi che

implementano l’interfaccia ExecutorService
• Si utilizzano come metodo alternativo per
eseguire delle classi che implementano
Runnable (definite Task)
• Utilizzo di Executor
– void submit(Runnable task) – Schedula
l’esecuzione del task evitando l’overhead dovuto
alla creazione degli oggetti thread

COURTESY OF PROF. LUCIANO BARESI.

public class EsempioEsecutori {
public static void main(String[] args) {
ExecutorService esecutore = [Link](2);
[Link](new TaskCheImpiegaTreSecondi("TaskA"));
[Link](new TaskCheImpiegaTreSecondi("TaskB"));
[Link](new TaskCheImpiegaTreSecondi("TaskC"));
[Link]();
}
}

class TaskCheImpiegaTreSecondi implements Runnable {

private final String nome;

public TaskCheImpiegaTreSecondi(String nome) {

[Link] = nome;
}

@Override
public void run() {
[Link](nome + " avviato alle: " + new Date());
try {[Link](3000);}
catch (InterruptedException e) {}
[Link](nome + " completato alle: " + new Date());
}
}
 Risultato

COURTESY OF PROF. LUCIANO BARESI.

 Oggetti Thread-Safe

• Quando due thread diversi accedono a un

oggetto contemporaneamente, possono
verificarsi dei problemi come la comparsa di
eccezioni o altri comportamenti anomali
• Questo tipo di problemi è dovuto al non-
determinismo dell’esecuzione parallela di più
thread
• Un oggetto si definisce thread-safe quando
permette (da contratto) l’accesso
contemporaneo a più thread senza anomalie
(cioè l’oggetto offre soltanto operazioni
atomiche)

COURTESY OF PROF. LUCIANO BARESI.

 Collezioni concorrenti

• Il package [Link] include

estensioni a collezioni quali
• Interface BlockingQueue<E>
– Struttura dati FIFO che blocca o dà timeout se si
cerca di inserire in una coda piena o estrarre da
coda vuota
• Interface ConcurrentMap<K V>
– Consente in maniera atomica di eliminare/
modificare una coppia chiave-valore solo se
chiave presente e aggiungere chiave-valore solo
se assente

COURTESY OF PROF. LUCIANO BARESI.

,​
 Variabili atomiche

• Il package [Link]
definisce classi che supportano operazioni
atomiche su singole variabili
• Esse posseggono tutte metodi get e set che
si comportano come lettura e scrittura delle
corrispondenti variabili non atomiche

COURTESY OF PROF. LUCIANO BARESI.

 Oggetti atomici

• Consentono di evitare i problemi di liveness

che possono essere causati dall’uso dei
metodi synchronized
public class AtomicCounter {
private AtomicInteger c;

public void increment() {

[Link]();
}

public void decrement() {

[Link]();
}

public int value() {

return [Link]();
}
COURTESY OF PROF. LUCIANO BARESI. }