Département
INFormatique
Communication inter-processus
Synchronisation entre processus
(Corrigés)
Exercice 1 : Un programme d'impression simple
Le programme imprime0.c simule une application d'impression qui attend de la part de l'utilisateur des noms de fichier à imprimer et les envoie à l'imprimante (l'impression étant simulée par un sleep de quelques secondes).Telle qu'elle est écrite, l'utilisateur doit attendre qu'un fichier soit imprimé pour pouvoir donner le nom d'un autre fichier.
Modifier l'application de sorte qu'à chaque fois que l'utilisateur a entré un nom de fichier, un enfant est forké pour s'occuper de l'impression de ce fichier.
---beginCorr
imprime1.corrige.c
---endCorr
Exercice 2 : Un seul enfant pour imprimer
On reprend le programme imprime0.c évoqué à l'exercice 1. Cette fois, on souhaite modifier ce programme pour qu'il commence par forker un enfant à qui il enverra, via un tube, les noms des fichiers à imprimer. Ecrire ce programme modifié.---beginCorr
imprime2.corrige.c
---endCorr
Exercice 3 : Un seul processus pour imprimer
Le programme réalisé à l'exercice 2 présente l'inconvénient que si on lance plusieurs fois l'application en parallèle, on a plusieurs enfants qui sont en charge des impressions. Pour pallier cet inconvénient, on souhaite créer :- une application serveur en charge de créer un tube nommé et d'attendre sur ce tube nommé les noms de fichier à imprimer
- une application cliente capable de se connecter, via le tube nommé, au serveur et de lui envoyer les noms de fichier à imprimer.
---beginCorr
imprime3.corrige.h
imprime3s.corrige.c
imprime3c.corrige.c
---endCorr
Exercice 3bis : Un seul processus pour imprimer (le retour)
Reprenez l'exercice 3, mais en utilisant une file de messages au lieu d'un tube nommé.---beginCorr
A compléter
---endCorr
Exercice 4 : Synchronisation des enfants dans l'impression
Le programme développé dans l'exercice 1 présente l'inconvénient que les enfants peuvent tous accéder à l'imprimante en même temps, ce qui risque de mélanger les impressions.Au lieu d'utiliser un enfant dédié à l'impression comme il a été fait dans l'exercice 2, ajouter au programme de l'exercice 1 l'utilisation d'un sémaphore pour veiller à ce qu'un seul enfant imprime à la fois.
---beginCorr
imprime4.corrige.c
---endCorr
Exercice 5 : Producteur/consommateur et impression
On souhaite pouvoir connaître la liste des fichiers qui sont en attente d'impression au niveau du serveur d'impression développé à l'exercice 3. On ne peut pas interroger le contenu du tube nommé. On décide donc de le remplacer par une zone de mémoire partagée pouvant contenir au maximum 10 noms de fichiers, cette zone étant gérée selon un paradigme producteur/consommateur.Reprendre le code développé à l'exercice 3 pour qu'il travaille selon ce nouveau principe.
NB : l'application de consultation sera développée à l'exercice 6.
---beginCorr
imprime5.corrige.h
imprime5s.corrige.c
imprime5c.corrige.c
---endCorr
Exercice 6 : Lecteur/rédacteur et impression
Développer l'application de consultation de la liste des fichiers évoquée à l'exercice 5.Pour ce faire, commencer par rappeler les différents paradigmes présents dans cet exercice. Quels est(/sont) le(s) rôle(s ) tenu(s) par les clients, le serveur et l'application de consultation.
NB : si la liste des fichiers est en train de changer (ajout de fichiers par des clients ou retrait par le serveur), l'application de consultation doit attendre. De plus, si une (ou plusieurs) application(s) de consultation est (sont) en train de consulter la liste des fichiers, les clients ou le serveur doivent attendre avant de la modifier cette liste.
---beginCorr
On est en présence de 2 paradigmes :
- Paradigme Producteur/Consommateur : les clients sont producteur tandis que le serveur est consommateur.
- Paradigme lecteur/Rédacteur : les clients
et le
serveur sont lecteur tandis que l'application de consultation est
rédacteur.
imprime6s.corrige.c
imprime6c.corrige.c
imprime6l.corrige.c
---endCorr
Exercice 7 : Correction d'un problème de famine
Dans la question 7 de l'exercice EntréesSorties/7, un problème de famine a été détecté. Modifier l'application pour corriger ce problème de famine.---beginCorr
La famine observée est un problème de famine de lecteur (les consultations de compte)/rédacteur (les débits de compte). Il faut donc rajouter un mutex au moment de la prise du verrou (cf. chapitre "Synchronisation entre processus"). Noter qu'un mutex est nécessaire pour chaque verrou, i.e. pour chaque compte !
---endCorr
Exercice 8 : Des chiffres et des lettres... et des tubes
L'application simple.c :- lit le flux de caractères arrivant sur l'entrée standard
- sépare les chiffres et les lettres
- effectue l'opération appropriée en fonction du type de caractère, à savoir :
- sommer les chiffres
- réaliser un spectre de fréquence pour les lettres
- affiche le résultat obtenu
- un distributeur (en charge de la répartition des caractères) ;
- un additionneur (opérant sur les chiffres) ;
- un compteur (opérant sur les lettres).
---beginCorr
pipe.corrige.c
---endCorr
Exercice 9 : Des chiffres et des lettres... et des files de message
Reprendre l'exercice 8, mais avec des communications par files de message.---beginCorr
msg.corrige.c
---endCorr
Exercice 10 : Des chiffres et des lettres... et de la mémoire partagée
Reprendre l'exercice 8, mais avec des communications par mémoire partagée.---beginCorr
shm.corrige.c
---endCorr
Exercice 11 : Des chiffres et des lettres... et de la mémoire partagée avec des sémaphores
Reprendre l'exercice 8, mais avec des communications par mémoire partagée et en utilisant des sémaphores pour faire la synchronisation entre les différents processus.---beginCorr
shm_sem.corrige.c
---endCorr
Exercice 12 : Le repas des philosophes
5 philosophes se retrouvent à un restaurant chinois pour déjeûner. Le restaurateur leur propose une table sur laquelle il dispose 5 bols et 5 baguette (une entre chaque bol). Chaque philosophe passe son repas à penser (pendant une durée aléatoire), puis à manger un peu (pendant une durée aléatoire, puis à penser... NB : pour pouvoir manger, un philosophe doit pouvoir prendre 2 baguettes : celle à sa gauche et celle à sa droite.Question 1
Écrire l'algorithme utilisé par chaque philosophe
pour
pouvoir penser, manger... sans qu'il y ait d'interblocage entre les
philosophes, ni de famine.---beginCorr
Le texte suivant est extrait du cours CNAM : Systèmes informatiques : structures et paradigmes des plates-formes informatiques
La solution simple consistant à considérer chaque baguette comme une ressource critique et à demander à chaque philosophe de prendre ses deux baguettes l'une après l'autre (entrer en section critiquie pour chacune d'elle) conduit à un interblocage quand chaque philosophe a pris une baguette et demande la seconde sans relâcher la première. Pour éviter ce cas d'interblocage, on ajoute la contrainte supplémentaire qui impose que 4 philosophes seulement puissent prendre des baguettes concurremment. Pour cela, on leur demande de manger assis et on ne leur fournit que 4 chaises : cela introduit une cohorte de 4 philosophes assis.
Cette solution est sans interblocage. En effet, comme il n'y a que 4 philosophes assis, l'un au moins peut recevoir deux baguettes au bout d'un temps fini.
---endCorr
Question 2
Programmer cet algorithme.---beginCorr
à compléter
---endCorr
Exercice 13 (ou 12 bis pour les superstitieux...) : Expériences autour d'un serveur Web
Préparation
Se placer dans un répertoire de travailtar xvfz serveurWeb.tgz
cd ServeurWeb
Introduction
Le code présent dans le répertoire Question1 contient un serveur Web très simplifié : quand on l'interroge, ce serveur se contente de renvoyer une page Web contenant le nombre de fois qu'on l'a interrogé (et donc qu'il a répondu).---beginCorr
Pour information, le code de ce serveur est une adaptation du code tiré du chapitre 11 du livre Advanced Linux Programming (http://www.advancedlinuxprogramming.com/).
---endCorr
Avant de rentrer dans le vif du sujet, faites fonctionner ce serveur :
- dans
un terminal, positionnez-vous dans le répertoire Question1, tapez make pour
compiler, puis server
pour lancer l'exécution du serveur ;
NB : - par défaut, le serveur se met en attente sur le port 8080 ;
- si vous
souhaitez qu'il utilise un autre numéro de port, tapez la
commande :
server -p numeroPort - dans un navigateur Web, tapez l'adresse http://localhost:8080 (ou un autre numéro de port, si vous avez démarré votre serveur avec un autre numéro de port) ;
- le navigateur Web affiche : « compteurReponse = 1 » (le serveur indique qu'il a été interrogé une fois et donc qu'il a répondu une fois) ;
- si
vous cliquez plusieurs fois sur le bouton
« Rafraîchir / Actualiser la
page courante » du navigateur, votre navigateur
interroge à chaque fois
le serveur qui renvoie donc successivement : « compteurReponse
= 2 », « compteurReponse
= 3 »...
NB : avec Firefox, pour une raison indéterminée (et qui ne fait pas l'objet du présent exercice), un clic sur le bouton « Rafraîchir / Actualiser la page courante » peut éventuellement faire sauter le compteurReponse de plusieurs unités. Si ce comportement vous gêne, utilisez le navigateur textuel lynx (commande lynx http://localhost:8080, le rafraichissement se faisant avec les touches Control et R, l'arrêt avec la touche « q ») ; - arrêtez votre serveur (à l'aide des touches Control et C).
- la procédure init réalise toutes les initialisations de votre module avant que le serveur web ne se mette en attente de requêtes Web. Ainsi, dans le code livré dans le répertoire Q3-1, cette procédure initialise à 0 une variable appelée compteurReponse ;
- la procédure gestion_connexion_entrante est appelée lorsque le serveur web reçoit une requête Web. Cette procédure (qui est appelée avec un paramètre connexion_fd) est chargée de confier à un thread la responsabilité d'appeler la procédure handle_connection (définie dans un des autres modules que vous n'avez pas à modifier) avec la valeur de ce paramètre connexion_fd. Ainsi, dans le code livré dans le répertoire Q3-1, cette procédure crée un thread thread_gestion_connexion_entrante (avec en paramètre la valeur de connexion_fd). Et ce thread se charge, quand il prend la main, d'appeler handle_connection avec la valeur de connexion_fd ;
- la fonction gestion_compteurReponse est chargée d'effectuer les traitements liés à la variable compteurReponse lorsque le serveur répond à une requête HTTP. Elle modifie la valeur de compteurReponse, puis retourne la valeur courante de compteurReponse. Ainsi, dans le code livré dans le répertoire Q3-1, cette fonction incrémente compteurReponse, puis retourne sa valeur.
main(){
Appeler la procédure init() de codeEtudiant.c
Tant que VRAI faire
connexion_fd = attente_connexion_TCP_d_un_navigateur()
Appeler gestion_connexion_entrante(connexion_fd) de codeEtudiant.c
fait
}
Les threads que vous manipulez (et qui sont créés, dans la question 1, par gestion_connexion_entrante()) ont la responsabilité d'appeler la procédure handle_connection(connexion_fd). Voici l'algorithme de cette procédure:
handle_connection(int connection_fd){
char reponse_HTTP[256];
requete_HTTP = lire_octets(connection_fd);
sprintf(reponse_HTTP, "compteurReponse = %d", résultat appel à gestion_compteurReponse() de codeEtudiant.c);
ecrire_octets(connection_fd, reponse_HTTP);
}
Les questions 1 à 6 sont destinées à améliorer le fonctionnement de ce serveur. Noter que seront évalués :
- la clarté du code,
- le fait que le code compile (sans warning),
- le fait que le retour de chaque appel
système, s'il y en a un,
est testé avec appel à
perror(), puisexit(EXIT_FAILURE)en cas de problème détecté, - le fait que le code répond correctement à la question posée.
Question 1 : Empêcher les pertes d'incrémentation de compteurReponse (3,5 points)
La variable compteurReponse peut être manipulée par plusieurs threads travaillant en parallèle. On peut donc potentiellement perdre des incrémentations de cette variable. Pour tenter de l'observer, utilisons ab, l'outil de benchmark d'Apache, qui permet d'envoyer un certain nombre de requêtes vers un serveur, dans un laps de temps très court. Effectuez les opérations suivantes :- dans un terminal, démarrez le serveur ;
- dans
un autre terminal, tapez la commande :
ab -n 1000 -c 6 http://localhost:8080/
(où 1000 désigne le nombre d'invocations au serveur et 6 désigne le nombre de connexions simultanées faites au serveur). ab vous indique les performances de votre serveur.
NB : - Si jamais ab vous affiche le message Benchmarking localhost (be patient)...apr_socket_recv: Connection refused (111), arrêtez le server et redémarrez le en lui ajoutant l'option -i 4 pour lui spécifier d'utiliser le protocole IPv4 (exemple de ligne de commande : server -i 4).
- Le programme ab
disponible sur les machines des salles TP a tendance à afficher un
nombre important de Failed
requests: . En fait, il a contacté à chaque fois server !
- dans un navigateur, tapez l'adresse http://localhost:8080 : à cause de ces pertes d'incrémentation potentielle, il est possible que le navigateur affiche une valeur de compteurReponse inférieure à la valeur attendue, c'est-à-dire 1001 (1000 requêtes réalisées par ab et 1 requête réalisée par votre navigateur) ;
- arrêtez votre serveur.
---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 : 1,25 ;
- encadrement de l'incrémentation par mutex_lock et mutex_unlock : 1,5.
---endCorr
Question 2 : Sauvegarde de compteurReponse sur disque (3,5 points)
Jusqu'à présent, lorsque l'on arrête le serveur, la valeur courante de compteurReponse est perdue. On se propose donc de mémoriser sur disque sa valeur dans un fichier sauvegardeCompteurReponse :- recopiez Question1/codeEtudiant.c dans Question2 ;
- modifiez Question2/codeEtudiant.c de sorte que :
- au démarrage du serveur :
- si le fichier sauvegardeCompteurReponse n'existe pas, il est créé (avec les droits de lecture-écriture pour vous-même, le groupe et les autres, avant modification par le umask) et compteurReponse est initialisé à 0 ;
- si le fichier sauvegardeCompteurReponse existe, compteurReponse est initialisé à la valeur mémorisée dans ce fichier ;
- à chaque appel de gestion_compteurReponse, on sauvegarde la valeur de compteurReponse dans le fichier.
- la valeur de compteurReponse sera stockée dans le fichier sauvegardeCompteurReponse sous forme binaire ou textuelle, selon votre préférence.
- le fichier sauvegardeCompteurReponse sera ouvert avec ou sans l'option O_SYNC, selon votre préférence. En revanche, vous veillerez à justifier (dans un commentaire au niveau de l'instruction d'ouverture du fichier) votre décision par rapport à l'utilisation ou la non-utilisation de O_SYNC.
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 :
- création correcte du fichier : 0,5 (seulement 0,25 si les droits ne sont pas corrects) ;
- traitement correct (lecture bien faite de la valeur de la variable) si le fichier existe déjà : 0,5 ;
- écriture correcte de la variable : 1,0 (0,5 pour le lseek et 0,5 pour le write proprement dit) ;
- justification par rapport à l'utilisation de O_SYNC (vu le flou de l'énoncé, on peut décider d'utiliser O_SYNC ou non) : 0,5 ;
- encadrement de l'incrémentation et éventuellement (ce n'est pas obligatoire, car on écrit seulement 1 entier ==> Ecriture atomique) de l'écriture dans le fichier par mutex_lock et mutex_unlock : 0,25.
voir codeEtudiant.Question2bis.corrige.c pour une sauvegarde dans le fichier au format texte.
---endCorr
Question 3 : Améliorer les performances de la sauvegarde sur disque (4 points)
En utilisant ab, on constate que le serveur réalisé à la question 2 voit ses performances chuter par rapport à celui de la question 1. C'est pourquoi, dans cette question, on met en œuvre une architecture logicielle préservant les performances de la question 1 tout en conservant la sauvegarde de compteurReponse abordée à la question 2. Le principe de cette architecture est de confier l'écriture sur disque à un thread spécifique qui écrit, chaque seconde, la valeur courante de compteurReponse dans le fichier sauvegardeCompteurReponse. Certes, si le serveur tombe, on perd le décompte de requêtes effectuées depuis la dernière seconde où ce thread spécifique s'est activé, mais on préserve les performances du serveur !- recopiez Question2/codeEtudiant.c dans Question3 ;
- modifiez Question3/codeEtudiant.c de sorte que :
- au démarrage du serveur :
- si le fichier sauvegardeCompteurReponse n'existe pas, il est créé (avec les droits de lecture-écriture pour vous-même, le groupe et les autres) et compteurReponse est initialisé à 0 ;
- si le fichier sauvegardeCompteurReponse existe, compteurReponse est initialisé à la valeur mémorisée dans ce fichier ;
- on crée ce thread spécifique ;
- ce thread spécifique exécute une boucle sans fin dans laquelle :
- il écrit la valeur courante de compteurReponse dans sauvegardeCompteurReponse ;
- il dort pendant une seconde ;
- à chaque appel de gestion_compteurReponse, on se contente d'incrémenter compteurReponse de 1 (sans faire aucune écriture dans le fichier sauvegardeCompteurReponse).
---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 :
- création du nouveau thread : 0,25 ;
- code correct pour ce nouveau thread :
- écriture de la valeur : 0,75 ;
- non-encadrement de l'écriture sur disque par mutex_lock et mutex_unlock : 1,0 (pour avoir l'ensemble de ces 1,0 point, il faut recopier la valeur de compteurReponse dans une variable locale (en protégeant cette recopie via mutex_lock/mutex_unlock), puis faire l'écriture hors mutex (sinon on bloque tous les threads incrémenteurs, i.e. on n'a rien gagné par rapport à Q3-2) ;
- sommeil : 0,5 ;
- justification par rapport à l'utilisation de O_SYNC (on doit l'utiliser, car l'énoncé suggère qu'on ne souhaite pas perdre plus de 1 seconde d'incrémentation) : 0,5 ;
- encadrement de l'incrémentation par mutex_lock et mutex_unlock : 0,25.
---endCorr
Question 4 : Utilisation d'un pool de threads (4,5 points)
Dans le code livré à la question Q3.1, la procédure handle_connection() crée systématiquement un thread avec pthread_create(), thread qui est détaché de sorte que, quand il se termine, il se libère automatiquement (dit autrement, le système récupére la place mémoire qu'il occupait).Donc, à chaque fois que votre navigateur se connecte à votre serveur Web, votre serveur Web crée un thread pour traiter votre requête, puis le libère. Ce n'est pas très efficace.
L'objectif de cette question 4 est d'éviter cette opération de création/suppression qui est coûteuse en temps machine.
- recopiez Question3/codeEtudiant.c dans Question4 ;
- modifiez Question4/codeEtudiant.c de sorte que :
- au
démarrage du serveur, outre les traitements mis en
œuvre à la question
Question3, on crée 20
threads
qui sont mises dans un pool de threads en attendant du travail (vous
trouverez des conseils d'implémentation de pools de threads dans la
note du transparent 3.1 (Principe) du cours « Eléments d'architecture
client-serveur ») ;
- lors de l'appel à gestion_connexion_entrante, on confie le traitement de cette connexion à l'un des threads inactifs de ce pool ;
- lorsqu'un thread a terminé son appel à handle_connection, il se remet en attente de travail.
Dans la procédure init() de codeEtudiant.c, vous allez créer un tube (il est totalement inutile que ce soit un tube nommé) et faire 20 pthreads_create() et 20 pthread_detach().
Chacun de ces threads va dérouler l'algorithme suivant :
Tant que VRAI faire
connexion_fd_local_au_thread = read sur le tube
handle_connection(connexion_fd_local_au_thread);
fait
L'algorithme de gestion_connexion_entrante(int connexion_fd) devient simplement:
ecrire connexion_fd sur tube
Ainsi (NB : pour suivre ces explications, il est recommandé de faire un schéma sur un papier avec le serveur, le tube et ses 20 threads), quand le serveur démarre, il appelle init() qui crée le tube et les 20 threads. Il attend qu'un navigateur se connecte à lui (cf. instruction attente_connexion_TCP_d_un_navigateur() du main() du serveur, évoquée ci-dessus). Pendant ce temps, les 20 threads démarrent et se bloquent tous sur l'instruction de lecture sur le tube.
Quand un navigateur se connecte au serveur, le serveur appelle gestion_connexion_entrante(int connexion_fd) qui écrit donc la valeur de connexion_fd sur le tube.
L'un des threads va donc trouver quelque chose à lire sur le tube et va le ranger dans connexion_fd_local_au_thread. Il se débloque donc du read sur le tube et appelle handle_connection(connexion_fd_local_au_thread). Quand ce thread a fini, il se remet en attente de lecture sur le tube.
Noter que si, pendant ce temps, un autre navigateur a contacté le serveur, le serveur a écrit une autre valeur de connexion_fd sur le tube, valeur qui a été lue sur le tube par un autre thread, etc.
---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 :
- création des 20 threads (pas forcément détachées) : 0,75
- implémentation répondant au problème : 3 point. Pour info, dans le corrigé :
- on crée un tube sur lequel les 20 threads se mettent en lecture d'un connexion_fd ;
- gestion_connexion_entrante écrit la valeur du paramètre connexion_fd sur ce tube ;
- un seul des threads en attente arrive à lire cette valeur. Il appelle handle_connection.
---endCorr
Question 5 : Utilisation de deux serveurs sur la même machine (4,5 points)
On souhaite tester les performances lorsque la machine héberge deux serveurs Web, l'un étant à l'écoute du port 8080, tandis que l'autre est à l'écoute du port 8082. ces deux serveurs partagent la même variable compteurReponse et le même fichier sauvegardeCompteurReponse dans lequel ils sauvegardent la valeur de la variable compteurReponse.- recopiez Question4/codeEtudiant.c dans Question5 ;
- modifiez Question5/codeEtudiant.c de sorte que :
- au démarrage de la première instance de serveur (par exemple, celui qui sera à l'écoute du port 8080), tous les objets système nécessaires soient créés et initialisés ;
- la variable compteurReponse est partagée entre les deux instances de serveurs et aucune incrémentation n'est perdue ;
- la variable compteurReponse est sauvegardée dans le fichier sauvegardeCompteurReponse par les deux instances de serveurs ;
- NB : le pool de threads de chaque instance de serveur est spécifique à chaque serveur : il n'est pas partagé.
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 :
- création d'une variable partagée entre les deux processus : 0,75
- création (et initialisation correcte) d'un sémaphore protégeant les accès simultanés à cette variable : 1
- protection, via ce sémaphore, des accès à cette variable : 1
- gestion correcte du fichier : 1 (seulement 0,5 si pas de verrou posé au moment de l'écriture)
---endCorr
Question 6 (bonus) : Autre implémentation du pool de threads mis en œuvre à la question 4 (bonus de 2 points)
Lors de la question 4, il est probable que vous avez implémenté le pool de threads à l'aide d'un tube.Si c'est effectivement le cas, implémentez maintenant ce pool avec un paradigme producteur/consommateur utilisant des conditions (au sens pthread_cond_t).
Si ce n'est pas le cas, implémentez ce pool avec un tube.
- recopiez Question5/codeEtudiant.c dans Question6 ;
- modifiez Question6/codeEtudiant.c pour mettre en œuvre cette nouvelle implémentation.
Barème :
- Clarté du code : 0,25
- Compilation sans warning : 0,25
- Test du retour de chaque appel système : 0,25
- Nouvelle implémentation correcte (NB : la création des 20 threads ne rapportent pas de points : c'est vraiment l'implémentation du nouveau mécanisme qui est ici jugée) : 1,25
---endCorr