🔀Grafo Precedenze in Java

Thread Paralleli di Calcolo con Vincoli di Precedenza

🔵Livello Intermedio ☕Programmazione Concorrente in Java

🏠Home

🎦Video

🧰Notebook

apri il Notebook e apprendi con chat, quiz, flashcard e mappe concettuali

📖

Problema

Il problema da risolvere consiste nella realizzazione di un sistema in Java che esegua calcoli in modo concorrente, rispettando i vincoli di un grafo delle precedenze.

In un grafo delle precedenze, alcuni calcoli (nodi) non possono essere completati finché non sono disponibili i risultati di altri calcoli dai quali dipendono.

1) Il Problema e le Dipendenze tra i Nodi

L'obiettivo è calcolare il valore finale di un nodo "F", dove ogni nodo rappresenta un'operazione matematica.

Le dipendenze esplicite tra i vari nodi, sono le seguenti:

Nodo A: È il punto di partenza e non ha dipendenze. Restituisce il valore costante 5.0.
Nodo B: Dipende dal risultato di A. Calcola: B=A+2.
Nodo C: Dipende dai risultati di A e B. Calcola: C=A+B.
Nodo D: Dipende dai risultati di B e C. Calcola: D=B+C.
Nodo E: Dipende dai risultati di A e C. Calcola: E=A+C.
Nodo F: È il nodo finale e dipende dai risultati di D ed E. Calcola: F=D+E.

In un ambiente multi-thread, la sfida è avviare tutti i calcoli contemporaneamente e fare in modo che ogni thread attenda correttamente i dati necessari senza sprecare risorse (busy waiting) e senza causare deadlock.

Soluzione

La soluzione si basa sull'utilizzo dei metodi wait() e notifyAll() per gestire la sincronizzazione tra i thread.

Calcolo.java

Questa classe implementa Runnable e rappresenta un singolo nodo del grafo. Utilizza un oggetto Callable<Double> per definire l'operazione da compiere.

Nella soluzione proposta, l'uso di wait() e notifyAll() all'interno della classe Calcolo è fondamentale per gestire le dipendenze del grafo in modo che ogni thread attenda i dati necessari senza consumare CPU inutilmente.

Ecco come funzionano nel dettaglio:

1. Il Meccanismo di Attesa con wait()

Il metodo getRisultato() è dichiarato come synchronized, il che significa che un thread deve acquisire il "lock" (il monitor) dell'oggetto Calcolo prima di eseguirlo.

Condizione di attesa: All'interno del metodo, un ciclo while controlla se il risultato è ancora null.
Sospensione: Se il calcolo non è terminato, viene invocato wait().
Questa chiamata ha due effetti immediati:
1. Rilascia il lock sull'oggetto, permettendo ad altri thread (incluso quello che deve effettivamente impostare il risultato) di entrare nei metodi sincronizzati dello stesso oggetto.
2. Sospende il thread attuale, che entra in uno stato di attesa finché non riceve un segnale di notifica.
Esempio: Se il Thread-B ha bisogno del risultato di A, chiama a.getRisultato().
Se A non ha finito, il Thread-B si ferma su wait() all'interno dell'oggetto a.

2. Il Meccanismo di Notifica con notifyAll()

Quando un thread completa il calcolo assegnatogli (nel metodo run), deve comunicarlo a tutti i thread che sono in attesa del suo risultato attraverso i metodi setRisultato() o setErrore().

Impostazione del valore: Questi metodi sono anch'essi synchronized.
Una volta impostato il valore di risultato o di errore, viene chiamato notifyAll().
Risveglio: Il comando notifyAll() invia un segnale a tutti i thread che erano stati sospesi dal wait() su quel particolare oggetto.
Riconferma: I thread risvegliati non ripartono immediatamente; devono prima ri-acquisire il lock dell'oggetto.
Una volta ottenuto, escono dal wait(), il ciclo while ricontrolla la condizione (trovando ora il risultato disponibile) e il metodo restituisce il valore finale.

Perché while invece di if?

