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

Institut National des Télécommunications
Télécom INT 2è année

TP Noté CS21 du 24/06/03
(2è session)

(Corrigés)

Modalités

Durée : 1h30

Tous documents autorisés

Les questions 1 à 5 sont indépendantes les unes des autres. La question 6 dépend de la question 5.

Le barême est donné à titre indicatif. Pour le code, seront notés :
  • La clarté du code,
  • Le fait que le code compile (sans warning),
  • La justesse du code par rapport à la question posée,
  • Le fait que le retour de chaque appel système, s'il y en a un, est testé avec appel à perror(), puis exit(1) en cas de problème détecté,
  • La libération des ressources système réservées pendant l'exécution du programme, à la fin de son exécution.
La "livraison de la copie" en fin de TP noté pour les questions 5 et 6 se fera par envoi d'un mail à Michel.Simatic@int-evry.fr, sujet "TP noté 2 CS21" avec en pièce jointe le fichier d'extension tgz constitué de la manière suivante :
cd ~/CS21
tar cvfz $USER.tgz TPNote2

Préparation

cd
mkdir CS21
cd CS21
cp ~simatic/CS21/tpNote2.tgz .
tar xvfz tpNote2.tgz
cd TPNote2

Question 1 : Mémoire (2 points)

Vous avez développé une application CPU-intensive qui, au cours de son exécution, effectue un million d'accès mémoire.
Cette application étant lente, vous lui appliquez la commande time pour en faire une première analyse. Voici le résultat de la commande time :

$ /usr/bin/time monAppli

0.15user 20.37system 8:03.29elapsed 4%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (540837major+100000minor)pagefaults 0swaps

Expliquer, sur feuille, le(s) problème(s) de performances de votre application (5 lignes maximum).
Puis présenter brièvement (3 lignes maximum par cas) les solutions envisageables dans les cas suivants :
  1. Vous avez du temps.
  2. Vos finances permettent un investissement.
---beginCorr
L'application fait 100.000 défauts de pages mineurs. On peut extrapoler de ce nombre que l'application utilise environ 100.000 pages mémoire différentes. Or, lorsqu'elle fait 1.000.000 d'accès mémoire (à ces 100.000 pages), elle fait 540.837 défauts de pages majeurs. En d'autres termes, elle n'arrête pas de swapper des pages sur disque et donc d'attendre que les pages soient remontées du disque vers la mémoire (ce qui explique qu'elle n'utilise la CPU qu'à 4%).
  1. Si on a du temps, on a intérêt à analyser l'algorithme de l'application pour que les différents accès à une page mémoire soient le plus rapprochés possibles dans le temps. Ainsi, si la page est swappée sur disque, on diminuera la probabilité qu'on ait à nouveau besoin d'y accéder.
  2. Si on peut faire un investissement, on a intérêt à acheter de la RAM pour éviter le swap sur disque. NB : on a quand même intérêt à analyser l'algorithme, car en ne rapprochant pas les différents accès à une page mémoire, on ne profite pas du cache se chargeant de la traduction adresse page virtuelle/adresse page physique.
---endCorr

Question 2 : Communications et synchronisations (3,5 points)

Le nouveau système d'exploitation "Winux" ne dispose que de tubes pour les communications inter-processus (il n'offre donc pas de file de messages, de sémaphore, de moniteur ou de mémoire partagée).
Parmi les paradigmes de synchronisation de processus suivants :
  1. Exclusion mutuelle
  2. Cohorte
  3. Passage de témoins : Envoi de signaux
  4. Producteurs/consommateurs
  5. Lecteurs/rédacteurs
