Fibbonaci utilizando Multithreading e Vector de Mutex

[FasTer]

Pessoal,

Preciso da vossa ajuda. Neste programa, tenho que executar o programa a partir do terminal e passar-lhe como argumento a quantidade de termos (n=[0..n]) que pretendo calcular da série de fibbonaci.

Tenho que utilizar um vector de Mutex e Multithreading para calcular individualmente esta série.

Por alguma razão que me transcende a 90% das vezes da-me o valor correcto contudo, 10% do output vem baralho.

Podem ajudar-me nesta questão? Este é um problema de sincronização.

Aqui está o código (praticamente finalizado).

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
int *vector; // dec vector global
pthread_mutex_t *mutex;
void *func(void*arg)
{
int n;
n=(int)arg;

if (n==0){
 vector[n]=0;
pthread_exit(0);
}

if (n==1){
 vector[n-1]= 0;
vector[n]= 1;
pthread_exit(0);
}

pthread_mutex_lock(&mutex[n-2]);
pthread_mutex_lock(&mutex[n-1]);


printf("tarefa %d",n);
vector[n]=vector[n-2]+vector[n-1];

pthread_mutex_unlock(&mutex[n-2]);
pthread_mutex_unlock(&mutex[n-1]);
pthread_mutex_unlock(&mutex[n]);


pthread_exit(0);


}




int main(int argc,char*argv[])
{

int i,n=0,j;
n=atoi(argv[1]);

vector= malloc(sizeof(int)*(n+1)); // aloca memória necessária para o array dinamico
mutex = malloc(sizeof(pthread_mutex_t)*(n+1));
pthread_t tid[n]; // declaracao de threads

for (i = 0; i <=n; i++){
 pthread_mutex_init(&mutex[i], NULL);}
for (i=0;i<=n;i++){
j=i+2;
 pthread_mutex_lock(&mutex[j]);
pthread_create(&tid[i],NULL,func,(void*)i); // Criacao de threads passamos o i como nr da thread e argumento para a seq fib

}

for (i=0; i<=n; i++){

pthread_join(tid[i], NULL);
 }
for (i=0; i<=n; i++){
 printf("Valor: Array[%d]: %d\n",i,vector[i]);}

return 0;
}

[HappyHippyHippo]

eu nem sei como é que tens uma percentagem tam alta

void * func(void * arg) {
// ...
 pthread_mutex_lock(&mutex[n-2]);
 pthread_mutex_lock(&mutex[n-1]);

 // o que te garante que vector[n-2] e vector[n-1] tem o valor correcto ?
 printf("tarefa %d",n);
 vector[n]=vector[n-2]+vector[n-1];

 pthread_mutex_unlock(&mutex[n-2]);
 pthread_mutex_unlock(&mutex[n-1]); 
 pthread_mutex_unlock(&mutex[n]);
// ...
}

[FasTer]

Boas HappyHippyHippo ,

Neste programa utilizo um vector de mutex para sincronizar as tarefas. A ideia é mesmo essa sincronizar as tarefas de modo a que todas sejam executadas uma uma (não concorrentemente) e calculando o o valor de fibbo na respectiva posição do array.

O problema com que me deparo. é sincronizar todas estas tarefas...

[FasTer]

Se alguém me puder ajudar, no que está a falhar na sincronização agradecia.

[HappyHippyHippo]

Se alguém me puder ajudar, no que está a falhar na sincronização agradecia.

responde à pergunta que foi colocada no comentário

[FasTer]

Boas HappyHippy.

PF executa este código:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
int *vector; // dec vector global
pthread_mutex_t *mutex;
void *func(void*arg)
{
   int n;
n=(int)arg;


   if (n==0){
       vector[n]=0;
 printf("tarefa %d \n",n);

   }

   if (n==1){
       vector[n-1]=0;
 vector[n]=1;
 printf("tarefa %d \n",n);

}
if(n>1){

pthread_mutex_trylock(&mutex[n-2]);
 pthread_mutex_trylock(&mutex[n-1]);

 vector[n]=vector[n-2]+vector[n-1];
    printf("tarefa %d\n",n);
 pthread_mutex_unlock(&mutex[n-2]);
 pthread_mutex_unlock(&mutex[n-1]); 
 pthread_mutex_unlock(&mutex[n]);


}
return NULL;
}




