Thread interference

Ora che abbiamo visto come รจ semplice creare i thread e alcune primitive della classe Thread per controllare il flusso di esecuzione dei thread (sleep(), join(), interrupt()), vediamo ora dove ci sono i possibili problemi utilizzando i thread.

Consideriamo la semplice classe chiamata Counter:

class Counter {
    private int c = 0;

    public void increment() {
        c++;
    }

    public void decrement() {
        c--;
    }

    public int value() {
        return c;
    }

}

La classe Counter ha un metodo increment() che aggiunge 1 alla variabile intera c, il metodo decrement() invece sottrae 1 alla stessa variabile. Tutto molto semplice. Tuttavia se una variabile di tipo Counter รจ riferita da piรน thread, l'interferenza tra i thread puรฒ generare comportamenti inaspettati eseguendo le operazioni di increment e decrement sulla variabile.

L'interferenza si verifica quando due operazioni, essendo eseguite da thread differenti, ma che agiscono sulla stessa variabile, agiscono intervallandosi.

Questo significa che le due operazioni in realtร  consistono di molti step, e le sequenze degli step si intervallano dando risultati imprevisti.

Non sembra possibile che operazioni su una variabile di tipo Counter si possano intervallare, poichรฉ le due operazioni su c sono degli unici, semplici statement. Tuttavia, anche semplici statement possono essere tradotti in molti step dalla virtual machine.

Ad esempio il semplice statement di increment c++ puรฒ essere decomposto in 3 step:

  1. Caricare il valore corrente di c;

  2. Incrementare il valore recuperato di 1;

  3. Immagazzinare nella variabile c il valore incrementato;

L'espressione c-- puรฒ essere decomposta nello stesso modo, solo che il secondo step esegue un decremento invece di un incremento.

Supponiamo che Thread A invoca increment e contemporaneamente Thread B invoca decrement. Se il valore iniziale di c รจ 0, l'intervallarsi delle azioni potrebbe essere:

  1. Thread A: Recupera c;

  2. Thread B: Recupera c;

  3. Thread A: Incrementa il valore recuperato; risultato รจ 1;

  4. Thread B: decrementa il valore recuperato; risultato รจ -1;

  5. Thread A: Immagazzina il risultato in c; c ora รจ 1;

  6. Thread B: Immagazzina il risultato in c; c ora รจ -1;

Il risultato di Thread A รจ sovrascritto da Thread B. Questa sequenza di esecuzione non รจ l'unica possibile, potrebbe invece accadere che sia perso invece il risultato di Thread B o potrebbe esserci l'esecuzione di increment e decrement senza intervallarsi e questo porterebbe al risultato corretto. Il problema che quando si lavora con i thread e si accede a variabili condivise su cui si fanno operazioni si vede che il comportamento non รจ deterministico (diversamente a quando abbiamo un programma con un solo flusso di esecuzione in cui le operazioni sono eseguite in sequenza senza possibilitร  di intervallarsi).

Abbiamo visto un esempio di race condition cioรจ l'accesso concorrente a variabili condivise dette anche sequenza critiche: le race condition avvengono in applicazioni multi-thread, quando piรน di un thread accedono a una risorsa o piรน risorse condivise e tramite una serie di istruzioni, eseguono delle modifiche contemporaneamente. Da notare che non ci sono problemi se piรน thread accedono in lettura a una risorsa condivisa, fino a quando qualche thread non tenta di cambiare il valore. Vedremo che per ovviare ai problemi delle race condition si fa in modo che certe sequenze di istruzioni vengono eseguite da un thread alla volta, si dice, in mutua esclusione.

Come esempio di race condition (piรน thread che accedono a una variabile condivisa) vediamo l'esempio di una variabile di tipo contatore che viene incrementata da piรน thread. La classe Incrementer di tipo thread esegue l'incremento della variabile di tipo Counter:

package contatore.v1;

public class Incrementer extends Thread {

    private final Counter counter;
    private final int incrementValue;

    public Incrementer(Counter counter, int incrementValue) {
        this.counter = counter;
        this.incrementValue = incrementValue;
    }

    public void run() {
        for (int i = 0; i < incrementValue; i++) {
            counter.increment();
        }
    }



}

Una prima implementazione della classe contatore:

package contatore.v1;

public class Counter {

    private int counter;

    public void increment() {
        counter++;
    }

    public int getValue() {
        return counter;
    }
}

L'applicazione contatore.v1.TestUnsafeCounter mandata in esecuzione fa vedere un caso di race condition: instanza due oggetti di tipo Incrementer che in modo concorrente eseguono l'incremento della variabile condivis adi tipo Counter.

package contatore.v1;

import java.util.Locale;

public class TestUnsafeCounter {

