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.

GitHub - checksound/EsempioTrasferimentoContoGitHub

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

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