int main(int argc,char*argv[])
{

   int i,n=0;
n=atoi(argv[1]);

   vector= malloc(sizeof(int)*(n+1)); // aloca memória necessária para o array dinamico
   mutex = malloc(sizeof(pthread_mutex_t)*(n+1));
pthread_t tid[n]; // declaracao de threads

for (i = 0; i <=n; i++){
       pthread_mutex_init(&mutex[i], NULL);
}

for(i=2; i<=n ; i++)
{
       pthread_mutex_trylock(&mutex[i]);

}

for (i=0;i<=n;i++){

pthread_create(&tid[i],NULL,func,(void*)i); // Criacao de threads passamos o i como nr da thread e argumento para a seq fib

}
   for (i=0; i<=n; i++){

 pthread_join(tid[i], NULL);
      }
for (i=0; i<=n; i++){
       printf("Valor: Array[%d]: %d\n",i,vector[i]);}

   return 0;
}

Vais ver que a percentagem é bastante alta.

Respondendo à tua questão tem origem na sincronização do vector de mutex, ou seja inicializamos os mutex todos a fechados e voltamos a fechar na tarefa correspondente (N) os dois primeiros estao abertos e vão abrindo e fechando os seguintes a medida que as tarefas vão sendo executadas...

Edited October 7, 2013 at 08:26 PM by thoga31
GeSHi

[HappyHippyHippo]

esse código já é bem diferente do teu primeiro post ...

responde agora a estas perguntas :

- porque razão andas a "fechar"/"abrir" os mutexes à fartazana ?

- qual o sentido do uso dos mutexes ?

- qual o sentido de um único mutex do array ?

[FasTer]

Estive a modificar o código.

Este foi o trabalho que me foi proposto ou seja: 2 vectores globais 1 que vai conter cada número de sequência de fibbonaci e um vector de mutex.

Objectivo: Calcular sequência fibbonaci usando multithreading e sincronizando as tarefas de modo a serem todas executadas de modo ordeiro, ou seja só poderemos saber o valor da posição de vector[3] quando as duas posiçoes anteriores estiverem preenchidas.

Para isto sabemos que v[0] = 0 e v[1] = 1 . com estes dois números já podemos começar a trabalhar na nossa sequência... o resto é olhar para o código... está-me a falhar algo na sincronização e não percebo o quê. Tenho quase a certeza que é do facto de trabalhar com vários mutexes na mesma thread...

[HappyHippyHippo]

Estive a modificar o código.

Este foi o trabalho que me foi proposto ou seja: 2 vectores globais 1 que vai conter cada número de sequência de fibbonaci e um vector de mutex.

Objectivo: Calcular sequência fibbonaci usando multithreading e sincronizando as tarefas de modo a serem todas executadas de modo ordeiro, ou seja só poderemos saber o valor da posição de vector[3] quando as duas posiçoes anteriores estiverem preenchidas.

Para isto sabemos que v[0] = 0 e v[1] = 1 . com estes dois números já podemos começar a trabalhar na nossa sequência... o resto é olhar para o código... está-me a falhar algo na sincronização e não percebo o quê. Tenho quase a certeza que é do facto de trabalhar com vários mutexes na mesma thread...

é dificil responder às perguntas ?

- porque razão andas a "fechar"/"abrir" os mutexes à fartazana ?

- qual o sentido do uso dos mutexes ?

- qual o sentido de um único mutex do array ?

Edited October 7, 2013 at 07:37 PM by HappyHippyHippo

[FasTer]

Mas tem que haver um porquê? Foi o problema de sincronização que me foi colocado.... de qualquer da maneira já o resolvi.O programa dorme durante 1 ms entre a criação de cada tarefa assim não existe possibilidade de estas irem a correrem todas ao mesmo lock. Obviamente que com semáforos era mais fácil. O código final ficou assim :

Em 10 tentativas houve 10 respostas certas.

Abraço e mesmo assim obrigado pela disponibilidade, pena não ter um enunciado.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
int *vector; // dec vector global
pthread_mutex_t *mutex;
void *func(void*arg)
{
int n;
   n=(int)arg;


if (n==0){
	vector[n]=0;
   printf("tarefa %d \n",n);

}

if (n==1){
	vector[n-1]=0;
   vector[n]=1;
   printf("tarefa %d \n",n);

}
if(n>1){

   pthread_mutex_trylock(&mutex[n-2]);
   pthread_mutex_trylock(&mutex[n-1]);

   vector[n]=vector[n-2]+vector[n-1];
   printf("tarefa %d\n",n);
   pthread_mutex_unlock(&mutex[n-1]);
   pthread_mutex_unlock(&mutex[n]);
}
return NULL;
}



