Département INFormatique 
  CSC4508/M2 : Concepts des systèmes d'exploitation et mise en œuvre sous Unix


    Évaluation



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

TP Noté CSC4508/M2 du 19/05/09

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 remise de votre copie à l'enseignant et 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 TPNote2009

Préparation

cd votreRepertoireDeTravailPourCSC4509M2
cp ~simatic/Cours/CSC4508/tPNote2009.tgz .
tar xvfz tPNote2009.tgz
cd TPNote2009

Question 1 : Questions de cours (4 points)

Pour chacune des questions ci-dessous, répondez sur votre copie ou bien dans le fichier Q1/reponse1.txt (dans ce dernier cas, indiquez sur votre copie « Réponse dans Q1/reponse1.txt » ).

Question 1-1 : Sync versus fsync/O_SYNC (2 points)

Les différentes versions de Windows n'ont ni option O_SYNC associée à l'ouverture de fichier, ni appel système fsync. En contrepartie, http://technet.microsoft.com/fr-fr/sysinternals/bb897438(en-us).aspx propose le téléchargement de l'utilitaire Sync. Cet utilitaire (qui nécessite les privilèges administrateur) est lancé à partir d'une fenêtre commande. Il prend en paramètre la lettre du disque qu'on souhaite synchroniser. Il force la purge de tous les tampons système associés à ce disque pour les écrire effectivement sur disque.

Sync présente un avantage par rapport à fsync/O_SYNC. Quel est-il ?
En revanche, Sync présente au moins trois inconvénients par rapport à fsync/O_SYNC. Quels sont-ils ?

Question 1-2 : Threads et fonction ctime

Le code du fichier Q1/threadEtCtime.c crée 2 threads. Chaque thread affiche la date sous forme littérale à 2 secondes d'intervalle (constante TEMPO1).
Ce code est incorrect : la date affichée est la même pour les 2 threads.
  1. Pourquoi ce code est-il incorrect?
  2. Expliquez (sur votre copie ou bien dans le fichier Q1/reponse.txt) les modifications nécessaires pour corriger ce problème.

Question 2 : Synchronisation autour d'une pile (7 points)

Pour cette question, répondez sur votre copie ou bien dans le fichier Q2/reponse2.txt (dans ce dernier cas, indiquez sur votre copie « Réponse dans Q2/reponse2.txt »).

