[Java] Problema Thread e multicore

[Lim]

Salve a tutti.
Durante lo sviluppo di un simulatore di una ambiente fisico, sono incappato in un problema apparentemente strano.

Ho cercato di ottimizzare il simulatore (scritto in Java) utilizzando il multi-thread per sfruttare al meglio i 4 core di cui dispongo.

Spiego in due parole in cosa consistono le simulazioni:
Ci sono vari "oggetti" nell'ambiente simulato, alcuni sono in grado di creare ed emettere moltissimi "oggetti" molto piccoli, altri sono in grado di assimilarli.
Con un solo emettitore e alcuni ricevitori ed un numero totale di oggetti intorno ai 15000-17000 oggetti, nessun problema.

Se lancio delle simulazioni con più di un emettitore, il numero totale di oggetti si aggira tra i 30000 e gli 80000. E' in questi casi che ho problemi.

Dopo pochissimo tempo, si genera un'eccezione lanciata dai vari Thread attivi (che si occupano di fare una semplicissima elaborazione degli oggetti presenti nell'ambiente da simulare): in pratica mi da un Java.null.pointer exception, quindi è come se il thread non avesse più il riferimento alla lista di oggetti che gli era stata passata in fase di creazione ed avvio...

Tale problema non sembra presentarsi se uso un solo core (le simulazioni avvengono su una macchina virtuale ospitata da un server con 24 core, quindi in linea di massima posso assegnare le risorse a piacimento...).

L'unica cosa che mi viene in mente al momento, è che magari i 4 core si passano i thread in base a qualche strategia e durante il passaggio si perdano i riferimenti agli oggetti...

[PGI-Bis]

Può essere un problema di sincronizzazione (che manca) o un errore logico. Nel secondo caso dovresti notare il problema sempre nello stesso momento, nel primo dovrebbe verificarsi in modo apparentemente casuale.

Se il problema è di sincronizzazione allora devi controllare il tuo codice perchè da qualche parte assumi la visibilità inter-thread di una mutazione di stato che in verità, per com'è fatto il codice, non è garantita.

[Lim]

Originariamente inviato da PGI-Bis

Può essere un problema di sincronizzazione (che manca) o un errore logico. Nel secondo caso dovresti notare il problema sempre nello stesso momento, nel primo dovrebbe verificarsi in modo apparentemente casuale.

Se il problema è di sincronizzazione allora devi controllare il tuo codice perchè da qualche parte assumi la visibilità inter-thread di una mutazione di stato che in verità, per com'è fatto il codice, non è garantita.

Beh, non penso che sia un errore logico, sembra casuale la cosa, ma avviene sempre poco dopo l'avvio.
I Thread li sincronizzo con il Join, dici che può bastare?

Più o meno faccio così:

for (int i=0; i<threadQuantity; i++){
threadList.add(new myThread(objectList));
threadList.get(threadList.size()-1).start();
}

for (int i=0; i<threadQuantity; i++){
threadList.get(i).join();
}

[PGI-Bis]

Bisogna vedere il programma. Ad esempio quel pezzo di codice ci dice che le operazioni compiute su objectList (cioè in generale ciò che è contenuto in quella lista e le operazioni che sono state compiute sui singoli elementi di quella lista) sono correttamente sincronizzate, nel senso che i singoli thread effettivamente partono "vedendo" la lista ed il suo contenuto correttamente formati.

Questo deriva dalla regola secondo cui la prima operazione eseguita da un thread è sincronizzata con le operazioni compiute dal thread che lo avvia (in questo caso presumo il thread main).

Dunque il problema non è nell'avvio. Escluso l'avvio, resta ciò che capita dopo. Se almeno dei thread modifica objectList nel corso della sua esecuzione, senza curarsi del fatto che objectList sia condiviso (ammesso che lo sia) allora potrebbe verificarsi un problema come quello descritto.

Ripeto, bisogna vedere il programma per capire se c'è questo problema o no. Ad esempio, se objectList non è una lista thread-safe, prova ad usare al suo posto, ad esempio, CopyOnWriteArrayList. Se il problema non si verifica più allora derivava dall'accesso condiviso alla lista.

[Lim]

Originariamente inviato da PGI-Bis

