Portail informatique 2019-2020

Systèmes d'exploitation

Avec l'augmentation du nombre d'utilisateurs, le serveur FaceBook doit faire face à une augmentation du nombre de connexion à traiter chaque seconde. Pour absorber cette augmentation, une solution est d'accélérer le traitement de certaines pages.

Pour cela, nous allons mettre en place un système de cache mémoire inspiré de memcached. Le principe est de stocker en mémoire le contenu d'une page qui peut être réutilisée plus tard. Par exemple, la page de profil d'un utilisateur peut être gardée en mémoire, puis réutilisée telle quelle tant que son profil n'est pas modifié.

Pour commencer, récupérez la base du TP d'aujourd'hui:

  • git clone -b tp7_base https://stark2.int-evry.fr/asr3/csc4508_facebook/ csc4508_tp7
  • ou git checkout tp7_base

Le cache que nous allons mettre en place associe une clé (par exemple, l'URL demandée) avec une donnée (par exemple, le contenu de la page à afficher). Les différents couples (clé, valeur) sont stockés sous la forme d'un arbre binaire de recherche ordonnée par la clé.

Le but de cet exercice est d'implémenter un arbre AVL (arbre de Georgy Adelson-Velsky et Landis) qui a pour propriété de s'autoéquilibrer. Dans un arbre AVL, la hauteur de deux arbres enfant d'un nœud quelconque diffère d'au plus 1. Si à un moment, leur hauteur diffère de plus de un, un rééquilibrage est déclenché.

Cela garantit une vitesse de recherche dans l'arbre qui est en log2(n), n étant le nombre de nœuds.

Par exemple, l'arbre de la figure 1 est un arbre AVL, car, pour chaque nœud, la différence de hauteur entre le sous-arbre de gauche et le sous-arbre de droite est inférieure ou égale à 1.

Exemple d'arbre AVL
Figure1 : exemple d'abre AVL (exemple provenant d'ici)

En revanche, l'arbre de la figure 2 n'est pas un arbre AVL. En effet, pour le nœud 12, la hauteur du sous-arbre de gauche est 4, tandis que la hauteur du sous-arbre de droite est 2.

Exemple d'arbre non-AVL
Figure 2 : exemple d'arbre non-AVL (exemple provenant d'ici)

Dans cet exercice, vous allez coder un arbre AVL que nous utiliserons pour stocker des paires clé/valeur comme le font les classes Dictionnary de Java et std::map de la STL C++.

Le répertoire memcache contient un ensemble de fonctions qui vont servir de base à l'implémentation de cet arbre.

Dans arbreAVL.c, complétez tous les TODO des fonctions updateHeight(), nbNodes(), newNode() et insert(). Ne vous occupez pas de release() pour l'instant.

NB : Ne vous préoccupez pas pour l'instant de construire un arbre équilibré (la fonction insert ne réalise donc pas, pour l'instant, d'auto-équilibrage) ou du stockage de la valeur associée à chaque clé. Aussi, votre fonction insert doit travailler de la manière suivante :

  • Si node vaut NULL, insert renvoie newNode(key)
  • Si key est plus petit que node->key, insert insère key dans une feuille la plus basse possible du sous-arbre de gauche de node.
    Pour ce faire, nous vous recommandons d'appeler récursivement insert. NB : la fonction insert() renvoie un struct node *. Aussi, n'oubliez pas de stocker le noeud renvoyé par insert() dans votre structure de données (ne vous contentez pas d'appeler insert() sans tenir compte de sa valeur de retour, dit autrement comme si c'était une procédure ; vous auriez alors probablementdes bugs à cette question ou aux questions suivantes).
  • Si key est plus grand que node->key, insert insère key dans une feuille la plus basse possible du sous-arbre de droite de node.
    Pour ce faire, nous vous recommandons d'appeler récursivement insert. Même NB qu'au point précédent.
  • Si key est égal à node->key, insert renvoie simplement node sans rien faire d'autre (ainsi, il n'y jamais deux valeurs identiques dans l'arbre).
  • Puis, insert met à jour le champ height de node.

Une fois que vos fonctions sont codées, tapez make run. Corrigez vos fonctions jusqu'à ce que make run affiche:

[ RUN      ] test_insert_et_nbNode [       OK ] test_insert_et_nbNode

Dit autrement, le test unitaire test_insert_et_nbNode est OK.