    public static void main(String[] args) throws InterruptedException {
        long startTime = System.currentTimeMillis();

        Counter counter = new Counter();

        int incrementValue1 = 200_000_000;
        int incrementValue2 = 100_000_000;

        Incrementer incrementer1 =
                new Incrementer(counter, incrementValue1);

        Incrementer incrementer2 =
                new Incrementer(counter, incrementValue2);

        incrementer1.start();
        incrementer2.start();

        incrementer1.join();
        incrementer2.join();

        int counterValue = counter.getValue();

        long timeElapsed = System.currentTimeMillis() - startTime;

        System.out.format(Locale.ITALIAN, "SUM VALUE: %,d - SHOULD BE: %,d\n",
                counterValue,
                (incrementValue1 + incrementValue2));

        int difference = incrementValue1 + incrementValue2 - counterValue;

        double percent = ((0.0 + difference) /
                (incrementValue1 + incrementValue2)) * 100;

        System.out.format(Locale.ITALIAN,
                "DEFFERENCE: %,d - DIFF: %f %%\n", difference, percent);

        System.out.format(Locale.ITALIAN,
                "FINISHED Counter UNSAFE, elapsed time: %,d ms\n",
                timeElapsed);
    }
}

L'output di piรน esecuzioni:

SUM VALUE: 299.889.741 - SHOULD BE: 300.000.000
DEFFERENCE: 110.259 - DIFF: 0,036753 %
FINISHED Counter UNSAFE, elapsed time: 15 ms
SUM VALUE: 299.754.709 - SHOULD BE: 300.000.000
DEFFERENCE: 245.291 - DIFF: 0,081764 %
FINISHED Counter UNSAFE, elapsed time: 54 ms
SUM VALUE: 299.859.355 - SHOULD BE: 300.000.000
DEFFERENCE: 140.645 - DIFF: 0,046882 %
FINISHED Counter UNSAFE, elapsed time: 32 ms

Ad ogni esecuzione i risultati sono diversi, ma comunque il risultato dell'incremento eseguito dai due thread non รจ quello che ci si aspetterebbe. Nel seguito capiremo come mai c'รจ questa differenza e che precauzioni adottare quando due o piรน thread accedono in modifica a una variabile condivisa.

Mutua esclusione con "synchronized"

E' piuttosto semplice programmare diversi thread per portare avanti task (attivitร ) completamente indipendenti.

La vera difficoltร  si ha quando devono interagire in qualche modo.

Un modo in cui i thread interagiscono รจ condividendo le risorse.

Quando due thread hanno bisogno di accedere alla stessa risorsa, come una variabile o una finestra sullo schermo, una certa attenzione deve essere presa perchรฉ non utilizzino la stessa risorsa allo stesso tempo.

Altrimenti la situazione potrebbe essere come questa: Immaginiamo diversi cuochi che condividono un misurino, e immaginiamo che il Cuoco A riempie il misurino con il latte, ma il Cuoco B gli prende il misurino prima che il Cuoco A possa svuotare il latte nella pentola. Ci deve essere un modo per il Cuoco A per reclamare l'utilizzo esclusivo del misurino mentre compie le due operazioni: Aggiungi-Latte-A-Misurino e Vuota-Misurino-Nella-Pentola.

Qualcosa di simile succede con i thread, anche con qualcosa di semplice come aggiungere uno a un contatore. Questo statement

count = count + 1

e in realtร  una sequenza di tre operazioni:

Step 1. Prendi il valore di count

Step 2. Aggiungi 1 al valore

Step 3. Salva il nuovo valore in count

Ammettiamo che ognuno di molti thread esegue questi step. Ricordiamo che รจ possibile che due thread siano in esecuzione allo stesso tempo, e anche se abbiamo un solo processore, รจ possibile per quel processore passare l'esecuzione da un thread a una altro (switch) in ogni momento. Ammettiamo che mentre il thread รจ tra lo Step 2 e 3, un altro thread inizia l'esecuzione della stessa sequenza di passi. Siccome il primo thread non ha ancora salvato il nuovo valore in count, il secondo thread legge il vecchio valore di count e aggiunge uno a quel vecchio valore. Entrambi i thread hanno calcolato lo stesso nuovo valore di count, e entrambi i thread ora vanno a salvare questo valore in count eseguendo lo Step 3. Dopo che i due thread hanno fatto cosรฌ, il valore di count risulta incrementato solo di 1 invece di 2!

Questo tipo di problema รจ chiamato race condition o accesso a una sequenza critica.

Questo accade quando un thread รจ nel mezzo di un'operazione multi-step, e un altro thread puรฒ cambiare un valore o una condizione sul quale il primo thread dipende. (Il primo thread รจ "in corsa" per completare tutti gli step prima di essere interrotta da un altro thread)