Bisogna vedere il programma. Ad esempio quel pezzo di codice ci dice che le operazioni compiute su objectList (cioè in generale ciò che è contenuto in quella lista e le operazioni che sono state compiute sui singoli elementi di quella lista) sono correttamente sincronizzate, nel senso che i singoli thread effettivamente partono "vedendo" la lista ed il suo contenuto correttamente formati.

Questo deriva dalla regola secondo cui la prima operazione eseguita da un thread è sincronizzata con le operazioni compiute dal thread che lo avvia (in questo caso presumo il thread main).

Dunque il problema non è nell'avvio. Escluso l'avvio, resta ciò che capita dopo. Se almeno dei thread modifica objectList nel corso della sua esecuzione, senza curarsi del fatto che objectList sia condiviso (ammesso che lo sia) allora potrebbe verificarsi un problema come quello descritto.

Ripeto, bisogna vedere il programma per capire se c'è questo problema o no. Ad esempio, se objectList non è una lista thread-safe, prova ad usare al suo posto, ad esempio, CopyOnWriteArrayList. Se il problema non si verifica più allora derivava dall'accesso condiviso alla lista.

Ora che mi ci fai pensare, potrebbe dipendere proprio dal fatto che objList è condiviso tra i vari thread. Devo essere più preciso però, perché in realtà ho incollato un codice semplificato. Durante la creazione di ogni Thread, ad esso gli viene passata la lista completa di oggetti e viene indicato l'intervallo della lista assegnata a quel Thread, così che ogni Thread possa agire solo su una partizione della lista totale.
Probabilmente devo ricontrollare questa strategia, ma mi resta comunque un dubbio, perché funziona con 1 core e non funziona con 2 o 4?

Per renderla ThreadSafe come dovrei manipolarla?

[PGI-Bis]

Bisogna analizzare il codice per capire se ci sia un problema derivante dalla condivisione della lista. Come nel caso dell'avvio di un thread, esistono dei punti di sincronizzazione impliciti quindi non è detto che l'intoppo stia lì.

Ad esempio se data una lista X creata e riempita dal thread main lanci n nuovi thread, ciascuno dei quali legge una porzione della lista, non ci sono problemi di sincronizzazione.

