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 16/05/12

(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}_TPNote2012
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 ~trahay_f/Cours/CSC4508/tPNote2012.tgz .
tar xvfz tPNote2012.tgz
mv TPNote2012 ${USER}_TPNote2012
cd ${USER}_TPNote2012


Question 1 : Questions de cours (4 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 dans un processus multi-threadé (3 points)

On considère la portion de code suivante issue d'un programme multi-threadé :



int a;

static int b;

int foo() {

int c;

static int d;

char *e = malloc(sizeof(char) * 80);

char *f = alloca(sizeof(char) * 80);

...

}

Expliquez en justifiant brièvement si, pour chacune des variables a, b, c et d, il s'agit d'une variable partagée entre les différents threads du programme ? Dit autrement, si un thread change la valeur de cette variable, un autre thread voit-il le changement ?

Même question pour les zones de données pointées par e et f.

---beginCorr
Barème : 0.5 point par proposition (0,25 pour la justesse de la réponse et 0,25 pour la justification), soit un total de 3 points.

a et b sont partagées. Ce sont des variables globales allouées dans le segment de données.

c n'est pas partagée. C'est une variable locale allouée sur la pile d'un thread.

d est partagée. C'est une variable statique locale allouée dans le segment de données.

*e est partagée. C'est une zone mémoire allouée sur le tas. On peut également considérer que *e n'est pas partagée (tant que l'adresse de la zone mémoire n'est pas partagée entre les threads). A juger en fonction de la justification.

*f n'est pas partagée. C'est une zone mémoire allouée sur la pile d'un thread.

---endCorr

Question 1.2 : 640 Ko de mémoire devraient suffire à tout le monde (1 points)

Le développeur d'une application destinée à faire l'inventaire dans un supermarché réfléchit actuellement à la structure de données à utiliser pour son programme. Il compte utiliser cette structure :

struct object{

int identifiant;

char code_barre[10];

int nombre;

};


Comme la machine sur laquelle fonctionnera l'application dispose de très peu de mémoire et que le nombre d'objets à créer dans l'application est très grand, le développeur souhaite minimiser la taille mémoire occupée par chaque objet.

Modifiez cette structure (sans en modifier les champs) pour minimiser la taille d'un objet.

---beginCorr
Barème : 1 point

struct object{

int identifiant;

char code_barre[10];

int nombre;

} __attribute__((packed));


---endCorr

Question 2 : Passer le gué (8 points)

Les ponts permettant de traverser la Bruinen sont rares et il est parfois nécessaire de prendre une barge (un bateau à fond plat) pour traverser la rivière. À l'Est d'un village peuplé d'elfes se trouve une barge permettant de traverser la rivière et ainsi accéder à la forêt située de l'autre côté pour y cueillir les framboises dont raffolent les elfes. Cette barge est située à l'Ouest du village des nains et ceux-ci l'empruntent pour se procurer leur bière préférée produite par un brasseur habitant près du village elfe.

Le propriétaire de la barge n'accepte de traverser que si 4 passagers montent à bord et comme les elfes et les nains entretiennent de mauvaises relations, il ne peut y avoir 1 elfe et 3 nains, ni 3 elfes et 1 nain, sous peine de bagarre générale. Les autres combinaisons (4 nains seuls, 4 elfes seuls, ou 2 nains et 2 elfes) ne posent pas de problème.

L'objectif de cet exercice est de simuler la circulation des nains et des elfes. Pour cela, chaque elfe ou nain de l'histoire est représenté par un thread.

Lorsqu'un thread (elfe ou nain) monte sur la barge, il doit appeler la fonction embarquer. Il faut garantir que 4 threads ont appelé embarquer avant que les threads de la traversée suivante n'embarquent.

Lorsque les 4 threads ont embarqué, l'un d'eux (peu importe lequel) doit appeler la fonction ramer. On appelle le thread chargé de ramer le Capitaine.

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é.
  • Les questions 2.1 et 2.2 sont indépendantes.

Question 2.1 : Implémenter une barrière (3 points)

On souhaite dans un premier temps implémenter une "barrière" à partir d'un ou plusieurs sémaphores permettant d'attendre que les 4 threads aient embarqué. Une barrière est un point de synchronisation qui garanti que N tâches sont arrivées à un point spécifique. Lorsqu'un thread atteint la barrière, il attend jusqu'à ce que le nombre de thread requis soit atteint.

À 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(), écrivez l'algorithme de barriere().

---beginCorr
Barème : 3 points

Variables utilisées :

int nb_threads : initialisé à zero

semaphore mutex: initialisé à 1

semaphore attente : initialisé à 0

procedure barriere ( )

P(mutex)

nb_threads++;

si( nb_threads == 4) alors

Pour i de 1 à 4 faire
V(attente);
Fin Pour

nb_threads = 0;

V(mutex);

sinon
V(mutex);

P(attente);

Fin Si

Fin Procedure

---endCorr

Question 2.2 : Algorithme du passage de la Bruinen (5 points)

Chaque nain est modélisé par un thread exécutant l'algorithme codePassageNain(). Chaque elfe est modélisé par un thread exécutant un algorithme codePassageElfe() similaire.

procédure codePassageNain()

je_suis_capitaine = faux;

// à compléter, si besoin, avec du code d'initialisation et de synchronisation

embarquer( );

// à compléter, si besoin, avec du code de synchronisation

barriere( );

// à compléter, si besoin, avec du code de synchronisation

si je_suis_capitaine alors

// à compléter, si besoin, avec du code de synchronisation
ramer();
// à compléter, si besoin,avec du code de synchronisation
Fin Si
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 codePassageNain().
---beginCorr

Barème : 5 points
int nb_nains=0;

int nb_elfes=0;

Semaphore mutex_compte : initialisé a 1;

Semaphore sem_nains : initialisé a 0;

Semaphore sem_elfes : initialisé a 0;

Procedure codePassageNain() {

boolean je_suis_capitaine = false;

P(mutex_compte);

nb_nains++;

if(nb_nains == 4) {

// le dernier monté rame

je_suis_capitaine = true;

nb_nains = 0;

for( i = 1 ; i <= 4 ; i++) {

V(sem_nains);

}

} else if (nb_nains == 2 && nb_elfes >= 2) {

je_suis_capitaine = true;

nb_nains = 0;

nb_elfes -= 2;/* on reveille 2 elfes */

for( i= 1 ; i<=2 ; i++) {

V(sem_nains);

V(sem_elfes);

}

} else {

/* on doit attendre */

V(mutex_compte);

}

P(sem_nains);

Embarquer();

Barriere();

if(je_suis_capitaine) {

/* le capitaine a garde le mutex */

ramer();

V(mutex_compte);

}

}

---endCorr

Question 3 : Remote Procedure Calls (8 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 ».

Le but de cet exercice est de développer un système de RPC (Remote Procedure Call) permettant d'appeler des fonctions dans un processus distant. Un serveur founi un ensemble de fonctions qu'il peut exécuter à la place de l'application cliente. Par exemple, si une application souhaite calculer la somme de deux vecteurs, elle peut le demander au serveur qui lui retourne le résultat.


Protocole

À l'initialisation, le serveur crée un tube nommé ./serveur-rpc (noté Ts dans la suite) et attend que des applications clientes se connectent et donnent des ordres. Lorsqu'un ordre est reçu, le serveur traite la requête, puis attend un nouvel ordre.

Lorsqu'une application souhaite exécuter une fonction sur le serveur, elle envoie le numéro de la fonction à exécuter sur le tube Ts. Elle ouvre ensuite un nouveau tube (de la forme /tmp/client-rpc.<PID>, noté Tc dans la suite) pour que le serveur puisse lui répondre et envoie le nom de ce tube sur Ts. Selon la fonction à exécuter, le serveur attend alors que l'application envoie les paramètres de la fonction. Une fois le calcul effectué sur le serveur, celui-ci envoie le résultat sur Tc et ferme la connexion.

Question 3.1 (2.5 points)

Compléter dans le répertoire Q3/Q3.1 les fichiers client.c et serveur.c pour gérer la création des tubes, l'établissement et la fermeture de la connexion entre serveur et client (parties A COMPLETER dans le code). Testez votre serveur avec 1 client.

---beginCorr
Barème :

  • Création/ouverture correctes des tubes : 2 points
  • Fermeture des connexions : 0.5 points

Voir les fichiers serveur.Q3.1.corrige.c et client.Q3.1.corrige.c
---endCorr

Question 3.2 (1 point)

En testant le serveur avec plusieurs client, un problème se pose.

Ainsi, si vous tapez dans un terminal : for ((i=1;i<=30;i+=1)); do (./client &);done
vous risquez d'obtenir l'affichage suivant du coté serveur :

[...]

En attente...

Traitement d'une requete MUL

Calcul de mul(14.500000, 18.500000)

En attente...

Traitement d'une requete SOMMEV

Calcul de sommv(taille des vecteurs: 10)

En attente...

Traitement d'une requete SOMME

Calcul de somme(14.500000, 0.000000)

En attente...

Traitement d'une requete inconnue (1886221359)

En attente...

Traitement d'une requete inconnue (762605157)

En attente...

open(nomtube): No such file or directory

Expliquer, dans le fichier Q3/reponse3.txt, la raison de ce problème.

---beginCorr

Comme tous les processus clients écrivent dans le même tube et que pour traiter une requête, le client doit écrire plusieurs fois, les écritures des différents clients risquent de se mélanger. Le serveur risque donc de lire un nom de tube à la place d'un double (par exemple)

---endCorr

Question 3.3 (2.5 points)

Proposer, dans le fichier Q3/reponse3.txt, une solution qui permettrait de résoudre se problème

---beginCorr

Il faut s'assurer que les écritures des clients ne se mélangent pas. Une solution est d'utiliser un mutex (implémenté avec des sémaphores IPC), mais cela empêche le traitement de plusieurs requêtes à la fois par le serveur (si on décide de le rendre multi-threadé par exemple).

Une autre solution consiste à ouvrir un autre tube nommé pour chaque client. Chaque client crée donc 2 tubes nommés : Te pour les communications vers le serveur et Tr pour les communications du serveur au client. Lors de la connexion au serveur, le client écrit sur Ts (le tube créé par le serveur) le nom de Tr. Le reste des communications du client vers le serveur passe ensuite par Tr.

Par ailleurs, comme l'écriture d'une chaine de caractère dans le tube n'est pas atomique, il faut ajouter un mutex pour s'assurer qu'un seul processus client écrit sur Ts.

---endCorr

Question 3.4 (2 points)

Implémentez votre solution en modifiant les fichiers client.c et serveur.c situés dans le répertoire Q3/Q3.4.

Vérifier que votre serveur peut désormais gérer un grand nombre de clients en parallèle en tapant dans un terminal: for ((i=1;i<=30;i+=1)); do (./client &);done

---beginCorr


Voir les fichiers serveur.Q3.4.corrige.c et client.Q3.4.corrige.c

---endCorr



Page mise à jour le 10 mai 2012