CSC 4103 – Programmation système

Portail informatique

Contrôle Final 1 – Année 2019/2020

Le barème est donné à titre indicatif
  • Durée du contrôle : 3h
  • Tous les documents sont autorisés

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

$ tar xf csc4103-cf1.tar.xz

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

Afin de rendre votre projet sous moodle, vous devez générer une archive avec la commande suivante :

$ make dist

Cette commande va générer une archive csc4103-cf1-rendu.tar.xz dans le répertoire parent de csc4103-cf1. Il vous suffit ensuite de déposer cette archive dans moodle.

Si par hasard vous avez un souci avec la commande make dist, générez votre archive manuellement avec la commande cd .. && tar -f csc4103-rendu.tar.xz -cJ csc4103-cf1.
Si, globalement, le Makefile qui se trouve dans l'archive ne fonctionne pas sur votre machine, vous pouvez essayer le Makefile simplifié que vous pouvez trouver ici.

L'archive contient les fichiers exo1.c à exo4.c destinés à recevoir les programmes que vous allez réaliser à chacune des questions. Normalement, tous les includes nécessaires à la réalisation du TP sont dans pokemon.h. Pour vous aider, nous avons mis en commentaire dans ce fichier la liste des fonctions utilisées dans le contrôle. On vous rappelle au passage que pour savoir comment utiliser une fonction, il faut faire man 2 fonction ou man 3 fonction. Par exemple pour comprendre comment utiliser sleep, il suffit de faire man 3 sleep (le 3 ici est important, sans lui, c'est la commande sleep et non la fonction sleep que vous verrez).

Pour compiler vos programmes, il vous suffit de lancer la commande make. Dans la correction, un bonus sera donné si la compilation se passe sans erreur. Si vous voulez nettoyer, il faut faire make cleanall et si vous avez besoin d'aide sur l'utilisation du makefile, il faut faire make help.

Les exercices se suivent, il faut donc, de préférence, les faire les uns après les autres. Si par hasard vous êtes bloqué et n'arrivez pas à terminer un exercice, on vous donne la liste des dépendances entre exercices :

  • l'exercice 2 peut être fait indépendamment de l'exercice 1, sauf pour la dernière question,
  • l'exercice 3 peut être fait indépendamment des exercices 1 et 2,
  • pour faire l'exercice 4, il faut avoir terminé les exercices 2 et 3,
  • certaines questions ne sont pas nécessaires pour la suite, dans ce cas, on vous l'indique.
Si vous réussissez à répondre à une question de l'exercice 1 alors que vous êtes en train de travailler dans un autre exercice, il n'est pas nécessaire de recopier vos modification dans les fichiers des exercices qui précédent. En d'autre terme, si vous réussissez à répondre à une question de l'exercice 1 alors que vous travaillez dans exo4.c, ne recopiez pas vos modifications dans les fichiers exo1.c à exo3.c. Les professeurs corrigerons les exercices en partant du fichier d'exercice le plus abouti. La séparation en exercices dans différents fichiers est principalement là pour vous aider si vous avez besoin de recommencer d'une version qui fonctionne.
De façon à gagner du temps, il ne vous est pas demandé pas de gérer les cas d'erreurs.

Liste chaînée (7 points)

Comme vous le savez peut-être, les pokemons sont des personnages imaginaires qui peuvent avoir différents types (feu, air etc...). Le but de cet exercice est d'être capable de compter le nombre de pokemons ayant un type donné. Pour cela, vous allez concevoir une liste chaînée dans laquelle les nœuds donnent le nombre de pokemons d'un type donné.

1 points

Dans le fichier exo1.c, ajoutez une structure nommée pokemon_type. Cette structure donne le nombre de pokemons d'un type donné, et contient un pointeur vers le nœud suivant de la liste. En détail, la structure pokemon_type contient :

  • un pointeur vers l'élément suivant nommé next,
  • un tableau de MAXLEN caractères nommée type donnant un type (MAXLEN est déjà défini dans pokemon.h),
  • et un entier nommé n donnant le nombre de pokemon du type stocké par le nœud.

Ajoutez aussi une variable globale nommée pokemon_types pointant vers le premier nœud de la liste chaînée des types de pokemons. Initialement, ce pointeur doit être initialisé à NULL puisque, initialement, il n'y a aucun type de pokemon enregistré.

2 point

