Département INFormatique 
 CSC4508/M2 : Conception et programmation des systèmes centralisés


   Évaluation



TÉLÉCOM SudParis 2ème année

TP Noté CSC4508/M2 du 13/06/17

(Corrigés)

Modalités

Durée : 3 heures

Tous documents autorisés.

Les questions 1, 2 et 3 sont indépendantes les unes des autres. Aussi, n'hésitez pas à lire tout le sujet avant de commencer pour déterminer l'ordre dans lequel vous souhaitez traiter les questions.

Le barème est donné à titre indicatif des poids entre les différentes questions.

La « livraison » de votre travail en fin de TP noté se fera par remontée sous Moodle (rubrique « TP noté de 3 heures ») du fichier d'extension tgz constitué de la manière suivante :
cd votreRepertoireDeTravailPourCSC4508M2
tar cvfz ${USER}.tgz ${USER}_TPNote2017

Préparation

	      cd votreRepertoireDeTravailPourCSC4508M2
	      wget http://www-inf.it-sudparis.eu/COURS/CSC4508/Current/Documents/ExoCoursSys/TPNote2017/WWW/tPNote2017.tgz
	      tar xvfz tPNote2017.tgz
	      mv TPNote2017 ${USER}_TPNote2017
	      cd ${USER}_TPNote2017

Question 1 : Gestion de comptes en banque (7.5 points)

Dans le réperoire Q1, vous trouverez un programme permettant de gérer des comptes en banque. Ce programme stocke dans le fichier comptes.dat le solde de tous les comptes d'une banque. Le solde de chaque compte est stocké sous la forme d'un entier (codé sur 4 octets).

Par exemple, le fichier peut contenir:

AAAABBBBCCCCDDDDEEEE

Ce qui signifie que le compte numéro 0 a pour solde la valeur entière codée par les 4 octets AAAA. Le compte numéro 1 a pour solde BBBB, le compte 2 a pour solde CCCC, etc.

Question 1.1

Implémentez, dans le fichier Q1/Q1.1/libcompte.c, les fonctions suivantes:

  • int compte_init(const char* filename): cette fonction ouvre le fichier filename en mode lecture/écriture et retourne le file descriptor obtenu. Si le fichier n'existe pas, la fonction le crée. Vous pouvez également initialiser des variables dans cette fonction. En cas d'erreur lors d'un des traitements de la fonction, la fonction retourne la valeur -1.
  • void compte_finalize(int fd): cette fonction ferme le fichier dont le file descriptor est passé en paramètre. Vous pouvez utiliser cette fonction pour terminer proprement le programme (libérer des buffers alloués dynamiquement, etc.)
  • int ecrire_solde(int fd, int cpt_id, int new_solde): cette fonction écrit dans le fichier la valeur new_solde à l'emplacement du compte cpt_id. La fonction retourne -1 en cas d'erreur, ou 0 sinon.
  • int lire_solde(int fd, int cpt_id): cette fonction lit dans le fichier et retourne le solde du compte cpt_id. La fonction retourne -1 en cas d'erreur.
  • int nb_compte(int fd): cette fonction calcule le nombre de comptes stockés dans le fichier. Elle retourne -1 en cas d'erreur.

Pour chacune de ces fonctions, veillez à traiter proprement les erreurs.

---beginCorr (3.5 points)
programme corrigé
Barème:

  • int compte_init(const char* filename)+void compte_finalize(int fd): 1 point
  • int ecrire_solde(int fd, int cpt_id, int new_solde):1 point
  • int lire_solde(int fd, int cpt_id): 1 point
  • int nb_compte(int fd): 0.5 point
---endCorr

Question 1.2

Le fichier libcompte.c implémente un ensemble de fonctions pour manipuler des comptes. Les fonctions que vous avez implémentées à la question précédentes servent de base pour deux fonctions utilisées par l'application:

  • void transfert(int fd, int cpt_src, int cpt_dest, int montant): effectue un transfert d'argent entre deux comptes
  • int balance(int fd): parcoure l'ensemble des comptes et calcule la balance

L'implémentation actuelle n'est pas thread-safe. Identifiez les deux problèmes (des fonctions dans libcompte.c) qui risquent de survenir si plusieurs threads utilisent simultanément les fonctions implémentées dans libcompte.c.

Pour chaque problème, décrivez dans Q1/reponses_Q1.txt un exemple d'exécution générant le problème.