On considère K processus producteurs et P processus consommateurs.
Le paradigme producteur/consommateur présenté en cours est de type FIFO (First In First Out, Premier Arrivé Premier Sorti). Il correspond donc à une file.
Dans cette exercice, on cherche à écrire les algorithmes pour le type LIFO (Last In First Out, Dernier Arrivé premier Sorti). Le paradigme correspondra donc à une pile. Les K producteurs empilent des infos dans un tableau T utilisé pour stocker une pile de N cases (Les K producteurs ne peuvent donc empiler qu'au plus N infos). Des consommateurs deviennent actifs seulement quand il existe des infos dans la pile. Ils dépilent ces infos en commençant par dépiler celle qui a été empilée en dernier.

Question 2-1 : Paradigmes de synchronisation (1,5 point)

Indiquez tous les paradigmes présents dans ce problème.

Question 2-2 : Algorithmes (2,5 points)

En utilisant des sémaphores, décrivez toutes les données nécessaires à cette gestion de pile, sans oublier de donner toutes les valeurs initiales des sémaphores et des variables utilisés. Puis, écrivez l'algorithme déroulé par chaque producteur et celui déroulé par chaque consommateur.

Question 2-3 : Algorithmes pour une variante (3 points)

Dans cette question, on souhaite coder la variante suivante de la question Q2-2 : les P consommateurs ne démarrent que quand la pile est pleine. De plus, les K producteurs ne peuvent empiler des informations que quand la pile a été complètement vidée.
Indiquez le (ou les) paradigme(s) présents dans cette variante.
En utilisant des sémaphores, décrivez toutes les données nécessaires à cette variante, sans oublier de donner toutes les valeurs initiales des sémaphores et des variables utilisés. Puis, écrivez l'algorithme déroulé par chaque producteur et celui déroulé par chaque consommateur.

Question 3 : Variations autour d'un serveur multi-threadé (9 points)

Dans cet exercice, on considère un processus serveur contenant N+1 threads. L'un de ces threads, nommé distributeur, est chargé de recevoir les requêtes venant des différents clients et de communiquer ces requêtes vers l'un des N autres threads, nommés traiteurs. Ces derniers sont chargés d'effectuer le traitement de la requête et de répondre au client.
Pour simplifier l'exercice, on simule les processus clients de ce processus serveur : le thread distributeur est chargé de générer les requêtes (comme s'il les avait reçues des clients) à l'aide de la procédure simulerReceptionRequeteDeClient ; par ailleurs, dès qu'il reçoit une requête, chaque thread traiteur appelle simulerTraitementEtEnvoiReponseAuClient (qui simule notamment l'envoi du résultat du traitement de la requête au client).

Le médium de communication utilisé entre le thread distributeur et les threads traiteurs doit garantir que :
  1. aucune requête n'est perdue ;
  2. les threads traiteurs sont bloqués, en attente, quand aucune requête n'est disponible dans le médium ;
  3. le thread distributeur est bloqué, en attente, lorsque le médium est plein et ne peut donc pas recevoir une nouvelle requête.
Or, un tube est un médium de communication qui offre toutes ces garanties. C'est pourquoi, dans le code fourni en exemple, le thread distributeur communique les requêtes à traiter aux threads traiteurs via le tube distr_traite.

Avant de rentrer dans le vif du sujet, faites fonctionner ce serveur :
  • dans un terminal, positionnez-vous dans le répertoire Q3-1, tapez make pour compiler, puis serveur 20 pour lancer l'exécution du serveur ; le paramètre « 20 » indique le nombre de requêtes à traiter ; dans ce premier exemple, on met un nombre faible pour vérifier le bon fonctionnement en analysant visuellement la sortie ;
  • pour faire un test de performances, tapez /usr/bin/time serveur 100000 ; dans ce second exemple, on met un nombre important de requêtes à traiter pour avoir des chiffres de performance significatifs. Noter que le serveur ne fait plus aucun affichage à l'écran dès que le nombre de requêtes à traiter dépasse 100.
Pour fonctionner, ce serveur utilise 2 modules : codeEtudiant.c et simulateur.c. Mais, dans les questions suivantes, vous serez amené à modifier seulement codeEtudiant.c (c'est pourquoi c'est le seul module sur lequel vous avez les droits en écriture).

Dans cet exercice, on suppose qu'un profilage (profiling) a été effectué sur ce code. Il a révélé que le seul endroit où l'on peut gagner en performance au niveau de ce serveur est dans le médium de communication entre le thread distributeur et les threads traiteur. L'objectif de toutes les questions suivantes est de comparer différents média de communication pour retenir le plus performant.

Question 3-1 : Moins d'octets dans le tube (2 points)

Une analyse statistique des requêtes montre qu'elles ont une longueur moyenne de 416 caractères (caractère '\0' inclus) avec de très rares pointes à TAILLE_MAX_REQUETE octets (caractère '\0' inclus). Or, dans le code actuel, on écrit systématiquement TAILLE_MAX_REQUETE (soit 4096) octets dans le tube. Dans cette question, on se propose de tester une méthode faisant transiter moins d'octets dans le tube. Modifiez Q3-1/codeEtudiant.c de sorte que :
  • le thread distributeur écrit d'abord dans le tube distr_traite la longueur de la chaîne qu'il s'apprête à écrire, puis la chaîne elle-même (et pas tous les octets du tableau de caractères dans lequel est stockée cette chaîne) ;
  • chaque thread traiteur lit d'abord la longueur de la chaîne qui a été écrite par le thread distributeur, puis la chaîne elle-même, avant d'appeler simulerTraitementEtEnvoiReponseAuClient.
Une fois le code écrit et opérationnel, sur votre copie ou dans le fichier Q3/reponse3.txt, indiquez le résultat de votre test de performances. Commentez-le.

Question 3-2 : Encore moins d'octets dans le tube (2 points)

Dans cette question, on cherche à écrire encore moins d'octets dans le tuyau et à économiser d'une part les recopies d'octets entre la mémoire du thread distributeur et le tube, et d'autre part celles entre le tube et la mémoire de chaque thread traiteur :
  • recopiez Q3-1/codeEtudiant.c dans Q3-2 ;
  • modifiez Q3-2/codeEtudiant.c de sorte que :
    • à chaque requête, le thread distributeur alloue, à l'aide de malloc, une zone mémoire de TAILLE_MAX_REQUETE qu'il passe en paramètre de simulerReceptionRequeteDeClient ; puis il stocke le pointeur (vers cette zone mémoire) dans le tube ;
    • chaque thread traiteur lit ce pointeur dans le tube, puis appelle simulerTraitementEtEnvoiReponseAuClient (avec ce pointeur) et enfin libère cette zone mémoire à l'aide de free.
Une fois le code écrit et opérationnel, sur votre copie ou dans le fichier Q3/reponse3.txt :
  1. expliquez pourquoi on doit désormais allouer une nouvelle zone mémoire pour chaque requête (au lieu d'utiliser une seule zone de mémoire statique comme on le faisait à la question Q3-1) ;
  2. indiquez le résultat de votre test de performance. Commentez-le.

Question 3-3 : Le couple tableau/sémaphores sem_t est-il plus performant que le tube ? (2 points)

La question Q3-2 a montré qu'on ne gagne pas de temps à trop réduire les écritures sur le tube.
Dans cette question, on souhaite remplacer le tube de la question Q3-1 par un tableau de Z=2*N cases géré par les threads selon un paradigme de synchronisation Producteur/Consommateur, en utilisant des sémpahores sem_t (primitives sem_init, sem_post...). L'objectif est de déterminer si ce médium de communication est plus performant.
  • Q3-3/codeEtudiant.c correspond actuellement au code d'exemple qui vous était donné au tout de début de cet exercice ;
  • modifiez Q3-3/codeEtudiant.c de sorte que :
    • on définit un tableau tab_distr_traite de 2*N chaînes de TAILLE_MAX_REQUETE caractères ;
    • à chaque requête, le thread distributeur :
      1. essaye d'accéder à l'une des cases de ce tableau selon le paradigme de synchronisation Producteur/Consommateur,
      2. communique l'adresse de cette case à simulerReceptionRequeteDeClient,
      3. informe les threads traiteurs grâce au paradigme Producteur/Consommateur qu'une information est prête ;
    • chaque thread traiteur attend qu'une information soit prête dans ce tableau ;
    • quand c'est le cas, le thread traiteur :
      1. recopie le contenu de la case prête dans une variable locale,
      2. indique au thread distributeur (grâce au paradigme Producteur/Consommateur) que cette place est à nouveau disponible,
      3. transmet l'adresse de cette variable locale à simulerTraitementEtEnvoiReponseAuClient ;
    • toutes les opérations de synchronisation sur ces tableaux sont réalisées à l'aide de sémaphores sem_t.
Une fois le code écrit et opérationnel, sur votre copie ou dans le fichier Q3/reponse3.txt :
  1. indiquez la valeur minimum de Z ;
  2. expliquez quel est, selon vous, l'intérêt de fixer Z à 2*N ;
  3. indiquez le résultat de votre test de performance ; commentez-le.

Question 3-4 : Le couple tableau/conditions pthread_cond_t est-il plus performant que le tube ? (3 points)

Dans cette question, on remplace les sémaphores de la question Q3-3 par des conditions. L'objectif est de déterminer si ce mécanisme de synchronisation est plus performant.
  • recopiez Q3-3/codeEtudiant.c dans Q3-4 ;
  • modifiez Q3-4/codeEtudiant.c de sorte qu'il utilise des conditions pthread_cond_t au lieu de sémaphores sem_t.
    Une fois le code écrit et opérationnel, indiquez sur votre copie ou dans le fichier Q3/reponse3.txt le résultat de votre test de performance. Commentez-le.



      Page mise à jour le 12 mai 2009