CSC4508/M2 - Évaluation du 16/05/13

Département INFormatique

CSC4508/M2 : Concepts des systèmes d'exploitation et mise en œuvre sous Unix

Évaluation

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

TP Noté CSC4508/M2 du 16/05/13

Modalités

Durée : 3 heures

Tous documents autorisés.

Les questions 1, 2 et 3 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}_TPNote2013

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
cp ~trahay_f/Cours/CSC4508/tPNote2013.tgz .
tar xvfz tPNote2013.tgz
mv TPNote2013 ${USER}_TPNote2013
cd ${USER}_TPNote2013

Question 1 : Questions de cours (4 points)

On considère le programme Q1/lsOriginal.c qui est sensé lancer la commande ls au sein d'un autre processus, de récupérer sa sortie à l'aide de popen, et de sauter toutes les lignes renvoyées par ls à l'aide de fseek.
Il semble que ce programme ne fonctionne pas, puisqu'il affiche systématiquement toutes les lignes renvoyées par ls.

Question 1.1 (2 points)

Expliquez dans le fichier Q1/reponse1.txt pourquoi le programme ne donne pas le résultat attendu.

Question 1.2 (2 points)

Proposez une correction du programme qui permette de mieux comprendre pourquoi le programme ne fonctionne pas.

Question 2 : Analyse des allocations/libérations d'un programme (7 points)

On souhaite utiliser la bibliothèque libmemory située dans le répertoire Q2/Q2.1 afin d'analyser l'utilisation mémoire d'une application. Pour cela, l'application remplace les appels à malloc par des appels à monMalloc et les appels à free par des appels à monFree.

La version actuelle de la bibliothèque se contente d'afficher un message lors des appels à malloc et free :

allocation d'un bloc de 256 octets liberation d'un bloc de 256 octets

Pour cela, la fonction monMalloc alloue une zone mémoire plus grande que ce que demande l'application. La taille de la zone mémoire demandée par l'application est alors stockée au début du tampon :

Question 2.1 (3 points)

On souhaite faire évoluer la bibliothèque afin qu'elle vérifie que l'application ne fait pas d'accès en dehors de la zone allouée. Pour cela, on ajoute un champ canary à la structure memory_block:

struct memory_block {

size_t buffer_size;

char canary;

int data;

};

Lors de l'allocation, une valeur particulière (CANARY_VALUE) est assignée au champ canary. Lors de la libération de la zone mémoire, on peut détecter certains accès en dehors de la zone allouée en vérifiant si la valeur du canary a changé. Si le canary a été écrasé par l'application, on souhaite afficher un message d'erreur et terminer l'application :

Attention! canary écrasé (0x17 au lieu de 0x42)

Complétez dans le répertoire Q2/Q2.1 le fichier memory.c afin d'implémenter cette fonctionnalité. Utilisez le programme test_memory.c pour tester cette fonctionnalité.

Question 2.2 (2 points)

Afin d'améliorer les performances de la fonction compute, on décide de l'implémenter en utilisant les instructions SSE du processeur. Cette implémentation est disponible dans le fichier Q2/Q2.3/test_memory.c.

Bien que l'implémentation de la fonction compute soit correcte, l'application génère une erreur de segmentation lorsqu'on l'exécute.

Expliquez, dans le fichier Q2/reponse2.txt pourquoi l'application ne fonctionne plus.

Question 2.3 (2 points)

Modifiez dans le répertoire Q2/Q2.3 le fichier memory.c afin de corriger le problème rencontré à la question 2.2.

Question 3 : Stencil 5 points (9 points)

Le programme stencil.c effectue des calculs successifs permettant de "lisser" des valeurs. Ce type d'application appelée stencil permet, par exemple, de résoudre l'équation de la chaleur. A chaque pas de l'application, on lisse une matrice: pour un pas donné, chaque élément de la matrice vaut la moyenne des éléments adjacents dans la matrice calculée au pas précédent. Pour un stencil 5 points, chaque élément de la matrice M est donc calculée de cette façon pour le pas n:


	  M_n[i][j] = (M_(n-1)[i-1][j] + M_(n-1)[i+1][j] + M_(n-1)[i][j-1] +
	  M_(n-1)[i][j+1] + M_(n-1)[i][j]) / 5

Afin de simplifier le programme, on ne calcule pas les valeurs situées aux bords de la matrice (c'est à dire quand i=0, i=N, j=0 ou j=N).
Lorsque tous les éléments de la matrice ont été calculés, on passe au pas suivant.
La programme utilise les valeurs de la matrice M0 pour calculer M1. Lorsque M1 est calculée, on l'utilise pour calculer M2. M2 servira ensuite à calculer M3, etc.


Matrice `M0`	Matrice `M1`	Matrice `M2`

Comme on ne souhaite pas conserver toutes les matrices, mais uniquement le résultat (la matrice Mn), le programme n'alloue que 2 matrices et utilise les pointeurs cur_step et next_step pour désigner respectivement les matrices Mi et Mi+1. Le programme stencil_reference.c (situé dans le répertoire Q3/Q3.2) calcule la valeur d'une matrice après 20 itérations. Exécutez ce programme et observez l'évolution de la matrice.

Question 3.1 (1.5 points)

On souhaite dans un premier temps paralléliser le programme original. Pour cela, plusieurs threads (le nombre de threads est défini par #define NB_THREADS dans stencil.h) sont lancés à l'initialisation de l'application. Chaque thread se charge d'une partie du calcul. Par exemple pour 4 threads, la répartition du travail se fait de la façon suivante :

Avant de commencer le calcul de la matrice Mi+1, chaque thread doit attendre que les éléments de la matrice Mi qu'il utilise aient été calculés. Par exemple, le thread 1 ne peut commencer le calcul que quand les lignes N/4-1 à N/2 de la matrice Mi ont été calculées. Le thread 1 doit donc attendre que le thread 0 ait calculé la ligne N/4-1 et que le thread 2 ait calculé la ligne N/2.

Expliquez, dans le fichier Q3/reponse1.txt, comment résoudre ce problème de synchronisation.

Question 3.2 (1.5 points)

Complétez dans le répertoire Q3/Q3.2 le fichier stencil.c pour gérer la synchronisation entre les threads (parties A COMPLETER dans le code). Testez votre programme avec plusieurs threads et assurez vous que le résultat est le même que pour le programme original.

Question 3.3 (1 point)

On souhaite maintenant pouvoir suivre l'évolution de la matrice à partir du programme visualizer.c. Après chaque pas de calcul, le programme stencil.c doit communiquer le résultat au programme visualizer qui se charge de l'afficher.

Expliquez, dans le fichier Q3/reponse3.txt, le type de problème de synchronisation qu'il faut résoudre ici.

Question 3.4 (3 points)

Modifiez les fichiers stencil.h stencil.c et visualizer.c situés dans le répertoire Q3/Q3.4 afin de résoudre ce problème lorsque seul un thread se charge du calcul (la constante NB_THREADS définie dans stencil.h vaut 1).

Question 3.5 (2 points)

On souhaite maintenant que l'implémentation fonctionne lorsque plusieurs threads se partagent le travail (par exemple lorsque la constante NB_THREADS définie dans stencil.h vaut 4). Modifiez les fichiers situés dans le répertoire Q3/Q3.5 afin d'implémenter une solution à ce problème.

TÉLÉCOM SudParis 2ème année TP Noté CSC4508/M2 du 16/05/13