TP n° 4

Exercice 1.

Réaliser un programme C qui lance 3 threads. Ces trois threads exécutent la fonction ma_nouvelle_sequence_control ci-dessous :

//Cette fonction doit recevoir comme argument
//le nom donné au thread
void *ma_nouvelle_sequence_control (void * arg)
{
int i;
for (i = 0 ; i < 10 ; i++) {
printf ("Thread %s: %d\n", (char*)arg, i);
sleep (1);
}
pthread_exit (0);
}
  
Exécuter votre programme et interpréter son comportement.


Exercice 2.

(Tri parallèle) Paralléliser l'algorithme de tri fusion en utilisant les threads.

Une fonction qui fusionne les 2 moitiés triées d'un morceau de tableau t[debut..fin] :

#define MAX ...

int t[MAX];
int temp[MAX];

void fusion(int debut, int fin) {
  int i1,i2,i,mil;
  mil = (debut + fin)/2;
  i1 = debut;
  i2 = mil+1;
  i = debut;
  while((i1<=mil) && (i2<=fin)) {
    if(t[i1]<t[i2])
      {temp[i] = t[i1]; i++; i1++;}
    else
      {temp[i] = t[i2]; i++; i2++;}
  }
  while(i1<=mil) {temp[i] = t[i1]; i++; i1++;}
  while(i2<=fin) {temp[i] = t[i2]; i++; i2++;}
  for(i=debut;i<=fin;i++)
    t[i] = temp[i];
}


Exercice 3.

(Fibonacci) Voici ci-dessous une fonction séquentielle qui calcule le nième terme de la suite 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 ; 
  }
}

L'objectif de l'exercice est de paralléliser ce calcul.

1. Réaliser une première parallélisation en attachant un thread à chacun des appels récursifs à la fonction fib(). On construit ainsi un arbre de threads. Avant de retourner son résultat, un thread attend que ses deux fils aient terminé.

2.  On propose d'améliorer la solution précédente de la manière suivante : plutôt que de créer un thread alors que la valeur a déjà été calculée auparavant par un autre thread, on récupère cette valeur. Pour cela, on garde les résultats intermédiaires calculés dans un tableau partagé entre les threads. (Les éléments de ce tableau sont par exemple initialisés à la valeur INCONNUE pour dénoter que la valeur n'a pas encore été calculée.)

    #define INCONNUE        -1
   int * fibtab ;


Exercice 4.

(Producteurs et consommateurs) Ecrire un programme qui décrit un système de P producteurs et Q consommateurs partageant un buffer borné à 1 place, il s'agit pour les producteurs et les consommateurs de se synchroniser sur le buffer. Un producteur doit attendre que le buffer soit vide pour mettre la valeur produite dans le buffer. Un consommateur doit attendre que le buffer soit plein pour consommer la valeur.

Chaque producteur produit 30 valeurs et chaque concommateur consomme 10 valeurs. On testera le programme pour P=1, Q=3.


Généraliser le programme de l'exercice précédent à un bufffer à N places : Ecrire un programme qui décrit un système de P producteurs et Q consommateurs partageant un buffer borné à N places, il s'agit pour les producteurs et les consommateurs de se synchroniser sur le buffer. Un producteur doit attendre que le buffer ait au moins une place libre pour mettre la valeur produite dans le buffer. Un consommateur doit attendre que le buffer ait au moins une place occupée pour consommer la valeur. 

Chaque producteur produit 30 valeurs et chaque concommateur consomme 10 valeurs. On testera le programme pour P=1, Q=3 et N=10.