[C] Chiarimento sui Threads

[Balop]

Ciao a tutti, per ora sto imparando ad usare i threads in C, però vorrei un chiarimento a livello teorico da qualcuno che li sa usare:
da quanto ha detto il prof, ho capito che si usano i threads perchè dovrebbero essere meno dispendiosi a livello di risorse perchè sono parti dello stesso processo e inoltre dovebbero lavorare contemporaneamente giusto?
Solo che io ho fatto un programmino per il calcolo dei numeri primi e fra l'uso dei threads e delle normali funzioni non c'è differenza a livello di tempo, dipende dal fatto che ho usato i join (altrimenti non funzionava) giusto?
Io volevo fare in modo che i 4 threads che ho creato mi cercassero contemporaneamente i numeri primi in modo da ridurre ad 1/4 il tempo di ricerca che si avrebbe richiamando 4 volte la funzione ricerca... ma si vede che non ho saputo usarli bene... per questo prima di scervellarmi chiedo se la teoria dei threads è quella che ho capito o no... ed eventualmente se qualcuno mi può anche illuminare su come modificare il programma che ho fatto (poi lo posto) come avevo in mente di farlo io..

Grazie

[tuccio`]

se hai un processore con più core (fisici o logici, cosa molto probabile nel 2011 :asd: ) 2 thread possono essere seguiti in maniera parallela, ovviamente tocca al sistema operativo schedularli su processori diversi (se hai più thread che core ovviamente vanno solo a dividersi i core), ovviamente sta a te dividere un compito in modo tale che i thread possano lavorare in maniera abbastanza indipendente da essere efficienti

comunque l'altro vantaggio dei thread rispetto ai processi è che condividono la memoria, che non è cosa da poco

[Balop]

allora facendo un programma come questo:

//------ con i threads
pthread_t thread1;
pthread_t thread2;
pthread_t thread3;
pthread_t thread4;

pthread_create (&thread1,NULL,&trovaprimo,&num1);
pthread_create (&thread2,NULL,&trovaprimo,&num2);
pthread_create (&thread3,NULL,&trovaprimo,&num3);
pthread_create (&thread4,NULL,&trovaprimo,&num4);

pthread_join (thread1, (void *) &primo1);
pthread_join (thread2, (void *) &primo2);
pthread_join (thread3, (void *) &primo3);
pthread_join (thread4, (void *) &primo4);

//------ con le funzioni
int candidate1= (int)trovaprimo(&num1);
int candidate2= (int)trovaprimo(&num2);
int candidate3= (int)trovaprimo(&num3);
int candidate4= (int)trovaprimo(&num4);


con i threads non dovrebbe trovare più velocemente gli n-esimi numeri primi richiesti rispetto all'ultima parte dove si richiama 4 volte la stessa funzione??

[tuccio`]

cosa fa trovaprimo?

[Balop]

cosa fa trovaprimo?

trova l'n-esimo numero primo.
per esempio se come argomento passo 4 mi trova 5, se passo 5 mi trova 7 ecc.. se passo 15000 mi trova il 25000° numero primo, quindi ci sta un po..
per vedere giusta la differenza ieri ho fatto la prova a cercare il 150000°, 149500°, 149000°, 148500°,
entrambi i metodi ci sono stati circa 20 minuti per la ricerca, ma con i threads addirittura c'è stato più che con le funzioni!!
quando invece in teoria ci dovrebbe impiegare il tempo che ci sta per trovare quello maggiore (perchè gli altri threads dovrebbero finire prima..), invece con le funzioni ogni volta deve cominciare da capo..

ti posto l'intero programma dove c'è anche la funzione time per calcolare i tempi ed ho messo anche una printf in modo da fare stampare subito quando trova i numeri..

#include <pthread.h>
#include <stdio.h>
#include <time.h>


void *trovaprimo (void *num){
int n = *((int *)num);
int i;
int candidate=1;

while(1){
int var=1;
for (i=2; i<=(candidate/2); i++){
if(candidate%i == 0) {
var=0;
break;
}
}
if (var){
n--;
if(n==0){
printf("Il %d° numero primo è %d\n", *((int *)num), candidate);
return (int *)candidate;
}
}
candidate++;
}//fine while
}