---beginCorr (2 points)

  • Problème 1: on utilise lseek pour positionner le curseur où lire/écrire. Donc si le thread T1 exécute lire_compte(cpt=1) pendant que T2 exécute ecrire_solde(cpt=2), on peut avoir l'exécution suivante:
    • T1 positionne le curseur sur le compte 1
    • T2 positionne le curseur sur le compte 2
    • T1 lit la valeur où est positionné le curseur (donc la valeur du compte 2)
  • Problème 2: dans transfert(), on lit le solde de 2 comptes, on calcule le nouveau solde, puis on écrit le solde. Si le solde d'un des comptes est modifié entre temps, une des modifications est perdue.

---endCorr

Question 1.3

Copiez le fichier Q1/Q1.1/libcompte.c dans le répertoire Q1/Q1.3, et modifiez l'implémentation de façon à corriger les deux problèmes identifiés à la question précédente.

---beginCorr (2 points)
programme corrigé
---endCorr

Question 2 : liste chaînée (7 points)

Vous avez chargé un étudiant de développer un programme remplissant une liste de valeurs aléatoire. Le programme doit ensuite trier la liste, l'afficher, puis libérer la mémoire allouée.

Malheureusement, l'étudiant a décidé d'arrêter le travail pour se consacrer à sa carrière de Youtubeur spécialisé dans les Hand Spinner. Vous vous retrouvez donc avec le programme inachevé Q2/linked_list.c.

Question 2.1

Bien que le programme compile sans warning, le programme génère une erreur de segmentation à l'exécution.

Dans le réperteroire Q2/Q2.1, corrigez le programme pour qu'il s'exécute sans erreur.

---beginCorr (1 points)
programme corrigé
---endCorr

Question 2.2

Les blocs mémoire alloués dans la fonction list_add ne sont jamais libérés. Cela peut poser problème car vous envisagez d'utiliser ce programme pour manipuler de nombreuses listes.

Implémentez la fonction free_list dans le fichier Q2/Q2.2/linked_list.c. Cette fonction doit libérer les blocs mémoire d'une liste et remettre à NULL le pointeur list déclaré dans la fonction main.

---beginCorr (3 points)
programme corrigé
Barème:

  • 2.5 point pour la libération de tous les blocs de la liste
  • 0.5 point pour la réinitialisation de list
---endCorr

Question 2.3

La dernière partie manquante dans le programme est la fonction sort_list. Cette fonction trie la liste suivant la valeur du champs value des noeuds.

Implémentez la fonction sort_list dans le fichier Q2/Q2.3/linked_list.c.

---beginCorr (3 points)
programme corrigé
---endCorr

Question 3 : Nouveaux exemples pour le cours Éléments d'architecture Client-Serveur (13,5 points)

Pendant le cours Éléments d'architecture Client-Serveur, nous avons étudié l'exemple d'un client qui communique, via TCP, avec un serveur pour lui envoyer plusieurs requêtes. Le serveur répond avec un message contenant la réponse ou bien le fait que le client doit arrêter d'envoyer des requêtes. Dans ce dernier cas, le client s'arrête.

Dans cet exercice, nous étudions un client qui communique, via UDP, avec un serveur. En utilisant UDP, nous pouvons illustrer d'autres architectures Client-Serveur vues en cours. Ainsi, le client et le serveur fournis dans le répertoire Q3.1 sont basés sur une architecture dans laquelle le client fournit le contexte de sa requête au serveur, en l'occurrence le nombre de réponses que le serveur a faite(s) à ce client jusqu'à présent.

# Travail préparatoire qui sert à toutes les compilations et servira à partir de la question 3.2
$ cd Q3
$ tar xzvf libredblack-1.3.tar.gz
$ cd libredblack-1.3
$ ./configure ; make
$ cd ../..

# Génération de la version initiale de l'application
$ cd Q3/Q3.1
$ make

# Exécution d'un exemple
$ ./serveurUDP
# Dans une autre fenêtre
$ ./clientUDP essai

Le serveur affiche :

1-ieme client a traiter (localhost:45499)

Le client affiche

Client  essai : A trouve le serveur !
Client  essai : Envoi de requetes vers le serveur...
Client  essai : Nouvelle reponse du serveur = " 1-ieme reponse au client" ==> OK
Client  essai : Nouvelle reponse du serveur = " 2-ieme reponse au client" ==> OK
...
Client  essai : Nouvelle reponse du serveur = " 9-ieme reponse au client" ==> OK
Client  essai : Nouvelle reponse du serveur = "10-ieme reponse au client" ==> OK
Client  essai : Envoi de requetes termine !

Question 3.1

Le serveur actuel est monotâche. Dans le fichier Q3/reponses3.txt ou bien sur votre copie, indiquez le principal inconvénient de cette architecture.

