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
:
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:
Caricare il valore corrente di
c
;Incrementare il valore recuperato di
1
;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:
Thread A: Recupera c;
Thread B: Recupera c;
Thread A: Incrementa il valore recuperato; risultato รจ 1;
Thread B: decrementa il valore recuperato; risultato รจ -1;
Thread A: Immagazzina il risultato in c; c ora รจ 1;
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
:
Una prima implementazione della classe contatore:
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
.
L'output di piรน esecuzioni:
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:
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:
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:
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:
Da notare che il blocco synchronized prende un oggetto - in questo caso tsc
- come un parametro. La sintassi per il synchronized
statement รจ:
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):
leggi contoA in una variabile locale cA;
leggi contoB in una variabile locale cB;
scrivi in contoA il valore cA + importo;
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):
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
Il risultato corretto dovrebbe essere sempre contoA=130, contoB=170 e totale=300.
Le sequenze S1 e S2 corrispondono alle esecuzioni sequenziali dei due tread t1<t2 e t2<t1, quindi danno sicuramente risultati corretti.
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.
L'output di alcune esecuzioni successive del programma:
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:
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:
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
Il metodo run del secondo thread controllerร il valore di terminate
frequentemente, e terminerร quando il valore di terminate
diventerร true
:
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.
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:
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.
L'output di alcune esecuzioni:
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

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
Last updated