CSC 4103 – Programmation système

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

Le barème est donné à titre indicatif

Durée du contrôle : 2h
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.

Les exercices sont indépendants.

Mise en œuvre d'une Hashmap (10 points)

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

hashmap.h: defini l'interface d'une hashmap
hashmap.c: implemente une hashmap
test_hashmap.c: un programme pour tester l'implémentation de la hashmap

Une hashmap est une structure de données qui associe un clé à une valeur. Ce type de structure de données est fréquemment utilisée 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.

Puisque plusieurs clés peuvent avoir le même hash, la case du tableau entries contient une liste chaînée de toutes les clés ayant le même hash.

2 points

Dans un premier temps, créez le fichier Makefile permettant de générer:

la bibliothèque partagée libhashmap.so à partir du fichier hashmap.c
l'exécutable test_hashmap à partir de test_hashmap.c et libhashmap.so

Makefile

1 point

Complétez le code de la fonction hashmap_init.

Cette fonction doit initialiser la structure hashmap passée en paramètre en mettant à NULL toutes les cases du tableau entries.

3 points

Complétez le code de la fonction hashmap_put.

Cette fonction doit:

appeler hash(key) pour savoir dans quelle case (appelée h) du tableau entries insérer la nouvelle entrée;
allouer une nouvelle struct hashmap_entry_t (appelée new_entry) et l'initialiser. Pensez à y recopier key et value;
insérer new_entry dans la liste chaînée h.

Pour simplifier l'implémentation de cette fonction, on suppose que la clé à insérer n'est pas déja présente dans la hashmap.

2 points

Complétez le code de la fonction get.

Cette fonction doit retourner le struct hashmap_entry_t correspondant à la clé key. Pour cela, la fonction doit parcourir la liste chaînée h (où h=hash(key)) et comparer key avec chaque clé de la liste. Lorsqu'une clé identique est trouvée, la fonction retourne l'entrée correspondante. Si la clé n'est pas trouvée dans la liste, la fonction retourne NULL.

2 points

Complétez le code de la fonction hashmap_finalize.

Cette fonction doit libérer toutes les entries stockées dans la structure hashmap.

hashmap.c

Dépouillage de votes à l'américaine (10 points)

Pour ou contre le retour en présentiel en cours? Les étudiants de la planète entière ont été invités à répondre à cette question et il est à présent l'heure de dépouiller les votes. Ceux-ci-sont stockés sous la forme de caractères : 1 pour exprimer un "pour" et 0 pour "contre"; mis les uns à la suite des autres dans un fichier au format texte nommé votes.txt.

Afin d'accélérer le traitement de cet énorme fichier, on propose dans cet exercice de procéder au dépouillement en faisant appel à plusieurs dépouilleurs en charge de traiter en parallèle des parties différentes du fichier de votes et de transmettre le résultat exprimé par la majorité des votes qu'il a eus à traiter. Le résultat final étant ainsi un décompte de ces résultats partiels, comme cela serait fait aux États-Unis en faisant le dépouillement état par état puis en comptant le nombre d'états exprimant le même avis.

À partir de l'archive fournie, les questions vous permettront de construire le programme de manière incrémentale. Seul le code final devra être soumis pour notation. Le programme depouillage.c correspond au programme principal en charge de distribuer les données à traiter et de collecter les résultats produits par les dépouilleurs dont le code se trouve dans le fichier depouilleur.c.

1 points

Chaque dépouilleur traite le même nombre de vote. Dans le fichier depouillage.c, après avoir ouvert le fichier "votes.txt", placez-vous en fin de fichier afin de connaître le nombre de votes exprimés et stockez dans la variable chunk le nombre de votes devant être traités par chaque dépouilleur. Le traitement du surplus est traité par le programme initial depouillage par la suite (le code vous en est donné).

3 points

A présent, il vous est demandé de lancer itérativement les processus dépouilleurs grâce à une fonction de la famille exec, execl étant suggérée. Pour cela, convertissez les différents paramètres à lui donner sous la forme de chaînes de caractères grâce à la fonction snprintf. Faites attention à mettre en premier paramètre le chemin (relatif ou absolu) de l'exécutable depouilleur puis le nom du programme à lancer depouilleur et l'ensemble des paramètres tels qu'ils doivent se présenter dans le tableau argv de la fonction principale de depouilleur. Vous ferez également bien attention à vous rappeler que les fonctions de la famille exec ne reprennent le fil de l'exécution du programme initial qu'en cas d'erreur. Pour tester votre programme, n'oubliez pas de compiler au préalable depouilleur.

Après avoir traité le surplus de votes non assignés aux dépouilleurs, le programme depouillage se met à ce stade en attente des résultats partiels des depouilleurs grâce à une boucle conditionnée par la variable nb_contrib, correspondant au nombre de dépouilleurs ayant transmis son résulat.

1 points

Placez-vous à présent dans le fichier depouilleur.c. Avant de vous intéresser à comment les depouilleurs transmettent leur résultats partiels au depouillage, positionnez la tête de lecture au début des données à traiter par le dépouilleur. Le nom du fichier ayant collecté les votes, le démarrage et la taille de la portion de votes à traiter par le depouilleur lui sont donnés en paramètre.

1 points

Décomptez les votes en lisant caractère par caractère la portion du fichier à traiter en utilisant les variables pour et contre.

3 points

À présent, il faut transmettre au depouillage le résultat obtenu sur le sous-ensemble de votes traités, i.e. égalité, pour ou contre. Pour cela, utiliser trois signaux différents pour notifier depouillage et mettant en place leur traitement du côté depouillage.

2 points

Les résultats partiels sont collectés dans des variables pour, contre et par effet de bord nb_contrib dans depouillage. Étudiez les situations de concurrence possibles et protégez les sections critiques en fonction. Vous pouvez donner une explication en la mettant en commentaire en fin du fichier depouillage.c

depouilleur_solution.c

depouillage_solution.c