Aggiunta di thread in modo ricorrente a un pool di thread Java

Question

Sto lavorando su un tutorial per il mio corso di concorrenza Java. L'obiettivo è utilizzare i pool di thread per calcolare i numeri primi in parallelo.

Il design è basato sul setaccio di Eratostene. Ha una matrice di n bool, dove n è il numero intero più grande che stai controllando, e ogni elemento nella matrice rappresenta un intero. True è primo, false non è primo e l'array è inizialmente tutto vero.

Un pool di thread viene utilizzato con un numero fisso di thread (si suppone di sperimentare il numero di thread nel pool e osservare le prestazioni).

A thread viene assegnato un numero intero multiplo da elaborare. Il thread trova quindi il primo vero elemento nell'array che non è un multiplo del numero intero di thread. Il thread crea quindi un nuovo thread nel pool di thread a cui viene assegnato il numero trovato.

Dopo aver formato un nuovo thread, il thread esistente continua quindi a impostare su false tutti i multipli del suo intero nell'array.

Il thread del programma principale avvia il primo thread con il numero intero '2' e quindi attende che tutti i thread generati siano terminati. Quindi sputa fuori i numeri primi e il tempo impiegato per calcolare.

Il problema è che più thread ci sono nel pool di thread, più lento è il tempo impiegato da 1 thread. Dovrebbe essere sempre più veloce, non più lento!

Tutte le cose su Internet relative ai pool di thread Java creano n thread di lavoro il thread principale, quindi attendi che tutti i thread finiscano. Il metodo che utilizzo è ricorsivo in quanto un lavoratore può generare più thread di lavoro.

Mi piacerebbe sapere cosa non funziona e se i pool di thread Java possono essere utilizzati in modo ricorsivo.

Answer 1

La soluzione può essere eseguito più lento in quanto le discussioni sono aggiunti per alcuni dei seguenti problemi:

• spese generali di creazione Discussione: creazione di un thread è costoso.

• Contesa processore: se ci sono più thread di quanti siano processori per eseguirli, alcuni thread verranno sospesi in attesa di un processore libero. Il risultato è che la velocità di elaborazione media per ogni thread diminuisce. Inoltre, il sistema operativo deve quindi suddividere i thread a tempo, e ciò richiede tempo che altrimenti verrebbe utilizzato per il lavoro "reale".

• Contesa della memoria virtuale: ogni thread ha bisogno di memoria per il suo stack. Se la tua macchina non ha abbastanza memoria fisica per il carico di lavoro, ogni nuovo stack di thread aumenta la contesa della memoria virtuale che risulta nel paging che rallenta le cose

• Contesa di cache: ogni thread eseguirà (presumibilmente) una scansione di una sezione diversa di l'array, con conseguente mancanza di memoria cache. Questo rallenta gli accessi alla memoria.

• Contesa del blocco: se i thread stanno leggendo e aggiornando un array condiviso e utilizzando synchronized e un oggetto di blocco per controllare l'accesso all'array, si potrebbe essere affetti da conflitto di blocco. Se viene utilizzato un oggetto a blocco singolo, ciascun thread impiegherà la maggior parte del suo tempo in attesa di acquisire il blocco. Il risultato netto è che il calcolo viene effettivamente serializzato e la velocità di elaborazione complessiva scende alla velocità di un singolo processore/thread.

I primi quattro problemi sono inerenti al multi-threading, e non ci sono soluzioni reali ... oltre a non creare troppi thread e il riutilizzo di quelli che avete già creato. Tuttavia, esistono diversi modi per attaccare il problema della contesa del blocco. Ad esempio,

• Ricodifica l'applicazione in modo che ogni thread esegua la scansione per più interi, ma nella propria sezione dell'array. Ciò eliminerà la contesa di blocco sugli array, anche se sarà necessario un modo per dire a ogni thread cosa fare e che deve essere progettato tenendo presente la contesa.
• Creare una serie di blocchi per diverse regioni della matrice e fare in modo che i thread scelgano il blocco da utilizzare in base alla regione della matrice su cui stanno operando. Continuerai comunque a litigare, ma in media dovresti ottenere meno contese.
• Progettare e implementare una soluzione senza chiave. Ciò comporterebbe una comprensione profonda del modello di memoria Java. E sarebbe molto difficile dimostrare/dimostrare che una soluzione senza serratura non contiene sottili difetti di concorrenza.

Infine, ricorsiva creazione di fili è probabilmente un errore, dato che renderà più difficile implementare riutilizzo filo e le misure antibloccaggio-contesa.

Answer 2

Quanti processori sono disponibili sul sistema? Se #threads> #processors, l'aggiunta di più thread rallenterà le cose per un compito legato all'elaborazione come questo.

Ricorda, indipendentemente dal numero di thread avviati, tutti condividono le stesse CPU. Più tempo impiega la CPU a passare da un thread all'altro, minore è il tempo di lavoro effettivo.

Si noti inoltre che il costo di iniziare un thread è significativo rispetto al costo del controllo di un primo - è possibile eseguire centinaia o migliaia di moltiplicazioni nel tempo necessario per attivare 1 thread.

Answer 3

Il punto chiave di un pool di thread consiste nel mantenere attivo un set di thread e riutilizzarli per elaborare le attività. Di solito il modello prevede una coda di attività e sceglie in modo casuale un thread dal pool per elaborarlo. Se non ci sono thread liberi e la piscina è piena, aspetta.

Il problema che hai progettato non è buono per essere risolto da un pool di thread, perché hai bisogno di thread da eseguire in ordine. Correggimi se sbaglio qui.

discussione # 1: impostare più 2 di false

filo # 2: trovare 3, impostare più 3 di false

filo # 3: trovare 5, impostare più 5 di false

filo # 4: trovare 7, impostare più di 7 su false

....

Questi fili devono essere eseguiti in ordine e stanno interleaving (come l'orari di esecuzione t orlo) importa.

Ad esempio, se il thread n. 3 inizia a essere eseguito prima che il thread n. 1 imposti "4" su falso, troverà "4" e continuerà a reimpostare i multipli di 4. Questo finisce per fare un sacco di lavoro extra, anche se il risultato finale sarà corretto.

Answer 4

Ristruttura il programma per creare un ThreadPoolExecutor fisso in anticipo. Assicurati di chiamare ThreadPoolExecutor # prestartAllCoreThreads(). Chiedi al metodo principale di inviare un'attività per il numero intero 2. Ogni attività invierà un'altra attività. Poiché si utilizza un pool di thread, non si creano e non si chiude un gruppo di thread, ma si consente invece agli stessi thread di assumere nuove attività man mano che diventano disponibili. Questo ridurrà il sovraccarico complessivo di esecuzione.

Si dovrebbe scoprire che in questo caso il numero ottimale di fili è uguale al numero di processori (P) sulla macchina. È spesso il caso che il numero ottimale di thread sia P + 1. Questo perché P + 1 riduce al minimo il sovraccarico dal cambio di contesto, riducendo al minimo la perdita dal tempo di inattività/blocco.