CSC 4103 – Programmation système

Contrôle Final 2 – Année 2020/2021

Le barème est donné à titre indicatif

Durée du contrôle : 2h
Tous les documents sont autorisés
Les exercices sont indépendants.

Pour commencer, téléchargez l'archive se trouvant ici puis décompressez-la avec la commande suivante :

$ tar xf csc4103-cf2.tar.xz

Dans la suite du contrôle, vous devez travailler dans le répertoire csc4103-cf2.

En vue du rendu, après vous être placé dans le répertoire parent de csc4103-cf2, vous devez créer une archive de vos fichiers grâce à la commande :

$ tar -f csc4103-cf2-rendu.tar.xz -cJ csc4103-cf2

L'archive générée csc4103-cf2-rendu.tar.xz est ensuite à déposer dans Moodle.

Mise en œuvre d'une hashmap - la suite (10 points)

Dans le répertoire exo1/, vous trouverez plusieurs fichiers :

hashmap.h définit l'interface d'une hashmap,
hashmap.c implémente la hashmap,
test_hashmap.c permet de tester l'implémentation de cette hashmap,
le Makefile associé.

Pour rappel, une hashmap est une structure de données qui associe une clé à une valeur. Ce type de structure de données est fréquemment utilisé pour indexer des bases de données ou pour mettre en cache des données.

Dans notre mise en œuvre, la clé (une chaîne de caractères) est hachée par la fonction uint32_t hash(K key). Le hash obtenu identifie la case du tableau entries dans laquelle est stockée la valeur.

Comme plusieurs clés peuvent avoir le même hash, chaque case du tableau entries contient une liste chaînée d'éléments de type struct hashmap_entry_t dont les clés ont toutes le même hash.

Les opérations de base permettant de manipuler la hashmap vous sont données, à savoir : l'initialisation/destruction et les accesseurs put/get.

3 points

Écrivez le code de la fonction hashmap_size qui retourne le nombre total d'éléments stockés dans la hashmap donnée en paramètre.

4 points

Écrivez le code de la fonction hashmap_remove qui supprime l'élément de la hashmap correspondant au couple clé/valeur passé en paramètre.

3 points

Écrivez le code de la fonction hashmap_replace qui remplace la valeur de l'élément de la hashmap correspondant à la clé passée en paramètre.

Pour simplifier l'implémentation de cette fonction, on suppose qu'il ne peut pas y avoir plusieurs éléments ayant la même clé dans la hashmap.

Décompte participatif (10 points)

On veut connaître le nombre total de lignes d'un ensemble de fichiers texte.

Dans le répértoire exo2, se trouvent :

decompte_global.c, le squelette du code du programme principal;
decompte_local.c, le squelette du code d'un programme secondaire décrit un peu plus tard;
des fichiers de données fichierx, x allant de 0 à 9;
un fichier fichiers.txt inventoriant le chemin vers ces fichiers de données;
un Makefile.

Dans cet exercice, vous devez compléter le code de decompte_global et de decompte_local.

Le programme principal decompte_global distribue les fichiers du fichier fichiers.txt à un ensemble de processus fils decompte_local auxquels il sous-traite le décompte des lignes des fichiers leur étant assignés. Le nombre de ces processus fils est donné en paramètre de decompte_global. Une fois les décomptes locaux achevés, le processus decompte_global accumule les résultats intermédiaires pour obtenir le nombre de lignes global.

Afin de simplifier l'exercice, nous supposons que le nombre de processus sous-traitants permet une répartition équitable des fichiers. L'archive fournissant seulement 10 fichiers, répartissez-les uniquement sur 1, 2 ou 5 processus; ou adaptez à votre guise les fichiers de données.

Chaque question donne lieu à l'implémentation d'une seule portion de code à insérer dans les fichiers decompte_global.c ou decompte_local.c identifiée par une balise unique de la forme /*TODO Q2.a - ....*/.

1 point

Le fichier fichiers.txt liste l'ensemble des fichiers dont on veut sommer le nombre de lignes. Ce fichier est un fichier texte où chaque ligne, d'au maximimun FILENAME_MAXLEN caractères, correspond au chemin vers un fichier à prendre en compte. Dans decompte_global.c, stockez dans la variable nb_files le nombre de fichiers devant être traités, c'est-à-dire le nombre de lignes présentes dans le fichier fichiers.txt.

3 points

L'étape suivante de decompte_global consiste à lancer itérativement les processus fils devant compter localement le nombre de lignes global des fichiers leur étant confiés. Pour cela, dans chaque processus fils créé, lancez l'exécution du programme decompte_local grâce à la fonction execl avec pour paramètres le chemin relatif de l'exécutable decompte_local, le nom du programme decompte_local (de nouveau), le chemin du fichier fichiers.txt, le rang du lancement du processus lancé (i.e. l'itération courante de la boucle de lancement, autrement dit i), le nombre de fichiers à traiter et le chemin vers le fichier où écrire le résultat intermédiaire result.bin.

Chaque paramètre doit être une chaîne de caractères et doit donc être converti au besoin grâce à la fonction snprintf dont vous pouvez consulter la page de manuel.

Les processus fils decompte_local lancés, nous passons au fichier decompte_local.c. Le code du programme vous y est massivement donné. Lisez-le attentivement afin de comprendre ce qui est réalisé.

2 points

En fin du programme, il reste à transmettre la contribution. Pour cela, decompte_local doit écrire la variable cpt_lines dans le fichier passé en 4ème paramètre du programme, en l'occurrence le fichier result.bin. Au bout du compte, les contributions de chaque processus fils lancés doivent être écrites les unes après les autres sans séparateur suivant l'ordre de lancement du processus fils decompte_local dans ce fichier. Ainsi, l'entier cpt_lines est à placer en ième position dans le fichier, i correspondant au rang de lancement du processus courant, rang donné en second paramètre du programme.

2 points

Les processus decompte_local s'exécutent en parallèle. Expliquez si des problèmes de concurrence sont engendrés. Et si oui, proposez une méthode pour y remédier sans en donner l'implémentation.

2 points

De retour au programme principal decompte_global, une fois les processus sous-traitants lancés, il faut maintenant attendre que chacun ait écrit sa contribution pour ensuite en faire l'accumulation. Grâce à une boucle, attendez la fin de tous les processus fils créés.

2 points

À présent, il reste à faire l'accumulation des résultats intermédiaires en sommant tous les entiers présents dans le fichier result.bin. Écrivez le code correspondant.