TÉLÉCOM SudParis 2^ème année

TP Noté CSC4508/M2 du 21/05/15

Modalités

cd votreRepertoireDeTravailPourCSC4508M2
tar cvfz ${USER}.tgz ${USER}_TPNote2015

Préparation

		cd votreRepertoireDeTravailPourCSC4508M2
		wget http://www-inf.it-sudparis.eu/COURS/CSC4508/Current/Documents/ExoCoursSys/TPNote2015/WWW/tPNote2015.tgz
		tar xvfz tPNote2015.tgz
		mv TPNote2015 ${USER}_TPNote2015
		cd ${USER}_TPNote2015
	      

Question 1 : Echauffement (3 points)

Le programme find_files.c cherche toutes les occurences d'un nom de fichier dans une arborescence de fichiers. Il s'agit en fait d'un équivalent de la commande find dirname -name filename. Le comportement souhaité pour ce programme est donc :

$ ./find_files stdio.h /usr/include/
Found /usr/include//stdio.h
Found /usr/include//c++/4.9/tr1/stdio.h
Found /usr/include//c++/4.9.2/tr1/stdio.h
Found /usr/include//x86_64-linux-gnu/bits/stdio.h
	    

Pour chacune des questions ci-dessous , répondez dans le fichier Q1/reponses1.txt ou bien sur votre copie (dans ce dernier cas, indiquez dans le fichier ; Q1/reponses1.txt « Réponse sur copie ») pour les questions portant sur la compréhension des problèmes.

Question 1.1 (2 points)

A l'exécution, la version actuelle du programme génère une erreur de segmentation. Expliquez est la cause du problème.

Question 1.2 (1 point)

Dans le répertoire Q1/Q1.2, modifiez le programme find_files.c pour corriger le problème.

Question 2 : Des p'tits tris, des p'tits tris, toujours des p'tits tris. (3 points)

Le programme merge_sort.c implémente un tri fusion. Cet algorithme de tri récursif consiste à "couper" un tableau T en deux sous-tableaux T1 et T2 et à appliquer l'algorithme récursivement sur T1 et T2. Une fois T1 et T2 triés, on fusionne les deux sous-tableaux pour obtenir le tableau T trié.

Question 2.1 (2 points)

A l'exécution, l'implémentation actuelle du programme ne donne pas le résultat attendu. Le problème ne vient pas de l'algorithme, mais de la gestion de la mémoire.

Expliquez pourquoi le programme n'affiche pas le résultat attendu.

Question 2.2 (1 point)

Corrigez le problème en modifiant le programme merge_sort.c dans le répertoire Q2/Q2.2.

Bonus: veillez à ce que toutes les données allouées dynamiquement soient désallouées proprement par le programme.

Question 3 : Au chat bouclé (7 points)

On souhaite modéliser le fonctionnement d'un salon de toilettage pour chats avec des sémaphores. Le salon possède N places d'attente (dans lesquelles les chats peuvent sagement attendre en dégustant des croquettes au saumon) et K places de toilettage. Le but de la première partie de l'exercice est de définir le code des processus chat.

Pour chacune des questions ci-dessous :

• Répondez dans le fichier Q3/reponses3.txt ou bien sur votre copie (dans ce dernier cas, indiquez dans le fichier Q3/reponses3.txt « Réponse sur copie »).
• Le langage algorithmique utilisé n'a pas besoin de respecter strictement la syntaxe apprise en première année. L'essentiel est qu'il soit lisible par le correcteur et sans ambiguïté.

Question 3.1 (1 point)

Quelles sont les variables et sémaphores utilisés par les processus chats?

Question 3.2 (2 points)

Donnez le code du processus chat.

Question 3.3 (1 point)

Pour parfaire leur toilettage, les chats doivent recevoir un noeud papillon rose avant de pouvoir sortir du salon de toilettage. Les noeuds papillons sont fabriqués au fur et à mesure par des chiens qui les déposent dans une boite de rangement contenant R emplacements. Les chats se servent dans cette boite. Le but de l'exercice est de définir le code des processus chats et chiens.

On modélise la boite de rangement par un tableau de R entiers. Déposer un noeud papillon consiste à mettre un 1 dans une des cases du tableau. Retirer un noeud papillon consiste à mettre un 0 dans une des cases du tableau.