L'uso del ciclo while (anziché un semplice if) per racchiudere wait() è una best practice della programmazione concorrente in Java per proteggersi dai cosiddetti "risvegli spuri" (spurious wakeups), garantendo che il thread prosegua solo se la condizione è realmente soddisfatta.

In sintesi nel Grafo:

Nel Main, tutti i thread vengono avviati quasi contemporaneamente. Grazie a wait() e notifyAll(), l'esecuzione si "auto-organizza": i thread dei nodi finali (come F) rimarranno in attesa finché i segnali di notifica non risaliranno tutto il grafo, partendo dal nodo A e procedendo via via attraverso B, C, D ed E.

Come viene simulato il tempo di calcolo nel codice?

Il tempo di calcolo nel codice fornito viene simulato all'interno del metodo run() della classe Calcolo attraverso l'uso combinato di numeri casuali e la sospensione temporanea del thread.

Ecco i passaggi specifici utilizzati per la simulazione:

Definizione del limite massimo: Viene definita una costante denominata TEMPO_MAX_CALCOLO_IN_SECONDI, impostata a 5 secondi, che stabilisce la durata massima possibile per ogni singolo calcolo.
Generazione di un ritardo casuale: Prima di salvare il risultato, il codice genera un numero intero casuale compreso tra 0 (incluso) e il valore massimo definito (escluso), utilizzando la classe java.util.Random: final int ritardo = new Random().nextInt(TEMPO_MAX_CALCOLO_IN_SECONDI);.
Sospensione del Thread: Il thread corrente viene messo in pausa per il numero di secondi calcolato precedentemente tramite il comando: TimeUnit.SECONDS.sleep(ritardo);.

Questa simulazione è inserita intenzionalmente dopo che il valore dell'espressione è stato calcolato, ma prima della chiamata al metodo setRisultato(valoreEspressione). In questo modo, si imita un'operazione computazionalmente onerosa, costringendo gli altri thread che dipendono da quel risultato ad attendere effettivamente per un tempo variabile.

Main.java

Il Main definisce la struttura del grafo collegando i vari oggetti Calcolo tra loro tramite espressioni lambda e avvia un thread dedicato per ciascuno .

Domande e risposte

Perché viene usato notifyAll() invece di notify()?

L'uso di notifyAll() invece di notify() è fondamentale in questa soluzione perché più thread possono dipendere contemporaneamente dal risultato dello stesso calcolo.

Ecco le ragioni tecniche basate sulla struttura del grafo delle precedenze presentato:

1. Presenza di dipendenze multiple

Nel grafo definito in Main.java, diversi nodi richiedono lo stesso input per procedere. Ad esempio:

Il risultato del nodo A è necessario per i calcoli dei nodi B, C ed E.
Il risultato del nodo C è necessario per i calcoli dei nodi D ed E.

Se utilizzassimo notify(), quando il thread del nodo A termina, verrebbe svegliato uno solo dei thread in attesa (scelto in modo arbitrario dalla JVM). Gli altri thread rimarrebbero sospesi in stato di wait(), col rischio di non essere mai più risvegliati se non ci sono altre chiamate a notify() sull'oggetto A.

2. Differenza tra i due metodi

notify(): Risveglia un singolo thread nel set di attesa dell'oggetto. Se ci sono tre thread in attesa (come nel caso di A), due di essi continuerebbero a dormire.
notifyAll(): Risveglia tutti i thread attualmente in attesa sul monitor dell'oggetto. Una volta risvegliati, tutti i thread competono per riacquisire il lock, verificano la condizione del while e, trovando il risultato disponibile, procedono con i propri calcoli.

3. Prevenzione del Deadlock

In un sistema basato su un grafo complesso, l'uso di notify() è spesso considerato pericoloso (un "anti-pattern"). Se il thread sbagliato viene svegliato o se un segnale viene "perso" perché non ha raggiunto tutti gli interessati, l'intero grafo potrebbe bloccarsi in un deadlock, dove alcuni thread attendono per sempre risultati che sono già stati calcolati ma per i quali non hanno ricevuto la notifica.