Un altro esempio di race condition puรฒ succedere in un if statement. Consideriamo il seguente statement, che ha lo scopo di evitare l'errore di divisione per zero:

if ( A != 0 ) {
    B = C / A;
} 

Supponiamo che questo codice รจ eseguito da alcuni thread. Se la variabile A รจ condivisa da uno o piรน thread, e se nulla รจ fatto per proteggere dalla race condition, allora รจ possibile che uno questi thread possa cambiare il valore di A portandolo a 0 nel frattempo che il primo thread ha controllato la condizione A != 0 e si appresta a eseguire la divisione. Questo significa potrebbe finire a dividere per zero, anche se ha controllato che A sia deversa da 0!

Per fissare il problema delle race condition, ci deve essere qualche modo per acquisire un accesso esclusivo a una risorsa condivisa. Questa non รจ una cosa semplice da implementare, ma Java dispone un modo semplice e di alto livello per ottenere l'accesso esclusivo. Questo รจ ottenuto tramite i metodi sincronizzati o i blocchi sincronizzati. Questi sono usati per proteggere una risorsa condivisa garantendo che un solo thread alla volta cercherร  di accedere alla risorsa.

La sincronizzazione in Java รจ solo tramite la mutua esclusione, ciรฒ significa che l'accesso esclusivo a una risorsa รจ garantito solo se ogni thread che desidera accedere a una risorsa condivisa utilizza la sincronizzazione.

La sincronizzazione รจ come un cuoco che lascia un avviso che dice, "Sto usando io il misurino". Questo darร  al cuoco l'utilizzo esclusivo del misurino, ma solo se tutti i cuochi sono d'accordo di controllare se c'รจ l'avviso prima di cercare di prendere il misurino.

Siccome l'argomento รจ difficile, iniziamo con un semplice esempio. Supponiamo che vogliamo evitare la race condition che accade quando abbiamo diversi thread e tutti vogliono aggiungere 1 a una variabile contatore. Noi possiamo fare questo definendo una classe per rappresentare un contatore e utilizzando metodi sincronizzati in quella classe.

Un metodo รจ dichiarato sincronizzato utilizzando la parola riservata synchronized come modificatore alla definizione del metodo:

package contatore.v2;

public class Counter {
    private int counter;

    public synchronized void increment() {
        counter++;
    }

    public synchronized int getValue() {
        return counter;
    }
}

Se tsc รจ di tipo Counter (ora rispetto alla prima versione di prima ha i metodi synchronized), allora ogni thread puรฒ chiamare tsc.increment() per aggiungere 1 al contatore in modo sicuro.

Il fatto che tsc.increment() รจ synchronized significa che solo un thread alla volta puรฒ eseguire questo metodo; una volta che un thread inizia l'esecuzione di questo metodo, รจ garantito che finirร  l'esecuzione senza che un altro thread possa cambiare il valore di tsc.counter nel frattempo.

Non c'รจ quindi possibilitร  di race condition. Notiamo che questa garanzia dipende dal fatto che counter รจ una variabile private. Questo fa si che ogni accesso a tsc.counter debba avvenire tramite i metodi synchronized che sono disponibili nella classe. Se counter fosse pubblica, sarebbe possibile per un thread bypassare la sincronizzazione, per esempio, facendo tsc.counter++. Questo permetterebbe il valore di counter mentre un altro thread รจ nel mezzo dell'esecuzione di tsc.increment().

Ricordiamoci che la sincronizzazione di per sรฉ, non garantisce l'accesso esclusivo; essa garantisce solo la mutua esclusione tra tutti i thread che sono sincronizzati.

Tuttavia, Counter anche se ha i metodi sinchronized non previene tutte le possibili race condition che potrebbero esserci quando utilizziamo una variabile di tipo Counter.

Consideriamo l'if statement:

if ( tsc.getValue() == 0 ) {
    doSomething();
}

dove doSomething() รจ qualche metodo che richiede il valore del contatore che sia zero. C'รจ ancora una race condition quรฌ, che accade se un secondo thread incrementa il contatore nel tempo in cui il primo thread testa che tsc.getValue() == 0 e il momento in cui esegue doSomething(). Il primo thread necessita l'accesso escusivo a tsc durante tutta l'esecuzione dell'if statement. (La sincronizzazione nella classe Counter da solo accesso esclusivo il tempo di esecuzione del test tsc.getValue().) Si puรฒ risolvere la race condition mettendo l'if statement in un blocco synchronized:

synchronized(tsc) {
    if ( tsc.getValue() == 0 )
        doSomething();
}

Da notare che il blocco synchronized prende un oggetto - in questo caso tsc - come un parametro. La sintassi per il synchronized statement รจ:

synchronized( โ€นobjectโ€บ  ) {
    โ€นstatementsโ€บ
}