De quelles variables et sémaphores devez-vous disposez pour assurer la synchronisation entre les chats et les chiens?

Question 3.4 (3 points)

Donnez le code complet des processus chat et chien

chat :
  P(attente)
  P(toilettage)
  V(attente)
  P(noeudPret)
  P(mutexQueue)
  T[queue] = 0;
  queue = (queue + 1 ) % R
  V(mutexQueue)
  V(placeDispo)
  V(toilettage)

chien :
  while(true) {
     P(placeDispo)
     P(mutexTete)
     T[tete] = 1
     tete = (tete+1) % R
     V(mutexTete)
     V(noeudPret)
  }

Question 4 : Ensemble de Mandelbrot (7 points)

L'ensemble de Mandelbrot est une fractale définie comme l'ensemble des points du plan complexe pour lesquels la suite de nombres complexes suivantes est bornée :

Le programme mandelbrot.c calcule et affiche l'ensemble des points compris entre (r=-2, i=-2) et (r=2, i=2). Pour chaque point (r,i), on calcule la vitesse de divergence de la suite. Le nombre d'itérations nécessaires pour faire diverger la suite détermine la couleur du point. Ainsi, le calcul des points "sombres" est rapide car les suites définies en ces points divergent au bout de quelques itérations seulement. Les points "lumineux" nécessitent, eux, plus de calcul car le nombre d'itérations à partir duquel ils divergent est plus important.

Le programme se lance en spécifiant le nombre maximum d'itérations à effectuer pour chaque point. Par exemple:

$ ./mandelbrot 1000
Press any key (with focus in display) to start the program
Maximum iterations = 1000
N threads = 4
Computation took 1064.565000 ms

Le but de cet exercice est de paralléliser l'application à l'aide de threads afin de réduire le temps nécessaire pour calculer et afficher l'ensemble des points.

Pour chacune des questions ci-dessous , répondez dans le fichier Q4/reponses4.txt ou bien sur votre copie (dans ce dernier cas, indiquez dans le fichier ; Q4/reponses4.txt « Réponse sur copie ») pour les questions portant sur la compréhension des problèmes de synchronisation.

Question 4.1 (2 points)

On souhaite dans un premier temps paralléliser la boucle suivante (située dans la fonction draw_mandelbrot) :

  /* Calculate and draw points */
  for (row = p_info->row_min; row < p_info->row_max; ++row) {
    for (col = 0; col < width; ++col) {
      /* Compute the color of point (row, col) */
      couleur = compute(row, col);
      /* Apply the color to point (row, col) */

      /* Change the drawing color */
      XSetForeground (display, gc, couleur);
      /* Color point (row, col) */
      XDrawPoint (display, win, gc, col, row);
      /* Apply change */
      XFlush (display);
    }
  }	      

Si plusieurs threads exécutent simultanément ce code, quel problème risque d'arriver lors de l'affichage ? Comment résoudre le problème ?

Question 4.2 (2 points)

Dans le répertoire Q4/Q4.2, modifiez le programme mandelbrot.c afin qu'il crée NTHREADS threads. Chaque thread traitera un des computation_info définis dans la fonction main. Ne pas oublier d'ajouter le mécanisme que vous avez proposé en questions 4.1.

---beginCorr
corrigé
---endCorr

Question 4.3 (3 points)

On souhaite mettre en place un schéma de type Producteur-Consommateur dans lequel le thread principal se charge d'afficher les lignes que les threads de calcul ont produites. Pour cela, on définit la structure line comme suit :

struct line{
  int row;
  ulong couleur[NCOLUMNS];
};
	    

Les threads de calcul remplissent donc une ligne complète avant de la soumettre au thread principal qui se charge d'afficher tous les pixels de la ligne.

Modifiez l'application pour mettre en place ce schéma Producteur-Consommateur.

---beginCorr
corrigé
---endCorr

Question 4.4 (bonus)

Afin de répartir la "quantité de travail" allouée à chaque thread et s'assurer qu'il n'y a pas de threads inactifs car plus rapides que les autres, modifiez le programme pour que les lignes à traiter soient mises en commun et que chaque thread de calcul "pioche" dans la liste des lignes à traiter.

---beginCorr
TODO
---endCorr