Pour pallier cet inconvénient, modifiez le code de Q3.1/serveurUDP.c pour que le serveur dispose d'un pool de 200 threads prêts à traiter une requête client.

---beginCorr (3.5 points)

Le principal inconvénient de cette architecture mono-tâche est que, si une requête client prend du temps à être traitée, les autres requêtes client devront attendre que le traitement de cette requête soit terminé.

serveurUDP_corrige_Q3.1.c

  • 1 pts pour justification
  • 2 pts pour les pthread_create et pthread_detach
  • 0.5 pts pour le mutex évitant la race condition sur rangClient
Des malus sont appliqués en fonction du code produit:
  • -0.5 en cas de code retour non testé
  • -0.5 en cas de problème d'indentation
  • -0.5 en cas de warning à la compilation
---endCorr

Question 3.2

Le client fourni envoie actuellement le contexte de sa requête au serveur, i.e. nbReponsesAuClient le nombre de réponses que le serveur a faite(s) à ce client jusqu'ici.
Dans le fichier Q3/reponses3.txt ou bien sur votre copie, indiquez en quoi stocker le contexte au niveau du client peut être un inconvénient.

Pour pallier cet inconvénient, nous allons stocker le contexte au niveau du serveur. Pour retrouver rapidement le contexte d'un client, nous allons le stocker dans un arbre (binaire de recherche) Rouge-Noir manipulé avec la bibliothèque libredblack fournie dans Q3/libredblack-1.3.tar.gz.

Copiez Q3/Q3.1/serveurUDP.c dans le répertoire Q3/Q3.2, puis :

  • Dans Q3/Q3.2/serveurUDP.c
    • Définissez une structure node_t constituée d'une chaîne de caractères key et d'un entier nbReponsesAuClient représentant le contexte d'une "connexion" entre un client et le serveur.
    • Dans un terminal, tapez man -l Q3/libredblack-1.3/rbinit.3 pour accéder au man des différentes fonctions de la bibliothèque et à un exemple. Lisez au moins le rôle des fonctions rbinit, rbsearch, rbfind (qui seront utilisées dans cette question), rbwalk et rbdelete (qui seront utilisées à la question 3.3).
    • Déclarez la variable globale suivante : struct rbtree *rbtree;
    • Implémentez la fonction int compare(const void *pa, const void *pb, const void *config) en
      • ignorant le paramètre config dans l'implémentation de compare,
      • renvoyant -1, 0 ou 1, selon que la valeur de la clé du nœud pointé par pa est respectivement strictement inférieure, égale ou strictement supérieure à la valeur de la clé du nœud pointé par pb
    • Dans main(), initialisez rbtree avec la fonction rbinit.
    • Dans la fonction gestionRequete() :
      • Calculez la clé associée à l'émetteur de la requête en concaténant le contenu de la variable host, la chaîne de caractère ":" et le contenu de la variable service.
      • Cherchez cette clé dans rbtree avec la fonction rbfind. Si rbfind ne trouve pas cette clé dans rbtree, créez un nœud de type node_t. Stockez-y la clé calculée précédemment et initialisez nbReponsesAuClient à 0. Puis, insérez le nœud dans rbtree avec la fonction rbsearch.
      • Incrémentez nbReponsesAuClient de 1 : vous êtes maintenant en mesure de répondre au client.
    • NB :
      • Les fonctions de libredblack ne sont pas thread-safe. De ce fait, quand nécessaire, veillez à protéger les accès à rbtree en utilisant systématiquement une exclusion mutuelle.
      • Il se peut que la ligne où vous appelez rbfind vous génère le warning "warning: initialization discards ‘const’ qualifier from pointer target type" ou "warning: assignment discards ‘const’ qualifier from pointer target type". Dans ce cas, remplacez "rbfind(...)" par "(node_t *) rbfind(...)".
  • Dans Q3/Q3.2/clientUDP.c, pour être sûr que votre serveur ne fonctionne plus grâce à des données de contexte envoyées par le client, remplacez la ligne "msgRequete.infoSup.nbReponsesAuClient = nbReponsesOK;" par la ligne "msgRequete.infoSup.nbReponsesAuClient = -42;"
  • make, puis vérifiez le fonctionnement correct de votre serveur et de votre client.
    NB : vous pouvez lancer plusieurs clients à la fois en tapant dans un terminal : for((i=1;i<=200;i+=1)); do (./clientUDP $i &);done

---beginCorr (5 points)