In Java, la mutua esclusione รจ sempre associata con un oggetto; noi diciamo che la sincronizzazione รจ "su" quell'oggetto. Per esempio, if statement sopra รจ "sincronizzato su tcs." Un metodo d'istanza synchronized, come quelli nella classe Counter, รจ sincronizzato sull'oggetto che contiene i metodi d'istanza.

In effetti, aggiungere il modificatore synchronized alla definizione di un metodo d'istanza รจ praticamente equivalente a mettere il corpo del metodo in un blocco synchronized della forma synchronized(this) { ....... }. E' anche possibile avere metodi statici synchronized sull'oggetto speciale di tipo class che rappresenta la classe contenente il metodo statico.

La vera regola della sincronizzazione in Java รจ: Due thread non possono essere sincronizzati sullo stesso oggetto allo stesso tempo; cioรจ, essi non possono essere simultaneamente eseguire blocchi di codice che sono sincronizzati su quell'oggetto. Se un thread รจ sincronizzato su un oggetto, e un secondo thread cerca di sincronizzarsi sullo stesso oggetto, il secondo thread รจ costretto ad aspettare finchรฉ il primo thread non ha finito con quell'oggetto. Questo รจ implementato utilizzando qualcosa chiamato un synchronization lock. Ogni oggetto ha un synchronization lock, e quel lock puรฒ essere "tenuto" da un solo thread alla volta. Per entrare in un blocco synchronized o un metodo synchronized, un thread deve ottenere il lock associato all'oggetto. Se il lock รจ disponibile, allora il thread ottiene il lock e immediatamente comincia ad eseguire il codice sincronizzato. Esso rilascia il lock dopo che ha terminato di eseguire il codice sincronizzato.

Se Thread A cerca di ottenere un lock che รจ giร  tenuto da Thread B, allora Thread A allora deve aspettare finchรฉ il Thread B rilascia il lock. In effetti, Thread A sarร  messo in pausa, e non sarร  risvegliato finchรฉ il lock non diventa disponibile.

Esempio trasferimento fondi

Un tipico problema nella programmazione concorrente รจ legato alla necessitร  di garantire che alcune sequenze di istruzioni di due thread siano eseguite in maniera sequenziale tra loro.

Si consideri ad esempio il seguente problema: sono dati due conti bancari, contoA e contoB, e si vuole realizzare una funzione, che chiamiamo trasferisci(), che preleva un importo dal contoB e lo deposita sul contoA.

La struttura fondamentale della funzione possiamo immaginare che sia la seguente (si osservi che contoA e contoB devono essere considerati variabili globali e persistenti, tipicamente memorizzate in un file o in un database):

  1. leggi contoA in una variabile locale cA;

  2. leggi contoB in una variabile locale cB;

  3. scrivi in contoA il valore cA + importo;

  4. scrivi in contoB il valore cB - importo;

Si osservi che dopo l'esecuzione di tale funzione la somma dei due conti dovrร  essere invariata; una proprietร  di questo tipo รจ detta invariante della funzione.

Supponiamo ora che tale funzione sia invocata da un main() che riceve richieste di trasferimento tra i conti A e B (il tipico bonifico bancario) da diversi terminali. Per rendere piรน veloce il sistema, il main crea un diverso thread per ogni attivazione di funzione. I diversi thread eseguiranno quindi le 4 operazioni concorrentemente e saranno possibili molte sequenze di esecuzione diverse tra loro.

Per indicare una operazione all'interno di una sequenza di esecuzione introduciamo la seguente notazione:

ti.j indica l'operazione j svolta dal thread ti;

Con questa notazione possiamo indicare alcune delle possibili sequenze di esecuzione (ipotizziamo nei seguenti esempi che i thread siano 2):

S1) t1.1 < t1.2 < t1.3 < t1.4 < t2.1 < t2.2 < t2.3 < t2.4
S2) t2.1 < t2.2 < t2.3 < t2.4 < t1.1 < t1.2 < t1.3 < t1.4
S3) t1.1 < t1.2 < t1.3 < t2.1 < t2.2 < t2.3 < t2.4 < t1.4
...................

Esercizio 1. Determinare il risultato di queste esecuzioni, supponendo che i valori iniziali siano contoA=100 e contoB=200 e che i thread t1 e t2 trasferiscano rispettivamente gli importi 10 e 20.

Soluzione 1

  1. Il risultato corretto dovrebbe essere sempre contoA=130, contoB=170 e totale=300.

  2. Le sequenze S1 e S2 corrispondono alle esecuzioni sequenziali dei due tread t1<t2 e t2<t1, quindi danno sicuramente risultati corretti.

  3. Analizziamo ora la sequenza S3: si consideri l'effetto dell'esecuzione di ogni operazione svolta dai due thread, riportato nella seguente tabella (sono indicati solamente i cambiamenti di valore delle variabili)

