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


    Évaluation



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

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

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 TPNote2011
NB: Si vous êtes plus à l'aise en écrivant vos réponses sur une copie plutôt qu'en les tapant sur ordinateur, vous pouvez rendre également une copie papier à l'enseignant qui vous surveille. En fin d'épreuve, même si vous ne rendez pas de copie, passez voir l'enseignant qui vous surveille pour lui signaler explicitement que vous ne rendez pas de copie.

Préparation

cd votreRepertoireDeTravailPourCSC4508M2
cp ~simatic/Cours/CSC4508/tPNote2011.tgz .
tar xvfz tPNote2011.tgz
cd TPNote2011

Question 1 : Questions de cours (4,5 points)

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

Question 1.1 :  Mémoire parent / mémoire enfant (3 points)

On considère le code suivant (dans lequel toute la gestion des codes d'erreur a été omise pour gagner en lisibilité) :












int d1;
int *pd2;
int *pd3;

int main(){
pd2 = malloc(sizeof(int));

shm_id = shmget(SHMKEY, sizeof(int), 0700|IPC_CREAT));
pd3 = (int *)shmat(shm_id, NULL, 0));

fork();

// Section de code concernée par les questions ci-dessous
// ------------------------------------------------------
...
}

Pour chacune des questions suivantes, vous justifierez brièvement.

Après le fork, la variable d1 est-elle partagée entre le parent et l'enfant qu'il a créé ? Dit autrement, après le fork, si le parent change la valeur de d1, l'enfant voit-il ce changement ?

Après le fork, la zone de données pointée par pd2 est-elle partagée entre le parent et l'enfant qu'il a créé ? Dit autrement, si le parent change la valeur de *pd2, l'enfant voit-il ce changement ?

Même question pour la zone de donnée pointée par pd3.

Question 1.2 : Libevent et sémaphore (1,5 points)

Le cours « Architectures Client-Serveur » étudie la librairie libevent. Nous avons vu, pendant ce cours, que l'exemple de code utilisant libevent était limité par le nombre de descripteurs de fichiers simultanément ouverts par le processus serveur. Nous avons vu également qu'utiliser un sémaphore au niveau de ce processus serveur pour limiter le nombre de clients simultanés (et donc ne pas atteindre cette limite du nombre de descripteurs de fichiers) n'était pas une bonne idée.

Réexpliquez pourquoi l'utilisation d'un sémaphore n'est pas une bonne idée.

Question 2 : La Trace du Hourra (8,5 points)

Pour chacune des questions ci-dessous :
  • Répondez dans le fichier Q2/reponse2.txt ou bien sur votre copie (dans ce dernier cas, indiquez dans le fichier Q2/reponse2.txt « Réponse sur copie »).
  • Le langage algorithmique utilisé n'a pas besoin de respecter strictement la syntaxe apprise en première année. L'essentiel est qu'il soit lisible par le correcteur et sans ambiguïté.
Au Parc d'attractions Astérix, « La Trace du Hourraanbsp;» est une montagne russe avec 3 trains qui circulent simultanément sur un circuit. Cet exercice a pour objectif d'écrire les algorithmes de synchronisation qui permettraient de gérer automatiquement cette montagne russe.

