CSC 4103 – Programmation système

Portail informatique

Le but de cet exercice est de s'exercer à l'utilisation de pointeurs, tout en faisant un peu d'algorithmique.

Pour cela, nous allons implémenter une table d'association (map en anglais). Le principe d'une table d'association est d'associer une clé à une valeur. Les tables d'associations sont très souvent utilisées comme mémoire cache afin d'augmenter la vitesse de réponse de site web. Par exemple, la table d'association memcached est utilisée par facebook ou twitter.

Pour cet exercice, nous vous fournissons plusieurs fichiers (dans map.tgz):

  • map.h: contient l'interface de la table d'association
  • test_map.c: un programme de test utilisant la table d'association. Ce programme simule le comportement d'un site web. Des requêtes de clients souhaitant consulter un produit sont générées. Si le produit est dans la table d'association, il est affiché. Sinon, il la description du produit est chargée depuis un fichier et ajouté à la table d'association.
  • products.dat: un fichier contenant la liste des produits disponibles

Pour commencer, mettons en place la chaîne de compilation. Dans le fichier map.c, créez des fonctions "vides" dont les prototypes sont dans map.h.

Créez ensuite un Makefile permettant de générer l'exécutable test_map à partir de test_map.c et map.c.

Dans un premier temps, nous allons implémenter la table d'association sous la forme d'un tableau de struct couple. Définissez le type struct couple comme une structure contenant une clé de type int, et une valeur de type void*.

Un struct map peut maintenant être défini comme une structure contenant un tableau de struct couple, et un entier représentant le nombre de couples (clé, valeur) stockés dans le tableau.

Implémentez la fonction map_init. Cette fonction alloue un struct map. Lors de l'initialisation de la structure, le pointeur est initialisé à NULL (donc le tableau est vide).

Implémentez la fonction map_put. Cette fonction cherche le couple dont la clé est passée en paramètre. Si aucun couple n'est trouvé, le tableau de couple est agrandi (en utilisant la fonction realloc), et le couple est stocké dans la dernière case du tableau. Enfin, la clé et la valeur passées en paramètre sont affectées au couple.

Implémentez la fonction map_get. Cette fonction cherche le couple dont la clé est passée en paramètre et retourne la valeur associée. Si la clé n'est pas trouvée, la fonction retourne NULL.

Enfin, implémentez la fonction map_free qui libère le tableau de couples et la structure map.

Vous pouvez maintenant tester votre implémentation en utilisant le programme test_map. Voici un exemple d'exécution attendu:

$ ./test_map Product #0: Fabulous Flower - Daisies http://dummyimage.com/214x137.png/dddddd/000000 Product #8: Helpful Wine - Dubouef Macon - Villages http://dummyimage.com/157x132.png/ff4444/ffffff [Cached] Product #0: Fabulous Flower - Daisies http://dummyimage.com/214x137.png/dddddd/000000 Product #9: Quirky Chocolate Bar - Coffee Crisp http://dummyimage.com/162x132.bmp/ff4444/ffffff Product #2: Industrious Wine - Jafflin Bourgongone http://dummyimage.com/218x203.bmp/ff4444/ffffff Product #1: Striped Rice - Jasmine Sented http://dummyimage.com/154x130.jpg/ff4444/ffffff [Cached] Product #1: Striped Rice - Jasmine Sented http://dummyimage.com/154x130.jpg/ff4444/ffffff [Cached] Product #9: Quirky Chocolate Bar - Coffee Crisp http://dummyimage.com/162x132.bmp/ff4444/ffffff [Cached] Product #0: Fabulous Flower - Daisies http://dummyimage.com/214x137.png/dddddd/000000 [Cached] Product #0: Fabulous Flower - Daisies http://dummyimage.com/214x137.png/dddddd/000000

L'implémentation d'une table d'association en utilisant des tableaux extensibles est certes simple mais très inefficace quand le nombre d'entrées devient grand (l'insertion d'un nouveau couple se fait en O(n), où n est le nombre des couples de la table d'association). Nous allons maintenant fournir une autre implémentation se basant sur un arbre binaire de recherche.

Faites une copie du fichier map.c nommée map_tree.c, et modifiez le Makefile pour créer un deuxième exécutable test_map_tree utilisant cette iméplementation à la place de celle présente dans map.c.

Pour stocker les couples dans un arbre binaire de recherche, définissez un type struct node contenant une clé, une valeur, et deux pointeurs vers struct node nommés left et right. La structure node représente un noeud de l'arbre, et left et right représentent les fils gauche et droit du noeud.

Modifiez la structure map afin qu'elle contienne un pointeur sur struct node nommé root. Ce pointeur fait référence à la racine de l'arbre binaire de recherche.

Implémentez la fonction map_init. Cette fonction alloue un struct map, et initialise root à NULL.

Implémentez la fonction map_free. Une façon simple d'implémenter cette fonction consiste à créer une fonction void free_node(struct node*n) qui libère récursivement les fils gauche et droit de n avant de libérer n.

Implémentez une fonction static struct node* insert_node(struct node* tree, struct node* n). Cette fonction insère le noeud n dans l'arbre tree et retourne la nouvelle racine de l'arbre. Cette fonction doit créer un arbre binaire de recherche: toutes les clés inférieures à la clé d'un noeud sont stockées dans son sous-arbre gauche, et toutes les clés supérieures à la clé d'un noeud sont stockées dans son sous-arbre droit.

Modifiez la fonction map_put afin d'utiliser insert_node lorsqu'un nouveau couple est inséré.

Modifiez la fonction map_get afin qu'elle recherche un couple dans l'arbre binaire de recherche.

L'utilisation d'un arbre binaire de recherche permet de réduire la complexité de la recherche d'une clé. Toutefois, il existe des cas pathologiques pour lesquels l'arbre construit est déséquilibré, et pour lequel la recherche d'une clé ne se fait pas en O(log(n)), mais en O(n) (où n est le nombre de couples (clé, valeur) stockés dans l'arbre).