Exécutez maintenant valgrind ./testsUnitaires. Valgrind vous signale au minimum que vous avez des fuites mémoires. Complétez release() et éventuellement les autres fonctions codées jusqu'à présent pour que valgrind ./testsUnitaires ne vous signale aucun problème d'accès mémoire ou de fuite mémoire.

Ainsi, test_insert_et_nbNode et test_release sont OK.

Implémentez la fonction interne getKeyNode() qui permet de rechercher une clé dans l'arbre. N'oubliez pas de vérifier avec valgrind que vous n'avez aucun soucis d'accès mémoire ou de fuite mémoire.

Cette question a pour objectif de travailler à l'équilibrage de l'arbre au moment de sa construction.

Pour ce faire, une fois l'insertion réalisée, pour chacun des nœuds concernés par l'insertion, il faut calculer sa "balance", i.e. la différence de hauteur entre le sous-arbre gauche du nœud et son sous-arbre droit.

Si la balance d'un nœud est comprise entre -1 et +1, il n'y a rien à faire.

En revanche, si la balance d'un nœud est strictement inférieure  à -1 ou strictement supérieure à +1, il faut rééquilibrer l'arbre au niveau de ce nœud. 4 cas se présentent (à traiter dans la fonction insert() après le calcul de la balance). Dans la présentation de ces 4 cas, 3 nœuds jouent un rôle particulier :

  • z est le nœud le plus profond au niveau duquel la balance est strictement inférieure à -1 ou strictement supérieure à +1 ;
  • x est le nœud petit-enfant de z, dont l'arbre contient la clé qui vient d'être insérée ;
  • y est le nœud enfant de z, qui est parent de x.

1er cas - Cas Gauche-Gauche : Au niveau de z, l'arbre est déséquilibré à gauche. De plus, x est situé à gauche de y. Alors, pour rééquilibrer l'arbre, il suffit d'effectuer une rotation droite de z (cf. figure 3).