int main (){
time_t tempo1, tempo2, tempo3, tempo4;
int tempotrascorso1;
int tempotrascorso2;


int num1, num2, num3, num4, primo1, primo2, primo3, primo4;
printf("inserire n-esimo numero prima che si cerca: ");
scanf("%d", &num1);
printf("\ninserire n-esimo numero prima che si cerca: ");
scanf("%d", &num2);
printf("\ninserire n-esimo numero prima che si cerca: ");
scanf("%d", &num3);
printf("\ninserire n-esimo numero prima che si cerca: ");
scanf("%d", &num4);


pthread_t thread1;
pthread_t thread2;
pthread_t thread3;
pthread_t thread4;

pthread_create (&thread1,NULL,&trovaprimo,&num1);
pthread_create (&thread2,NULL,&trovaprimo,&num2);
pthread_create (&thread3,NULL,&trovaprimo,&num3);
pthread_create (&thread4,NULL,&trovaprimo,&num4);

tempo1= time(NULL);
pthread_join (thread1, (void *) &primo1);
pthread_join (thread2, (void *) &primo2);
pthread_join (thread3, (void *) &primo3);
pthread_join (thread4, (void *) &primo4);
tempo2= time(NULL);

printf("\nCon i threads:\n");
printf("Il %d° numero primo è %d\n", num1, primo1);
printf("Il %d° numero primo è %d\n", num2, primo2);
printf("Il %d° numero primo è %d\n", num3, primo3);
printf("Il %d° numero primo è %d\n", num4, primo4);

tempotrascorso1 = difftime(tempo2, tempo1);
printf("Sono trascorsi %d secondi!\n\n", tempotrascorso1);

tempo3= time(NULL);
int candidate1= (int)trovaprimo(&num1);
int candidate2= (int)trovaprimo(&num2);
int candidate3= (int)trovaprimo(&num3);
int candidate4= (int)trovaprimo(&num4);
tempo4= time(NULL);

tempotrascorso2 = difftime(tempo4, tempo3);
printf("\nCon le funzioni:\n");
printf("Il %d° numero primo è %d\n", num1, candidate1);
printf("Il %d° numero primo è %d\n", num2, candidate2);
printf("Il %d° numero primo è %d\n", num3, candidate3);
printf("Il %d° numero primo è %d\n", num4, candidate4);
printf("Sono trascorsi %d secondi!\n\n", tempotrascorso2);

return 0;
}

[WarDuck]

Non tutti gli algoritmi sono parallelizzabili.

In particolare il tuo trova-primo non sfrutta in alcun modo le informazioni generate in precedenza, ogni volta ricomincia da 2 per testare se l'i-esimo numero è primo.

Praticamente esegui 4 volte la funzione per numeri diversi, e non sfrutti nessuna delle informazioni generate prima.

Comunque indenta meglio il codice perché così è illeggibile.

Prima di provare con i thread ti suggerisco di ottimizzare il codice attuale.

[Balop]

Non tutti gli algoritmi sono parallelizzabili.

In particolare il tuo trova-primo non sfrutta in alcun modo le informazioni generate in precedenza, ogni volta ricomincia da 2 per testare se l'i-esimo numero è primo.

Praticamente esegui 4 volte la funzione per numeri diversi, e non sfrutti nessuna delle informazioni generate prima.

Comunque indenta meglio il codice perché così è illeggibile.

Prima di provare con i thread ti suggerisco di ottimizzare il codice attuale.

quindi per usare i threads al meglio si deve cercare di sfruttarli fra di loro.. allora non è come pensavo che lavorassero contemporaneamente...

per quanto riguarda l'indentatura è scritto così perchè uso linux con i semplici file di testo e li scrive senza aggiungere spaziatura automatica.. ero abituato male con eclipse che usavo per il java...

inoltre qualcuno ha qualche suggerimento su come si potrebbero sfruttare i threads in questo esempio?

[tuccio`]

lavorano contemporaneamente, dipende dallo scheduler, onestamente lì è strano che tu non abbia proprio vantaggi, certo non è ottimizzato benissimo, ma comunque già se 2 di quei 4 venissero eseguiti contemporaneamente dovresti avere un vantaggio

comunque... 5 sarebbe il quarto numero primo? :asd:

[Balop]

lavorano contemporaneamente, dipende dallo scheduler, onestamente lì è strano che tu non abbia proprio vantaggi, certo non è ottimizzato benissimo, ma comunque già se 2 di quei 4 venissero eseguiti contemporaneamente dovresti avere un vantaggio

comunque... 5 sarebbe il quarto numero primo? :asd:

se i numeri primi sono 1 2 3 5 7 11 13 17 19... il 4° numero primo è 5..... :mbe:
ovviamente ho tenuto conto anche del numero 1 come primo...

comunque bo... non riesco a capire com'è che non abbia vantaggi.....

[tuccio`]

