Exercice 1 (Arbre de calcul)
Soit le programme suivant de calcul du ne nombre de
Fibonacci :
int
fib (int n)
{
if (n<2)
return n;
else {
int x, y;
x = fib(n-1);
y = fib(n-2);
return x + y;
}
}
int
main (int argc, char *argv[])
{
int n, res;
n = atoi(argv[1]);
res = fib(n);
printf("Fibo (%d) = %d\n", n, res);
exit(EXIT_SUCCESS);
}
Question 1
On désire attacher un processus léger à chacune des instances
de la fonction fib(). On construit ainsi un arbre de
processus légers. Avant de retourner son résultat, un
processus léger attend que ses deux fils aient
terminé.
Question 2
On désire maintenant changer le prototype de la fonction de
calcul associée à un thread pour que le résultat ne soit plus
retourné par la fonction, mais rangé à une adresse passée en
paramètre.
Exercice 2 (Recherche parallèle)
On désire réaliser une implantation multithreadée de la recherche
d’une valeur v dans un tableau de valeurs selon la
méthode suivante :
-
on délègue la recherche de la valeur dans la première
moitié du tableau à un thread ;
- on recherche la valeur dans la seconde moitié du
tableau (en utilisant la même méthode de recherche parallèle) ;
- on récupère le résultat de la recherche effectuée par le
thread pour le combiner au résultat de notre recherche.
Soit la fonction
int search(int *tab, unsigned int size, int (*pred)(int));
de recherche d’une valeur entière satisfaisant la fonction
prédicat pred() dans le tableau tab de
size éléments. On cherche donc une valeur
v=tab[i] telle que pred(v).
Question 1
Donnez l’implantation d’une fonction pt_search() de
prototype compatible avec la fonction principale d’un thread.
Cette fonction pt_search() réalise la recherche par
un simple appel à search().
Question 2
Donnez une implantation de search().