Rotation droite de z
Figure 3 : Traitement du cas Gauche-Gauche (figure provenant d'ici)

2ème cas - Cas Droite-Droite : Au niveau de z, l'arbre est déséquilibré à droite. De plus, x est situé à droite de y. Alors, pour rééquilibrer l'arbre, il suffit d'effectuer une rotation gauche de z (cf. figure 4).

Rotation gauche de z
Figure 4 : Traitement du cas Droite-Droite (figure provenant d'ici)

3ème cas - Cas Gauche-Droite : Au niveau de z, l'arbre est déséquilibré à gauche. De plus, x est situé à droite de y. Alors, pour rééquilibrer l'arbre, il suffit d'effectuer une rotation gauche de y, puis une rotation droite de z (cf. figure 5).

Rotation gauche de y, puis rotation droite de z
Figure 5 : Traitement du cas Gauche-Droite (figure provenant d'ici)

4ème cas - Cas Droite-Gauche : Au niveau de z, l'arbre est déséquilibré à droite. De plus, x est situé à gauche de y. Alors, pour rééquilibrer l'arbre, il suffit d'effectuer une rotation droite de y, puis une rotation gauche de z (cf. figure 6).

Rotation droite de y, puis rotation gauche de z
Figure 6 : Traitement du cas Droite-Gauche (figure provenant d'ici)

Gérer ces 4 cas pour ce nœud suffit à rééquilibrer l'arbre entier, car l'arbre retrouve sa hauteur d'origine.

Les fonctions rightRotate et leftRotate vous sont fournies. Ajoutez le calcul de la balance et le traitement des 4 cas à la fonction insert().

Puis, tapez make run. Corrrigez vos fonctions jusqu'à ce que :

  1. les tests test_equilibrageGaucheGauche, test_equilibrageDroiteDroite, test_equilibrageGaucheDroite et test_equilibrageDroiteGauche soient OK ;
  2. valgrind ./testsUnitaires ne vous signale aucun problème d'accès mémoire ou de fuite mémoire.

Jusqu'à présent, notre arbre AVL n'a servi qu'à stocker des clés. Cette question a pour objectif d'utiliser cet arbre pour y stocker des paires clé/valeur, et ainsi obtenir une structure de données de type dictionnaire (cf. classes Dictionnary de Java et std::map de la STL C++) nous permettant de retrouver la valeur associée à une clé avec une complexité en O(log(n)).

Complétez arbreAVL.h et arbreAVL.c :

  1. ajoutez un champ char *value à la structure Node ;
  2. ajoutez un paramètre char *value à la fonction newNode et recopiez son contenu dans la chaîne de caractère value du nœud créé ;
  3. ajoutez un paramètre char *value à la fonction insert et utilisez ce paramètre de manière adéquate dans cette fonction. En particulier, s'il existe déjà un nœud ayant pour clé key dans l'arbre, veillez à remplacer l'ancienne valeur du champ value de ce nœud à l'aide de ce paramètre ;
  4. Complétez la fonction getValue()
    NB : il est probable que l'algorithme de recherche du nœud dans getValue()ressemble à s'y méprendre à l'algorithme de recherche du nœud dans getKeyHeight(). Pour éviter une duplication de code (jamais saine dans un projet), créez une fonction qui centralise ce code et qui est appelée par getValue()et getKeyHeight().

Prenez en compte, dans les tests unitaires testsUnitaires_usernameUnix.c, le changement de la signature de la fonction insert() en tapant les commandes suivantes dans un terminal:

cp   testsUnitaires_$USER.c   /tmp   # pour sauvegarder votre fichier initial sed   's@); //@,@g'   testsUnitaires_$USER.c > /tmp/toto.c cp   /tmp/toto.c   testsUnitaires_$USER.c

Par précaution, vérifiez que les changements de ligne se sont bien passés en tapant

diff  testsUnitaires_$USER.c   /tmp/testsUnitaires_$USER.c   |   grep   -v   insert

Vous ne devez avoir que des lignes du style:

38c38 --- 54,58c54,58 ---

dit autrement, que des lignes mentionnant des numéros de lignes (comme 38c38 ci-dessus) ou "---". Si ce n'est pas le cas, faites

cp   /tmp/testsUnitaires_$USER.c   .

afin de récupérer votre fichier initial. Puis, postez un message de SOS sur le forum.

Enfin, tapez make run. Corrigez vos fonctions jusqu'à ce que :

  1. le test test_getValue soit OK ;
  2. valgrind ./testsUnitaires ne vous signale aucun problème d'accès mémoire ou de fuite mémoire.
Modifier les fichiers memcache.h et memcache.c afin d'implémenter un cache à partir de l'arbre de recherche. Le cache comporte 3 fonctions:
  • void memcache_init(struct memcache_t* cache): initialize le cache
  • void memcache_set(struct memcache_t* cache, const char* key, void* value) : ajoute le couple (key, value) au cache
  • void* memcache_get(struct memcache_t* cache, const char* key): retourne la valeur associée à la clé key

Une fois intégré au serveur FaceBook, le cache risque d'être utilisé par plusieurs threads simultanément. Il est donc nécessaire de le protéger contre des accès concurrents.

Modifiez votre implémentation afin de gérer les accès concurrents tout en limitant les problèmes de contention.

Afin d'accélérer l'affichage de certaines pages, nous allons utiliser le cache en associant une URL (par exemple "view_user?user=0") à une réponse (dans ce cas, la page affichée pour l'utilisateur 0).

Dans process_requests.c, déclarez une variable globale de type struct memcache_t et initialisez le.

Dans un premier temps, nous allons commencer par la mise en cache de la fonction do_help. Modifiez cette fonction de la façon suivante:

  • Si la clé page_request->url est dans le cache, recopier la valeur associée dans page_request->reply et sortir de la fonction
  • Sinon, allouer un struct page_reply et le remplir avec le contenu de la page
  • Ajouter le couple (clé, valeur) dans le cache.

Pour tester votre implémentation, il est conseillé d'ajouter des messages indiquant si la page est générée ou recopiée depuis le cache. Vous pouvez également simuler un calcul complexe nécessaire à la génération de la page en ajoutant un appel à la fonction sleep()

Procédez de la même manière pour la fonction do_hello.

La fonction do_view_user est légèrement plus complexe à mettre en cache. En effet, le contenu affiché peut changer lorsque le profil de l'utilisateur est modifié.

Une solution à ce problème consiste à ajouter une estampille à la page en cache et au profil de l'utilisateur. Si l'estampille de l'utilisateur est plus récente que l'estampille en cache, il est nécessaire de mettre à jour le cache.

Implémentez cette solution dans la fonction do_view_user

  • ajoutez un champ last_modified de type struct timeval dans la structure user. À chaque modification de l'utilisateur, mettez à jour ce champ avec un appel à gettimeofday()
  • Définissez une structure struct reply contenant un tableau de caractères reply et une estampille.
  • Dans la fonction do_view_code, si l'estampille de la réponse est plus ancienne que l'estampille de l'utilisateur, regénérez la page et mettez à jour l'estampille.
Le corrigé de cet exercice est disponible dans la branch tp7_corrige du dépôt git.