Écrivez une fonction void add(const char* type, int n) qui crée un nœud (type, n) et l'insère en tête de la liste chaînée. Cette fonction ne doit créer le nœud que si le paramètre type n'est pas une chaîne vide (c'est-à-dire une chaîne avec zéro caractères).

À cette question, on ne vous demande pas de vérifier si il existe déjà un nœud du type donné en paramètre dans la liste.

On vous rappelle que :
  • la fonction strncpy permet de copier une chaîne de caractères dans une autre,
  • la fonction strlen donne le nombre de caractères d'une chaîne.

Copiez-collez le code suivant au début de votre fonction main pour tester votre code :

add("Terre", 1); add("Feu", 3); add("Féérique", 4); add("Eau", 5); add("Féérique", 3);

1 point

Écrivez une fonction void print(FILE* f) écrivant dans le flux f le nombre de pokemon de chaque type. Le formatage de cet affichage deviendra important vers la fin de l'exercice : il faut afficher, sur une ligne, le type suivi d'un espace, suivi du nombre de pokemons. Ajoutez aussi un appel à print(stdout) pour afficher l'état de la liste sur le terminal à la fin de la fonction main. Si votre code est correct, vois devriez avoir cet affichage :

$ ./exo1 Féérique 3 Eau 5 Féérique 4 Feu 3 Terre 1

2 points

On souhaite maintenant éviter d'avoir plusieurs fois le même type dans la liste. La première fois qu'un type est ajouté, il faut donc créer un nœud, mais les fois suivantes, il faut réutiliser le nœud préalablement créé. Sur notre exemple, à la fin, on souhaite donc qu'il n'y ait qu'un unique nœud Féérique qui compte 7 pokemons de ce type. Modifiez votre code en conséquence.

On vous rappelle que la fonction strcmp permet de comparer deux chaînes de caractères.

1 point

Ajoutez une fonction void cleanup() permettant de libérer tous les nœuds de la liste chaînée et de réinitialiser pokemon_types à NULL. Ajoutez un appel à cleanup() à la fin de la fonction main.

La réussite de cette question n'est pas nécessaire pour faire la suite de l'examen.

Lecture de fichiers (4 points)

Dans cet exercice, nous allons compter le nombre de pokemons de chaque type en lisant un fichier contentant tous les pokemons existants.

Avant de commencer, copiez le fichier exo1.c en exo2.c. Ensuite, supprimez l'ajout manuel des 5 pokemons du début de la fonction main (les 5 add de la question 1.b), mais gardez les appels à print et cleanup.

1 point

La liste des pokemons se trouve dans le fichier pokedex.dat (défini par la macro POKEDEX dans pokemon.h). Ce fichier contient un tableau de structures pokemon (voir aussi fichier pokemon.h).

Au début de la fonction main, commencez par calculer le nombre de pokemons se trouvant dans le fichier pokedex.dat avant de fermer le fichier. Stockez ce nombre dans une variable locale total. Si vous trouvez que total vaut 719, c'est que vous avez réussi la question.

On vous demande de ne pas lire le fichier pour répondre à cette question.

3 point

Ajoutez une fonction void process(int first, int n) à exo2.c. Cette fonction ouvre le fichier pokedex.dat et parcourt n entrées à partir de first. Pour chaque entrée, la fonction doit mettre à jour la structure pokemon_types (voir exercice 1) en fonction des types du pokemon lu. Il faut savoir qu'un pokemon a un ou deux types (champs type[0] et type[1] de la structure pokemon), et qu'un même pokemon peut donc compter deux fois.

Dans la fonction main, utilisez process(0, total) puis affichez le nombre total de pokemons de chaque type. Si vous trouvez 18 types différents de pokemons, et si, parmi ceux-ci, vous trouvez 117 pokemons de type Water, vous avez réussi la question, félicitations.

Processus et synchronisations (4 points)

Le but des deux exercices suivants est de paralléliser le calcul du nombre de pokemons de chaque type. Au lieu d'utiliser un unique processus pour traiter le fichier pokedex.dat, le processus père va donc créer nb_children processus fils qui vont se répartir ce traitement.

À haut niveau, le but est que chaque processus fils parcourt q = total/nb_children entrées : le fils 0 parcourt q entrées à partir de l'indice 0, le fils 1 parcourt q entrées à partir de l'indice q, etc...

Toutefois, comme nb_children ne divise par forcément total, il va y avoir un reste r = total - q*nb_children. Idéalement, il faudrait équirépartir ces r entrées restantes entre les nb_children fils. Toutefois, pour simplifier le code, on choisit de faire traiter les r entrées supplémentaires par le dernier fils. En détail, le iième fils traite q entrées à partir de l'entrée i * q, sauf le dernier fils qui traite q + r entrées.

Pour illustrer, avec nb_children = 7 et total = 719, les 6 premiers fils traitent 102 entrées et le dernier traite 107 entrées.

Dans cet exercice, on s'occupe de créer les fils, de calculer les entrées qu'ils doivent traiter et de synchroniser le père et ses fils. Dans l'exercice suivant, on s'occupe de la parallélisation proprement dite.

Avant de commencer, copiez exo2.c en exo3.c.

1 point

On souhaite que le nombre de processus fils utilisé pour la parallélisation soit un paramètre du programme. Au début de la fonction main, avant le code que vous avez écrit pour les exercices précédents, stockez, dans une variable nb_children de type entier, le paramètre donné au programme. En l'absence de paramètre, votre programme doit afficher une erreur et quitter.

On vous rappelle que la fonction atoi permet de convertir une chaîne de caractères en entier. Si vous n'arrivez pas à faire cette question, définissez simplement une variable locale nb_children valant 7 dans votre fonction main.

1 point

Après avoir calculé le nombre d'entrées de pokedex.dat mais avant l'appel à process, créez nb_children processus fils à l'aide d'une boucle. Chaque processus fils doit, pour le moment, s'endormir 1 seconde (fonction sleep) avant d'afficher [PID] child quitting et de quitter.

1 point

Modifiez votre programme de façon à ce que le père exécute la fonction process en parallèle des ses enfants, mais ne quitte que après la terminaison des nb_children enfants. Pour vous assurez que le comportement de votre programme est correct, ajoutez un affichage de [PID] quitting juste avant que la fonction main retourne. Si vous voyez systématiquement les affichages de [PID] children quitting avant l'affichage de [PID] quitting, c'est que votre synchronisation est correcte.

1 point

Pour chaque fils, stockez dans une variable first l'indice à partir duquel le fils doit traiter le fichier pokedex.dat, et dans une variable n le nombre d'entrées que le fils doit traiter. Affichez aussi ces bornes avec le PID du fils.

À cette étape, le code de votre programme devrait être à peu près celui-ci :

  • Pour un fils :
    • calcul first et n (ajouté à cette question),
    • affiche [PID] process n entries from first (ajouté à cette question),
    • dort 1 seconde (question 3.b)
    • affiche [PID] child quitting (question 3.b),
    • quitte (question 3.b).
  • Pour le père :
    • extrait nb_children à partir de l'argument donné au programme (question 3.a),
    • calcul total (question 2.a)
    • crée les nb_children processus enfants (question 3.b),
    • calcul et affiche du nombre de pokemons de chaque type (question 2.b),
    • attend la terminaison des enfants (question 3.c),
    • affiche [PID] quitting (question 2.b),
    • quitte.

Parallélisation finale (5 points)

Dans cet exercice, on s'occupe de terminer la parallélisation de notre programme. Pour commencer, copiez exo3.c en exo4.c.

1 point

Commencez par supprimer le process(0, total) du père. Ensuite, dans un fils, juste après avoir affiché [PID] process n entries from first, appelez process de façon adéquate pour traiter les entrées assignées au fils. Ensuite, il va falloir communiquer le résultat du traitement au père. Pour cela, nous utilisons un fichier result. Pour communiquer son résultat, un fils doit simplement utiliser la fonction print que vous avez mise en œuvre à question 1.c de façon à ajouter ses résultats au fichier result.

Il n'est pas nécessaire de synchroniser les processus enfants entre eux car un appel à fprintf est atomique, c'est-à-dire qu'un fprintf s'exécute entièrement avant qu'un autre ne puisse commencer. C'est aussi le cas pour la fonction fopen qui peut créer le fichier result.
Pour vos tests, il vous est conseillé d'ajouter un unlink("result") au début du main de façon à vous assurer que le programme démarre toujours avec un fichier result vide.

2.5 points

Dans le père, utilisez le fichier result afin de calculer et afficher le nombre total de pokemons de chaque type.

À cette question, le père n'a plus le droit d'appeler process lui-même : il ne peut plus qu'utiliser le fichier result. Pour vous assurer que votre code est correct, pensez à vérifier que vous avez toujours le même nombre de pokemons de chaque type.

1,5 points

Dans cette question, on vous propose d'optimiser légèrement la synchronisation entre le père et ses fils. Techniquement, on vous demande d'utiliser un sémaphore pour que le père puisse commencer à traiter le fichier result dès que les fils ont écrit le résultat de leur traitement dans le fichier result. Commencez par ajouter sleep 1 juste avant la terminaison du fils. Ensuite, faîtes en sorte que le père puisse lire un fichier result correct sans avoir besoin d'attendre cette seconde artificiellement ajoutée.

Pour votre culture (à lire si vous avez le temps), il faut savoir que l'architecture de calcul que vous avez mise en œuvre dans ce contrôle s'appelle MapReduce. La phase de répartition du calcul entre les enfants s'appelle la phase de Map (projection des données), et la phase d'agrégation des résultats partiels s'appelle la phase Reduce. L'architecture MapReduce a été popularisée par Google avec le framework MapReduce qui utilise cette architecture pour répartir les calculs sur plusieurs machines. Cette architecture est aujourd'hui utilisée pour effectuer des traitements sur de grands volumes de données par la plupart des entreprises majeures du Web.