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 ?
---beginCorr
Barême = 0,5 point par avantage ou inconvénient avec un maximum de 2 points
Avantage
  1. Sync synchronise l'ensemble du disque alors que fsync/O_SYNC ne permettent que de travailler au niveau d'un descripteur de fichier. Pour certaines applications, Sync est donc plus performant si on doit synchroniser tous les fichiers ouverts de ce disque.
Inconvénients
  1. Sync est un utilitaire. Donc, pour l'invoquer, il faut passer par l'appel système system qui génère un shell : pour l'invoquer, on perd en performance par rapport à un appel système normal.
  2. Sync synchronise tous les fichiers, sans distinction ! On perd donc en performance dans la grande majorité des cas, puisqu'il est probable qu'on synchronise des fichiers qu'on n'avait pas besoin de synchroniser.
    NB : on est loin de la préoccupation de performances d'Unix qui, pour gagner quelques micro-secondes, va jusqu'à proposer l'appel système fdatasync pour ne synchroniser que les méta-données requises pour pouvoir redémarrer en cas de défaillance.
  3. Sync ne permet pas une synchronisation implicite comme on peut l'avoir avec l'option O_SYNC.
  4. Sync nécessite le privilège administrateur. Un utilisateur standard ne peut donc pas utiliser une application faisant des appels à Sync.
---endCorr

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?
    ---beginCorr
    Barême : 1 point
    La fonction ctime n'est pas réentrante. En effet, elle utilise une variable statique pour stocker la chaîne de caractères résultat. De ce fait, quand deux threads l'utilisent en parallèle, la valeur stockée par l'appel à ctime du deuxième thread écrase la valeur stockée par l'appel à ctime du premier thread.
    ---endCorr
  2. Expliquez (sur votre copie ou bien dans le fichier Q1/reponse.txt) les modifications nécessaires pour corriger ce problème.
    ---beginCorr
    Barême : 0,5 point pour la définition du tableau de caractères (avec longueur d'au moins 26) et 0,5 pour le remplacement de ctime par ctime_r.
    Dans chaque thread, il faut remplacer l'appel à ctime (non-réentrant) par son équivalent réentrant ctime_r.
    man ctime_r explique que cette fonction doit être appelée avec un paramètre qui est une chaîne de caractères de longueur au moins 26 caractères. Chaque thread doit donc définir une variable locale correspondant à un tel tableau.
    ---endCorr

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.
---beginCorr
Barême : 0,5 point par paradigme
  • Les K processus producteurs forment une cohorte qui peut écrire au plus N informations dans le tableau.
  • Les P processus consommateurs forment une cohorte qui peut lire au plus N informations dans le tableau.
  • Par ailleurs, les K processus producteurs et les P processus consommateurs sont en exclusion mutuelle pour accéder à la variable contenant le rang de la prochaine case du tableau T qui peut être écrite par l'un des producteurs.
    NB : dans le paradigme producteur/consommateur classique, on a une variable qui indique où écrivent les producteurs et une autre qui indique où lisent les consommateurs. Mais ici, ces deux variables n'en forment qu'une.
---endCorr

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.
---beginCorr
Barême :
  • 1 point décomposé en 0,25 point pour chaque variable sommetPile, placeDispo, infoPrete et mutex (et leur initialisation correcte)
  • 0,75 point par algorithme ==> 1,5 points pour les 2 algorithmes
    • 0,25 si les P et V sont bien faits.
    • 0,5 si la pile est correctement gérée.
Variables globales
==================
// Tableau contenant la pile
info T[N]

// Variable indiquant la prochaine case où un producteur devra écrire
int sommetPile = 0

// Sémaphores
Semaphore placeDispo initialisé à N
Semaphore infoPrete initialisé à 0
Semaphore mutex initialisé à 0

Algorithme des producteurs
==========================

répéter
 ...
 calcul(info)
 P(placeDispo)
 P(mutex)
 T[sommetPile] = info
 sommetPile += 1
 V(mutex)
 V(infoPrete)
 ...
finRépéter

Algorithme des consommateurs
============================

répéter
 ...
 P(infoPrete)
 P(mutex)
 info = T[sommetPile - 1]
 sommetPile -= 1
 V(mutex)
 V(placeDispo)
 utiliser(info)
 ...
finRépéter
---endCorr

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.
---beginCorr
Barême :
  • 1 point pour les 2 paradigmes
  • 1 point décomposé en 0,25 point pour chaque variable sommetPile, placeDispo, infoPrete et mutex (et leur initialisation correcte)
  • 0,5 point pour chaque algorithme (tous les points sont affectés à la gestion correcte de la variante) ==> 1 pour les 2
Quand l'un des K producteurs (respectivement P consommateurs) empile la N-ème (respectivement dépile la dernière) donnée dans la pile, il doit envoyer N signaux aux consommateurs (respectivement producteurs) pour qu'ils commencent à dépiler (respectivement empiler).  Dans les 2 cas, le paradigme est un paradigme de type signal (on peut le voir aussi comme un paradigme de type cohorte). 
Variables globales
==================
// Tableau contenant la pile
info T[N]

// Variable indiquant la prochaine case où un producteur devra écrire
int sommetPile = 0

// Sémaphores
Semaphore placeDispo initialisé à N
Semaphore infoPrete initialisé à 0
Semaphore mutex initialisé à 0

Algorithme des producteurs
==========================

répéter
 ...
 calcul(info)
 P(placeDispo)
 P(mutex)
 T[sommetPile] = info
 sommetPile += 1
 si sommetPile == N alors
   répéter N fois
     V(infoPrete)
   finRépéter
 finSi
 V(mutex)
 ...
finRépéter

Algorithme des consommateurs
============================

répéter
 ...
 P(infoPrete)
 P(mutex)
 info = T[sommetPile - 1]
 sommetPile -= 1
 si sommetPile == 0 alors
   répéter N fois
     V(placeDispo)
   finRépéter 
 finSi
 V(mutex)
 utiliser(info)
 ...
finRépéter
---endCorr

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.
---beginCorr
En terme de performances, sur la machine b02-13, on obtient :
$ /usr/bin/time serveur 100000
0.18user 10.30system 0:03.59elapsed 291%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+205minor)pagefaults 0swaps
---endCorr
 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.
