Metodologie di Programmazione: Lezione 15
Nella lezione precedente abbiamo trattato task IO-intensive, dominati cioè da operazioni di I/O, i cui tempi di esecuzione sono per la gran parte dovuti ad attese per accedere a risorse. Adesso vedremo task computation-intensive che in un certo senso sono all'altro estremo dello spettro perché i loro tempi di esecuzione sono dovuti esclusivamente a calcoli senza tempi d'attesa. Una conseguenza importante di questa differenza è che la mera programmazione multithreading, cioè l'uso di più thread, per quest'ultimo tipo di compiti non porta a miglioramenti delle prestazioni se non ci sono due o più processori disponibili. In altri termini, per ottenere miglioramenti dalla programmazione multithreading è necessario eseguire calcoli in parallelo non semplicemente in modo concorrente.
Gli esempi discussi finora non richiedono che i thread debbano comunicare tra loro o che debbano accedere a dati condivisi mutabili durante la loro esecuzione. Ma ci sono molte situazioni in cui ciò è conveniente o indispensabile. In questa lezione introdurremo i meccanismi di base per far fronte a tali situazioni tramite la sincronizzazione dei thread.
Un task ad alta intensità di calcolo richiede esclusivamente esecuzioni di calcoli e non richiede operazioni di I/O bloccanti (come connessioni a server remoti). Quindi l'esecuzione di tali task impegna solamente le unità di calcolo e la memoria del computer. Non ci sono tempi d'attesa che possono essere compensati sfruttando l'esecuzione in multithreading. Se il computer dispone di una sola unità di calcolo, una sola CPU, non c'è modo di migliorare il tempo di calcolo usando più thread. Se però si dispone di più unità di calcolo che possono operare in parallelo, allora c'è la possibilità che suddividendo opportunamente i calcoli del nostro compito tra i processori si riesca a ridurre il tempo di calcolo. Se il numero di processori è N, il meglio a cui si può aspirare è che il tempo di calcolo T si riduca a T/N. Difficilmente si riesce a ottenere questo miglioramento ottimale, ma spesso ci si può avvicinare. In generale dipende sia dall'architettura hardware/software sia dal tipo di problema che si vuole risolvere. Per alcuni problemi è addirittura impossibile ottenere miglioramenti indipendentemente dal numero di processori. All'altro estremo ci sono problemi o compiti che si parallelizzano molto facilmente. Nel mezzo ci sono una gran varietà di problemi con varie possibilità di parallelizzazione più o meno efficienti.
Esula da questo corso il trattamento di tecniche di parallelizzazione, il cui approfondimento richiede corsi a sé stanti. Ci limiteremo a mostrare alcuni semplici esempi la cui parallelizzazione è molto facile. Nonostante la loro semplicità, mettono in evidenza alcuni fenomeni che hanno una valenza più generale.
La congettura di Collatz, conosciuta anche come congettura 3n + 1, è un problema aperto da quando è stata enunciata per la prima volta nel 1937 da Lothar Collatz (si veda Collatz conjecture). La congettura è facile da enunciare. Dato un qualsiasi intero positivo n, si consideri la seguente procedura: se n è pari, dividilo per 2; altrimenti moltiplicalo per 3 e aggiungi 1; ripeti per sempre o finché n diventa 1. La ragione per cui ci si ferma a 1 è che dopo 1 la sequenza dei numeri prodotti dalla procedura diventa periodica 1,4,2,1,... La congettura afferma che partendo da un qualsiasi intero positivo la procedura arriva sempre ad 1 (e quindi termina). La congettura è stata verificata sperimentalmente per numeri molto grandi ma nessuno è riuscito finora a dimostrare che vale per tutti gli infiniti numeri interi.
La verifica sperimentale della congettura richiede di eseguire la procedura per un dato intervallo di numeri interi, determinando per ogni n il numero di passi che la procedura deve fare per arrivare ad 1. Non siamo interessati a trovare l'algoritmo più veloce, che magari mantiene in memoria una opportuna tabella, ecc. Ma semplicemente a vedere come tale task può essere parallelizzato e con quale efficacia.
Iniziamo a scrivere una versione sequenziale che per ogni intero in un dato intervallo esegue la procedura di Collatz, calcola il numero di passi e determina il massimo numero di passi per tutti gli interi nell'intervallo. Introduciamo una classe CompIntensive nel package mp.concur.
/** Classe per testare implementazioni parallele di task ad alta intensità
* di calcolo. */
public class CompIntensive {
/** Ritorna il massimo numero di passi della procedura della congettura
* di Collatz, per gli interi nell'intervallo [a, b].
* @param a inizio intervallo
* @param b fine intervallo
* @return il massimo numero di passi */
public static long collatz(long a, long b) {
long max = 0;
for (long i = a ; i <= b ; i++) {
long s = 0, n = i;
while (n != 1) {
n = ((n % 2) == 0 ? n/2 : 3*n + 1);
s++;
}
if (s > max) max = s;
}
return max;
}
}
Il calcolo effettuato da collatz è facilmente parallelizzabile perché per ogni intero dell'intervallo di input esegue una computazione indipendente da tutte le altre. Così è sufficiente partizionare l'intervallo in sotto-intervalli ed eseguire la funzione su ognuno di questi in modo concorrente o parallelo e poi ricombinare i risultati. Questa strategia di parallelizzazione può essere applicata anche ad altri calcoli che hanno le stesse caratteristiche, cioè l'input è un intervallo di interi, per ogni intero nell'intervallo è eseguito un calcolo indipendente dai calcoli per gli altri interi e il risultato si ottiene combinando i risultati relativi ai singoli interi tramite un'operazione binaria1. Nel caso di collatz l'operazione di combinazione è il max. È quindi conveniente definire un metodo generale che implementa la strategia di parallelizzazione appena descritta con la possibilità di variare sia il numero di thread che il numero di sotto-intervalli,
/** Esegue in multithreading la funzione func per l'intervallo [a, b]
* partizionando [a, b] in nt sotto-intervalli, eseguendo func su di essi in
* altrettanti task in modo concorrente su nThreads thread e infine ricombinando
* i risultati con l'operazione comb.
* @param nThreads numero thread
* @param nt numero task e numero sotto-intervalli
* @param func funzione da calcolare sull'intervallo [a, b]
* @param a inizio intervallo
* @param b fine intervallo
* @param comb operazione per ricombinare i risultati dei sotto-intervalli
* @return il risultato della funzione func sull'intervallo [a,b] */
public static long parallel(int nThreads, int nt, LongBinaryOperator func,
long a, long b, LongBinaryOperator comb) {
ExecutorService exec = Executors.newFixedThreadPool(nThreads);
long size = (b - a + 1);
long nParts = Math.min(nt, size), partSize = size/nParts;
List<Future<Long>> tasks = new ArrayList<>(); // Lista per i task
long res = 0;
try {
for (int i = 0 ; i < nParts ; i++) { // Sottomette i task all'esecutore
long ta = i*partSize + a; // Inizio sotto-intervallo
long tb = (i == nParts-1 ? b : ta+partSize-1); // Fine sotto-intervallo
tasks.add(exec.submit(() -> func.applyAsLong(ta, tb)));
}
for (Future<Long> t : tasks) // Ottiene i risultati relativi ai
res = comb.applyAsLong(res, t.get()); // sotto-intervalli e li ricombina
} catch (InterruptedException | ExecutionException e) {
} finally { exec.shutdown(); }
return res;
}
Ricordiamoci sempre di effettuare lo shutdown dell'esecutore una volta che abbiamo finito di usarlo (altrimenti i thread di alcuni esecutori, come newFixedThreadPool, rimangono in vita).
Definiamo un metodo test per mettere alla prova parallel che misura il tempo totale impiegato e riporta anche i tempi di esecuzione dei thread coinvolti durante il calcolo. Java permette, tramite alcuni metodi e classi in java.lang.management, di misurare il tempo2 in cui un thread è stato effettivamente in esecuzione da quando è iniziato fino al momento della richiesta. Per fare un tale monitoraggio dei thread useremo la classe ThreadsMonitor3 che è pronta per essere posta nel package mp.concur.
/** Esegue la funzione func sull'intervallo [a, b] con nThreads thread, nTasks
* task e altrettanti sotto-intervalli e stampa il risultato e il campionamento
* dei tempi di esecuzione dei thread che hanno effettuato il calcolo.
* @param name nome della funzione
* @param nThreads numero thread, se <= 0, è il numero di processori
* @param nt numero task e numero sotto-intervalli, se <= 0, è nThreads*abs(nt)
* @param func la funzione da eseguire sull'intervallo [a, b]
* @param a inizio intervallo
* @param b fine intervallo
* @param comb operazione per ricombinare i risultati dei sotto-intervalli */
public static void test(String name, int nThreads, int nt, LongBinaryOperator func,
long a, long b, LongBinaryOperator comb) {
if (nThreads <= 0) nThreads = Runtime.getRuntime().availableProcessors();
if (nt <= 0) nt = nt < 0 ? Math.abs(nt)*nThreads : nThreads;
out.println(String.format("Test %s nThreads %d nTasks %d", name, nThreads, nt));
out.println(" Interval ["+a+", "+b+"]: ");
String p = nThreads == 1 && nt == 1 ? "main" : "pool";
ThreadsMonitor monitor = new ThreadsMonitor(100, true, 5, out, s -> s.startsWith(p));
long time = System.currentTimeMillis();
long res = nThreads == 1 && nt == 1 ? func.applyAsLong(a, b) :
parallel(nThreads, nt, func, a, b, comb);
out.println(String.format(" Result: %d Time: %dms", res,
(System.currentTimeMillis()-time)));
monitor.stop();
}
Per determinare il numero di processori usiamo Runtime.getRuntime().availableProcessors(). Adesso possiamo finalmente fare qualche test. Iniziamo con un'esecuzione sequenziale nel main thread,
public static void main(String[] args) {
test("collatz", 1, 1, CompIntensive::collatz, 1, 60_000_000, Math::max);
}
Provandolo su una macchina con 8 core (o processori) potremmo ottenere
Test collatz nThreads 1 nTasks 1
Interval [1, 60000000]:
Result: 744 Time: 28926ms
Period 100ms CPU time charts Levels 5
┤┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
main ┤┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
CPU time: Total 28900ms Percentage 12.5%
User time: Total 28874ms Percentage 12.5%
Machine time: Total 231415ms Percentage 100.0%
Real time: 28927ms
Il monitoraggio conferma le attese ovvero che il singolo thread, cioè il main thread, è stato in effettiva esecuzione per tutto il tempo del calcolo (il diagramma ha tutte le colonnine complete) e che questo tempo ha consumato il 12.5% del tempo di esecuzione messo a disposizione dalla macchina. Infatti avendo 8 core il tempo macchina, quello che è chiamato nel report Machine time, è il tempo reale moltiplicato per il numero di processori disponibili. Il calcolo ha consumato 1/8, cioè il 12.5% del tempo macchina.
Le figure seguenti mostrano l'attività istantanea per ognuno degli 8 core in tre istanti durante il calcolo
La figura sottostante mostra l'attività degli 8 core durante l'esecuzione, campionata ogni secondo. Ogni colonnina rappresenta quindi un campionamento effettuato in un dato secondo e il numero di colonnine è all'incirca pari alla durata del calcolo (circa 29 secondi).
Dalla figura potrebbe sembrare che la JVM effettui una qualche forma di parallelizzazione automatica del calcolo perché 4 degli 8 core sono abbastanza impegnati. Ma se si esaminano le colonnine degli 8 core in ogni secondo si osserva che la somma delle attività non supera mai il massimo che si può avere su un singolo core4. L'uso di più core invece che uno solo è probabilmente dovuto a molteplici fattori che riguardano le politiche degli scheduler della JVM e del sottostante sistema operativo. Sostazialmente l'esecuzione del task è spostatata più volte da un processore all'altro.
Proviamo ora con un numero di thread pari al numero di processori e un eguale numero di task
test("collatz", -1, -1, CompIntensive::collatz, 1, 60_000_000, Math::max);
Potremmo ottenere,
Test collatz nThreads 8 nTasks 8
Interval [1, 60000000]:
Result: 744 Time: 6039ms
Period 100ms CPU time charts Levels 5
┤ ┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃ ┃ ┃┃ ┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃ ┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-1 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁▁▁▁▁▁
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃ ┃┃ ┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-2 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁▁▁
┤ ┃┃ ┃┃┃┃┃┃┃┃┃┃ ┃ ┃┃┃┃ ┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃ ┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-3 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁
┤ ┃┃┃┃┃┃┃┃┃ ┃┃┃ ┃┃┃┃┃ ┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃ ┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-4 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁
┤ ┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃ ┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-5 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃ ┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-6 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃ ┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃ ┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-7 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃
┤ ┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-8 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
CPU time: Total 41694ms Percentage 86.3%
User time: Total 41647ms Percentage 86.2%
Machine time: Total 48311ms Percentage 100.0%
Real time: 6039ms
Si osserva che gli 8 thread sono stati in effettiva esecuzione per quasi tutto il tempo di calcolo, con un consumo complessivo del tempo di esecuzione superiore all'86% del tempo macchina. Questo è in accordo con quello che si evince dal monitoraggio dell'attività dei processori. Le figure sottostanti mostrano due istantanee dell'attività dei core una durante il calcolo e l'altra alla fine.
Si può notare che gli 8 core lavorano a pieno regime durante il calcolo. Questo è ulteriormente confermato dalla figura qui sotto che mostra l'attività, campionata ogni secondo, degli 8 core durante i circa 6 secondi del calcolo.
Le colonnine sono quasi sempre al massimo su ogni core. Questo ci dice che la nostra semplice suddivisione del lavoro tra gli 8 core ha già raggiunto il massimo o quasi che potevamo ottenere (non modificando l'algoritmo sequenziale). Il fattore di miglioramento del tempo di calcolo è 28926/6039 = 4.79, cioè quasi 5. Siamo abbastanza lontani dal fattore ideale 8. Le ragioni potrebbero essere piuttosto complesse e dovute alla particolare architettura hardware della macchina oltre che da come i vari thread sono gestiti dalla JVM e dal sistema operativo. In generale, anche se la macchina dispone di più processori, o core, questi non possono funzionare come se fossero CPU di computer diversi. Tipicamente ci sono vari dispositivi hardware che sono ad uso condiviso, come la memoria, memorie cache, bus, ecc. Tutto ciò limita la possibilità di raggiungere un pieno parallelismo.
Aumentare il numero di thread non può portare a miglioramenti perché non ci sono tempi d'attesa da ammortizzare. Aumentare il numero di task, riducendo così il lavoro svolto da ogni singolo task, ha di solito l'effetto di migliorare il bilanciamento del lavoro svolto dai diversi thread perché compensa le eventuali differenze di lavoro dei task. Però provando ad aumentare il numero di task, non si nota alcun effetto significativo. Confermando quello che risulta anche dai campionamenti dei thread e dell'attività dei core, cioè la suddivisione del lavoro è già ben bilanciata.
Consideriamo un altro esempio di task che richiede alta intensità di calcolo. Vogliamo calcolare il numero di numeri primi contenuti in un dato intervallo. Definiamo quindi il seguente metodo sempre in mp.concur.CompIntensive,
/** Ritorna il numero di primi nell'intervallo [a, b].
* @param a inizio intervallo
* @param b fine intervallo
* @return il numero di primi nell'intervallo [a, b] */
public static long numPrimes(long a, long b) {
long nPrimes = 0;
for (long n = a ; n <= b ; n++) {
long d = 2;
double sqrt = Math.sqrt(n);
while (d <= sqrt && n % d != 0) d++;
if (d > sqrt) nPrimes++;
}
return nPrimes;
}
Proviamolo su un intervallo abbastanza grande
test("numPrimes", 1, 1, CompIntensive::numPrimes, 1, 20_000_000, Long::sum);
Potremmo ottenere,
Test numPrimes nThreads 1 nTasks 1
Interval [1, 20000000]:
Result: 1270608 Time: 40754ms
Period 100ms CPU time charts Levels 5
┤┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
main ┤┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
CPU time: Total 40736ms Percentage 12.5%
User time: Total 40698ms Percentage 12.5%
Machine time: Total 326048ms Percentage 100.0%
Real time: 40756ms
I risultati del monitoraggio dei thread è molto simile a quello per collatz, sempre per un singolo thread. Anche le attività dei core non mostrano differenze sostanziali,
Proviamo ora con un numero di thread pari al numero di processori e un eguale numero di task,
test("numPrimes", -1, -1, CompIntensive::numPrimes, 1, 20_000_000, Long::sum);
ottenendo
Test numPrimes nThreads 8 nTasks 8
Interval [1, 20000000]:
Result: 1270608 Time: 10917ms
Period 100ms CPU time charts Levels 5
┤ ┃ ┃┃┃┃┃ ┃┃┃ ┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-1 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃╻▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁
┤ ┃┃┃┃┃┃┃┃ ┃┃┃┃ ┃┃┃┃┃┃┃ ┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃
┤ ┃┃┃┃┃┃ ┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-2 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃ ┃┃┃ ┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-3 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-4 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁
┤ ┃ ┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃ ┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃ ┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-5 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁▁▁▁▁▁▁▁▁▁▁▁▁▁
┤ ┃┃┃ ┃ ┃┃ ┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃ ┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-6 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁▁▁▁▁▁▁
┤ ┃ ┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃ ┃┃ ┃ ┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-7 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁▁▁
┤ ┃┃┃┃┃ ┃┃┃┃ ┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃ ┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-8 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
CPU time: Total 64322ms Percentage 73.6%
User time: Total 64249ms Percentage 73.6%
Machine time: Total 87339ms Percentage 100.0%
Real time: 10917ms
Qui si notano differenze significative rispetto allo stesso caso per collatz. Soprattutto per i primi thread il tempo di effettiva esecuzione non dura per tutto il tempo di calcolo. Addirittura il primo thread
ha un'esecuzione effettiva che dura meno della metà dell'intero calcolo. Inoltre il tempo totale di esecuzione effettiva è solamente il 73% del tempo macchina, invece dell'86% di collatz. Ciò è confermato anche dal monitoraggio dell'attività dei core,
Infatti verso gli ultimi secondi alcuni core non sembrano lavorare a pieno regime. D'altronde i sotto-intervalli non richiedono tutti lo stesso carico di lavoro. Il primo sotto-intervallo, quello relativo ai numeri più piccoli, sicuramente richiede molto meno lavoro dell'ultimo, quello relativo ai numeri più grandi. Per tentare di compensare ciò, possiamo aumentare il numero di sotto-intervalli e quindi anche il numero di task. Così ogni thread non eseguirà più un singolo task, cioè il calcolo di un singolo sotto-intervallo, ma più task e quindi più sotto-intervalli. In questo modo sotto-intervalli meno onerosi e quelli più onerosi si mescoleranno, sperando che possano compensarsi a vicenda. Proviamo con un numero di task e quindi sotto-intervalli pari a 10 volte il numero di processori (nel nostro caso 80 task),
test("numPrimes", -1, -10, CompIntensive::numPrimes, 1, 20_000_000, Long::sum);
ottenendo
Test numPrimes nThreads 8 nTasks 80
Interval [1, 20000000]:
Result: 1270608 Time: 9997ms
Period 100ms CPU time charts Levels 5
┤ ┃┃┃┃┃┃┃┃ ┃┃ ┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃ ┃┃┃┃┃┃
┤ ┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-1 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁▁▁▁▁▁
┤ ┃┃┃ ┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃ ┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-2 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁▁▁▁
┤ ┃┃┃┃ ┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃ ┃ ┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃ ┃┃┃ ┃ ┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-3 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃╻▁▁
┤ ┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃ ┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃
┤ ┃ ┃┃┃ ┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-4 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁▁
┤ ┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃ ┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-5 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃▁
┤ ┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃ ┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃ ┃┃┃┃┃
┤ ┃┃ ┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-6 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃ ┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃ ┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-7 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃ ┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃
┤ ┃┃ ┃┃ ┃ ┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
pool-1-thread-8 ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
CPU time: Total 71681ms Percentage 89.6%
User time: Total 71613ms Percentage 89.5%
Machine time: Total 79976ms Percentage 100.0%
Real time: 9997ms
È evidente il miglioramento del bilanciamento indicato sopratutto dalla percentuale di consumo del tempo macchina che adesso è salita all'89%. Si può notare che il tempo reale impiegato dal calcolo è migliorato ma non quanto ci si sarebbe potuti aspettare dal netto miglioramento dell'uso del tempo macchina. L'attività dei core mostra anch'essa il migliorato bilanciamento,
Non sembra esserci ulteriore spazio per il miglioramento. Nel momento in cui i processori appaiono lavorare tutti a pieno regime non possiamo sperare di ottenere miglioramenti suddividendo il lavoro in qualche altro modo. Abbiamo già ottenuto il massimo che potevamo ottenere fermi restando l'architettura hardware/software e l'algoritmo del calcolo.
Nonostante la loro semplicità i due esempi discussi mettono in evidenza alcune caratteristiche che hanno valenza generale. Per migliorare l'efficienza di task computation-intensive sono necessari più processori e il lavoro deve essere suddiviso tra i diversi processori. La suddivisione deve bilanciare il più possibile il carico di lavoro eseguito da ogni processore per evitare di avere tempi morti su qualche processore. Inoltre, non ci sono ricette che permettono di determinare a priori il modo migliore di parallelizzare un task. La dipendenza dall'architettura hardware/software rende necessarie delle sperimentazioni per calibrare i vari parametri. In generale però si può dire che usare più thread del numero di processori disponibili non porta alcun vantaggio mentre il numero di task in cui è suddiviso il compito originale può essere maggiore per bilanciare meglio il carico di lavoro dei processori.
Gli esempi di programmazione concorrente visti finora non richiedono uno scambio di dati tra i thread in esecuzione. Né richiedono accesso a dati condivisi mutabili, cioè che possono essere modificati durante l'esecuzione dei thread. Però spesso è conveniente poter scambiare dati tra thread o condividere dati mutabili, e talvolta è indispensabile. Si pensi ad esempio a un sistema software che deve gestire le transazioni di una banca effettuate tramite sportelli, bancomat, siti online, ecc. È chiaro che il sistema usa molti processi o thread di esecuzione che possono accedere a dati condivisi (la base di dati della banca) sia in lettura che in scrittura. Mentre un thread sta accedendo a un certo conto corrente e magari lo sta aggiornando a seguito di un prelievo un altro thread potrebbe accedere allo stesso conto corrente per fare un versamento. Se i due thread non sono propriamente sincronizzati i due aggiornamenti potrebbero non avvenire in modo corretto lasciando il conto corrente in uno stato inconsistente. Come si vede dalla figura qui sotto
le istruzioni di due thread che accedono allo stesso conto corrente non sono sincronizzate e si intrecciano in un modo tale che solamente il secondo aggiornamento ha effetto mentre quello del primo thread viene perso.
Una situazione, come quella sopra descritta, in cui il risultato dipende da come avviene l'intreccio delle esecuzioni di thread concorrenti è chiamata race condition. Il nome deriva dal fatto che il risultato dipende da quale thread "vince" la corsa (race). Chiaramente è una situazione di errore perché non si vuole che il risultato cambi a seconda dell'ordine con cui sono eseguiti i passi dei thread concorrenti.
Per esaminare il problema della race condition con un esempio concreto ma molto semplice consideriamo un generatore di numeri distinti che possono essere richiesti da thread diversi. Potrebbe essere utile per generare numeri che devono essere unici perché servono ad identificare risorse, ad esempio file o altri oggetti. Definiamo un'interfaccia per i generatori così che possiamo cambiarne agevolmente l'implementazione e diamo anche una semplice implementazione in una nuova classe TestSync in mp.concur.
/** Classe per testare la sincronizzazione di threads */
public class TestSync {
/** Un generatore di interi distinti */
public interface Gen {
/** @return un intero sempre differente */
int getNext();
}
/** Implementazione semplice di {@link Gen} */
public static class SimpleGen implements Gen {
@Override
public int getNext() { return counter++; }
private int counter = 0;
}
}
A questo punto definiamo un metodo che mette alla prova un generatore con un esecutore che gestisce un certo numero di thread che eseguono un certo numero di task ognuno dei quali invoca il generatore e ne ritorna il risultato. Alla fine il metodo controlla se i numeri ritornati dai task sono tutti diversi.
/** Mette alla prova un generatore con un dato numero di thread e task.
* @param g un generatore
* @param nThreads numero thread
* @param nTasks numero task */
public static void test_Gen(Gen g, int nThreads, int nTasks) {
out.println("Threads: "+nThreads+" Tasks: "+nTasks);
ExecutorService exec = Executors.newFixedThreadPool(nThreads);
List<Future<Integer>> tasks = new ArrayList<>();
Set<Integer> vals = new HashSet<>();
for (int i = 0; i < nTasks; i++)
tasks.add(exec.submit(g::getNext));
for (Future<Integer> t : tasks)
try {
vals.add(t.get());
} catch (InterruptedException | ExecutionException e) {}
exec.shutdown();
out.println("Valori ripetuti: " + (nTasks - vals.size()));
}
Ogni task semplicemente chiede il prossimo numero al generatore e lo ritorna. I numeri ritornati dai task sono inseriti in un insieme così da poter controllare che alla fine ve ne siano tanti distinti quanti sono i task. Se questo non accade vuol dire che due o più thread hanno ottenuto lo stesso numero. Proviamo con un solo thread e un milione di task.
public static void main(String[] args) {
test_Gen(new SimpleGen(), 1, 1_000_000);
}
Otteniamo
Threads: 1 Tasks: 1000000
Valori ripetuti: 0
Quindi è andato tutto bene, ogni task ha ottenuto un numero diverso così come deve essere. Però proviamo adesso con due thread e con un numero inferiore di task
test_Gen(new SimpleGen(), 2, 10_000);
Potremmo ottenere un risultato del tipo
Threads: 2 Tasks: 10000
Valori ripetuti: 8
Ci sono valori ripetuti, questo vuol dire che alcuni task hanno ottenuto lo stesso numero. Se proviamo a ripetere l'esecuzione probabilmente otterremo numeri diversi di valori ripetuti. Come è potuto accadere? L'istruzione return counter++; sembra essere monolitica, cioè un blocco indivisibile. Ma non è così, in realtà sono tre operazioni:
countercounterQuindi può accadere che le esecuzioni di due thread si intreccino similmente al caso del conto corrente. Ad esempio, se ad un dato momento counter ha valore 8 e due thread invocano getNext in rapida successione. Il primo thread legge il valore 8 e prima che possa incrementarne il valore il secondo thread legge il valore di counter ottenendo anch'esso il valore 8. Entrambi i thread otterranno il valore 8. Si tratta quindi di una race condition.
synchronizedNella situazione del generatore e più in generale in una qualsiasi race condition affinché il funzionamento sia corretto dobbiamo garantire che una certa sequenza di passi avvenga in modo indivisibile, ovvero in modo atomico. L'esecuzione di una sequenza di passi è atomica se non può mai accadere che un thread esegue una parte della sequenza e prima che finisce qualche altro thread inizia ad eseguire la stessa sequenza di passi. Per garantire ciò ci sono come vedremo vari meccanismi. Quello che è direttamente supportato dal linguaggio Java è la sincronizzazione tramite la parola chiave synchronized che può essere usata come modificatore di un metodo. Si possono sincronizzare sia metodi statici che metodi dell'oggetto. L'effetto per i metodi dell'oggetto è il seguente. Se un thread T invoca un metodo con modificatore synchronized su un oggetto obj finché tale esecuzione non finisce, cioè il thread T non esce dal blocco sincronizzato del metodo, nessun altro thread può iniziare l'esecuzione di un qualsiasi metodo sincronizzato dell'oggetto obj. Quindi l'effetto è esattamente uguale a quello che si avrebbe se il thread T ottenesse un lock relativamente all'oggetto obj. Finché detiene il lock nessun altro thread può ottenere lo stesso lock5. In realtà il modificatore synchronized è proprio equivalente a ottenere un lock sull'oggetto obj. Ma su questo torneremo più avanti. Per adesso vediamo subito un esempio implementando il nostro generatore usando la sincronizzazione.
/** Implementazione thread safe di {@link Gen} che usa la sincronizzazione */
public static class SyncGen implements Gen {
@Override
public synchronized int getNext() { return counter++; }
private int counter = 0;
}
Proviamo il generatore sincronizzato con 1000 thread e un milione di task
test_Gen(new SyncGen(), 1000, 1_000_000);
E otteniamo un comportamento corretto, tutti i task prendono numeri diversi.
Threads: 1000 Tasks: 1000000
Valori ripetuti: 0
La sincronizzazione dei metodi, ma anche la sincronizzazione in generale, può ostacolare l'efficienza perché può causare attese più o meno lunghe da parte dei thread che competono per ottenere lo stesso lock. Ad esempio se un metodo sincronizzato ha un tempo di esecuzione piuttosto lungo, quando un thread ne acquisisce il lock e un altro thread cerca di invocare lo stesso metodo deve attendere, senza poter fare nient'altro per il lungo tempo di esecuzione del metodo. La sincronizzazione dei metodi da questo punto di vista può essere particolarmente inefficiente sopratutto quando sottopone alla sincronizzazione un blocco di codice troppo grande, cioè l'intero corpo di un metodo. Per sincronizzare un blocco di codice qualsiasi si può usare il costrutto
synchronized (this) {
blocco di codice da sincronizzare
}
Il costrutto si può usare con un qualsiasi oggetto obj al posto di this, in tal caso il lock sarà relativo a obj. Così si può sincronizzare solamente il blocco di codice che necessita essere sincronizzato.
In alcune situazioni un'alternativa alla sincronizzazione sono le variabili atomiche. Una variabile atomica è una variabile che permette di effettuare alcune combinazioni di operazioni molto comuni, come nel caso del generatore un valore che deve essere letto e poi incrementato, in modo atomico, esattamente come se fossero in un blocco sincronizzato. Il package java.uti.concurrent.atomic ha diversi tipi di variabili atomiche. Nel nostro caso possiamo usare un AtomicInteger e il suo metodo int getAndIncrement() che in modo atomico incrementa il valore e ritorna il valore prima dell'incremento.
/** Implementazione thread safe di {@link Gen} che usa una variabile atomica */
public static class AtomGen implements Gen {
@Override
public int getNext() { return counter.getAndIncrement(); }
private final AtomicInteger counter = new AtomicInteger(0);
}
Provando questa versione del generatore
test_Gen(new AtomGen(), 1000, 1_000_000);
otteniamo il comportamento corretto
Threads: 1000 Tasks: 1000000
Valori ripetuti: 0
Ovviamente le race condition possono accadere solamente in relazione a dati condivisi, da più thread, e mutabili. Se un valore non è condiviso, come quello di una variabile locale di un metodo, non può mai portare a una race condition. Parimenti un valore anche condiviso se non è mutabile, non può provocare race condition perché nessun thread può modificarne il valore.
Le esecuzioni concorrenti possono provocare, sempre in relazione a valori condivisi e mutabili, anche un altro tipo di problemi più sorprendenti di quelli delle race condition. Consideriamo il semplice esempio di una classe Do con un metodo doSomething() che esegue un qualche task e appena lo finisce imposta a true un campo done e un metodo waitForDone() che semplicemente attende che il task sia stato completato monitorando il valore del campo done,
public static class Do {
public void doSomething() {
for (long i = 0 ; i < 1_000_000_000 ; i++) ; // Esegue un qualche task
done = true; // Segnala che ha completato il task
out.println("Done!");
}
public void waitForDone() {
out.println("Start waiting");
while (!done) ; // Aspetta che il task sia stato completato
out.println("End waiting");
}
private boolean done = false;
}
Ora facciamo eseguire doSomething() a un thread e waitForDone() ad un altro thread. Per osservare meglio l'esecuzione monitoriamo i due thread con ThreadsMonitor.
public static void test_Do() {
Do d = new Do();
ThreadsMonitor monitor = new ThreadsMonitor(50,true,5,out,s->s.startsWith("*"));
new Thread(d::doSomething, "*doSomething").start();
new Thread(d::waitForDone, "*waitForDone").start();
try {
Thread.sleep(3000);
} catch (InterruptedException e) {}
monitor.stop();
}
public static void main(String[] args) {
test_Do();
}
Provandolo otteniamo
Start waiting
Done!
Period 50ms CPU time charts Levels 5
┤ ┃┃┃┃┃
┤ ┃┃┃┃┃
┤ ┃┃┃┃┃
┤ ┃┃┃┃┃
*doSomething ┤.┃┃┃┃┃..................................................
┤ ┃┃┃┃┃┃┃ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃ ┃┃┃ ┃┃┃┃ ┃┃┃ ┃┃┃ ┃ ┃┃┃┃┃┃┃ ┃ ┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
┤ ┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
*waitForDone ┤.┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃┃
CPU time: Total 3182ms Percentage 13.2%
User time: Total 3173ms Percentage 13.2%
Machine time: Total 24028ms Percentage 100.0%
Real time: 3003ms
Come si vede il thread *doSomething completa il task e termina ma il thread *waitForDone non termina (infatti dobbiamo bloccare il programma). Il monitor ci mostra che il thread è stato continuamente ed effettivamente in esecuzione anche dopo che il thread *doSomething è terminato, quindi ha letto il campo done per moltissime volte dopo che è stato posto a true. E allora come è possibile che apparentemente sia rimasto nel loop while (!done) ;? Il problema è la visibilità del valore del campo done. Il thread *waitForDone non vede il valore che è stato aggiornato dall'altro thread. Le cause di questo fenomeno possono essere molteplici ma hanno tutte a che fare con vari tipi di ottimizzazione come caching6 e instruction reordering7 operate dal compilatore, la JVM e il sistema sottostante. Nel nostro caso specifico, siccome per default la JVM assume che non ci siano accessi concorrenti alla memoria, potrebbe aver operato un riordinamento di while (!done) ; nel seguente modo:
if (!done) while (true) ;
Infatti, assumendo che non ci siano accessi concorrenti alla memoria, il valore di done non può essere modificato durante le iterazioni del while. Per garantire la visibilità bisogna che la JVM sia informata che ci possono essere accessi concorrenti alla memoria e possa così inibire tali ottimizzazioni. Un modo è usare la sincronizzazione perché una qualsiasi modifica effettuata prima di rilasciare un lock è visibile a qualsiasi thread che successivamente acquisisce lo stesso lock. Oppure si può usare il modificatore volatile che comunica al compilatore e alla JVM che il valore di quel campo può essere soggetto a cambiamenti di valore operati in modo concorrente. Nel nostro caso basta aggiungere volatile alla dichiarazione del campo done,
private volatile boolean done = false;
e provando si vede che il thread *waitForDone adesso vede il valore aggiornato. La visibilità del valore è garantita anche dal modificatore final. Se il valore di un campo non cambia mai ma è letto da thread diversi da quello che ha creato l'oggetto a cui appartiene, la visibilità del suo valore, seppur costante, non è garantita se non è dichiarato final. Infine è bene sottolineare che i modificatori volatile e final garantiscono solamente che il valore corretto di un campo è visibile a tutti i thread ma non hanno nessun effetto riguardo alle race condition.
La proprietà che una corretta programmazione concorrente dovrebbe garantire è chiamata thread safety (sicurezza/protezione dei thread). Questa richiede che il programma (concorrente) si comporti correttamente qualunque sia l'ordine con cui sono eseguiti i passi dei thread concorrenti determinata dal sottostante runtime system. Come abbiamo già avuto modo di vedere tutto dipende dai dati condivisi e dagli accessi concorrenti ad essi. Per cercare di raggiungere l'obiettivo della thread safety, tenendo nel giusto conto anche le esigenze di efficienza, si possono adottare le seguenti strategie riguardanti l'uso e l'accesso dei dati condivisi.
Se un campo mutabile è accessibile da più di un thread, tutti gli accessi al campo devono essere eseguiti sotto lo stesso lock.Il principio è stringente per tutti i casi in cui il valore del campo può essere mutato in modo qualsiasi e quindi anche tramite aggiornamenti che dipendono dal valore precedente. Solamente in casi particolari, come quello della classe
Do, si può usare volatile al posto della sincronizzazione. Però in caso di dubbio è meglio usare la sincronizzazione.
Quello che abbiamo visto sulla sincronizzazione è solamente l'inizio. In seguito approfondiremo l'uso di tali meccanismi e ne vedremo altri.
[Fattori] Scrivere un metodo che preso in input un intervallo di interi [a, b] ritorna il numero medio di fattori primi dei numeri nell'intervallo. Implementare una versione parallela e confrontarla con la versione sequenziale.
[HappyNumbers] Scrivere un metodo che preso in input un intervallo di interi [a, b] ritorna il numero di happy number (vedere HappyNumber per la definizione) contenuti nell'intervallo. Implementare una versione parallela o usare parallel e confrontare le due versioni.
[Gen] Modificare il metodo per testare i generatori in modo che prenda in input anche un intero period, void test_Gen(Gen g, int nThreads, int nTasks, int period), e che lo usi per fare il monitoraggio dei thread tramite ThreadsMonitor con levels = 10 e selezionando solamente i thread che appartengono all'esecutore. Provarlo con SyncGen() e AtomGen() con un numero non troppo grande di thread, ad es. 10 e circa 100_000 task. Che differenze si osservano? Perché i thread non lavorano a pieno regime neanche se sono meno del numero dei processori? Perché il tempo di CPU è significativamente più alto del tempo utente?
[CC] Scrivere un programma che simula operazioni su un conto corrente da parte di più thread concorrentemente. Il conto corrente è un oggetto con due metodi double getBalance e void setBalance(double b). Ogni task legge l'attuale totale con getBalance e lo aggiorna con un versamento o un prelievo tramite setBalance. Il programma deve verificare che alla fine il saldo del conto corrente è corretto, cioè che risulti uguale alla somma algebrica del saldo iniziale e di tutti i versamenti e prelievi effettuati.
[Bonifici] Usando conti correnti definiti come nell'esercizio precedente. Scrivere un programma che simula bonifici concorrenti tra due conti correnti, cioè un prelievo da un conto e un versamento di pari importo sull'altro conto. Il programma deve quindi usare due oggetti di tipo conto corrente. Inoltre deve verificare che alla fine i saldi dei due conti correnti siano corretti.
[Do] Cercare di rendere corretto il comportamento della classe Do usando la sincronizzazione o le variabili atomiche.
[FibDispenser] Modificare l'implementazione della classe FibDispenser qui sotto in modo che rispetti le specifiche dei javadoc e quindi diventi thread-safe. L'implementazione concorrente dovrebbe essere anche efficiente. Chiaramente l'implementazione originale è corretta solo se usata in un solo thread.
/** Un FibDispenser è un dispensatore di numeri di Fibonacci. Ad ogni richiesta
* ritorna il prossimo numero di Fibonacci senza ripetizioni e senza salti. Le
* richieste possono essere eseguite anche in modo concorrente. */
public static class FibDispenser {
/** Crea un FibDispenser che parte da F_n, cioè la prima invocazione del
* metodo next() ritorna l'n-esimo numero di Fibonacci F_n.
* @param n indice del primo numero di Fibonacci */
public FibDispenser(int n) {
this.n = n;
}
/** Ritorna il prossimo numero di Fibonacci. Ad ogni invocazione anche
* concorrente deve ritornare un numero di Fibonacci differente. Inoltre
* non deve fare salti, cioè se in una invocazione ritorna F_k e in una
* successiva F_m, allora devono esserci (tra le due invocazioni) delle
* invocazioni che ritornano F_k+1, F_k+2,...,F_m-1.
* @return il prossimo numero di Fibonacci senza ripetizioni e senza salti */
public BigInteger next() {
BigInteger a = BigInteger.valueOf(0);
BigInteger b = BigInteger.valueOf(1);
for (long i = 1; i < n; i++) {
BigInteger c = b.add(a);
a = b;
b = c;
}
n++;
return b;
}
private int n;
}
28 Apr 2016
Assumiamo che l'operazione di combinazione dei risultati sia commutativa altrimenti il risultato finale dipende dall'ordine con cui sono ricombinanti i risultati dei sotto-intervalli e questo può ostacolare l'efficacia della parallelizzazione e comunque richiede una particolare attenzione all'ordine di ricombinazione rendendo l'algoritmo di parallelizzazione più difficile da implementare.↩
In realtà si tratta di una stima del tempo di esecuzione che può essere affetta da un errore anche del 10%.↩
Estrarre dal jar, con il solito comando jar -xf ThreadsMonitor.jar, il file sorgente ThreadsMonitor.java e copiarlo nella directory del package mp.concur.↩
Ogni colonnina ha al massimo 15 tacche, se si sommano le tacche delle 8 colonnine relative ad uno dato secondo, queste non superano mai 15 o quasi.↩
Un thread acquisisce il lock di un metodo marcato synchronized non appena l'esecuzione del metodo inizia e lo rilascia non appena l'esecuzione termina, in qualsiasi modo questo accada. Se un thread invoca il metodo marcato synchronized mentre il relativo lock è detenuto da un altro thread, rimane in attesa nello stato BLOCKED finché non riesce ad acquisire il lock. ↩
Per migliorare l'efficienza i compilatori e il sistema che gestisce le memorie di una macchina possono mantenere copie di valori in memorie cache. Questo per evitare di dover leggere tali valori da locazioni “più lontane” che richiedono tempi d'accesso più lunghi. Ovviamente da qui poi nascono i problemi relativi alla coerenza tra i valori cached e quelli originali.↩
Il compilatore, la JVM e il sistema dei processori possono riordinare le istruzioni da eseguire per renderne più efficiente l'esecuzione mantenendo il risultato corretto.↩