Il risultato finale รจ contoA = 130, contoB = 190; inoltre l'invariante alla fine vale 130 + 190 = 320, quindi il risultato รจ errato.

Esercizio 2. determinare altre sequenze di esecuzione possibili e il loro risultato.

Sotto รจ mostrata una realizzazione in Java del programma descritto sopra; per semplicitร  i valori iniziali e gli importi trasferiti sono assegnati come costanti.

public class Banca {
   public int contoA;
   public int contoB;
   public Banca(int contoA, int contoB) {
       this.contoA = contoA;
       this.contoB = contoB;
   }
}
class TrasferimentoFondi extends Thread {
    private int valueToTransfer;
    private Banca banca;
    public TrasferimentoFondi(String name, Banca banca, int valueToTransfer) {
        super(name);
        this.banca = banca;
        this.valueToTransfer = valueToTransfer;
    }

    public void run() {

        try {
            Thread.sleep(10);
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }

        int contoLocalA = banca.contoA;  // step 1
        int contoLocalB = banca.contoB;  // step 2

        contoLocalA += valueToTransfer;
        contoLocalB -= valueToTransfer;

        banca.contoA = contoLocalA;     // step 3
        banca.contoB = contoLocalB;     // step 4

    }
}
public class GestoreConti {
    public static void main(String[] args) throws InterruptedException {

        // trasferire da contoB --> contoA;

        int transfer1 = 10;
        int transfer2 = 20;

        Banca banca = new Banca(100, 200);

        TrasferimentoFondi threadA = new TrasferimentoFondi("threadA", banca, transfer1);
        TrasferimentoFondi threadB = new TrasferimentoFondi("threadB", banca, transfer2);

        System.out.println("START CONTO A: " + banca.contoA + " - CONTO B: " + banca.contoB +
                ", TOTALE: " + (banca.contoA + banca.contoB));

        System.out.println("TRASFERIAMO " + transfer1 + " B --> A");
        System.out.println("TRASFERIAMO " + transfer2 + " B --> A");

        threadA.start();
        threadB.start();

        threadA.join();
        threadB.join();

        System.out.println("CONTO A: " + banca.contoA + " - CONTO B: " + banca.contoB +
                ", TOTALE: " + (banca.contoA + banca.contoB));
    }
}

L'output di alcune esecuzioni successive del programma:

START CONTO A: 100 - CONTO B: 200, TOTALE: 300 
TRASFERIAMO 10 B --> A 
TRASFERIAMO 20 B --> A 
CONTO A: 130 - CONTO B: 170, TOTALE: 300

START CONTO A: 100 - CONTO B: 200, TOTALE: 300 
TRASFERIAMO 10 B --> A 
TRASFERIAMO 20 B --> A 
CONTO A: 110 - CONTO B: 180, TOTALE: 290

START CONTO A: 100 - CONTO B: 200, TOTALE: 300 
TRASFERIAMO 10 B --> A 
TRASFERIAMO 20 B --> A 
CONTO A: 110 - CONTO B: 170, TOTALE: 280

START CONTO A: 100 - CONTO B: 200, TOTALE: 300 
TRASFERIAMO 10 B --> A 
TRASFERIAMO 20 B --> A 
CONTO A: 120 - CONTO B: 170, TOTALE: 290

START CONTO A: 100 - CONTO B: 200, TOTALE: 300 
TRASFERIAMO 10 B --> A 
TRASFERIAMO 20 B --> A 
CONTO A: 110 - CONTO B: 190, TOTALE: 300

START CONTO A: 100 - CONTO B: 200, TOTALE: 300 
TRASFERIAMO 10 B --> A 
TRASFERIAMO 20 B --> A 
CONTO A: 120 - CONTO B: 180, TOTALE: 300

START CONTO A: 100 - CONTO B: 200, TOTALE: 300
TRASFERIAMO 10 B --> A
TRASFERIAMO 20 B --> A
CONTO A: 120 - CONTO B: 190, TOTALE: 310

START CONTO A: 100 - CONTO B: 200, TOTALE: 300
TRASFERIAMO 10 B --> A
TRASFERIAMO 20 B --> A
CONTO A: 120 - CONTO B: 190, TOTALE: 310

L'output corretto รจ solo quello con conto A = 130 e conto B = 170, gli altri non sono risultati corretti.

Esercizio 3. Per ogni risultato dell'output sopra del programma si determini almeno una sequenza di esecuzione che produce tale risultato.

***********************

