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

(Corrigés)

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.

---beginCorr

fseek ne peut pas être appelé sur un stream créé par popen (errno contient donc EBADF) : il n'a aucun effet. Pour sauter toutes les lignes renvoyées par ls, il faut lire explicitement toutes ces lignes.


---endCorr

Question 1.2 (2 points)

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

---beginCorr

Il faut ajouter le test du code d'erreur de fseek (cf. lsOriginal.Q1.2.corrige.c)


---endCorr

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é.

---beginCorr

Voir le fichier memory.Q2.1.corrige.c

---endCorr

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.

---beginCorr

Il s'agit d'un problème d'alignement : les instructions SSE agissent sur des données alignées sur 16 octets. Avec monMalloc, la zone allouée pour l'utilisateur est décalée de 8 octets (4 octets pour buffer_size, 1 octet pour canary et 3 octets pour l'alignement du champ data) : les données ne sont plus alignées sur 16 octets.

---endCorr

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.

---beginCorr

Voir le fichier memory.Q2.3.corrige.c

---endCorr

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.

---beginCorr
Chaque thread doit disposer d'un sémaphore (appelé upper_border par exemple) permettant de signaler au thread en charge de la tranche supérieure qu'il a terminé le calcul. Avant de commencer le calcul de M_i, chaque thread doit donc prendre le sémaphore sem_sup du thread en charge de la tranche inférieure.
Ce méchanisme permet d'assurer la synchronisation pour la "bordure supérieure" d'une zone de calcul. On utilise la même méthode (avec les sémaphores lower_border par exemple) pour la bordure inférieure. ---endCorr

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.

---beginCorr

Voir le fichier stencil.Q3.2.corrige.c

---endCorr

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.

---beginCorr

Il s'agit d'un problème de type appel procédural entre processus : le processus stencil sous-traite la visualisation au processus visualizer
Cela peut également être vu comme un problème de type Producteur / Consommateur: le processus stencil produit des données que le processus visualizer consomme.

---endCorr

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).

---beginCorr

Voir les fichiers stencil.Q3.3.corrige.c, stencil.Q3.3.corrige.h et visualizer.Q3.3.corrige.c

---endCorr

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.

---beginCorr

Voir les fichiers stencil.Q3.5.corrige.c et stencil.Q3.5.corrige.h.

---endCorr



Page mise à jour le 15 mai 2013