Table des matières
Exercice 1 - Jeu du pendu
On veut simuler une variante du jeu du pendu, dans lequel il s’agit de découvrir une combinaison de 5 chiffres (entre 0 et 9) enregistrée dans un tableau de 5 entiers (directement dans le programme). Ce jeu fait intervenir un serveur (le meneur de jeu) ainsi que n fils (les n joueurs). Chaque joueur (processus fils) envoie au serveur (processus père) une proposition comportant 3 informations: son numéro de joueur, le chiffre qu’il propose ainsi que l’indice (entre 0 et 4 puisque on se limite à une combinaison de 5 chiffres) auquel il souhaite mettre ce chiffre. Si la proposition du joueur est correcte, le serveur enregistre le chiffre proposé au bon indice dans un tableau réponse (tableau de 5 entiers déclaré dans le programme). Quand tous les joueurs ont épuisé le nombre d’essais auxquels ils ont droit (ici 10 essais), le jeu se termine, et le serveur affiche la réponse trouvée et si les joueurs ont trouvé ou non la bonne réponse.
On se propose de résoudre le problème de manière progressive.
Question 1
Écrire le programme ``exo1q1.c`` qui prend en paramètre le nombre *n* de joueurs. Ce programme lancera en parallèle *n* processus fils qui représentent les *n* joueurs. Vous sauvegarderez le numéro du joueur, afin de pouvoir l’afficher par la suite. Chaque joueur communiquera chacune de ses 10 propositions au serveur, via un tube de communication, en utilisant la structure suivante pour l’envoi dans le tube :
struct reponse { int numj; // numero du joueur (entre 1 et n) int chiffre; //chiffre propose (entier aleatoire entre 0 et 9) int place; // indice ou le chiffre doit etre place (entier aleatoire entre 0 et 4) };
Dans cette question, le traitement réalisé par chacun des fils est l’affichage à l’écran de sa proposition puis l’envoi dans le tube de cette proposition (remplissage de la structure ``reponse``, puis écriture de cette structure dans le tube) ceci 10 fois de suite, et enfin terminaison du fils. Le processus père(serveur), après avoir créé ses *n* fils, lit les propositions dans le tube (et les affiche à l’écran) jusqu’à ce qu’il n’y ait plus rien à lire dans le tube. A chaque fois que le serveur reçoit une proposition d’un joueur, il vérifie si cette proposition est bonne. Si elle l’est, il affiche le message “bonne réponse trouvee: chiffre xx trouve”, puis mémorise ce résultat dans le tableau réponse de 5 chiffres (préalablement initialisé à -1). Finalement, quand il n’y a plus rien à lire, le serveur compare le tableau réponse à la combinaison à découvrir, et affiche la combinaison trouvée par les joueurs avec un message (“trouve” ou “non trouve” avec la combinaison qu’il fallait trouver). Enfin il attend la fin de ses n fils avant de se terminer.
Exemple d’exécution :
>$ ./exo1q1 6 PID du pere : 495 on cree fils no 1 on cree fils no 2 on cree fils no 3 on cree fils no 4 Joueur no 1 - essai no 1 : j'envoie 9 pour l'indice 3 on cree fils no 5 on cree fils no 6 SERVEUR *** Reception : numJ=1 chiffre=9 place=3 Joueur no 2 - essai no 1 : j'envoie 3 pour l'indice 0 Joueur no 3 - essai no 1 : j'envoie 7 pour l'indice 2 Joueur no 4 - essai no 1 : j'envoie 0 pour l'indice 2 SERVEUR *** Reception : numJ=2 chiffre=3 place=0 SERVEUR *** Reception : numJ=3 chiffre=7 place=2 SERVEUR *** Reception : numJ=4 chiffre=0 place=2 Joueur no 6 - essai no 1 : j'envoie 5 pour l'indice 3 Joueur no 5 - essai no 1 : j'envoie 4 pour l'indice 4 SERVEUR *** Reception : numJ=6 chiffre=5 place=3 SERVEUR *** Reception : numJ=5 chiffre=4 place=4 ...etc ... Joueur no 5 - essai no 7 : j'envoie 8 pour l'indice 3 SERVEUR *** Reception : numJ=5 chiffre=8 place=3 ======== SERVEUR : bon chiffre trouve 8 ..etc.. Joueur no 5 - essai no 10 : j'envoie 7 pour l'indice 4 SERVEUR *** Reception : numJ=5 chiffre=7 place=4 Joueur 1 : j'ai fini mes 10 essais donc je m'arrete Joueur 6 : j'ai fini mes 10 essais donc je m'arrete Joueur 2 : j'ai fini mes 10 essais donc je m'arrete Joueur 3 : j'ai fini mes 10 essais donc je m'arrete Joueur 5 : j'ai fini mes 10 essais donc je m'arrete Joueur 4 : j'ai fini mes 10 essais donc je m'arrete SERVEUR : j'attends la fin de mes fils PAS trouve combinaison trouvee :-1 -1 -1 8 1 // -1 represente un chiffre non trouve La combinaison a trouver etait : 6 5 2 8 1
Question 2
Recopiez votre programme précédent exo1q1.c dans un autre fichier de nom ``exo1q2.c``
On veut maintenant que les *n* joueurs s’arrêtent si la combinaison a été trouvée avant qu’ils aient épuisé leurs 10 essais. Rajouter les instructions nécessaires dans le processus père et dans le processus fils pour répondre à cette question. Il vous est conseillé de prévoir un tableau permettant au processus père de stocker tous les PID de ses processus fils.
NB:
on vous conseille de faire les tests avec un grand nombre de joueurs (15 par exemple). Dans l’exemple d’exécution qui suit, on a enlevé les messages de création de fils pour un gain de place.
Exemple d’exécution :
>$ ./exo1q2 15 // ici 15 correspond au nombre de joueurs PID du pere : 470 Joueur no 1 - essai no 1 : j'envoie 3 pour l'indice 0 Joueur no 2 - essai no 1 : j'envoie 4 pour l'indice 2 Joueur no 3 - essai no 1 : j'envoie 7 pour l'indice 3 Joueur no 5 - essai no 1 : j'envoie 2 pour l'indice 0 Joueur no 4 - essai no 1 : j'envoie 1 pour l'indice 0 Joueur no 7 - essai no 1 : j'envoie 9 pour l'indice 3 SERVEUR *** Reception : numJ=1 chiffre=3 place=0 SERVEUR *** Reception : numJ=2 chiffre=4 place=2 SERVEUR *** Reception : numJ=3 chiffre=7 place=3 SERVEUR *** Reception : numJ=5 chiffre=2 place=0 SERVEUR *** Reception : numJ=4 chiffre=1 place=0 SERVEUR *** Reception : numJ=7 chiffre=9 place=3 ..etc ... Joueur no 15 - essai no 3 : j'envoie 8 pour l'indice 3 SERVEUR *** Reception : numJ=15 chiffre=8 place=3 ======== SERVEUR : bon chiffre trouve 8 Joueur no 1 - essai no 4 : j'envoie 3 pour l'indice 4 Joueur no 2 - essai no 4 : j'envoie 5 pour l'indice 3 SERVEUR *** Reception : numJ=1 chiffre=3 place=4 SERVEUR *** Reception : numJ=2 chiffre=5 place=3 SERVEUR *** Reception : numJ=3 chiffre=5 place=1 Joueur no 3 - essai no 4 : j'envoie 5 pour l'indice 1 ======== SERVEUR : bon chiffre trouve 5 Joueur 2 : j'ai recu un signal du serveur donc je m'arrete Joueur 1 : j'ai recu un signal du serveur donc je m'arrete SERVEUR : j'attends la fin de mes fils Joueur 6 : j'ai recu un signal du serveur donc je m'arrete Joueur 9 : j'ai recu un signal du serveur donc je m'arrete Joueur 10 : j'ai recu un signal du serveur donc je m'arrete Joueur 3 : j'ai recu un signal du serveur donc je m'arrete Joueur 13 : j'ai recu un signal du serveur donc je m'arrete Joueur 4 : j'ai recu un signal du serveur donc je m'arrete Joueur 5 : j'ai recu un signal du serveur donc je m'arrete Joueur 15 : j'ai recu un signal du serveur donc je m'arrete Joueur 7 : j'ai recu un signal du serveur donc je m'arrete Joueur 8 : j'ai recu un signal du serveur donc je m'arrete Joueur 11 : j'ai recu un signal du serveur donc je m'arrete Joueur 12 : j'ai recu un signal du serveur donc je m'arrete Joueur 14 : j'ai recu un signal du serveur donc je m'arrete Bonne reponse trouvee combinaison trouvee :6 5 2 8 1
Exercice 2 - Chacun son tour
On vous fournit le programme ``exo2.c`` qui initialise une donnée en mémoire partagée puis la modifie (en l’incrémentant de 2) 10 fois de suite en affichant sa valeur avant et après modification. On vous demande d’écrire ``exo2b.c`` (sur le même modèle que ``exo2.c``) qui va accéder à la même donnée en mémoire partagée, et la modifie également 10 fois de suite en la décrémentant de 2 et en affichant sa valeur avant et après modification. Compilez et exécutez les 2 programmes, en lançant d’abord ``exo2`` juste avant ``exo2b`` dans 2 terminaux séparés. Vous constatez que les modifications sur la donnée ne se font pas à tour de rôle comme on le souhaite.
Modifiez maintenant les 2 programmes en rajoutant les objets IPC nécessaires pour réaliser une synchronisation de la modification de la donnée (les 2 programmes modifient à tour de rôle la donnée, c’est à dire en alternance).
Exercice 3 - Austin Power
Dans cet exercice nous allons simuler le déplacement dans un couloir de plusieurs auto-tamponneuses modélisées par un processus et prendre en compte les collisions sur l’état des véhicules qui ne pourront accepter qu’une certaine quantité *PTV* de dégâts. Pour cela un processus père créera les éléments nécessaires et les *K* processus fils représentants les voitures. Le couloir sera modélisé par deux zones de mémoire partagée de *N* cases: la première, de nom ``grille``, contiendra pour l’élément ``i`` le pid du processus occupant la case ``i``, ``0`` sinon; la deuxième, de nom ``libre``, indiquera si la case ``i`` contient une voiture ou non (0 = case pas libre = contient une voiture, 1 = case libre = pas de voiture dedans).
L’accès à ces deux zones devra être protégé par un seul sémaphore d’exclusion mutuelle.
On se propose de résoudre le problème de manière progressive.
Question 1
Ecrire le programme ``exo3q1.c`` qui va créer et initialiser les différents objets IPC nécessaires et écrire les procédures ``P`` et ``V`` et ``terminaison``. ``terminaison`` sera appelé en cas de fin (naturelle ou interruption manuelle par SIGINT ou SIGTERM) du processus père afin d’effacer les objets IPC créés.
Question 2
Recopier le programme précédent dans un autre fichier de nom ``exo3q2.c`` et modifier le afin que le processus père soit sensible aux signaux de fin des fils et que dans ce cas:
- Affiche Pere - fin du fils 1 (3184), c’est-à-dire le numéro du fils qui s’est terminé ainsi que son pid (voir man 2 wait et la fonction WEXITSTATUS);
- S’il ne reste plus qu’un processus fils, le père enverra un signal SIGUSR2 pour lui dire qu’il est le dernier.
- S’il ne reste aucun fils, le père se termine proprement
Question 3
Recopier le programme précédent dans un autre fichier de nom ``exo3q3.c`` et modifier celui-ci afin de créer *K* processus fils possédant ``PTV`` points de vie et que ceux-ci suivent le comportement suivant:
- Le processus tire au hasard une case du couloir et s’y place si celle-ci est libre, sinon il retire une case au hasard jusqu’à trouver une case libre. Le processus modifie donc en conséquence les deux zones de mémoire partagée;
- Le processus affiche par exemple: Fils 1 (3184) - position: 2, point: 4 afin d’indiquer son numéro de fils (1), son pid (3184), sa position dans le couloir (2), et le nombre de points de vie qu’il possède (4 = le nombre de points de dégâts qu’il peut encore accepter);
- Le processus s’endort entre 1 et 5 secondes (tiré au hasard);
- Le processus se termine en effaçant dans les deux zones partagées les informations qui lui sont relatives (et en détachant la zone), et en transmettant au père son numéro de fils à la du code de retour du processus;
- Modifier le code des fils afin qu’ils soient sensibles au signal SIGUSR2 et que dans ce cas affichent Fils 1834 vainqueur puis se termine;
- Modifier le code du père afin qu’après la création des fils il fasse une boucle infini et qu’il ignore le signal SIGUSR2 (voir man signal).
Question 4
Recopier le programme précédent dans un autre fichier de nom ``exo3q4.c`` et modifier les fils de façon à ce que tant qu’il reste des points de vie au fils il fasse:
- Choisir au hasard une direction pour se déplacer d’une case en plus ou en moins;
- Si la case est libre, le fils s’y déplace;
- Si la case est occupée, dans ce cas le fils ne bouge pas et
- Affiche: Fils 1 (3184) - Case occupee = collision avec 3186
- Envoie un signal SIGUSR1 au processus avec lequel il entre en collision
- Décrémente ses points de vie de 1
- S’endort entre 1 et 5 secondes (tiré au hasard)
- Modifier également de façon à ce que les processus fils soient
sensibles au signal SIGUSR1 et quand il le reçoit,
- Affiche Fils 3186 - collision!
- . Décrémente de 1 ses points de vie.
Exemple d’exécution du programme avec N=3, K=2 et PVT=2
Fils 0 (4764) - position: 2, point: 2
Fils 1 (4765) - position: 1, point: 2
Fils 1 (4765) - déplacement de 1 vers 2, point: 2
Fils 1 (4765) - Case occupee = collision avec 4764
Fils 4764 - collision !
Fils 0 (4764) - déplacement de 2 vers 1, point: 1
Fils 0 (4764) - Case occupee = collision avec 4765
Fils 4765 - collision !
Pere - fin du fils 1 (4765)
Fils 4764 vainqueur
Pere - fin du dernier fils (4764)