int main(int argc,char*argv[])
{
int i,n=0;
   n=atoi(argv[1]);

vector= malloc(sizeof(int)*(n+1)); // aloca memória necessária para o array dinamico
mutex = malloc(sizeof(pthread_mutex_t)*(n+1));
   pthread_t tid[n]; // declaracao de threads

   for (i = 0; i <=n; i++){
	pthread_mutex_init(&mutex[i], NULL);
   }

   for(i=2; i<=n ; i++)
   {
	pthread_mutex_trylock(&mutex[i]);
   }

   for (i=0;i<=n;i++){

       pthread_create(&tid[i],NULL,func,(void*)i); // Criacao de threads passamos o i como nr da thread e argumento para a seq fib
       sleep(1);
   }
for (i=0; i<=n; i++){
      pthread_join(tid[i], NULL);
   }
   for (i=0; i<=n; i++){
	printf("Valor: Array[%d]: %d\n",i,vector[i]);}

return 0;
}

[HappyHippyHippo]

estou a ver que a vontade de perceber também não é muita ... fica a solução para quem vier ver este post no futuro :

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

pthread_mutex_t * mutexes;
pthread_t * tids;
int * result;
size_t size;

void * func(void * arg)
{
   size_t id = (size_t) arg;

   // perdir permissão para resolver o termo "id"
   pthread_mutex_lock(&mutexes[id]);

   /* calcular o termo "id" */
   if (id == 0) {
       result[0] = 0;
   } else if (id == 1) {
       result[1] = 1;
   } else {
       result[id] = result[id - 1] + result[id - 2];
   }

   /* notificar o termo "id" + 1 que pode ser calculado */
   if (id < size - 1) {
       pthread_mutex_unlock(&mutexes[id + 1]);
   }

   pthread_exit(0);
}

int main(int argc, char ** argv)
{
   size_t i = 0;

   /* vertificar o numero de argumentos da linha de comandos */
   if (argc < 2) {
       fprintf(stderr, "Missing number of terms to be calculated\n");
       return -1;
   }

   /* ler/validar o argumento com o numero de termos a calcular/apresentar */
   if (sscanf(argv[1], "%ld", &size) != 1) {
       fprintf(stderr, "Error/unable to read the number of arguments to be calcualted\n");
       return -1;
   }

   /* validar o numero de termos a serem calculados/apresentados */
   if (size <= 1) {
       fprintf(stderr, "Invalid number of terms to be calculated : min = 2\n");
       return -1;
   }

   /* alocar o vector com o termos calculados */
   if ((result = malloc(sizeof(int) * size)) == NULL) {
       fprintf(stderr, "Error allocating memory to store the result vector\n");
       return -1;
   }

   /* alocar o vector com os mutexes */
   if ((mutexes = malloc(sizeof(pthread_mutex_t) * size)) == NULL) {
       free(result);

       fprintf(stderr, "Error allocating memory to store the mutex vector\n");
       return -1;
   }

   /* alocar o vector dos thread a serem criados */
   if ((tids = malloc(sizeof(pthread_t) * size)) == NULL) {
       free(mutexes);
       free(result);

       fprintf(stderr, "Error allocating memory to store the threads ids vector\n");
       return -1;
   }

   /* inicializar todos os mutexes como "locked" */
   for (i = 0; i < size; i++) {
       pthread_mutex_init(&mutexes[i], NULL);
       pthread_mutex_lock(&mutexes[i]);
   }

   /* criar os threads que irão calcular os termos */
   for (i = 0;i < size; i++) {
       pthread_create(&tids[i], NULL, func, (void *) i);
   }

   /* dizer que pode ser calculado o primeiro termo */
   pthread_mutex_unlock(&mutexes[0]);

   /* esperar que todos os termos estejam calculados */
   for (i = 0; i < size; i++) {
       pthread_join(tids[i], NULL);
   }

   /* apresentar o resultado */
   printf("Result : ");
   for (i = 0; i < size; i++){
       printf("%d ", result[i]);
   }
   printf("\n");

   /* destruir todos os mutexes inicializados */
   for (i = 0; i < size; i++) {
       pthread_mutex_destroy(&mutexes[i]);
   }

   /* libertar toda a memória alocada */
   free(tids);
   free(mutexes);
   free(result);

   return 0;
}

[eatg75]

Por alguma razão que me transcende a 90% das vezes da-me o valor correcto contudo, 10% do output vem baralho.