Se invece i thread scrivono, possono esserci dei problemi a seconda di dove scrivono, di come sia fatta la lista e di quando il risultato della scrittura sia letto. Ad esempio se la lista è un array list, ciascun thread scrive nella sua porzione di lista limitandosi a cambiare il valore di celle già esistentti (cioè non espande o comprime l'array sottostante) e la lettura è fatta dal thread main dopo aver atteso con una join il termine di tutti i sotto-thread, allora il codice è già sincronizzato (perchè il join, sempre secondo il jmm, stabilisce che cioè che il thread di cui si attende il termine abbia fatto sia visibile al thread che ha atteso).

Circa la ragione per cui il problema si manifesta solo con più thread, essa deriva dal java memory model: un programma a thread singolo è obbligato a produrre quegli effetti che si avrebbero se il codice fosse eseguito nell'ordine in cui appare nel sorgente. Nulla vieta che sia eseguito parallelamente della jvm o che il compilatore riordini le istruzioni a suo piacimento MA, gli effetti del codice devono essere quelli che si avrebbero se...

Dal punto di vista "meccanico", la ragione per cui è possibile che un programma multi-thread manifesti problemi che un programma single thread non ha deriva dalla parziale, temporanea incoerenza dei livelli di memoria più prossimi al core rispetto al livello in cui risiedono i dati oggetto di computazione prima dell'invio alla cpu.

Detta alla bucaniera, la RAM è una sola ma le cache possono essere tante quante i core. Se il compito di un thread è gestito da un core e il codice non contiene istruzioni che forzino la coerenza della cache è possibile che il risultato computato da un core sia ancora in uno dei livelli non condivisi della cache quando un secondo thread/core inizia la sua esecuzione. Ma è solo un caso di possibile divergenza, se ne possono immaginare tanti altri.

PS.: prova ad usare una CopyOnWriteArrayList o un Vector per listObject. Se il problema è nella sovrapposizione delle invocazioni di scrittura sulla lista, dovrebbe risolversi.

[Lim]

Originariamente inviato da PGI-Bis

Bisogna analizzare il codice per capire se ci sia un problema derivante dalla condivisione della lista. Come nel caso dell'avvio di un thread, esistono dei punti di sincronizzazione impliciti quindi non è detto che l'intoppo stia lì.

[...] Se invece i thread scrivono, possono esserci dei problemi a seconda di dove scrivono, di come sia fatta la lista e di quando il risultato della scrittura sia letto. Ad esempio se la lista è un array list, ciascun thread scrive nella sua porzione di lista limitandosi a cambiare il valore di celle già esistentti (cioè non espande o comprime l'array sottostante) e la lettura è fatta dal thread main dopo aver atteso con una join il termine di tutti i sotto-thread, allora il codice è già sincronizzato (perchè il join, sempre secondo il jmm, stabilisce che cioè che il thread di cui si attende il termine abbia fatto sia visibile al thread che ha atteso).


PS.: prova ad usare una CopyOnWriteArrayList o un Vector per listObject. Se il problema è nella sovrapposizione delle invocazioni di scrittura sulla lista, dovrebbe risolversi.

Analizzando meglio il codice sembra proprio che il problema sia legato alla lettura e scrittura di una lista condivisa.

Ho provato ad usare il CopyOnWriteArrayList al posto dell'ArrayList, in modo molto semplice, ma il programma ora è tremendamente più lento! Sembrerebbe non generare più l'eccezione (sembrerebbe, perché al momento non ho avuto modo di fare altre simulazioni per avere ulteriori conferme, sono troppo lente...).

Forse non è sufficiente sostituire l'ArrayList con il CopyOnWriteArrayList, forse serve una tecnica + raffinata... idee?

[banryu79]

Originariamente inviato da Lim

Ho provato ad usare il CopyOnWriteArrayList al posto dell'ArrayList, in modo molto semplice, ma il programma ora è tremendamente più lento! Sembrerebbe non generare più l'eccezione (sembrerebbe, perché al momento non ho avuto modo di fare altre simulazioni per avere ulteriori conferme, sono troppo lente...).

CopyOnWriteArrayList è buono nello scenario in cui si facciano molte letture concorrenti e poche scritture, proprio perchè ad ogni mutazione viene appunto ricreato per intero (come il nome suggerisce).
Un caso tipico d'uso è come struttura per mantenere una lista di listener registrati presso una stessa sorgente: le letture sono moltissime (ad ogni notifica di un evento a tutti gli ascoltatori) mentre le scritture relativamente poche (solo quando si registra o de-registra un listener).

Sono abbastanza certo che PGI-Bis volesse farti fare questa prova appunto per verificare se il problema può essere dovuto a scritture concorrenti, come sembrerebbe, se non ho capito male.

[PGI-Bis]

Per la tecnica più raffinata bisogna vedere il programma. Come detto, se ogni thread lavora su una partizione della lista originale, senza mai sforare il suo range, allora non serve alcuna sincronizzazione esplicita e basta un ArrayList con il join finale - ma non dovrebbe andare bene una linked list. E' però un caso molto specifico.

Se "sforano" (cioè il thread 1 legge gli elementi da 0 a 10 e scrive da 0 a 11) puoi usare un Vector ma resterebbe un problema di ordine - è garantita l'integrità della struttura dati ma non l'ordine in cui scritture e letture sono eseguite.

Se hai un ordine da rispettare la faccenda diventa più complicata.

[Lim]

Originariamente inviato da PGI-Bis

Per la tecnica più raffinata bisogna vedere il programma. Come detto, se ogni thread lavora su una partizione della lista originale, senza mai sforare il suo range, allora non serve alcuna sincronizzazione esplicita e basta un ArrayList con il join finale - ma non dovrebbe andare bene una linked list. E' però un caso molto specifico.

Se "sforano" (cioè il thread 1 legge gli elementi da 0 a 10 e scrive da 0 a 11) puoi usare un Vector ma resterebbe un problema di ordine - è garantita l'integrità della struttura dati ma non l'ordine in cui scritture e letture sono eseguite.

Se hai un ordine da rispettare la faccenda diventa più complicata.

Vi ringrazio per tutte le info che siete riusciti a darmi fino ad ora.
Faccio il punto della situazione, mi sembra di aver capito quale sia il blocco di codice interessato ma a questo punto non capisco perché crei problemi.


Allora, piccolo riepilogo, il codice funzionava alla perfezione con un solo "oggetto" trasmittente (vi ricordo che ho simulato un ambiente composto da oggetti trasmittenti ed altri rice-trasmittenti). Inserendo due o più oggetti TX, si genera l'eccezione.
Il blocco di codice che genera l'eccezione non sembra essere multi-thread, quindi è un blocco sequenziale.
Cerco di spiegarlo a grandi linee, sperando di non tralasciare concetti importanti:

La classe interessata è quella che gestisce la propagazione degli oggetti nell'ambiente simulato. Il metodo che viene invocato esegue 3 macro-operazioni:

1) move(nanoObjList);

2) checkCollision(nanoObjList);