Pour information : Nous avons préféré libredblack aux fonctions tsearch, tfind, tdelete, twalk et tdestroy qui permettent aussi de gérer un arbre binaire et qui, en plus, font partie de la bibliothèque C. En effet, il s'avère que ce lot de fonctions n'offre pas de fonction de suppression de nœud (cf. rbdelete) dont nous nous servirons à la question 3.3.Par ailleurs, il est probable (mais c'est à vérifier) que libredblack qui est basé sur l'algorithme rouge-noir est plus performant que ces fonctions de la librairie C, basées sur l'algorithme T de Knuth (cf. man tsearch).

Lorsque le client envoie ses données de contexte au serveur, il peut envoyer des données trafiquées de sorte que les valeurs envoyées l'arrange. Par exemple, si les données de contexte permettent de facturer le client, il peut envoyer des données qui minimisent la facturation.

serveurUDP_corrige_Q3.2.c

  • 1 pts pour justification
  • 3 pts pour utilisation de libredblack
  • 1 pts pour mutex autour des fonctions libredblack
Des malus sont appliqués en fonction du code produit:
  • -0.5 en cas de code retour non testé
  • -0.5 en cas de problème d'indentation
  • -0.5 en cas de warning à la compilation
---endCorr

Question 3.3

Dans le serveur codé précédemment, une fois qu'un client a fini d'interagir avec le serveur, le nœud contenant ses données de contexte reste éternellement dans rbtree. L'objectif de cette question est d'écrire un thread ramasseNoeudsInutiles qui supprime les nœuds inutiles de rbtree.

Le principe est le suivant :

  • Nous ajoutons un entier lastNbReponsesAuClient à la structure node_t. Cet entier est initialisé à 0 lors de la création d'un nouveau nœud.
  • Toutes les 5 secondes, le thread ramasseNoeudsInutiles exécute la fonction rbwalk(rbtree, traitementNode, NULL) qui se charge d'appeler la fonction traitementCtxt() (décrite ci-dessous) pour chaque nœud stocké dans rbtree.
  • Nous codons la fonction traitementCtxt(const void *nodep, const VISIT unused1, const int unused2, void *unused3) selon l'algorithme suivant :
node_t *pnode = (node_t *) nodep;
si (which signale que ce noeud est une feuille ou bien que c'est la dernière visite à ce noeud) alors
    si (pnode->nbReponsesAuClient == pnode->lastNbReponsesAuClient) alors
        // Il n'y a plus de client qui utilise ce noeud : on peut le supprimer
        Appeler rbdelete pour supprimer ce noeud de rbtree
        Libérer ce noeud
    sinon
        pnode->lastNbReponsesAuClient = mnode->nbReponsesAuClient
    finsi
finsi

Dans le fichier Q3/reponses3.txt ou bien sur votre copie, indiquez comment vous allez synchroniser ramasseNoeudsInutiles avec les threads gestionConnexion qui recherchent un contexte dans l'arbre rbtree ou bien insèrent un nouveau nœud. Justifiez votre proposition.

Copiez Q3/Q3.2/serveurUDP.c dans le répertoire Q3/Q3.3, puis codez Q3/Q3.3/serveurUDP.c selon le principe présenté ci-dessus.

---beginCorr (5 points)

serveurUDP_corrige_Q3.3.c

Pour synchroniser ramasseNoeudsInutiles avec les threads gestionConnexion, nous pouvons choisir d'encadrer (void)rbwalk(rbtree, traitementCtxt, NULL); avec une exclusion mutuelle basée sur le mutex utilisé dans gestionConnexion. Si nous faisons cela avec le corrigé de la question 3.2, nous courons le risque que rbwalk s'exécute et décide d'effacer un nœud, alors que gestionConnexion accède à ce même nœud. C'est pourquoi, dans ce corrigé de la question 3.3, pour maximiser le parallélisme des différents threads, nous choisissons d'utiliser une synchronisation de type lecteurs-rédacteurs, où les lecteurs sont les différents threads gestionConnexion dont l'opération de "lecture" (en tant que lecteur) consiste à accéder à un nœud (éventuellement en le créant) pour incrémenter nbReponsesAuclient, et où le rédacteur est le thread dont l'opération de "rédaction" (en tant que rédacteur) est l'appel à rbwalk.

  • 2 pts pour justification
  • 2 pts pour codage thread (avec le lecteurs-rédacteur pour encadrer l'appel à rbwalk)
  • 1 pts pour le codage correct de traitementCtxt
Des malus sont appliqués en fonction du code produit:
  • -0.5 en cas de code retour non testé
  • -0.5 en cas de problème d'indentation
  • -0.5 en cas de warning à la compilation
---endCorr



Page mise à jour le 9 juin 2017