Programmazione concorrente in Java

Programmazione concorrente in Java da materiale di Carlo Ghezzi e Alfredo Mo8a Parallelismo = “mul<tasking” •  Possiamo scrivere un programma in cui diverse a?vità (task) evolvono in parallelo da un punto di vista ﬁsico o logico •  Massimo parallelismo ﬁsico –  Ogni a?vità parallela ha a disposizione un processore ﬁsico •  Altrimen< vengono eseguite da processori condivi –  Secondo modalità decise da uno scheduler, in generale non controllabile dal programmatore Mul<tasking su singolo processore •  Approccio –  Processore esegue un task –  Passa velocemente a un altro –  So8o il governo dello scheduler •  Il processore sembra lavorare sui diversi task concorrentemente •  Passaggio da un task all’altro nei momen< di ina?vità o per esaurimento della ﬁnestra temporale (“<me sharing”) Caso 1: Task singolo Caso 2: Due task 4
Mul<tasking a livello di processi •  Processo –  Programma eseguibile caricato in memoria –  Ha un suo spazio di indirizzi (variabili e stru8ure da< in memoria) –  Ogni processo esegue un diverso programma –  I processi comunicano via SO, ﬁle, rete –  Può contenere più thread Mul<tasking a livello di thread •  Thread è un’a?vità logica sequenziale •  Un thread condivide lo spazio di indirizzi 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 light-‐weight Thread in Java -‐ metodo 1 Classe Thread start
avvia il thread (eseguendo il metodo run)
join
un thread si me8e in a8esa della terminazione del thread su cui è invocato
isAlive
controlla se il thread è vivo (in esecuzione, in a8esa o bloccato)
sleep(int ms)
sospende l’esecuzione del thread
yield
sospende l’esecuzione del thread corrente
Esempio Thread in Java – metodo 2 •  La classe Thread in realtà implementa un’interfaccia chiamata Runnable •  L’interfaccia Runnable deﬁnisce un solo metodo run che con<ene il codice del thread •  Su ciò si basa un modo alterna<vo Thread in Java—metodo 2 •  metodo più generale si usa se si deve ereditare da qualche classe Da< condivisi •  Può essere necessario imporre che certe sequenze di operazioni che accedono a da< condivisi vengano eseguite dai task in mutua esclusione class ContoCorrente {
private float saldo;
public ContoCorrente (float saldoIniz)
{ saldo = saldoIniz; }
public void deposito (float soldi) { saldo += soldi; }
public void prelievo (float soldi) { saldo -= soldi; }
…
Interferenza •  Fenomeno causato dall’interleaving di operazioni di due o più thread –  Le8ura di y –  Esecuzione espressione –  Scri8ura in x •  L’esecuzione concorrente di x+=y e x-‐=y può avere uno dei seguen< eﬀe? –  incrementare x di y –  lasciare x immutata –  decrementare x di y 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” Altro problema di concorrenza •  A volte, oltre a voler l’atomicità di certe sequenze, si vogliono imporre cer< ordinamen< nell’esecuzione di operazioni •  Per esempio, che l’operazione A eseguita da un thread venga eseguita prima dell’operazione B di un altro thread •  Di solito ciò deriva dal fa8o di voler garan<re certe proprietà di consistenza della memoria (stato della computazione) Come rendere i metodi "atomici" •  La parola chiave "synchronized” applicata a metodi o blocchi di codice class ContoCorrente {
private float saldo;
public ContoCorrente (float saldoIniz)
{ saldo = saldoIniz; }
public synchronized void deposito (float soldi) { saldo += soldi; }
public synchronized void prelievo (float soldi) { saldo -= soldi; }
…
Esempio public class SynchronizedCounter {!
private int c = 0;!
!
public synchronized void increment() {!
c++;!
}!
!
public synchronized void decrement() {!
c--;!
}!
!
public synchronized int value() {!
return c;!
}!
}
Metodi synchronized •  Java associa un intrinsic lock a ciascun ogge8o –  I lock operano a livello di thread •  Quando il metodo synchronized viene invocato –  se nessun metodo synchronized è in esecuzione, l'ogge8o viene bloccato (locked) e quindi il metodo viene eseguito –  se l'ogge8o è bloccato, il task chiamante viene sospeso ﬁno a quando il task bloccante libera il lock Commen< sul lock •  Diverse invocazioni di metodi synchronized sullo stesso ogge8o non sono sogge8e a interleaving –  quanto un thread X esegue un metodo synchronized di un ogge8o, i thread che eseguono invocazioni di metodi synchronized sullo stesso ogge8o vengono sospesi ﬁno a che X termina l’esecuzione del metodo •  I costru8ori non possono essere synchronized –  Solo il thread che crea l’ogge8o deve avere accesso ad esso mentre viene creato –  A8enzione a non far uscire un riferimento prematuro all’ogge8o •  Eventuali da< ﬁnal (che non possono essere modiﬁca< dopo la creazione) possono essere le? con metodi non synchronized Ulteriori commen< sul lock •  L’intrinsic lock viene acquisito automa<camente all’invocazione del metodo synchronized e rilasciato al ritorno (sia normale che eccezionale che da uncaught excep<on) •  Se il metodo synchronized fosse sta<c –  Il thread acquisisce l’intrinsic lock per il Class object associato alla classe –  Pertanto l’accesso ai campi sta<c è controllato da un lock speciale, diverso da quelli associa< alle istanze della classe Synchronized statements •  Devono speciﬁcare l’ogge8o a cui applicare il lock public void addName(String name) {
synchronized(this) {
lastName = name;
nameCount++;
}
nameList.add(name);
} •  Si rilascia il lock all’ogge8o prima di invocare un metodo che potrebbe a sua volta richiedere di a8endere il rilascio di un lock Controllo “ﬁne” della concorrenza •  Esempio: classe con due campi che non vengono modiﬁca< mai insieme public class XXX {!
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++;!
}!
}!
}!
!
!
Alcune regole pra<che •  Usare lock per la modiﬁca degli a8ribu< dell’ogge8o –  Per essere cer< di avere uno stato consistente •  Usare lock per l’accesso a campi dell’ogge8o probabilmente modiﬁca< –  Per evitare di leggere valori “vecchi” •  Non usare lock quando si invoca un metodo su altri ogge? –  Per evitare deadlock •  Non c`è bisogno di lock per accedere alle par< “stateless” di un metodo Liveness •  È una proprietà molto importante in pra<ca •  Signiﬁca che un’applicazione concorrente viene eseguita entro acce8abili limi< di tempo •  Le situazioni da evitare a8raverso un’a8enta proge8azione sono –  deadlock, starva<on e livelock Deadlock •  Due o più thread sono blocca< per sempre, in a8esa 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 ﬁno a che l’amico res<tuisce l’inchino •  Problema: inchino reciproco allo stesso tempo class Friend {!
private final String name;!
public Friend(String name) {!
this.name = name;!
}!
public String getName() {!
return this.name;!
}!
public synchronized void bow(Friend bower) {!
System.out.format("%s: %s"!
+ " has bowed to me!%n", !
this.name, bower.getName());!
bower.bowBack(this);!
}!
public synchronized void bowBack(Friend bower) {!
System.out.format("%s: %s"!
+ " has bowed back to me!%n",!
this.name, bower.getName());!
}!
}
final Friend anna = new Friend(“Anna”);!
final Friend giacomo = new Friend("Giacomo");!
new Thread(new Runnable() {public void run() {anna.bow(giacomo);}}).start();!
new Thread(new Runnable() {public void run() {giacomo.bow(anna);}}).start();
Starva<on •  Situazione in cui un thread ha diﬃcoltà ad accedere a una risorsa condivisa e quindi ha diﬃcoltà a procedere •  Esempio: –  Task “greedy” che molto frequentemente invocano metodi lunghi ritardano costantemente il thread, o uno scheduler che usa priorità cede sempre precedenza ai task greedy Livelock •  Errore di proge8o che genera una sequenza ciclica di operazioni inu<li ai ﬁni dell’eﬀe?vo avanzamento della computazione •  Esempio: –  La sequenza inﬁnita di “vada prima lei” Guarded blocks •  Come evitare il prelievo se il conto va in rosso? class ContoCorrente {
private float saldo;
…
synchronized public void prelievo (float soldi) {
while (saldo-soldi<0) wait();
saldo -= soldi;
}
…
rilascia il lock sull'ogge8o e sospende il task Come risvegliare un task in wait? class ContoCorrente {
private float saldo;
public ContoCorrente (float saldoIniz)
{ saldo = saldoIniz; }
synchronized public void deposito (float soldi) {
saldo += soldi;
risveglia un task sospeso in
notify();
wait, se esiste nondeterminismo
}
synchronized public void prelievo (float soldi) {
while (saldo-soldi<0) wait();
saldo -= soldi;
Attenzione! }
…
if (saldo-soldi<0) wait();
Non è sufficiente
Esempio: una coda FIFO condivisa •  Operazione di inserimento di elemento –  sospende task se coda piena •  while (codaPiena()) wait(); –  al termine •  no<fy(); •  Operazione di estrazione di elemento –  sospende task se coda vuota •  while (codaVuota()) wait(); –  al termine •  no<fy(); invece notifyAll risveglia tutti…
MA uno solo guadagna il lock
Schema produ8ore/consumatore public synchronized String take() {!
// Wait until message is!
// available.!
while (empty) {!
try {!
wait();!
} catch (InterruptedException e) {}!
}!
// Toggle status.!
empty = true;!
public synchronized void put(String message) {!
// Notify producer that!
// Wait until message has!
// status has changed.!
// been retrieved.!
notifyAll();!
while (!empty) {!
return message;!
try { !
}
wait();!
} catch (InterruptedException e) {}!
}!
// Toggle status.!
empty = false;!
// Store message.!
this.message = message;!
// Notify consumer that status!
// has changed.!
notifyAll();!
}
Ciclo di vita di un thread born
start
notify
notifyAll
ready
scheduler
wait
running
I/O
lock
waiting
dead
fine I/O
fine lock
blocked
Problemi con ogge? mutabili public class SynchronizedRGB {!
public void set(int red,!
!
int green,int blue, String name) {!
// Values must be between 0 and 255.!
check(red, green, blue);!
private int red;!
synchronized (this) {!
private int green;!
this.red = red;!
private int blue;!
this.green = green;!
private String name;!
this.blue = blue;!
!
this.name = name;!
private void check(int red,!
}!
int green,int blue) {!
}!
if (red < 0 || red > 255!
!
|| green < 0 || green > 255!
public synchronized int getRGB() {!
|| blue < 0 || blue > 255) {!
return ((red << 16) | !
throw new IllegalArgumentException();!
(green << 8) | blue);!
}!
}!
}!
!
!
public synchronized String getName(){!
public SynchronizedRGB(int red,!
return name;!
int green, int blue, String name) {!
}!
check(red, green, blue);!
!
this.red = red;!
public synchronized void invert() {!
this.green = green;!
red = 255 - red;!
this.blue = blue;!
green = 255 - green;!
this.name = name;!
blue = 255 - blue;!
}
name = "Inverse of " + name;!
}!
}
Spiegazione return ((red << 16) | (green << 8) | blue);
//calcola un intero che rappresenta il colore con un intero
//costruito facendo manipolazione delle rappresentazioni binarie
//mediante bitwise inclusive or| (4|1 dà 5)
// << X esegue shift a sinistra di X posizioni
SynchronizedRGB color = new SynchronizedRGB(0, 0, 0, "Pitch Black");
...
int myColorInt = color.getRGB();
//Statement 1
String myColorName = color.getName(); //Statement 2
•  Se un altro thread invoca color.set dopo Statement 1 ma prima di Statement 2, il valore di myColorInt non corrisponde al valore di myColorName •  Il problema sorge perché l’ogge8o è mutabile Come creare ogge? immutabili •  Non fornire metodi "se8er" •  Deﬁnire tu? gli a8ribu< di istanza ﬁnal e private •  Non consen<re alle so8oclassi di fare override dei metodi –  Dichiarando la classe ﬁnal oppure dichiarando il costru8ore private e costruendo gli ogge? mediante factory method •  Se gli a8ribu< di istanza hanno riferimen< a ogge? mutabili, non consen<re la loro modiﬁca –  Non fornire metodi che modiﬁcano ogge? mutabili –  Non fare sharing di ref a ogge? mutabili –  Non salvare riferimen< a ogge? esterni mutabili passa< al costru8ore, se necessario fare copie e salvare riferimen< alle copie –  Inoltre creare copie degli ogge? interni mutabili se necessario per evitare di res<tuire gli originali a8raverso i metodi Esempio ImmutableRGB •  Ci sono due metodi se8er –  Il primo (set) trasforma arbitrariamente l’ogge8o e non avrà alcun corrispe?vo nella versione immutabile –  Il secondo, invert, viene ada8ato creando un nuovo ogge8o invece di modiﬁcare l’ogge8o corrente •  Tu? gli a8ribu< sono già private; vengono ulteriormente qualiﬁca< ﬁnal •  La classe viene qualiﬁcata ﬁnal •  Un solo a8ributo fa riferimento a un ogge8o, e l’ogge8o è immutabile –  Non è quindi necessario far nulla per salvaguardare lo stato di eventuali ogge? mutabili contenu< Soluzione ImmutableRGB final public class ImmutableRGB {!
!
// Values must be between 0 and 255.!
final private int red;!
final private int green;!
public int getRGB() {!
final private int blue;!
return ((red << 16) | !
final private String name;!
(green << 8) | blue);!
!
}!
private void check(int red,!
!
int green,!
public String getName() {!
int blue) {!
return name;!
if (red < 0 || red > 255!
}!
|| green < 0 || green > 255!
!
|| blue < 0 || blue > 255) {!
public ImmutableRGB invert() {!
throw new IllegalArgumentException();!
return new ImmutableRGB(255 - red,!
}!
255 - green,!
}!
255 - blue,!
!
"Inverse of " + name);!
public ImmutableRGB(int red,!
}!
int green,!
}
int blue,!
String name) {!
check(red, green, blue);!
this.red = red;!
this.green = green;!
this.blue = blue;!
this.name = name;!
}
Conce? avanza< •  Finora abbiamo visto i conce? di base, che però risultano inadegua< a un’eﬀe?va programmazione concorrente •  Vediamo ora conce? introdo? con Java 5.0, in par<colare nei packages java.u<l.concurrent.* –  Ogge? “lock” –  Esecutori –  Collezioni concorren< –  Variabili atomiche Ogge? “lock”-‐ Lock objects •  Il codice synchronized deﬁnisce un caso elementare di lock (implicito), ma meccanismi più soﬁs<ca< sono forni< dal package java.u<l.concurrent.locks •  Un lock, deﬁnito dall’interfaccia Lock, può essere acquisito da un solo thread, come nel caso degli “implicit lock” associa< a codice synchronized •  È però possibile ri<rarsi dalla richiesta di lock –  il metodo trylock esce dal lock se questo non è disponibile (immediatamente o dopo un <meout da speciﬁcare) –  il metodo lockInterrup<bly consente il ri<ro se un altro thread manda un interrupt prima che il lock sia acquisito Anna, Giacomo e l’inchino (creazione dei thread) 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();!
}
Anna, Giacomo e l’inchino (classe BowLoop) class BowLoop implements Runnable {!
private Friend bower;!
private Friend bowee;!
!
public BowLoop(Friend bower, Friend bowee) {!
this.bower = bower;!
this.bowee = bowee;!
}!
!
public void run() {!
Random random = new Random();!
for (;;) {!
try {!
Thread.sleep(random.nextInt(10));!
} catch (InterruptedException e) {}!
bowee.bow(bower);!
}!
}!
}
Anna, Giacomo e l’inchino (classe Friend) class Friend {!
res<tuisce vero se riesce ad acquisire …………………!
il lock di ciascuno dei due a8ori che consentono public void bow(Friend bower) {!
all’uno di inchinarsi e all’altro di res<tuire l’inchino
if (impendingBow(bower)) {!
try {!
System.out.format("%s: %s has” + " bowed to me!%n", !
this.name, bower.getName());!
bower.bowBack(this);!
} finally {!
lock.unlock();!
bower.lock.unlock();!
}!
} else {!
System.out.format("%s: %s started"!
+ " to bow to me, but saw that"!
+ " I was already bowing to"!
+ " him.%n”, this.name, bower.getName());!
}!
}!
public void bowBack(Friend bower) {!
System.out.format("%s: %s has" +!
" bowed back to me!%n",!
this.name, bower.getName());!
}!
}
Anna, Giacomo e l’inchino (Classe Friend -‐ altri de8agli) class Friend {!
…………….!
public boolean impendingBow(Friend bower) {!
Boolean myLock = false;!
Boolean yourLock = false;!
try {!
myLock = lock.tryLock();!
yourLock = bower.lock.tryLock();!
} finally {!
if (! (myLock && yourLock)) {!
if (myLock) {!
lock.unlock();!
}!
if (yourLock) {!
bower.lock.unlock();!
}!
}!
}!
return myLock && yourLock;!
}!
Codice completo import java.util.concurrent.locks.Lock;!
import java.util.concurrent.locks.ReentrantLock;!
import java.util.Random;!
public class Safelock {!
static class Friend {!
private final String name;!
private final Lock lock = new ReentrantLock();!
!
public Friend(String name) {!
this.name = name;!
}!
public String getName() {!
return this.name;!
}!
public boolean impendingBow(Friend bower) {!
Boolean myLock = false;!
Boolean yourLock = false;!
try {!
myLock = lock.tryLock();!
yourLock = bower.lock.tryLock();!
} finally {!
if (! (myLock && yourLock)) {!
if (myLock) {!
lock.unlock();!
}!
if (yourLock) {!
bower.lock.unlock();!
}!
}!
}!
return myLock && yourLock;!
}
Codice completo public void bow(Friend bower) {!
if (impendingBow(bower)) {!
try {!
System.out.format("%s: %s has"!
+ " bowed to me!%n", !
this.name, bower.getName());!
bower.bowBack(this);!
} finally {!
lock.unlock();!
bower.lock.unlock();!
}!
} else {!
System.out.format("%s: %s started"!
+ " to bow to me, but saw that"!
+ " I was already bowing to"!
+ " him.%n",!
this.name, bower.getName());!
}!
}!
!
public void bowBack(Friend bower) {!
System.out.format("%s: %s has" +!
" bowed back to me!%n",!
this.name, bower.getName());!
}!
}
static class BowLoop implements Runnable {!
private Friend bower;!
private Friend bowee;!
public BowLoop(Friend bower, Friend bowee) {!
this.bower = bower;!
this.bowee = bowee;!
}!
!
public void run() {!
Random random = new Random();!
for (;;) {!
try {!
Thread.sleep(random.nextInt(10));!
} catch (InterruptedException e) {}!
bowee.bow(bower);!
}!
}!
}!
!
!
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();!
}!
}
Codice completo !
Esecutori •  Gli strumen< ﬁnora disponibili impongono una stre8a relazione tra il compito che deve essere eseguito da un thread (deﬁnito dall’ogge8o Runnable) e il thread stesso, deﬁnito dall’ogge8o Thread •  I due conce? possono essere tenu< dis<n< in applicazioni complesse, mediante –  interfacce Executor –  thread pools –  fork/join •  Gli esecutori sono predeﬁni< e consentono una ges<one eﬃciente che riduce il pesante overhead dovuto alla ges<one dei thread Interfacce Executors •  Il package java.u<l.concurrent deﬁnisce 3 interfacce –  Executor –  ExecutorService (estende Executor) –  ScheduledExecutorService (estende ExecutorService) •  U<lizzo di Executor –  Se r è un Runnable ed e è un Executor, invece di (new Thread(r)).start(); facciamo e.execute(r); –  evitando l’overhead dovuto alla creazione degli ogge? thread Implementazione di Executor •  Le implementazioni dell’interfaccia Executor usano thread pools, ovvero thread che esistono al di fuori di Runnable •  Un esempio comune è un executor che usa un “ﬁxed thread pool”, che viene creato chiamando il factory method newFixedThreadPool della classe java.u<l.concurrent.Executors •  I task sono invia< al pool a8raverso una coda Cenno al Fork/Join framework •  È un’implementazione di ExecutorService u<le nel caso di più processori •  Consente di distribuire task a elemen< di un thread pool secondo questo schema if (il mio task è abbastanza piccolo)!
eseguo direttamente!
else!
spezzo il mio task in due task!
invoco i due pezzi e attendo il risultato
Collezioni concorren< •  Il package java.u<l.concurrent include estensioni a collezioni di Java, quali –  BlockingQueue •  stru8ura da< FIFO che blocca o dà <meout se si cerca di inserire in coda piena o estrarre da coda vuota –  ConcurrentMap •  consente in maniera atomica di eliminare/modiﬁcare una coppia chiave-‐valore solo se chiave presente e aggiungere chiave-‐valore solo se assente Variabili atomiche •  Il package java.u<l.atomic deﬁnisce classi che supportano operazioni atomiche su singole variabili •  Esse posseggono tu8e metodi get e set che si comportano come le8ura e scri8ura delle corrisponden< variabili non atomiche •  È disponibile anche un’operazione compareAndSet Esempio class Counter {!
class SynchronizedCounter {!
private int c = 0;!
private int c = 0;!
!
!
public void increment() {!
public synchronized void increment() {!
c++;!
c++;!
}!
}!
!
!
public void decrement() {!
public synchronized void decrement() {!
c--;!
c--;!
}!
}!
!
!
public int value() {!
public synchronized int value() {!
return c;!
return c;!
}!
}!
!
!
}!
}
•  Come evitare problemi di interferenza? Ogge? atomici •  Consentono di evitare i problemi di liveness che possono essere causa< dall’uso dei metodi synchronized import java.util.concurrent.atomic.AtomicInteger;!
!
class AtomicCounter {!
private AtomicInteger c = new AtomicInteger(0);!
!
public void increment() {!
c.incrementAndGet();!
}!
!
public void decrement() {!
c.decrementAndGet();!
}!
!
public int value() {!
return c.get();!
}

Download Report