3) while (collisionsList.size()>0){
avoidCollision();
}

La chiamata 1 si occupa di spostare tutti gli "oggetti del simulatore". E' in questa fase si fa uso del multi-thread, poiché all'interno del metodo move(...) vengono generati N Thread.
Assumo che prima di passare all'istruzione 2, tutti i Thread lanciati da move() siano stati chiusi...
L'istruzione 2 verifica se si sono generate delle collisioni durante lo spostamento degli oggetti avvenuto nella fase 1. Anche in questa fase si fa uso del multi-thread, poiché occorre verificare ogni oggetto con tutti gli altri (complessità quadratica!). Ogni collisione rilevata instanzia un semplice oggetto "Collision" (che ha semplici attributi e proprietà) e lo appende alla lista "collisionsList", che è un ArrayList<Collision>.
Terminata questa fase, si passa alla fase 3, che ha il compito di gestire le collisioni eventualmente occorse, quindi, finché non le ha risolte tutte, non va avanti con la simulazione (questa cosa la gestisco con il while...).
Il metodo avoidCollision() NON è multi-thread, ed è proprio qui che si genera l'eccezione. Vi incollo il codice del metodo:

public void avoidCollision(){		
		
	try {				
		reorderCollision();

	}catch (Exception e) {
		e.printStackTrace();		      
        } try{
		for (int i=0;i<collisionsList.size();i++){
			NanoObj p1=collisionsList.get(i).getNano1();
			NanoObj p2=collisionsList.get(i).getNano2();
			p1.estabilishContact(p2);
		}
	}catch (Exception e) {	      		
	      	e.printStackTrace();
	}	
}

Vengono lanciate due eccezioni, una relativa a reorderCollision() ed una relativa al secondo blocco di istruzioni, in particolare il messaggio d'errore riporta la riga "NanoObj p1=collisionsList.get(i).getNano1();" per quanto riguarda la seconda eccezione, mentre la prima indica la riga "if(collisionsList.get(j).getDt() > collisionsList.get(i).getDt())" di reorderCollision(), che riporto per intero qui sotto:

public boolean reorderCollision(){
                Collision tempCollision;		
		for (int i=0;i<collisionsList.size()-1;i++){
			for (int j=i+1;j<collisionsList.size();j++){
				if(collisionsList.get(j).getDt() > collisionsList.get(i).getDt()){
					tempCollision=collisionsList.get(i);
					collisionsList.set(i, collisionsList.get(j));
					collisionsList.set(j, tempCollision);
				}				
			}
		}
}

Utilizzando CopyOnWriteArrayList sembrano non esserci più problemi (anche se impiega moltissimo tempo in fase di start-up della simulazione), ma in teoria non ci sono accessi concorrenti alla collisionsList, o sbaglio?

[PGI-Bis]

In teoria il multithreading non ti aiuta per la parte a complessità quadratica a meno che tu non abbia a disposizione una macchina fortemente parallela, perchè il termine rilevante N^2 potrebbe essere ridotto solo da ~N^2 thread.

Per il codice che hai CopyOnWriteArrayList va malissimo. Funziona come dice banryu, per ogni set fa un System.arrayCopy che non è una piuma.

Usa java.util.Vector al posto di CopyOnWriteArrayList: ha un costo più alto in lettura e molto più basso in scrittura.

In java non sono i metodi ad essere "multithread" ma i campi. Il metodo avoidCollision è multithread in quanto al suo interno si verificano letture o scritture di campi che sono stati modificati da almeno un altro thread.

In linea generale a te non interessa sapere quali metodi siano "invocati da più thread" e quali no: devi solo assicurarti che eventuali letture o scritture di campi, direttamente o indirettamente eseguite in quei metodi, siano thread-safe. Lettura significa x = campo o campo.qualcosa, scrittura significa campo = qualcosa.

[Lim]

Originariamente inviato da PGI-Bis