In sintesi, notifyAll() garantisce che ogni nodo dipendente venga informato non appena il dato di cui ha bisogno è pronto, assicurando che l'esecuzione del grafo proceda fluidamente fino al nodo finale F.

Quali sono i vantaggi dell'interfaccia Callable in questo contesto?

L'uso dell'interfaccia Callable<Double> al posto della classica interfaccia Runnable per definire le operazioni dei nodi offre diversi vantaggi tecnici e architetturali nel contesto del grafo delle precedenze:

Restituzione di un valore: A differenza di Runnable, il cui metodo run() è void, il metodo call() di Callable è progettato per restituire un risultato. Questo è essenziale nel grafo, poiché ogni nodo deve produrre un valore numerico che i nodi successivi utilizzeranno per i propri calcoli.
Gestione nativa delle eccezioni: Il metodo call() può lanciare eccezioni controllate (checked exceptions). Nella classe Calcolo, questo permette di catturare facilmente eventuali errori durante l'esecuzione dell'espressione, memorizzarli nell'attributo errore e notificare i thread dipendenti che il calcolo è fallito.
Integrazione con le Lambda Expressions: Essendo una functional interface, Callable permette di definire la logica di ogni nodo in modo estremamente conciso nel Main tramite le lambda. Ad esempio, la dipendenza del nodo B da A viene scritta semplicemente come () -> a.getRisultato() + 2, rendendo la struttura del grafo immediatamente leggibile.
Separazione tra Logica e Sincronizzazione: L'uso di Callable permette una netta separazione delle responsabilità. La classe Calcolo si occupa esclusivamente della gestione dei thread e della sincronizzazione (wait/notifyAll), mentre la logica matematica specifica (l'espressione da calcolare) viene "iniettata" dall'esterno. Questo rende la classe Calcolo generica e riutilizzabile per qualsiasi tipo di operazione.
Calcolo differito (Lazy Evaluation): L'espressione non viene eseguita nel momento in cui l'oggetto viene creato, ma solo quando il thread dedicato invoca esplicitamente espressione.call() all'interno del proprio metodo run(). Questo permette di avviare tutti i thread contemporaneamente lasciando che si coordinino autonomamente.

Come vengono gestite le eccezioni durante i calcoli?

Nel codice fornito, la gestione delle eccezioni è strutturata per garantire che un errore in un nodo del grafo venga correttamente propagato ai thread dipendenti e infine al thread principale.

La gestione avviene attraverso i seguenti meccanismi:

Cattura nel metodo run(): Tutta la logica di calcolo all'interno del metodo run() (inclusa l'esecuzione della Callable e la simulazione del ritardo) è racchiusa in un blocco try-catch. Se si verifica un'eccezione, questa viene catturata e passata al metodo setErrore(e).
Memorizzazione e Notifica: Il metodo setErrore(Exception e) è sincronizzato e svolge due compiti fondamentali:
1. Memorizza l'eccezione nell'attributo privato errore.
2. Invoca notifyAll() per risvegliare tutti i thread che sono in attesa (nel metodo getRisultato) del completamento di quel particolare calcolo.
Propagazione tramite getRisultato(): Quando un thread dipendente si risveglia dalla wait() all'interno di getRisultato(), controlla se l'attributo errore non è nullo.
In caso di errore, il metodo lancia una RuntimeException che include il nome del nodo fallito e l'eccezione originale come causa. Questo interrompe a catena tutti i calcoli che dipendono dal nodo che ha fallito.
Gestione finale nel Main: Nel metodo main, la chiamata finale per ottenere il risultato del nodo "F" è protetta da un blocco try-catch, che cattura eventuali eccezioni propagate dal grafo e ne stampa lo stack trace (ex.printStackTrace()).

In sintesi, il sistema non si limita a catturare l'errore localmente, ma usa il meccanismo di monitoraggio e notifica per informare in modo sicuro tutti i nodi "discendenti" che il calcolo non può essere completato.

📊Infografica

Page updated

Google Sites

Report abuse