Département INFormatique 
 CSC4508/M2 : Conception et programmation des systèmes centralisés


   Évaluation



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

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

(Corrigés)

Modalités

Durée : 3 heures

Tous documents autorisés.

Les questions 1, 2, 3 et 4 sont indépendantes les unes des autres. Aussi, n'hésitez pas à lire tout le sujet avant de commencer pour déterminer l'ordre dans lequel vous souhaitez traiter les questions.

Le barème est donné à titre indicatif des poids entre les différentes questions.

La « livraison » de votre travail en fin de TP noté se fera par remontée sous Moodle (rubrique « TP noté de 3 heures ») du fichier d'extension tgz constitué de la manière suivante :
cd votreRepertoireDeTravailPourCSC4508M2
tar cvfz ${USER}.tgz ${USER}_TPNote2015
NB: Si vous êtes plus à l'aise en écrivant vos réponses sur une copie plutôt qu'en les tapant sur ordinateur, vous pouvez rendre également une copie papier à l'enseignant qui vous surveille. En fin d'épreuve, même si vous ne rendez pas de copie, passez voir l'enseignant qui vous surveille pour lui signaler explicitement que vous ne rendez pas de copie.

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.

---beginCorr
Le programme cherche récursivement dans les sous-répertoires, y compris dans les répertoires "." et "..". Il y a donc une récursion infinie.
---endCorr

Question 1.2 (1 point)

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

---beginCorr
corrigé
---endCorr

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.

---beginCorr
La fonction merge() utilise alloca() pour allouer le tableau fusionné qui est retourné. Lorsque la fonction merge se termine, le tableau est désalloué. L'utilisation du résultat entraine donc des accès à de la mémoire qui a été désallouée !
---endCorr

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.

---beginCorr
corrigé
---endCorr

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?

---beginCorr
attente : sémaphore initialisé à N
toilettage : sémaphore initialisé à K
---endCorr

Question 3.2 (2 points)

Donnez le code du processus chat.

---beginCorr
P(attente)
P(toilettage)
V(attente)
toilettage()
V(toilettage)
---endCorr

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?

---beginCorr
placeDispo = sémaphore initialisé à R
noeudPret = sémaphore initialisé à 0
tete = entier initialisé à 0
mutexTete = sémaphore initialisé à 1
queue = entier initialisé à 0
mutexQueue = sémaphore initialisé à 1
T = tableau de R entier
---endCorr

Question 3.4 (3 points)

Donnez le code complet des processus chat et chien

---beginCorr
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)
  }
---endCorr

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 :

z(0) = 0
z(n+1) = z(n)^2 + c

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 ?

---beginCorr
  1. Race-condition entre l'appel à XSetForeground() et XDrawPoint() : un thread T2 risque de changer la couleur entre le moment où un thread T1 choisi une couleur (XSetForeground()) et le moment où il l'applique (XDrawPoint) (1 point).
  2. Pour corriger le problème: mettre un mutex autour de la partie affichage (1 point).
---endCorr

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





Page mise à jour le 17 mai 2015