TP8 – Fichiers partagés (2/2)
Pour faire les exercices, vous avez besoin de connaître le langage bash. Vous pouvez vous référer à l'annexe shell. Vous pouvez aussi trouver une liste d'astuces ici. Tous les exercices sont obligatoires, sauf les exercices notés « défi » ou « optionnel » qui sont optionnels. En particulier, les exercices notés « hors présentiel » sont supposés fait d'une séance sur la suivante.
Vous aurez aussi besoin des scripts P.sh et V.sh.
Problème de la piscine (∼2h30)
- s'initier au concept de sémaphore (compteur et file d'attente),
- proposer une mise en œuvre approchée.
Dans cet exercice, nous étudions le concept de sémaphore. Comme indiqué par l'auteur du concept, Edsger Dijkstra, dans l'annexe de son article CACM de mai 1968, un sémaphore est une structure de données composée d'un compteur (un entier) et d'une file d'attente (de processus). De manière intuitive :
- lorsque la valeur du compteur est supérieure à 0, un processus peut décrémenter la valeur du compteur du sémaphore et continuer son exécution ;
- lorsque le compteur atteint la valeur 0, un processus peut décrémenter la valeur du compteur du sémaphore mais il devient bloqué et se retrouve dans la file d'attente ;
- lorsque le compteur redevient positif, un processus de la file d'attente est débloqué et retiré de la file d'attente.
Nous émulons le concept de sémaphore avec les scripts P.sh et V.sh. Notre mise en œuvre est une émulation qui s'approche du concept dans le sens où notre solution ne sera pas complète. Le concept est mis en œuvre dans le noyau UNIX et peut être utilisé par exemple en langage C : les curieux peuvent exécuter la commande apropos semaphore et à l'issue de cette séance parcourir les pages du manuel en ligne.
Nous considérons un ensemble de processus représentant les usagers d'une piscine. La création d'un processus correspond à l'arrivée de l'usager à la piscine. L'usager doit, dans cet ordre :
- acquérir une cabine disponible ;
- acquérir un panier pour y déposer ses vêtements ;
- se changer dans la cabine et la libérer ;
- nager ;
- acquérir une cabine disponible ;
- sortir de son panier ses affaires et libérer le panier ;
- libérer la cabine.
Pour suivre la disponibilité des ressources (cabines et paniers), nous disposons d'un fichier par type de ressource (semaphore_counter_cabines pour les cabines et semaphore_counter_paniers pour les paniers). Chacun des fichiers contient un entier qui correspond au nombre de ressources disponibles, c'est-à-dire au compteur du sémaphore du type de ressource. Par ailleurs, nous ajoutons un fichier par type de ressource pour mémoriser les processsus en attente d'une ressource de ce type (semaphore_waiting_queue_cabines pour les cabines et semaphore_waiting_queue_paniers pour les paniers). Ce sont les files d'attente des sémaphores. Enfin, à chaque ressource correspond un fichier (cabine1, cabine2, etc., et panier1, panier2, etc.). Ces fichiers contiennent un entier : soit 0 lorsque la ressource est disponible, soit le numéro du processus qui détient la ressource.
Gestion du compteur du sémaphore sans section critique
Pour commencer, nous ignorons la gestion des files d'attente des sémaphores ainsi que la mémorisation de quel processus possède quelles ressources.
Notez que nous forgeons le nom du fichier contenant la valeur compteur du sémaphore avec le nom du type de la ressource. Ce nom sera passé comme premier paramètre des scripts acquireresource.sh et releaseresource.sh. Ainsi, utilisez l'expression suivante pour forger le nom du fichier : "semaphore_counter_${1}s", sachant que ${1} est le nom du type de la ressource demandée.
Pour acquérir une ressource du type RT (avec RT égal cabine ou panier), il faut :
- lire le contenu du fichier du compteur du sémaphore (motif semaphore_counter_RTs) pour savoir combien de ressources sont disponibles ;
- tant que la valeur lue n'est pas au moins égale à 1, forcer une commutation avec la commande sleep 1 en espérant la libération d'une ressource pendant cette période, puis lire à nouveau le contenu du fichier ;
- mettre à jour le contenu du fichier semaphore_counter_RTs pour signaler qu'une ressource de moins est disponible.
Pour libérer une ressource du type RT, il faut :
- ajouter un à la valeur contenue dans le contenu du fichier du compteur du sémaphore (motif semaphore_counter_RTs) pour signaler qu'une ressource de plus du type RT est disponible.
Écrivez les script acquireresource.sh et releaseresource.sh qui permettent d'acquérir et de libérer une ressource. Ces scripts prennent en paramètre le type de la ressource demandée. Dans le cas de la piscine, par exemple, les paramètres seront cabine et panier. Pensez à tester votre code sur des fichiers factices que vous aurez initialisés. Par exemple avec le scénario suivant :
Gestion du compteur du sémaphore avec section critique
Comme première solution, erronée, nous vous proposons d'acquérir un verrou au début de chaque section critique et de le relâcher à la fin. De façon à assurer un maximum de parallélisme, vous veillerez à ce que deux processus accédant à des sémaphores différents n'utilisent pas le même verrou. Vous pouvez, par exemple, forger le nom du verrou avec "semaphore_counter_${1}s.lock", sachant que ${1} est le nom du type de la ressource demandée.
Pour tester vos scripts, initialisez votre compteur du sémaphore à une grande valeur, par exemple 100.Premier terminal | Second terminal |
$ echo 1 > semaphore_counter_cabines
$ ./acquireresource.sh cabine
$ cat semaphore_counter_cabines
0
$ ./acquireresource.sh cabine # doit bloquer |
$ ./releaseresource.sh cabine
# doit aussi bloquer |
Gestion des occupations des ressources
Nous ajoutons maintenant autant de fichiers qu'il y a de ressources et écrivons dans les fichiers des ressources les numéros de processus qui possèdent les ressources, avec le cas particulier 0 lorsqu'une ressource est disponible.
Dans le script acquireresource.sh, avant de mettre à jour le compteur du sémaphore, ajoutez ce qui suit :
- parcourez l'ensemble des fichiers des ressources du type RT passé en argument (motif RT* avec RT égal à cabine ou panier) pour trouver une ressource libre (un fichier avec la valeur 0) ;
- mettez à jour le fichier trouvé avec l'identité du processus demandant la ressource, c'est-à-dire avec l'identité du processus appelant le script acquireresource.sh (repéré avec la variable PPID [on utilise PPID et non $$ puisque c'est le père du processus acquireresource.sh qui doit acquérir la ressource) ;
- lorsque le fichier a été trouvé et mis à jour, sortez de la boucle avec l'instruction break afin de n'acquérir qu'une ressource.
Dans le script releaseresource.sh, avant de mettre à jour le compteur du sémaphore, ajoutez ce qui suit :
- parcourez l'ensemble des fichiers des ressources du type RT passé en argument (motif RT* avec RT égal à cabine ou panier) pour trouver la ressource prise par le processus appelant (le fichier avec la valeur de PPID) ;
- mettez à jour le fichier trouvé avec 0 pour indiquer que la ressource est de nouveau disponible ;
- lorsque le fichier a été trouvé et mis à jour, sortez de la boucle avec l'instruction break afin de ne rendre qu'une ressource.
Pensez à tester votre code sur des fichiers factices que vous aurez initialisés. Par exemple selon le scénario suivant :
Gestion des files d'attente des sémaphores
Nous terminons avec l'ajout des files d'attente. Un processus qui est bloqué en attente d'une ressource du type RT est présent dans la file d'attente du sémaphore correspondant. Nous proposons de forger le nom du fichier de la file d'attente du sémaphore avec "semaphore_waiting_queue_${1}s".
Modifiez le script acquireresource.sh comme suit :
- ajoutez le numéro du processus appelant le script (PPID) dans le fichier semaphore_waiting_queue_${1}s juste avant la boucle d'attente d'ouverture du verrou semaphore_counter_${1}s ;
- retirez le numéro du processus juste après la même boucle, c'est-à-dire lorsque le processus est garanti d'avoir une ressource. Pour le retrait, vous utilisez la même procédure que celle proposée dans le TP précédent : grep -v "^$PPID$" origine > origine.tmp puis mv origine.tmp origine.
Pensez à tester votre code sur des fichiers factices que vous aurez initialisés. Par exemple selon le scénario suivant :
Voici pour rappel l'algorithme de l'usager proposé en début d'énoncé :
- acquérir une cabine disponible ;
- acquérir un panier pour y déposer ses vêtements ;
- se changer dans la cabine et la libérer ;
- nager ;
- acquérir une cabine disponible ;
- sortir de son panier ses affaires et libérer le panier ;
- libérer la cabine.
- initialise semaphore_counter_paniers à 5 ;
- initialise semaphore_counter_cabines à 3 ;
- crée les fichiers des files d'attente (touch semaphore_waiting_queue_cabines et touch semaphore_waiting_queue_paniers) ;
- crée les paniers et les cabines (n'oubliez pas de mettre 0 comme valeur initiale dans tous ces fichiers) ;
- démarre 7 usagers en parallèle ;
- attend la fin de tous les processus usagers ; et
- affiche Processus lancement se termine à la fin de votre programme.
Lancez lancement.sh. Vérifiez que l'affichage est cohérent. Vérifiez aussi que, après la terminaison de lancement.sh, semaphore_counter_paniers contient bien 5 et semaphore_counter_cabines 3.
Afin de faciliter la conception, nous proposons le script cleanup.sh à exécuter entre deux exécutions du script lancement.sh.
- Cinq usagers vont se baigner. Ils prennent chacun une cabine, un panier et libèrent la cabine. Il y a alors trois cabines et zéro panier disponibles. Les baigneurs passent « beaucoup » de temps à se baigner, ce qui laisse le temps aux autres processus de s'exécuter.
- Trois nouveaux usagers prennent une cabine, mais comme il n'y a plus de panier disponible ils sont bloqués. Les trois occupants des cabines ne pourront les libérer que s'ils obtiennent un panier.
- Les deux derniers usagers (entrant dans la piscine) sont bloqués faute de cabine disponible.
Détection d'interblocage — défi
Écrivez le script detectdeadlock.sh qui détecte s'il y a un interblocage pendant une exécution.
Complétez le script lancement.sh de façon à vérifier régulièrement que la piscine n'est pas dans un état d'interblocage. Vous veillerez (1) à ce que le script lancement.sh se termine lorsque tous les usagers sont sortis de la piscine et (2) à ce que le script qui détecte l'interblocage arrête le script lancement.sh.
Voici quelques éléments d'aide pour la conception de cette dernière version :
- un processus est « inter-bloqué » lorsqu'il est en attente d'une ressource du type TR1 alors qu'il possède une ressource du type TR2. Un interblocage est détecté lorsque tous les processus possédant une ressource sont « inter-bloqués », c'est-à-dire, dans notre étude de cas, en attente d'une ressource de l'autre type. Autrement dit, il y a un interblocage du sytème lorsque le nombre de processus « inter-bloqués » atteint le nombre de ressources du système, soit le nombre de cabines + le nombre de paniers ;
- dans le script de détection, pensez à acquérir les verrous sur les deux compteurs afin d'utiliser un état cohérent dans l'algorithme de détection ;
- pour arrêter les processus de détection ou de lancement du scénario, pensez à utiliser les signaux : lorsque l'algorithme de détection établit l'interblocage, le script detectdeadlock.sh envoie un signal USR1 au script lancement.sh, et inversement lorsque le script lancement.sh arrive à la fin ;
- le wait à la fin du script lancement.sh doit être modifié pour attendre uniquement les processus usager.sh. Pour rappel, on peut écrire wait pid1 pid2... pour attendre plusieurs processus.
Problème du pont (∼1h – optionnel)
- avant de créer EstOuest.sh et OuestEst.sh, lancement.sh doit créer le fichier pas-fini pour indiquer qu'aucun des deux scripts n'est terminé;
- avant de faire passer une voiture, EstOuest.sh (resp. OuestEst.sh) attend soit que le fichier EstOuest.fic (resp. OuestEst.fic) soit présent, soit que le fichier pas-fini ne soit pas présent;
- EstOuest.sh et OuestEst.sh détruisent le fichier pas-fini avant de se terminer.
Producteur/consommateur (∼ 1h – défi)
- la parenthèse permettant de regrouper les instructions, la redirection du flux d'entrée à partir du fichier fichier s'adresse à l'ensemble des instructions entre parenthèse, soit l'ensemble du code while ... done (notez que techniquement, le while ... done est vu comme une unique commande par bash et que les parenthèses sont donc optionnelles);
- à chaque tour de boucle, read lit une ligne à partir du fichier (puisque le fichier sert de flux d'entrée), et avance d'autant la tête de lecture du flux, comme si on avait écrit les lignes les unes à la suite des autres dans le terminal;
- lorsque la tête de lecture n'a pas atteint la fin du fichier, la commande read renvoie vrai (i.e., la valeur 0) alors que lorsque la tête de lecture atteint la fin du fichier, la commande read renvoie faux (i.e., une valeur différente de 0), ce qui arrête la boucle;
- Le lecteur se termine avec un message d'erreur signalant que le fichier n'existe pas. Ce cas se produit lorsque le lecteur commence à lire alors que fic_test n'existe pas encore.
- Le lecteur lit la première valeur écrite avant de se terminer (conséquence de l'introduction du sleep). De manière quasi-certaine, le lecteur ne lira donc pas l'ensemble des valeurs écrites quelles que soient les commutations.
- la première opération effectuée soit une écriture;
- l'écrivain attende pour faire une nouvelle écriture que son écriture précédente ait été lue;
- le lecteur ne fasse pas de nouvelle lecture s'il n'y a pas eu de nouvelle écriture.