A razao por isso estar a suceder e que o printf(3) utiliza o stdout para fazer o output e o output do

stdout e buffered, i.e. o stdout internamente utiliza uma variavel onde guarda os caracteres

a serem escritos para a consola, e so escreve-os para consola quando essa variavel encher, isso

significa que cada chamada do printf( 3) o conteudo nao e escrito i mediatamente para o ecra, e

e possivel resolver este inconviniente de duas forma : fazer o flush do stdout utilizando a funcao

fflush(3) apos cada chamada da funcao printf(3), ou tens uma segunda opcao que e melhor (na

minha opiniao), utilizas o stderr como stream dos teus outputs, ve a funcao fprintf(3), porque

o output do stderr e unbuffered.

Se quiseres podes ir um bocado mais longe e defines uma macro para debug da seguinte forma:

#define WARN(...) fprintf(stderr, ## __VA_ARGS__)

[Rui Carlos]

O facto de usares o pthread_mutex_trylock, sem testares o resultado, não pode levar a que o algoritmo falhe?

O que é que acontece se quando chamas o pthread_mutex_trylock a função não consegue adquirir o lock?

A solução que implementaste é basicamente fazer batota. Simplesmente retardas o início das threads para garantir que a anterior já acabou, e nesse caso não precisas dos locks para nada.

Penso que deves conseguir resolver o problema alterando o pthread_mutex_trylock. No entanto terás um problema com deadlocks... É que a thread K tenta adquirir o lock K-2 e K-1, e a thread K+1 tenta adquirir o lock K-1 e K. Ora se a thread K+1 conseguir adquirir o lock K-1, a thread K não o conseguirá obter. Ficas então com a thread K à espera do lock K-1, que terá que ser libertado pela thread K+1. Mas a thread K+1 está à espera do lock K, que terá que ser libertado pela thread K.

Uma solução para este problema passa por trocares a ordem em que adquires os locks. Se tentares primeiro adquirir o lock N-1, a thread K+1 bloqueia logo à espera do lock K, não chegando a adquirir o lock K-1, permitindo à thread K adquirir os locks K-1 e K-2.

Tens também a solução do HappyHippyHippo, que usa um algoritmo ligeiramente diferente, que permite menos operações com locks.

[FasTer]

Muito obrigado pela ajuda de todos! Rui de facto tens razão, estava a fazer batota e perdendo um pouco de tempo e escrevendo num papel o algoritmo cheguei à mesma conclusão que a tua!

A solução final ficou assim, a funcionar a 100%:

Obrigado a todos os intervenientes pela ajuda.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
int *vector; // dec vector global
pthread_mutex_t *mutex;
void *func(void*arg)
{
   int n;
n=(int)arg;
pthread_mutex_lock(&mutex[n-1]);
pthread_mutex_lock(&mutex[n-2]);
vector[n]=vector[n-2]+vector[n-1];
printf("tarefa %d\n",n);

 pthread_mutex_unlock(&mutex[n-2]);
pthread_mutex_unlock(&mutex[n-1]);
 pthread_mutex_unlock(&mutex[n]);


return NULL;
}



int main(int argc,char*argv[])
{

   int i,n=0;
n=atoi(argv[1]);

   vector= malloc(sizeof(int)*(n+1)); // aloca memória necessária para o array dinamico
   mutex = malloc(sizeof(pthread_mutex_t)*(n+1));
pthread_t tid[n+1]; // declaracao de threads

vector[0]=0;
vector[1]=1;

for (i = 0; i <=n; i++){
       pthread_mutex_init(&mutex[i], NULL);
}

for(i=0; i<=n ; i++)
{
       pthread_mutex_lock(&mutex[i]);

}



for (i=2;i<=n;i++){

pthread_create(&tid[i],NULL,func,(void*)i); // Criacao de threads passamos o i como nr da thread e argumento para a seq fib
}
pthread_mutex_unlock(&mutex[1]);
pthread_mutex_unlock(&mutex[0]);


   for (i=2; i<=n; i++){

 pthread_join(tid[i], NULL);
      }
for (i=0; i<=n; i++){
       printf("Valor: Array[%d]: %d\n",i,vector[i]);}

/* destruir todos os mutexes inicializados */
   for (i = 0; i <= n; i++) {
       pthread_mutex_destroy(&mutex[i]);
   }


/* libertar toda a memória alocada */
   free(vector);
   free(mutex);


   return 0;
}

Edited October 8, 2013 at 10:54 PM by thoga31
GeSHi