Choisir 2 paradigmes qui vous semblent implémentables sous "Winux" avec un seul tube.
Expliquer, sur feuille, l'implémentation envisagée (5 lignes maximum par paradigme retenu).
---beginCorr
  1. L'exclusion mutuelle est implémentable de la manière suivante : on fait l'initialisation en écrivant un octet dans le tube. Quand un processus veut entrer en section critique, il lit un octet dans le tube (s'il y trouve un octet, il le lit et donc sa lecture est passante ; s'il ne l'y trouve pas, il est bloqué dans sa lecture jusqu'à ce qu'un octet soit déposé dans le tube). Quand il sort de section critique, il écrit un octet dans le tube.
  2. La cohorte est implémentable de la manière suivante : on fait l'initialisation en écrivant autant d'octets dans le tube qu'il y a de membres dans la cohorte. Quand un processus veut entrer dans la cohorte, il lit un octet dans le tube. Quand il veut en sortir, il écrit un octet dans le tube. NB: la cohorte ne peut pas contenir plus d'éléments que la capacité en octets du tube (i.e. le nombre d'octets maximum qu'on peut stocker dans le tube sans être bloqué). Sinon cela signifiera qu'un processus sortant de la cohorte peut se retrouver bloqué (ce qui peut éventuellement être acceptable).
  3. L'envoi de signaux est implémentable de la manière suivante : le tube est vide à l'initialisation. Pour se mettre en attente du signal, un processus lit un octet sur le tube (si le tube est vide, le processus est donc bloqué). Pour émettre le signal, un processus écrit un octet dans le tube.
  4. Le paradigme producteurs/consommateurs est implémentable de la manière suivante : le tube est vide à l'initialisation. Quand un producteur est prêt à produire, il écrit, dans le tube, les N octets de sa production. Quand un consommateur est prêt à consommer, il lit, dans le tube, les N octets à consommer. NB: cette implémentation ne marche correctement que si le nombre maximum d'octets productibles sans être consommés est inférieur à la capacité du tube. Sinon on a le risque que les écritures dans le tube ne soient pas atomiques et que donc les différentes productions se mélangent entre elles.
  5. Le paradigme lecteurs/rédacteurs n'est pas implémentable avec un seul tube.
---endCorr

Question 3 : Client-serveur (1,5 points)

Une société souhaite coder une application client-serveur permettant à des clients d'envoyer un message ping vers le serveur, ce dernier répondant par un message pong.
Quel type d'architecture client-serveur proposer pour minimiser le temps de réponse du serveur quand :
  1. Le serveur répond immédiatement au ping ?
  2. Le serveur ne répond au ping qu'après avoir interrogé une machine distante (ce qui lui nécessite en moyenne 10 secondes) ?
Répondre, sur feuille, en justifiant rapidement (3 lignes maximum pour chacun des cas).
---beginCorr
  1. Une architecture avec serveur mono-processus est idéale au vu de son faible coût de mise en oeuvre et du fait que le serveur répond immédiatement au ping.
  2. Dans le cas où le serveur a un temps de travail de 10 secondes, une architecture avec autant de serveurs que de processus client est préférable pour être en mesure de prendre en compte le plus rapidement possible les nouvelles requêtes.
---endCorr

Question 4 : Thread (2 points)

Répondre brièvement (3 lignes maximum par question), sur feuille, aux questions suivantes :
  1. Qu'est-ce qu'un thread ?
  2. Quels sont les différents types d'implantation de threads ?
---beginCorr
  1. Un thread est un processus léger défini par sa pile et son contexte. Il partage le code, le tas, l'espace d'adressage, les fichiers ouverts et les flux avec les autres threads du processus lourd auquel il appartient.
  2. Threads utilisateurs, noyaux ou intégrés dans un langage (Java, C++...).
---endCorr

Question 5 : Méthode pour trouver "instantanément" la iè ligne d'un fichier texte (6 points)

On se propose de développer (dans le répertoire Q5) un programme gl.c (pour GotoLigne) permettant de trouver "instantanément" la iè ligne d'un fichier texte dont les lignes ont des longueurs différentes (inférieures à 1024 caractères, caractère de nouvelle ligne inclus).
Le principe de la solution retenue est le suivant pour trouver la iè ligne du fichier exemple.txt :
  • Avant l'utilisation de gl.c, on construit (à l'aide d'un programme d'initialisation gli fourni) un fichier exemple.txt.idx tel que :
    • Les 4 premiers octets du fichier exemple.txt.idx contiennent le décalage de la 1ère ligne de exemple.txt (par rapport au début de exemple.txt), i.e. 0 (zéro).
    • Les 4 suivants contiennent le décalage de la 2è ligne de exemple.txt, i.e. longueur de la 1ère ligne. Par exemple, 7, si la 1ère ligne de exemple.txt contient "Coucou\n".
    • Les 4 suivants contiennent le décalage de la 3è ligne de exemple.txt, i.e. longueur de la 1ère ligne + longueur de la 2è. Par exemple, 13, si la 2è ligne contient "Hello\n".
  • Au moment de l'exécution de gl.c :
    • On ouvre le fichier exemple.txt.idx
    • On se décale pour se placer au niveau des octets correspondant au décalage du numéro de ligne cherchée
    • On lit, dans un entier, les 4 octets correspondant au numéro de ligne cherchée
    • On lit également les 4 octets correspondant au numéro de ligne recherché + 1 (on connaît ainsi la longueur de la ligne cherchée)
    • On ouvre le fichier exemple.txt
    • On se décale de la valeur des 4 octets correspondant à la ligne cherchée
    • On lit le fichier pour récupérer toute la ligne
Écrire le programme gl.c (à l'aide des fonctions système Unix ou des fonctions de la bibliothèque C d'entrées-sorties). Ce programme lit sur la ligne de commande le nom du fichier et le numéro de ligne (convertible en entier grâce à la fonction atoi), puis il affiche la ligne recherchée.
NB :
  • La 1ère ligne du fichier a pour numéro de ligne 0 (zéro).
  • Votre programme peut utiliser lseek, fseek ou mmap.
---beginCorr
glQ5.corrige.c
Pour information, voici le fichier source du programme d'initialisation gli : gli.corrige.c
---endCorr

Question 6 : Même méthode, mais avec un enfant (5 points)

Se placer dans le répertoire Q6 et y recopier le fichier gl.c réalisé à la question 5.
Modifier gl.c pour que dans le main(), on crée une activité (processus enfant ou thread) A :
  • A exécute l'algorithme de lecture de la ligne.
  • Une fois la ligne lue, A la transmet à P, le père de la hiérarchie.
  • P affiche la ligne.
NB : le mode de transmission d'information entre A et P est libre... du moment qu'il fonctionne correctement.
---beginCorr
glQ6.corrige.c
---endCorr

Page mise à jour le 15 mai 2006