La figure 1 modélise cette montagne russe. Elle est constituée de 4 zones:
  • zoneE est la zone d'Embarquement où les passagers montent et descendent d'un train. zoneE peut contenir au maximum 2 trains.
  • zoneA est la zone d'Attente juste avant de pouvoir entrer dans zoneE. Elle ne peut contenir qu'un train.
  • zoneH est la zone où un train monte avant de se lancer dans sa descente infernale (c'est donc la zone des Hurlements où les gens crient « Help, je veux descendre ! Non, pas comme çaaaaaaaa... »). Elle ne peut contenir qu'un train.
  • zoneG est la zone de Garage du train. Les trains y sont parqués avant d'être injectés dans le circuit zoneE-zoneH-zoneA. NB : dans cet exercice, on suppose qu'une fois qu'un train est sorti de zoneG, il n'y retourne plus jamais.
Schéma de la montagne russe "La Trace du Hourra"
Figure 1 : Modélisation de la montagne russe « La Trace du Hourra »

Quand cette attraction fonctionne :
  • Un train ne peut quitter zoneG que s'il y a de la place dans zoneE.
  • Un train ne peut quitter zoneE que si zoneH est vide.
  • Un train ne peut quitter zoneH que si zoneA est vide.
  • Un train ne peut quitter zoneA que s'il y a de la place dans zoneE.

Question 2.1 : Paradigmes de synchronisation des trains sur la Trace du Hourra (1,5 point)

Indiquez tous les paradigmes de synchronisation présents dans cette montagne russe.

Question 2.2 : Algorithme de synchronisation des trains sur la Trace du Hourra (5 points)

Chaque train est modélisé par un processus exécutant l'algorithme codeTrain() suivant :
procédure codeTrain()
// à compléter, si besoin, avec du code de synchronisation
codeLiéAlaPrésenceDansZoneG();
// à compléter, si besoin, avec du code de synchronisation
Tant que VRAI faire
// à compléter, si besoin, avec du code de synchronisation
codeLiéAlaPrésenceDansZoneE();
// à compléter, si besoin, avec du code de synchronisation
codeLiéAlaPrésenceDansZoneH();
// à compléter, si besoin, avec du code de synchronisation
codeLiéAlaPrésenceDansZoneA();
// à compléter, si besoin, avec du code de synchronisation
Fin Tant que
Fin Procédure

À l'aide de sémaphores (dont vous indiquerez les valeurs initiales), d'éventuelles variables additionnelles (dont vous indiquerez les valeurs initiales), et d'opérations P() et V(), complétez l'algorithme de codeTrain().

Question 2.3 : Algorithme d'embarquement et de débarquement des passagers (2 points)

NB : cette question est plus difficile. Nous vous recommandons de ne l'aborder qu'en fin de TP noté.

Quand un train entre dans zoneE, il stationne sur la voie voie0 si celle-ci est libre, et sur la voie voie1 sinon. Ensuite, ce train autorise ses passagers à débarquer. Une fois qu'il est vide, le train autorise les usagers en attente d'embarquement sur cette voie à embarquer. Quand le train est plein, il quitte zoneE.

Par ailleurs, quand un usager de l'attraction entre dans zoneE, il commence par choisir la voie (voie0 ou voie1) où il souhaite embarquer. Une fois embarqué dans un train, il attend d'être autorisé à débarquer du train. Voici son algorithme:
Procédure codeUsager()
Entier numéroTrain
voieChoisiePourEmbarquer = nombreAléatoireEntre_0_et_1
numéroTrain = embarquerDansTrain(voieChoisiePourEmbarquer);
débarquerDeTrain(numéroTrain);
Fin Procédure

Sachant qu'un train peut contenir au maximum N passagers, écrivez les algorithmes de embarquerDansTrain(), débarquerDeTrain() et codeLiéAlaPrésenceDansZoneE() évoqué à la question 2.1. Vous utiliserez des sémaphores (dont vous indiquerez les valeurs initiales), d'éventuelles variables additionnelles (dont vous indiquerez les valeurs initiales), et d'opérations P() et V(). Si vous en avez besoin (parce que, par exemple, du code de synchronisation de train écrit à la questionQ2.1 doit se retrouver dans codeLiéAlaPrésenceDansZoneE()), écrivez une nouvelle version de codeTrain().

Question 3 : Multi-threading pour un serveur de liste de M. et Mme (7 points)

NB : Pour certaines des questions ci-dessous, vous êtes conviés à répondre dans le fichier Q3/reponse3.txt . Si vous préférez répondre sur votre copie, indiquez dans le fichier Q3/reponse3.txt « Réponse sur copie ».

Dans cette question, on considère un serveur de liste de M. et Mme. Il permet à un processus client de récupérer la liste des M. et Mme stocké dans un fichier mEtMme.txt géré par un processus serveur.

Préliminaire

Avant de rentrer dans le vif du sujet, faites fonctionner cette application :
  • dans un terminal (noté TermS dans la suite), positionnez-vous dans le répertoire Q3, tapez make pour compiler, puis ./serveur
  • dans un autre terminal (noté TermC dans la suite), positionnez-vous dans le répertoire Q3, tapez ./client -v nomClient
    Le client affiche :
Client nomClient : Connexion au serveur...
Client nomClient : Connecte !
Client nomClient : Recuperation liste des M. et Mme...
Client nomClient : Nouveau M. et Mme = ABA   ont un fils :    Bart
...
Client nomClient : Nouveau M. et Mme = ZOUDANLCOU              ont une fille   Debby
Client nomClient : Recuperation terminee !
  • pendant ce temps, le serveur affiche dans TermS :
1-ieme client a traiter (point d'access client = ./serveur-client.3565)

Pour accomplir ce travail, le client se connecte via un tube nommé client-serveur commun à tous les clients du serveur. Puis, le client envoie un message CONNEXION indiquant le tube nommé serveur-client.pidClient sur lequel le client attend des réponses du serveur. Le serveur crée un tube nommé client-serveur.rangClient (qui sera spécifique aux échanges entre ce client et le serveur) et renvoie le message CONNEXION_OK (sur le tube serveur-client.pidClient) avec le nom du tube client-serveur.rangClient. Le client affiche « Connecte ! »
Ensuite, le client envoie, via le tube client-serveur.rangClient, un premier message REQUETE.  Le serveur répond, via le tube serveur-client.pidClient, le message REQUETE_OK avec le premier M. et Mme du fichier mEtMme.txt. Si le client a été lancé avec l'option -v, il affiche le M. et Mme reçu.
Le client envoie alors un deuxième message REQUETE auquel le serveur répond avec le M. et Mme suivant du fichier.
Et ainsi de suite jusqu'à ce que le serveur renvoie au client le message REQUETE_KO pour signifier qu'il a envoyé au client tous les M. et Mme du fichier. Le client affiche alors « Recuperation terminee ! »
Les tubes serveur-client.pidClient et client-serveur.rangClient sont alors détruits. Le client s'arrête.

Travail à faire

Le serveur est actuellement mono-activité, de sorte qu'il ne peut traiter qu'un client à la fois.
Ainsi, si vous tapez dans TermC: for ((i=1;i<=3;i+=1)); do (./client $i &);done
vous obtenez l'affichage :
$ for ((i=1;i<=3;i+=1)); do (./client $i &);done
Client      1 : Connexion au serveur...
Client      1 : Connecte !
Client      1 : Recuperation liste des M. et Mme...
Client      2 : Connexion au serveur...
Client      3 : Connexion au serveur...
Client      1 : Recuperation terminee !
Client      2 : Connecte !
# Le serveur a enfin répondu à la demande de connexion
# de Client 2, puisqu'il a fini de traiter la demande
# de liste faite par Client 1
Client      2 : Recuperation liste des M. et Mme...
Client      4 : Connexion au serveur...
Client      2 : Recuperation terminee !
Client      3 : Connecte !
# Le serveur a enfin répondu à la demande de connexion
# de Client 3, puisqu'il a fini de traiter la demande
# de liste faite par Client 2
traiter la demande de liste du Client 1
Client      3 : Recuperation liste des M. et Mme...
Client      3 : Recuperation terminee !

Ajoutez du multi-threading à Q3/serveur.c de sorte que le serveur puisse gérer plusieurs clients simultanément. Vous veillerez notamment à :
  1. protéger la section de code comprise rangClient++; printf(); f = fopen(); if (f == NULL); sprintf(nomTube, "%s.%d", NOM_POINT_ACCES_SERV,rangClient); par une exclusion mutuelle;
  2. expliquer, dans le fichier Q3/reponse3.txt, la raison pour laquelle il faut mettre cette exclusion mutuelle.
Vérifier que votre serveur gère désormais bien 3 clients en parallèle en tapant dans TermC: for ((i=1;i<=3;i+=1)); do (./client $i &);done
Vous devez obtenir un affichage montrant qu'il y a désormais parallélisme entre les clients comme, par exemple, dans la trace suivante :
$ for ((i=1;i<=3;i+=1)); do (./client $i &);done
Client      1 : Connexion au serveur...
Client      2 : Connexion au serveur...
Client      1 : Connecte !
Client      1 : Recuperation liste des M. et Mme...
Client      2 : Connecte !
Client      2 : Recuperation liste des M. et Mme...
Client      3 : Connexion au serveur...
Client      3 : Connecte !
Client      3 : Recuperation liste des M. et Mme...
Client      2 : Recuperation terminee !
Client      1 : Recuperation terminee !
Client      3 : Recuperation terminee !

Pour information, au delà de 299 clients simultanés, votre serveur s'arrête pour une raison qui sort du cadre de ce TP noté.



Page mise à jour le 20 mai 2011