In teoria il multithreading non ti aiuta per la parte a complessità quadratica a meno che tu non abbia a disposizione una macchina fortemente parallela, perchè il termine rilevante N^2 potrebbe essere ridotto solo da ~N^2 thread.

Beh, questo discorso un po' l'ho aggirato con una strategia che mi sono inventato per ridurre il numero di confronti, da N^2 passo a N Log(N), in ogni caso penso che segmentare l'insieme degli oggetti da confrontare in M sottoinsiemi, possa comunque portare dei benefici, anche se rimane il discorso generale che facevi tu...

Originariamente inviato da PGI-Bis

Per il codice che hai CopyOnWriteArrayList va malissimo. Funziona come dice banryu, per ogni set fa un System.arrayCopy che non è una piuma.

Usa java.util.Vector al posto di CopyOnWriteArrayList: ha un costo più alto in lettura e molto più basso in scrittura.

Ok, vedo come fare per integrare questa cosa. Comunque, a parte un overhead iniziale (che non giustifico) sembra non appesantire le prestazioni della simulazione, ma non ci metto la mano sul fuoco, devo fare altri test a riguardo. Immagino comunque che non si rivelerà la scelta migliore...

Originariamente inviato da PGI-Bis

In java non sono i metodi ad essere "multithread" ma i campi. Il metodo avoidCollision è multithread in quanto al suo interno si verificano letture o scritture di campi che sono stati modificati da almeno un altro thread.

In linea generale a te non interessa sapere quali metodi siano "invocati da più thread" e quali no: devi solo assicurarti che eventuali letture o scritture di campi, direttamente o indirettamente eseguite in quei metodi, siano thread-safe. Lettura significa x = campo o campo.qualcosa, scrittura significa campo = qualcosa.

Pensavo che mi fosse chiaro questo concetto, ma sembra che non sia così...
Capisco il discorso che i campi che sto leggendo siano stati scritti da thread diversi, ma nel momento in cui li leggo, tutti i thread che li hanno scritti sono ormai morti ed io li voglio leggere tramite un ciclo for, perché non dovrebbe riuscirci se non uso CopyOnWriteArrayList (o il Vector equivalentemente)??

Catturando le eccezioni ho cercato di monitorare il comportamento del metodo, quindi mi sono stampato a video gli indici dei cicli for di reorderCollision.
Sembra che il problema si generi grosso modo sempre per gli stessi indici!!!!

i=0
mentre j può trovarsi ai seguenti step: 1019, 2294, 679, 452, 3442, 1529, 1019, 1529...

Insomma gli indici sono più o meno sempre quelli e non sembrano uscire con la stessa sequenza...

Non capisco...

[Lim]

Comunque si, è come dite voi.
Anche se l'eccezione viene lanciata dal metodo reorderCollision(), che fa solo delle letture, disabilitando il multi-thread di checkCollision, il problema non si presenta. E' la scrittura non thread-safe...

Sto facendo delle prove con Vector, al momento non mi sembra molto veloce...

Suggerimenti per approcciare al problema in modo diverso?

[banryu79]

Originariamente inviato da Lim

Sto facendo delle prove con Vector, al momento non mi sembra molto veloce...

Anche se non deve essere ricreato ad ogni mutazione, Vector è sincronizzato "alla grossa", cioè tutti gli accessi (anche le letture) sono esclusivi. Rispetto a prima (con CopyOnWriteEcc...) risparmi il tempo usato per copiare la struttura della collezione ma hai performance peggiori in lettura.

Per i suggerimenti non so, dovrei capire meglio il tutto e studiare la cosa con più calma, che al momento non ho...

[PGI-Bis]

occhio che se gli indici sono sempre gli stessi allora il problema non è di threading che dovrebbe essere praticamente random. Forse sono i conti. Se puoi controlla.

Cosa succede se usi un ArrayList semplice come lista di oggetti? lo chiedo perchè ArrayList dovrebbe essere strutturalmente insensibile alle mutazioni di uno dei valori che già contiene.

In verità è possibile che il problema non sia nella lista (perchè nel codice vedo dei set ma non degli add o remove) ma negli oggetti che la lista contiene, cioè in quei NanoObj.

Io proverei a sincronizzare i metodi di NanoObj (detta alla pescivendola basta mettere un synchronized prima del tipo restituito dai metodi).