Come semplice esempio di risorse condivise, ritorniamo sul problema del conteggio dei numeri primi. In questo caso, invece di avere ogni thread che esegue perfettamente la stessa attivitร , noi faremo qualche reale processamento parallelo. Il programma eseguirร  il conteggio dei numeri primi in un certo range di interi, e lo farร  dividendo il lavoro tra diversi thread. A ogni thread verrร  assegnato una parte di tutto l'intervallo di interi, e conterร  i numeri primi in quel suo intervallo. Alla fine della computazione, ogni thread aggiungerร  il proprio conteggio al totale dei numeri primi in tutto il range. La variabile che rappresenta il totale รจ condivisa tra tutti i thread, poichรฉ ogni thread deve aggiungere un numero al totale. Se ogni thread deve eseguire:

total = total + count;

allora c'รจ una (piccola) possibilitร  che due thread cercheranno di compiere questa operazione simultaneamente e il risultato potrebbe essere sbagliato. Per prevenire questa race condition, l'accesso a total deve essere sincronizzato. Nell'esempio utilizziamo un metodo synchronized per aggiungere i conteggi parziali al totale. Questo metodo รจ chiamato una volta da ogni thread:

synchronized private static void addToTotal(int x) {
    total = total + x;
    System.out.println(total + " primes found so far.");
}

Il codice sorgente del programma puรฒ essere trovato in ThreadTest2.java. Questo programma conteggia i numeri primi nel range 3000001 e 6000000. Il metodo main del programma crea tra 1 e 5 thread e assegna a ogni thread parte del lavoro. Esso spetta che ogni thread termini utilizzando il metodo join() come visto sopra. Esso poi riporta il totale dei numeri primi trovati con il tempo impiegato. Da notare che join() รจ necessaria qui, perchรฉ non avrebbe senso riportare il totale dei numeri primi prima che tutti i thread abbiano finito il loro conteggio. Se eseguiamo il programma su un computer multiprocessore, esso dovrebbe metterci meno tempo di esecuzione utilizzando piรน thread che con un thread solo.

Le variabili volatile

La sincronizzazione รจ solo un metodo per controllare la comunicazione tra i thread. Vedremo in seguito anche altri metodi. Pero ora vediamo due altre tecniche: le variabili volatie e le variabili atomiche.

In generale, i thread comunicano attraverso la condivisione di variabili a accedendo alla variabili attraverso metodi sincronizzati o blocchi sincronizzati. Tuttavia, รจ piuttosto costoso computazionalmente, e un utilizzo eccessivo dovrebbe essere evitato. Cosรฌ in alcuni casi, puรฒ aver senso per i thread accedere a una variabile condivisa senza la sincronizzazione.

Tuttavia, un problema sottile si verifica quando il valore di una variabile condivisa รจ settata da un thread e utilizzata in un altro. A causa del modo in cui i thread sono implementati in Java, il secondo thread potrebbe non vedere immediatamente il valore cambiato della variabile. Cioรจ, รจ possibile che un thread continuerร  a vedere il vecchio valore della variabile condivisa ancora per qualche tempo dopo che รจ stata modificata da un altro thread. Questo perchรฉ i thread possono utilizzare i valori in cache delle variabili condivise. Cioรจ, ogni thread piรฒ tenere una copia locale dei dati condivisi. Quando un thread cambia il valore di una variabile condivisa, le copie locali nelle cache degli altri thread non sono immediatamente aggiornate, cosรฌ gli atri thread potrebbero, per breve periodo, vedere ancora il vecchio valore.

E' sicuro utilizzare una variabile condivisa in un metodo sincronizzato o statement, se e solo se l'accesso a quella variabile รจ sincronizzato, utilizzando lo steso oggetto di sincronizzazione in tutti i casi. Piรน precisamente, qualsiasi thread che accede a una variabile all'interno di codice sincronizzato รจ garantito che veda i cambiamenti fatti dagli altri thread, se e solo se i cambiamenti sono fatti in codice che รจ sincronizzato sullo stesso oggetto.

E' possibile utilizzare una variabile condivisa in modo sicuro fuori da codice sincronizzato, ma in questo caso la variabile deve essere dichiarata come volatile. La keyword volatile รจ un modificatore che puรฒ essere aggiunto a una dichiarazione di variabile, ad esempio:

private volatile int count;

Se una variabile รจ dichiarata volatile, nessun thread terrร  una copia locale della variabile nella sua cache. Invece il thread utilizzerร  la versione ufficiale, principale della variabile. Questo significa che ogni cambiamento che รจ fatto a questa variabile sarร  immediatamente visibile a tutti gli altri thread. Questo fa si che sia sicuro per i thread riverirsi a una variabile di tipo volatile condivisa anche fuori da codice sincronizzato. L'accesso a variabili volatili รจ meno efficiente che l'accesso a variabili non volatili, ma piรน efficiente che l'utilizzo della sincronizzazione. (Ricordiamo, tuttavia, che l'utilizzo di una variabile di tipo volatile non risolvono le race condition che accadono quando ad esempio il valore di una variabile รจ condivisa. L'operazione di incremento puรฒ essere comunque interrotta da un altro thread).