se i numeri primi sono 1 2 3 5 7 11 13 17 19... il 4° numero primo è 5..... :mbe:ex falso sequitur quodlibet ^_^

[Balop]

ex falso sequitur quodlibet ^_^

infatti ho specificato sotto che ho tenuto conto del numero 1 come primo... anche se fooorse... ma vabbè... la cosa importante era un'altra!! =)

[WarDuck]

quindi per usare i threads al meglio si deve cercare di sfruttarli fra di loro.. allora non è come pensavo che lavorassero contemporaneamente...

per quanto riguarda l'indentatura è scritto così perchè uso linux con i semplici file di testo e li scrive senza aggiungere spaziatura automatica.. ero abituato male con eclipse che usavo per il java...

inoltre qualcuno ha qualche suggerimento su come si potrebbero sfruttare i threads in questo esempio?

se i numeri primi sono 1 2 3 5 7 11 13 17 19... il 4° numero primo è 5..... :mbe:
ovviamente ho tenuto conto anche del numero 1 come primo...

comunque bo... non riesco a capire com'è che non abbia vantaggi.....

NOTA: 1 non è un numero primo.

I thread sono semplici esecutori a cui va detto esplicitamente quello che devono fare e comunque la loro utilità dipende dal contesto.

Ad esempio avresti più facilità a vedere i vantaggi del multi-threading nell'ordinamento merge-sort, piuttosto che in questo caso.