---beginCorr
Barème :
  • clarté du code : 0,25 ;
  • compilation sans warning : 0,25 ;
  • test du retour de chaque appel système : 0,25 ;
  • réponse correcte à la question posée :
    • déclaration du mutex : double écriture/double lecture correcte sur le tube : 0,5 ;
    • la double lecture est protégée par une exclusion mutuelle pour éviter qu'un thread ne lise la longueur tandis qu'un autre thread lit le contenu du message en pensant lire la longueur (NB : ce phénomène ne s'observe pas tout le temps, mais il existe, M. Simatic a pu l'observer !) : 0,75.
voir codeEtudiant.Q3-1.corrige.c
En terme de performances, sur la machine b02-13, on obtient :
$ /usr/bin/time serveur 100000
0.23user 2.33system 0:02.37elapsed 108%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+217minor)pagefaults 0swaps

On passe donc d'un temps d'exécution de 3.59 secondes à 2.37 secondes, soit un gain de 1,22 secondes (34%). Ce gain est dû au fait qu'on limite le nombre d'octets transférés (inutilement) entre la mémoire du thread distributeur et le tube d'une part, et entre le tube et la mémoire des threads traiteurs d'autre part.
---endCorr

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.
---beginCorr
Barème :
  • clarté du code : non comptabilisé ;
  • compilation sans warning : 0,25 ;
  • test du retour de chaque appel système : 0,25 ;
  • réponse correcte à la question posée :
    • explication : 0,5 point
    • malloc et free correctement utilisé (NB : après le free, on remet la variable qui contenait le pointeur (vers la zone qui a été libérée) à null) : 0,5 point ;
    • on passe bien seulement 4 octets (correspondant au pointeur) dans le tube : 0,5 point
On doit allouer une zone mémoire à chaque requête pour être sûr que, pendant que la requête est en transit dans le tube distr_traite, son contenu n'est pas modifié par un nouvel appel à genererRequete.

voir codeEtudiant.Q3-2.corrige.c
En terme de performance, sur la machine b02-13, on obtient :
$ /usr/bin/time serveur 100000
0.29user 10.09system 0:03.43elapsed 302%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+229minor)pagefaults 0swaps

Si on a gagné 3,59-3,43=0,16 secondes (4%) par raport au code initial, on a perdu par rapport au code de la question Q3-1. on a 3,43 - 2,37 = 1,06 seconde, soit une augmentation de 45% ! Les malloc/free sont ici beaucoup plus pénalisants que l'écriture/lecture des octets du message sur le tube.
---endCorr

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.
---beginCorr
Barème :
  • clarté du code : non comptabilisé ;
  • compilation sans warning : 0,25 ;
  • test du retour de chaque appel système : 0,25 ;
  • réponse correcte à la question posée :
    • indication de la valeur minimum de Z + explication de l'intérêt de fixer Z à 2*N : 0,5 point
    • gestion correcte du producteur/consommateur : 1 point
Z doit avoir au minimum la valeur N pour être sûr de pouvoir occuper les N threads traiteur en parallèle.
Fixer Z à une valeur strictement supérieure à N permet au thread distributeur d'accepter des requêtes même s'il sait qu'elles ne seront pas immédiatement traitées par un thread traiteur. Fixer Z à 2*N permet d'avoir un bon compromis pour ne pas avoir trop de requêtes en attente au niveau du serveur.

voir codeEtudiant.Q3-3.corrige.c
C'est le code le plus performant de tous puisqu'on obtient sur la machine b02-13 :
$ /usr/bin/time serveur 100000
1.32user 4.28system 0:00.91elapsed 611%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+218minor)pagefaults 0swaps

soit un gain de 2,37 - 0,91 = 1,46 seconde, soit 62% par rapport à codeEtudiant.Q3-1.corrige.c ! En effet, on économise au maximum les transferts mémoire entre la mémoire des threads et celle du tube. De plus, le mécanisme de synchronisation à base de sémaphore semble plus efficace que celui basé sur les tubes.
---endCorr

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.
      ---beginCorr
      Barème :
      • clarté du code : 0,25 ;
      • compilation sans warning : 0,25 ;
      • test du retour de chaque appel système : 0,25 ;
      • réponse correcte à la question posée :
        • commentaire : 0,25 point
        • gestion correcte des conditions : 2 points
      voir codeEtudiant.Q3-4.corrige.c
      En terme de performance, sur la machine b02-13, on obtient :
      $ /usr/bin/time serveur 100000
      0.51user 1.83system 0:01.88elapsed 125%CPU (0avgtext+0avgdata 0maxresident)k
      0inputs+0outputs (0major+218minor)pagefaults 0swaps

      Ce code est meilleur que celui de la question Q3-1 (il représente un gain de 2,37 - 1,88 = 0,49 secondes, soit 21%), mais moins bon que celui de la question Q3-3 (0,91 - 1,88 = -0,97, soit une pénalité de 107% !). Pour ce problème de synchronisation producteur/consommateur, les conditions sont moins performantes (ce qui semble logique, vu qu'on fait beaucoup plus d'appels à des primitives de synchronisation tout au long du code).
      ---endCorr



      Page mise à jour le 12 mai 2009