Jump to content
FasTer

Fibbonaci utilizando Multithreading e Vector de Mutex

Recommended Posts

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;
}

Share this post


Link to post
Share on other sites
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]);
// ...
}


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
HappyHippyHippo

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

responde à pergunta que foi colocada no comentário


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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 by thoga31
GeSHi

Share this post


Link to post
Share on other sites
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 ?


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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 by HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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;
}

Edited by Rui Carlos
GeSHi, indentação.

Share this post


Link to post
Share on other sites
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;
}

  • Vote 1

IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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__)


Victarion seized the dusky woman by the wrist and pulled her to him.

Victarion - She will do it. Go pray to your red god. Light your fire, and tell me what you see.

Moqorro's dark eyes seemed to shine.

Moqorro - I see dragons.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 by thoga31
GeSHi

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.