Non hai vantaggi perché sostanzialmente il tuo algoritmo non sfrutta il parallelismo, poi ho visto ora che hai messo JOIN, che in sostanza serve per aspettare che gli altri thread finiscano (praticamente lavori sequenzialmente con in più tutto l'overhead dei thread).

Al di là dei thread, se vuoi migliorare le prestazioni del tuo algoritmo dovresti prima di tutto cercare di sfruttare le informazioni che hai.

Se sai che 7 è il 4° numero primo è perché prima hai calcolato gli altri. Dunque ti conviene crearti una tabella (un array ad esempio) di quelli già calcolati.

Per esempio avresti che:


index 1 2 3 4 5
value 2 3 5 7 11


Dunque sia X l'indice che vuoi cercare:

se X < lunghezza array: ritorna l'elemento array[X]
se X > lunghezza array: calcola a partire dall'ultimo elemento dell'array


La tua funzione invece riparte sempre da 0 nel calcolare l'i-esimo primo, dunque ti ricalcoli quelli che hai già calcolato.

[Balop]

NOTA: 1 non è un numero primo.

I thread sono semplici esecutori a cui va detto esplicitamente quello che devono fare e comunque la loro utilità dipende dal contesto.

Ad esempio avresti più facilità a vedere i vantaggi del multi-threading nell'ordinamento merge-sort, piuttosto che in questo caso.

Non hai vantaggi perché sostanzialmente il tuo algoritmo non sfrutta il parallelismo, poi ho visto ora che hai messo JOIN, che in sostanza serve per aspettare che gli altri thread finiscano (praticamente lavori sequenzialmente con in più tutto l'overhead dei thread).

Al di là dei thread, se vuoi migliorare le prestazioni del tuo algoritmo dovresti prima di tutto cercare di sfruttare le informazioni che hai.

Se sai che 7 è il 4° numero primo è perché prima hai calcolato gli altri. Dunque ti conviene crearti una tabella (un array ad esempio) di quelli già calcolati.

Per esempio avresti che:


index 1 2 3 4 5
value 2 3 5 7 11


Dunque sia X l'indice che vuoi cercare:

se X < lunghezza array: ritorna l'elemento array[X]
se X > lunghezza array: calcola a partire dall'ultimo elemento dell'array


La tua funzione invece riparte sempre da 0 nel calcolare l'i-esimo primo, dunque ti ricalcoli quelli che hai già calcolato.

Intanto grazie per la proposta, ma oltre all'algoritmo che può essere più o meno efficiente (il tuo è palesemente migliore), sto imparando ad usare i threads e a che c'ero volevo vederne l'utilità pratica con questo algoritmo parzialmente modificato da un esempio preso dal libro..

per quanto riguarda i JOIN, li ho dovuti aggiungere perchè altrimenti non sapevo come fare ritornare i valori trovati nel main (ovviamente senza utilizzare quella printf dentro la funzione trovaprimo che era solo per vedere quando trovava i numeri..).
sai come potrei fare ritornare il valore trovato dai threads dentro il main?

[*andre*]

se vuoi trovare i numeri primi fino ad un certo numero, prova ad implementare questo algoritmo http://it.wikipedia.org/wiki/Crivello_di_Eratostene.

Lo puoi dividere efficentemente in vari threads.
I vantaggi o svantaggi dell'utilizzo dei thread conviene che li testi con un numero molto grande di operazioni, se no oltre a non notare vantaggi a volte noti pure un decadimento delle prestazioni.

[tuccio`]

la join fa aspettare il main thread che la chiama aspettando che finiscano i 4, non gli altri.. quindi non è che abbia una spiegazione diversa da "lo scheduler del tuo os fa schifo :asd: " magari ha creato troppi thread rispetto ai core che può usare l'os? anche se usi 2 (e non 4) thread è meglio con il flusso singolo che con i thread?

ps: se la cpu che stai usando è l'e8400 (leggo la firma) è probabile che vada meglio con 2 thread anziché 4, certamente 4 thread non potranno andare in parallelo.. se ci metti che comunque l'uso di thread comporta uno overhead dovuto allo scheduling, se non lo ammortizzi eseguendo davvero parallelamente, non hai nessun vantaggio

[Balop]

no ragazzi studio con il portatile e il processore è un i5 450m.
comunque ci avevo pensato anche io che fosse colpa del join (ragà ve l'ho scritto pure nel primo post ma nessuno ci ha fatto caso!! xD)
ma come ho scritto poco sopra, senza usarlo non saprei come fare tornare il valore trovato dentro il main, qualcuno sa come fare?
di pome lo rivedo un po.... vedo di provare con una variabile globale in modo da eliminare i join...

[tuccio`]

non capisco quale sarebbe il problema nel join :asd:

[Balop]

non capisco quale sarebbe il problema nel join :asd:

i join hanno la funzione di aspettare la fine del thread passato come argomento...
però ora che ci penso, aspetta il thread passato come argomento prima di deallocare le risorse, non prima di essere eseguito...
infatti con la printf messa nella funzione trovaprimo vedo che se passo per esempio 25, 10, 16, 5
mi trova prima il 5° poi il 10° poi il 16° e poi il 25°, quindi i threads funzionano,
invece con le funzioni mi trova i numeri per come glieli passo io, quindi prima il 25° poi il 10° ecc...

[WarDuck]

Ribadisco il concetto: il tuo problema è l'algoritmo che così com'è mi sembra poco parallelizzabile, join o non join, parametri passati o meno tra thread...

[Rsk]

Come ti hanno già suggerito, implementa il crivello di eratostene.
E' facilmente parallelizzabile.
Se hai n core e vuoi utilizzare n thread, puoi suddividere lo spazio dei numeri in n partizioni e assegnare ad ogni thread un set di S/n elementi su cui lavorare, dove S è il limite superiore del tuo insieme.

[tuccio`]

i join hanno la funzione di aspettare la fine del thread passato come argomento....appunto, tu hai 5 thread: il main thread che crea i thread, li avvia, ed aspetta che finiscano... gli altri 4 che dovrebbero lavorare in parallelo dovrebbero essere eseguiti intanto, e ci metteranno 4 tempi diversi: t1, t2, t3 e t4..

quindi in linea di principio:

comincia il main thread
avvia i 4 thread
fa la join sui 4, quindi aspetta circa max{t1, t2, t3, t4}
finisce

quindi diciamo che il grosso del tempo lo spende sulla join, quindi dovrebbe essere max{t1, t2, t3, t4} il tempo, senza considerare gli overhead dovuti al multithreading

invece con il single thread le chiami una alla volta in serie, quindi il tempo è t1 + t2 + t3 + t4

ora, posto che è chiaro che qui non serve il multithreading e potevi fare in mille modi, l'unica spiegazione possibile al fatto che ci mette di più con i thread, è che i 4 thread non vanno in parallelo, quindi per me dovresti provare con meno thread (2, ad esempio)

ps: visto che parlate del crivello di eratostene, c'è qualche limite superiore per il k-esimo primo che non conosco (cioè, ci sarà sicuramente, ce n'è qualcuno abbastanza vicino?).. voglio dire, voglio il k-esimo primo, con il crivello di eratostene posso calcolare i primi minori di n, questo n come lo scelgo?

[Balop]

edit

[Balop]

sono riuscito ad implementare il crivello di eratostene, in cui sfrutto 2 threads a ciascuno dei quali assegno una partizione n/2 sia per rieampire il vettore iniziale sia per cancellare i multipli.
la cosa che potrebbe essere migliorata è che il thread che cancella i multipli della seconda partizione comincia il controllo da 0, però trovando molti posti del vettore=0 passa subito avanti.

le stesse identiche funzioni le ho implementate senza usare i threads,
quindi anche la non perfetta efficienza nel cancellare i multipli della seconda partizione c'è pure qua..

in sintesi il risultato nel trovare i numeri primi da 2 a 500 milioni è:
con le funzioni 572 secondi
con i threads 600 secondi

28 secondi a favore delle funzioni!!!!

vabbè ci rinuncio....

[Rsk]

[edit]no

[Balop]

allora... o il mio pc va per i fatti suoi, o nelle slide ci sono esempi che non si possono applicare.. nelle slide c'è scritto:
http://img818.imageshack.us/img818/1295/immagineiqb.jpg (http://imageshack.us/photo/my-images/818/immagineiqb.jpg/)

mentre se realizzo questo stesso programma al pc non mi succede niente senza usare i mutex...
l'ho provato anche con 300 threads (di più mi dà segmentation fault..) ma mai dato valore finale inferiore a 0.. è normale?!?

questo è il programma pronto per essere compilato, se qualcuno lo vuole provare:
#include <stdio.h>
#include <malloc.h>
#include <pthread.h>
#include <string.h>
#define NUMTHREADS 300

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_t thread[NUMTHREADS];
int data;

void *decrementa (void *arg){
printf("Entra nella funzione il thread %d\n", *(int *)arg);
// pthread_mutex_lock (&mutex);
// printf("Ottiene il lock il thread %d\n", *(int *)arg);
// printf("Data= %d\n", data);
if (data>0) data--;
// pthread_mutex_unlock (&mutex);
}

int main (){
int i=0, *v;
v= (int *) malloc(2*NUMTHREADS * sizeof(int));
data= 1;
printf("Valore iniziale di data= %d\n", data);
for(i=0; i<NUMTHREADS; i++){
v[i]=i;
}
for(i=0; i<NUMTHREADS; i++){
pthread_create (&thread[i], NULL, &decrementa, &v[i]);
}

for(i=0; i<NUMTHREADS; i++){
pthread_join (thread[i], NULL);
}

printf("Valore finale di data= %d\n", data);
}

[Rsk]

mentre se realizzo questo stesso programma al pc non mi succede niente senza usare i mutex...
l'ho provato anche con 300 threads (di più mi dà segmentation fault..) ma mai dato valore finale inferiore a 0.. è normale?!?

questo è il programma pronto per essere compilato, se qualcuno lo vuole provare:
#include <stdio.h>
#include <malloc.h>
#include <pthread.h>
#include <string.h>
#define NUMTHREADS 300

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_t thread[NUMTHREADS];
int data;

void *decrementa (void *arg){
printf("Entra nella funzione il thread %d\n", *(int *)arg);
// pthread_mutex_lock (&mutex);
// printf("Ottiene il lock il thread %d\n", *(int *)arg);
// printf("Data= %d\n", data);
if (data>0) data--;
// pthread_mutex_unlock (&mutex);
}

int main (){
int i=0, *v;
v= (int *) malloc(2*NUMTHREADS * sizeof(int));
data= 1;
printf("Valore iniziale di data= %d\n", data);
for(i=0; i<NUMTHREADS; i++){
v[i]=i;
}
for(i=0; i<NUMTHREADS; i++){
pthread_create (&thread[i], NULL, &decrementa, &v[i]);
}

for(i=0; i<NUMTHREADS; i++){
pthread_join (thread[i], NULL);
}

printf("Valore finale di data= %d\n", data);
}


Se vuoi race conditions come se piovesse guarda le modifiche che ho effettuato al tuo codice.

void *decrementa (void *arg){
printf("Entra nella funzione il thread %d\n", *(int *)arg);
// pthread_mutex_lock (&mutex);
// printf("Ottiene il lock il thread %d\n", *(int *)arg);
// printf("Data= %d\n", data);

int u = rand()%5;
printf("Attesa= %d\n", u);
printf("Data = %d\n", data);
if (data>0) {
sleep(u);
data--;
}
// pthread_mutex_unlock (&mutex);
}


Creo i thread, li metto in pausa dopo che eseguono il controllo su data così lo scheduler può passare ad un altro thread..

In questo modo si ha la certezza di inconsistenza per la variabile "data", ma ricordati che, come hai sperimentato tu stesso, una race condition puo' anche non verificarsi mai.. dipende dalla sequenza di scheduling.. se è fortunata o meno