Quando il modificatore volatile รจ applicato a una variabile di tipo oggetto, solo la variabile stessa รจ dichiarata di essere volatile, non il contenuto dell'oggetto a cui la variabile si riferisce. Per questa ragione, volatile รจ utilizzata principalmente per variabili di tipo primitivo o tipi immutabili come le String.

Un esempio tipico dell'utilizzo di una variabile volatile รจ di inviare un segnale da un thread a un altro per dire al secondo di terminare. I due thread potrebbero condividere una variabile

volatile boolean terminate = false;

Il metodo run del secondo thread controllerร  il valore di terminate frequentemente, e terminerร  quando il valore di terminate diventerร  true:

public void run() {
    while (terminate == false) {
        // Do some work
    }
}

Questo thread sarร  in esecuzione finchรฉ qualche altro thread setterร  il valore di terminate a true. Qualcosa di questo tipo รจ realmente l'unico modo pulito per un thread di provocare la fine di un altro thread.

(A proposito, ci si potrebbe sorprendere perchรฉ i thread dovrebbero utilizzare la copia locale in cache delle variabili visto che la cosa sembra complicare le cose senza necessitร . Il caching รจ permesso a causa della struttura dei computer multiprocessore. In molti computer multiprocessore c'รจ una memoria locale che รจ direttamente collegata al processore. Una cache del thread puรฒ essere immagazzinata nella memoria locale del processore su cui il thread รจ in esecuzione. L'accesso a questa memoria locale รจ molto piรน veloce che l'accesso alla memoria principale che รจ condivisa da tutti i processori, cosรฌ รจ piรน efficiente per un thread utilizzare la copia locale di una variabile condivisa piuttosto della "copia master" che รจ memorizzata nella memoria principale.)

Le variabili atomiche

Il problema con uno statement come count = count + 1 nella programmazione parallela รจ che sono necessari diversi step per eseguile lo statement. Lo statement รจ solamente eseguito correttamente se questi step sono completati senza interruzioni.

Un' operazione atomica รจ qualcosa che non puรฒ essere interrotta. E' una operazione di tipo tutto-o-niente. Non puรฒ essere completata parzialmente. Molti computer hanno operazioni che sono atomiche a livello di linguaggio macchina. Per esempio, ci potrebbe essere una istruzione del linguaggio macchina che automaticamente incrementa il valore in una zona di memoria. Questa istruzione potrebbe essere utilizzata senza paura della race condition.

Java ha il package java.util.concurrent.atomic che implementano operazioni atomiche su alcuni semplici tipi di variabili.

private static AtomicInteger total = new AtominInteger();

Il total รจ creato con il valore iniziale di zero. Quando un thread vuole aggiungere un valore a total, puรฒ utilizzare il metodo total.addAndGet(x), che aggiunge x al totale e ritorna il nuovo valore di total dopo che x รจ stato aggiunto. Questa รจ un'operazione atomica, che non puรฒ essere interrotta, cosรฌ che noi possiamo essere sicuri che il valore sarร  corretto al termine dell'operazione.

L'esempio ThreadTest3.java รจ una piccola variazione di ThreadTest2.java che utilizza AtomicInteger invece della sincronizzazione per aggiungere in modo sicuro valori da parte di thread differenti.

AtomicInteger ha metodi simili per aggiungere uno al totale e sottrarre uno al totale: total.incrementAndGet() e total.decrementAndGet(). Il metodo total.getAndSet(x) setta il totale a x e ritorna il valore precedente che x sostituisce. Tutte queste operazioni sono eseguite in modo atomico (o perchรฉ utilizzano istruzioni atomiche a linguaggio macchina o perchรฉ utilizzano la sincronizzazione internamente).

L'utilizzo di una variabile atomica non risolve automaticamente tutte le race condition che ci possono essere con quella variabile. Per esempio, nel codice:

int currentTotal = total.addAndGet(x);
System.out.println("Current total is " + currentTotal)

E' possibile che nel momento in cui l'output statement รจ eseguito, il totale sia modificato da un altro thread cosรฌ che currentTotal non รจ piรน il valore corrente di total!

I Deadlock

La sincronizzazione puรฒ aiutare a prevenire le race condition, ma introduce la possibilitร  di un altro tipo di errore, il deadlock o stallo. Un deadlock avviene quando un thread continua ad aspettare una risorsa che non gli arriverร  mai.

In una cucina, un deadlock puรฒ succedere se due cuochi vogliono contemporaneamente misurare una tazza di latte. Il primo cuoco prende il misurino e il secondo cuoco prende il latte. Il primo cuoco ha bisogno del latte, ma non puรฒ averlo perchรฉ ce l'ha il secondo cuoco. Il secondo cuoco ha bisogno del misurino, ma non lo puรฒ ottenere perchรฉ ce l'ha il primo.

Nessun cuoco puรฒ continuare e niente di piรน puรฒ essere fatto. Questo รจ il deadlock. Esattamente la stessa cosa puรฒ succedere in un programma, per esempio se ci sono due thread (come i due cuochi) entrambi dei quali deve ottenere i lock su gli stessi due oggetti (come il latte e il misurino) prima che possano procedere. I deadlock possono capitare facilmente a meno che grande attenzione non รจ presa per evitarli.

La situazione piรน elementare di deadlock si crea quando due thread t1 e t2 bloccano due risorse A e B e raggiungono una situazione nella quale t1 ha bloccato A e attende di bloccare B mentre t2 ha bloccato B e attende di bloccare A.

Un programma che opera in questo modo รจ mostrato sotto. I due thread eseguono progressivamente il lock su obj1 e obj2, ma procedono in ordine inverso.

E' evidente che un deadlock puรฒ verificarsi se t1 acquisisce il lock ad A e t2 il lock a B prima che t1 acquisisca il lock a B.

Esercizio: Determinare una sequenza che porta al deadlock.

class LockAThenB extends Thread {

    private Object obj1;
    private Object obj2;

    public LockAThenB(String nameThread, Object obj1, Object obj2){
        super(nameThread);
        this.obj1 = obj1;
        this.obj2 = obj2;
    }

    public void run() {

        synchronized(obj1) {
            System.out.println(Thread.currentThread().getName() + " - PRESO LOCK A");

            synchronized(obj2) {
                System.out.println(Thread.currentThread().getName() + " - PRESO LOCK B");
            }

        }

        System.out.println(Thread.currentThread().getName() + " - FINITO");
    }
}
class LockBThenA extends Thread {

    private Object obj1;
    private Object obj2;

    public LockBThenA(String nameThread, Object obj1, Object obj2){
        super(nameThread);
        this.obj1 = obj1;
        this.obj2 = obj2;
    }

    public void run() {

        synchronized(obj2) {
            System.out.println(Thread.currentThread().getName() + " - PRESO LOCK B");

            synchronized(obj1) {
                System.out.println(Thread.currentThread().getName() + " - PRESO LOCK A");
            }
        }

        System.out.println(Thread.currentThread().getName() + " - FINITO");
    }

}
public class Main {

    public static void main(String[] args) throws InterruptedException {
        Object obj1 = new Object();
        Object obj2 = new Object();

        LockAThenB t1 = new LockAThenB("threadLockAThenB", obj1, obj2);
        LockBThenA t2 = new LockBThenA("threadLockBThenA", obj1, obj2);

        t1.start();
        t2.start();

        t1.join();
        t2.join();

        System.out.println("FINITA ESECUZIONE");
    }
}

L'output di alcune esecuzioni:

threadLockBThenA - PRESO LOCK B
threadLockAThenB - PRESO LOCK A
threadLockAThenB - PRESO LOCK A
threadLockBThenA - PRESO LOCK B

In tutte e due i casi si arriva a una situazione di deadlock (stallo) ed รจ necessario terminare il programma dall'esterno.

Una situazione di questo genere puรฒ essere rappresentata con un grafo di accesso alla risorse come quello di Figura 1 (a), da interpretare nel modo seguente:

  • i rettangoli rappresentano le attivitร  o thread,

  • i cerchi rappresentano le risorse (sequenze critiche),

  • una freccia da un thread a una risorsa indica che il thread รจ in attesa di bloccare la risorsa

  • una freccia da una risorsa a un thread indica che la risorsa รจ stata bloccata dal thread

Figura 1

Possiamo semplificare il grafo di accesso alle risorse sostituendo la sequenza "ti richiede la risorsa X bloccata da tj" con un'unica freccia che interpretiamo come "ti attende tj" e otteniamo un grafo di attesa come quello in Figura 1 (b).

La situazione di deadlock รจ rappresentata dall'esistenza di un ciclo in un grado di attesa.

Le situazioni di deadlock possono coinvolgere piรน di 2 thread, come mostrato dal grafo di attesa di Figura 2, dove esiste un ciclo che coinvolge 4 thread.

Nella scrittura di programmi concorrenti รจ necessario tener conto del rischio di deadlock e prevenire la possibilitร  che si verifichi. In base all'esempio precedente, utilizzando i lock il rischio di deadlock esiste se:

  • due o piรน thread acquisiscono accesso a piรน di una risorsa con lock;

  • l'odine in cui i thread bloccano le risorse con lock รจ diverso;

Esempi riassuntivi

Esempio incremento contatore

Esempio calcolo dei numeri primi

Esempio deadlock

Last updated