Par exemple, en insérant les clés dans l'ordre croissant:

for(int i=0; i<N; i++) { map_put(map, i, ptr); }

chaque élément est inséré à droite de l'élément précédent, et l'arbre généré est donc une liste. La recherche d'un élément se fait donc en O(n).

Pour palier ce problème, il est nécessaire d'équilibrer l'arbre lors de l'insertion d'un élément. Une façon d'équilibrer l'arbre consiste à implémenter un arbre rouge-noir.

Implémentez la fonction void print_tree(struct map* map) qui affiche l'arbre binaire de recherche. Vérifiez avec cette fonction que l'insertion des clés 1, 2, ..., 10 mène à un déséquilibre de l'arbre.

Modifiez ensuite la fonction map_put afin qu'elle garantisse l'équilibre de l'arbre en utilisant l'algorithme décrit sur cette page. Vérifiez avec print_tree que l'équilibrage fonctionne.

Le but de cet exercice est de faire quelques utilisations simples des signaux et de vous montrer les problèmes qui peuvent se poser lorsqu'un gestionnaire de signal travaille sur une variable utilisée ailleurs dans le programme. Écrivez un programme qui associe le gestionnaire de signal nommé hello au signal SIGINT et effectue une boucle infinie. Votre gestionnaire de signal doit afficher Hello puis quitter. Modifiez votre programme de façon à ce que le programme quitte après avoir reçu N signaux, où N est défini comme une macro. Pour vos tests, vous fixerez pour le moment N à 5. Au lieu de terminer le programme directement dans le gestionnaire de signal, on veut maintenant sortir de la boucle de la fonction main. Pour cela, on vous propose de définir une variable globale nommée n et initialisée à 0. À chaque fois que le programme reçoit le signal SIGINT, votre gestionnaire de signal doit incrémenter n. Dans la fonction main, vous devez quitter une fois que n atteint la valeur N. Dans votre boucle d'attente, vous veillerez à ne rien faire, en particulier, il vous ait demandé de ne pas appeler de fonction (comme la fonction sleep). On vous demande aussi de compiler votre programme en désactivant les optimisations de code, c'est-à-dire en utilisant le drapeau -O0 de gcc lorsque vous compilez. Nous testons maintenant le programme en activant des optimisations agressives pendant la compilation. Pour cela, recompiler votre programme en utilisant le drapeau -O3. Vous devriez remarquer que votre programme ne termine plus. Proposez des hypothèses expliquant que votre programme ne termine plus. Pour que votre programme redevienne correct, il faut déclarer la variable n volatile. Pour quelle raison est-ce la solution ? On souhaite maintenant que le programme utilise la fonction alarm pour générer des signaux. Vous devez donc :
  • associer le gestionnaire hello au signal SIGALRM et non à SIGINT,
  • utiliser judicieusement la fonction alarm pour générer un signal toutes les secondes.
On souhaite maintenant augmenter la fréquence de réception des SIGALRM. Au lieu d'utiliser la fonction alarm, utilisez la fonction ualarm pour générer un signal SIGALRM toutes les millisecondes. Ensuite, on vous demande de :
  • modifier la macro N de façon à quitter après l'arrivée de 5000 signaux,
  • modifier la fonction hello de façon à n'afficher Hello que toute les 1000 réceptions de signaux.
A partir de cette question, nous mettons en place du code qui illustre les problèmes de synchronisation qui peuvent se poser entre un gestionnaire de signal et le reste du programme, À cette étape préliminaire, on vous demande de :
  • définir une variable globale volatile de type unsigned long long (64 bits) nommée k et initialisée à 0,
  • définir une variable locale de type unsigned long long dans la fonction main nommée ref et initialisée à 0n
  • incrémenter k et ref à chaque tour de boucle dans la fonction main,
  • afficher la différence entre ref et k avant de quitter dans la fonction main,
  • quitter après avoir reçu 100 signaux au lieu de 5000.

Votre programme doit naturellement afficher le résultat 0 puisque vous incrémenter simultanément ref et k à chaque tour de boucle.
Maintenant, à chaque fois que vous recevez un signal, vous devez décrementer la variable k. Pour quelle raison le programme n'affiche pas 100 alors qu'il devrait décrémenter 100 fois la variable k ? De façon à résoudre le problème, il faut masquer les signaux pendant qu'on incrémente k dans la fonction main. Masquer un signal signifie que le signal est bien envoyé au processus, mais mis en attente tant que le signal est masqué. Le signal est alors délivré au processus lorsqu'il démasque le signal. En vous basant sur l'exemple fourni dans la page de man de sigprocmask ou pthread_sigmask (selon votre installation), masquez les signaux pendant que vous incrémentez k dans le main. Vérifiez que votre programme affiche bien 100 après cette modification.