• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

orium

[C] Calcular factoriais com multithreading (pthread) e gmp

1 mensagem neste tópico

Programa que escrevi só para aprender a trabalhar com múltiplas threads, calcula factoriais bem grandes (usa programação dinâmica) com o gmp.

Compilar com gcc -lpthread -lgmp -o fac fac.c

/*
*  GPL
*
*  fac - Written by Diogo Sousa aka orium
*  Copyright © 2008 Diogo Sousa
*
*  This program is free software: you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/


#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <gmp.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>

#define N_THREADS 10
#define N_FAC 50000

struct thread_arg
{
int start;
int end;
};

mpz_t *result;
pthread_mutex_t *mutex_result;

bool is_computed(int n)
{
bool r;

pthread_mutex_lock(&mutex_result[n-1]);
r=mpz_cmp_ui(result[n-1],0);
pthread_mutex_unlock(&mutex_result[n-1]);

return r;
}

/* Return the nearest smaller *index* of computed factorial
*/
int get_nearest_computed(int n)
{
int i;

for (i=n-1; i >= 0; i--)
	if (is_computed(i))
		return i-1;

return -1;
}

void compute_fac(int n)
{
mpz_t r;
int nearest_computed;
int i;

if (n == 1)
	return;

mpz_init(r);

nearest_computed=get_nearest_computed(n);

assert(nearest_computed >= 0);

pthread_mutex_lock(&mutex_result[nearest_computed]);
mpz_set(r,result[nearest_computed]);
pthread_mutex_unlock(&mutex_result[nearest_computed]);

for (i=nearest_computed+2; i <= n; i++)
{
	mpz_mul_ui(r,r,i);

	if (!is_computed(i))
	{
		pthread_mutex_lock(&mutex_result[n-1]);
		mpz_set(result[n-1],r);
		pthread_mutex_unlock(&mutex_result[n-1]);
	}
}

mpz_clear(r);
}

void *thread_init(void *data)
{
struct thread_arg *arg=data;	
int i;

for (i=arg->start; i <= arg->end; i++)
	compute_fac(i);

return NULL;
}

int main(void)
{
int i;
pthread_t *threads;
struct thread_arg *th_arg;

assert(!(N_FAC%N_THREADS));

threads=malloc(sizeof(*threads)*N_THREADS);
if (threads == NULL)
	return -1;

th_arg=malloc(sizeof(*th_arg)*N_THREADS);
if (th_arg == NULL)
	return -1;

result=malloc(sizeof(*result)*N_FAC);
if (result == NULL)
	return -1;

mutex_result=malloc(sizeof(*mutex_result)*N_FAC);
if (mutex_result == NULL)
	return -1;

for (i=0; i < N_FAC; i++)
{
	pthread_mutex_t mutex_tmp=PTHREAD_MUTEX_INITIALIZER;

	mpz_init(result[i]);
	mpz_set_ui(result[i],(!i) ? 1 : 0); /* 1! is set here */

	memcpy(&mutex_result[i],&mutex_tmp,sizeof(mutex_tmp));
}

for (i=0; i < N_THREADS; i++)
{
	th_arg[i].start=i*(N_FAC/N_THREADS)+1;
	th_arg[i].end=i*(N_FAC/N_THREADS)+(N_FAC/N_THREADS);

	pthread_create(&threads[i],NULL,thread_init,&th_arg[i]);
}

for (i=0; i < N_THREADS; i++)
	pthread_join(threads[i],NULL);

for (i=0; i < N_FAC; i++)
{
	gmp_printf("%d! = %Zd\n",i+1,result[i]);
	mpz_clear(result[i]);
}

free(threads);
free(th_arg);
free(result);
free(mutex_result);

return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora