CSC 3102 – Introduction aux systèmes d’exploitation

 Portail informatique

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.

  • comprendre et manipuler des fichiers partagés;
  • comprendre les notions de sections critiques et de mutex;
  • savoir utiliser les commandes P.sh et V.sh;
  • comprendre le problème d'inter-blocage.

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.
Quelques mots de présentation du concept de sémaphore

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.

Vue globale de l'application

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 :

  1. acquérir une cabine disponible ;
  2. acquérir un panier pour y déposer ses vêtements ;
  3. se changer dans la cabine et la libérer ;
  4. nager ;
  5. acquérir une cabine disponible ;
  6. sortir de son panier ses affaires et libérer le panier ;
  7. libérer la cabine.
La figure présente graphiquement l'ensemble des scripts et fichiers que vous allez manipuler.
Scripts et fichiers nécessaires à la réalisation de l'exercice.
Gestion des ressources

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.

L'utilisation de la forme ${nom_variable} n'a pas été vue en cours, mais n'est pas très difficile à comprendre. Elle permet ici de séparer le nom de la variable du texte qui suit.

Pour acquérir une ressource du type RT (avec RT égal cabine ou panier), il faut :

  1. lire le contenu du fichier du compteur du sémaphore (motif semaphore_counter_RTs) pour savoir combien de ressources sont disponibles ;
  2. 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 ;
  3. 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 :

  1. 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 :

$ echo 1 > semaphore_counter_cabines $ ./acquireresource.sh cabine $ cat semaphore_counter_cabines 0 $ ./acquireresource.sh cabine # bloque tant que vous n'avez pas invoqué ./releaseresource.sh cabine dans un autre terminal

acquireresource.a.sh
releaseresource.a.sh

Que peut-il se produire si deux processus invoquent acquireresource.sh ou releaseresource.sh en parallèle ? Donnez un scénario menant à une incohérence.
On peut avoir une perte d'écriture. Par exemple, semaphore_counter_cabines vaut initialement 3. Le premier processus acquireresource.sh s'exécute jusqu'au commentaire # met à jour le compteur... et possède donc une valeur c égale à 3. Le second processus s'exécute jusqu'au bout et écrit 2 dans le fichier. Enfin, le premier processus termine son exécution et écrit aussi 2 dans le fichier. Au résultat, deux ressources auraient du être acquises et seule une a été supprimée du fichier.

Identifiez les sections critiques dans les scripts acquireresource.sh et releaseresource.sh sans tenter de corriger le problème de synchronisation (la correction du problème est l'objet des questions suivantes).
La section critique commence à la première consultation de la ressource (le read) et se termine à sa dernière modification (le echo >).

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.
acquireresource.b.sh
releaseresource.b.sh

On vous propose d'exécuter le scénario suivant, en commençant par lancer toutes les commandes du terminal 1 avant de lancer celles du terminal 2 :

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

Commencez par vérifier que les dernières commandes de chaque terminal sont bien bloquées. Ensuite, expliquez pour quelle raison le ./releaseresource.sh lancé dans le terminal 2 est bloqué, et est donc incapable de libérer une ressource pour débloquer le ./acquireresource.sh du terminal 1.
Le problème est qu'un acquireresource.sh acquiert le verrou en début d'exécution et ne le relâche pas pendant qu'il attend une ressource. Le releaseresource.sh bloque donc lorsqu'il veut acquérir le verrou et ne peut donc pas effectuer la libération.

Modifiez le script acquireresource.sh de façon à vous assurer que le scénario décrit à la question précédente ne conduise plus à un interblocage.

Pour quitter votre programme à la question précédente, vous avez probablement du interrompre brutalement vos scripts qui n'ont donc pas pu libérer les verrous. Ces verrous sont donc toujours occupés au début de cette question, c'est pourquoi, avant d'effectuer le moindre test, nous vous conseillons de supprimer tous les verrous avec la commande rm -f *.lock et d'exécuter une commande ps pour regarder s'il ne reste pas des processus en suspens.
Il suffit de lâcher le verrou pendant l'attente.
acquireresource.c.sh

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.

un appel au script acquireresource.sh n'acquiert qu'une seule ressource. Il en va de même pour releaseresource.sh.

Dans le script acquireresource.sh, avant de mettre à jour le compteur du sémaphore, ajoutez ce qui suit :

  1. 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) ;
  2. 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) ;
  3. 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 les questions à venir, le script acquireresource.sh sera placé dans un script représentant les actions d'un usager (acquérir une cabine, etc.). Ainsi, le PPID identifiera l'usager. En conséquence, il ne faut pas s'inquiéter lorsque, à ce niveau du sujet, nous retrouvons N fois le même PPID propriétaire de plusieurs ressources dans les scénarios d'exécution.

Dans le script releaseresource.sh, avant de mettre à jour le compteur du sémaphore, ajoutez ce qui suit :

  1. 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) ;
  2. mettez à jour le fichier trouvé avec 0 pour indiquer que la ressource est de nouveau disponible ;
  3. lorsque le fichier a été trouvé et mis à jour, sortez de la boucle avec l'instruction break afin de ne rendre qu'une ressource.

dans le scénario qui suit, il faut que ce soit le même shell qui exécute les scripts acquireresource.sh et releaseresource.sh, ceci afin d'avoir le même PPID. Donc, contrairement aux premières exécutions en début d'exercice, les commandes sont à exécuter dans le même terminal, avec certaines commandes en arrière plan.

Pensez à tester votre code sur des fichiers factices que vous aurez initialisés. Par exemple selon le scénario suivant :

$ echo 2 > semaphore_counter_cabines $ echo 0 > cabine1; echo 0 > cabine2 $ echo $$ 10886 $ ./acquireresource.sh cabine $ cat cabine1 cabine2 10886 0 $ ./acquireresource.sh cabine $ cat semaphore_counter_cabines 0 $ cat cabine1 cabine2 10886 10886 # attention, le prochain en arrière plan dans le même terminal $ ./acquireresource.sh cabine & $ jobs [2]+ Stoppé ./acquireresource.sh cabine $ ./releaseresource.sh cabine $ ./releaseresource.sh cabine $ cat semaphore_counter_cabines 1 $ cat cabine1 cabine2 0 10886 $ ./releaseresource.sh cabine $ cat semaphore_counter_cabines 2 $ cat cabine1 cabine2 0 0

acquireresource.d.sh
releaseresource.d.sh

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 :

  1. 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 ;
  2. 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.

dans le scénario qui suit, il faut que ce soit le même shell qui exécute les scripts acquireresource.sh et releaseresource.sh, ceci afin d'avoir le même PPID. Donc, contrairement aux premières exécutions en début d'exercice, les commandes sont à exécuter dans le même terminal, avec certaines commandes en arrière plan.

Pensez à tester votre code sur des fichiers factices que vous aurez initialisés. Par exemple selon le scénario suivant :

$ echo 2 > semaphore_counter_cabines $ echo 0 > cabine1; echo 0 > cabine2 $ echo $$ 13049 $ ./acquireresource.sh cabine $ cat cabine1 cabine2 13049 0 $ cat semaphore_counter_cabines 1 $ cat semaphore_waiting_queue_cabines $ ./acquireresource.sh cabine $ cat semaphore_counter_cabines 0 $ cat cabine1 cabine2 13049 13049 # attention, le prochain en arrière plan dans le même terminal $ ./acquireresource.sh cabine & [2] 10657 $ jobs [2]+ Stoppé ./acquireresource.sh cabine $ cat semaphore_waiting_queue_cabines 13049 $ ./releaseresource.sh cabine $ cat semaphore_waiting_queue_cabines [2]+ Fini ./acquireresource.sh cabine $ cat semaphore_counter_cabines 0 $ cat cabine1 cabine2 13049 13049 $ ./releaseresource.sh cabine $ cat semaphore_counter_cabines 1 $ cat cabine1 cabine2 0 13049 $ cat semaphore_waiting_queue_cabines $ ./releaseresource.sh cabine $ cat semaphore_counter_cabines 2 $ cat cabine1 cabine2 0 0 $ cat semaphore_waiting_queue_cabines

acquireresource.e.sh

Bravo, vous venez de mettre en œuvre votre première primitive de synchronisation : un sémaphore avec son compteur et sa file d'attente ! Nous pouvons maintenant faire des expériences d'interblocage.
Gestion de la piscine

En utilisant vos scripts acquireresource.sh et releaseresource.sh, mettez en œuvre l'algorithme de l'usager de la piscine dans un script usager.sh. Symbolisez le fait de se baigner en affichant PID se baigne, où PID est le PID du processus usager.sh, et en exécutant la commande sleep 5 qui endort le processus pendant 5 secondes.

Voici pour rappel l'algorithme de l'usager proposé en début d'énoncé :

  1. acquérir une cabine disponible ;
  2. acquérir un panier pour y déposer ses vêtements ;
  3. se changer dans la cabine et la libérer ;
  4. nager ;
  5. acquérir une cabine disponible ;
  6. sortir de son panier ses affaires et libérer le panier ;
  7. libérer la cabine.
usager.a.sh

Écrivez un programme lancement.sh qui :
  • 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.

lancement.a.sh

Modifiez le script lancement.sh de façon à lancer 10 usagers au lieu de 7. Qu'observez-vous ? Donnez une explication.

cette question est la question clé de l'exercice ! Prenez le temps d'argumenter votre réponse par écrit. Et en séance, n'hésitez pas à la valider avec un encadrant.

Le nouveau code du script lancement.sh est le suivant :
lancement.b.sh

On observe que le programme bloque. Dès que le nombre d'usagers est au moins égal à la somme du nombre de cabines et du nombre de paniers, il peut en effet y avoir interblocage.

On observe que 1) les compteurs des deux sémaphores sont tous les deux à 0 et 2) tous les processus qui possèdent un panier sont en attente d'une cabine et que tous les processus en attente d'une cabine sont en attente d'un panier.
$ cat semaphore_counter_cabines 0 $ cat semaphore_waiting_queue_cabines 3270 3286 3303 3332 3262 3316 3275 $ cat cabine* 3264 3294 3280 $ cat semaphore_counter_paniers 0 $ cat semaphore_waiting_queue_paniers 3280 3264 3294 $ cat panier* 3262 3303 3332 3316 3275

L'interblocage se produit donc dès que tous les paniers sont utilisés par des usagers en train de se baigner et que nb_cabines=3 (au moins) nouveaux usagers se présentent et occupent les cabines. Dans ce cas, les usagers en cabine sont bloqués faute de paniers disponibles, et les usagers qui se baignent ne peuvent plus obtenir une cabine faute de cabines disponibles. Les usagers qui se baignent ne peuvent donc plus libérer les paniers et l'ensemble des usagers est bloqué.

Dans notre cas, l'interblocage se produit fréquemment puisque les usagers passent trois secondes à se baigner, ce qui constitue un temps très long en informatique. On a donc fréquemment l'exécution suivante :
  • 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.

Au résultat les dix processus sont donc bloqués.

Que se passe-t-il, si on inverse l'ordre de prise du panier et de la cabine, c'est-à-dire, un usager commence par acquérir un panier avant d'acquérir une cabine pour se changer, libère alors la cabine, se baigne, prend à nouveau une cabine, se change, puis libère le panier et la cabine. Modifiez le script usager.sh pour vérifier expérimentalement votre hypothèse.
Il n'y a plus d'interblocage car les usagers ne peuvent pas acquérir de cabine tant qu'ils n'ont pas de panier. Un usager qui prend une cabine possède donc toutes les ressources pour poursuivre son exécution sans blocage, il finira donc par libérer la cabine. Les usagers en train de se baigner auront donc toujours la possibilité de trouver une cabine pour pouvoir quitter la piscine et libérer les paniers pour les nouveaux arrivants.

Le nouveau code est le suivant :
usager.b.sh

Détection d'interblocage — défi

Écrivez le script detectdeadlock.sh qui détecte s'il y a un interblocage pendant une exécution.

nous pouvons écrire un tel script car la propriété d'interblocage est dite stable (non fugace), c'est-à-dire que, lorsqu'il y a un interblocage, le système reste en interblocage tant que l'on n'intervient pas pour résoudre le problème (par exemple en supprimant des processus ou en ajoutant des ressources).

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.
lancement.c.sh
detectdeadlock.sh

Bravo, vous avez détecté à la main, voire automatiquement, un interblocage dans le modèle le plus complexe, le modèle ET-OU : « il faut un panier parmi un ensemble et une cabine parmi un ensemble », autrement dit « (panier1 ∨ panier2 ∨ panier3 ∨ panier4 ∨ panier5) ∧ (cabine1 ∨ cabine2 ∨ cabine3) » !

Problème du pont (∼1h – optionnel)

Imaginez un pont routier à une seule voie. Des voitures se présentent aux deux extrémités du pont, notre but est d'écrire les contrôleurs présents à chaque extrémité du pont. Ces contrôleurs doivent assurer que deux voitures circulant dans des directions opposées ne se trouvent pas en même temps sur le pont. Nous allons bien sûr nous intéresser à une version simplifiée des contrôleurs.

Voici une proposition de scripts pour les contrôleurs. Le script EstOuest.sh représente le contrôleur qui gère les accès au pont pour une traversée d'est en ouest, le script OuestEst.sh gère les accès au pont pour une traversée d'ouest en est.

Nous vous rappelons que la boucle while [ ! -f EstOuest.fic ]; ...; done continue tant que le fichier EstOuest.fic n'existe pas puisque -f EstOuest.sh renvoie vrai si le fichier existe et ! -f EstOuest.fic inverse la proposition. Cette boucle permet donc d'attendre que le fichier EstOuest.fic soit créé.
EstOuest.sh
OuestEst.sh

Expliquez ce qui se passe lors de l'exécution du script suivant :
lancement.sh
L'exécution est la suivante :
$ ./lancement.sh Route Ouest-Est ouverte, 1 voitures sur 3 sont passées Route Est-Ouest ouverte, 1 voitures sur 3 sont passées Route Ouest-Est ouverte, 2 voitures sur 3 sont passées Route Est-Ouest ouverte, 2 voitures sur 3 sont passées Route Ouest-Est ouverte, 3 voitures sur 3 sont passées Route Est-Ouest ouverte, 3 voitures sur 3 sont passées
Le fichier OuestEst.fic est créé avant la création des contrôleurs, ce qui indique que les voitures peuvent passer d'ouest en est. Le processus exécutant EstOuest.sh ne peut pas avancer tant que le fichier EstOuest.fic n'est pas créé.

Le processus OuestEst.sh laisse passer une voiture, supprime le fichier OuestEst.fic et crée le fichier EstOuest.fic. Ce processus attend alors la création du fichier OuestEst.fic pour continuer sa progression.

Le processus EstOuest.sh peut maintenant progresser et laisser passer une voiture avant de supprimer le fichier EstOuest.fic et de créer le fichier OuestEst.fic.

L'algorithme se reproduit jusqu'à ce que toutes les voitures soient passées.

On modifie maintenant le script lancement.sh pour faire passer trois voitures d'ouest en est et quatre voitures d'est en ouest :
lancement.b.sh

Expliquez pourquoi le programme se bloque.
L'exécution, avant de bloquer, est la suivante :
$ ./lancement.b.sh Route Ouest-Est ouverte, 1 voitures sur 3 sont passées Route Est-Ouest ouverte, 1 voitures sur 4 sont passées Route Ouest-Est ouverte, 2 voitures sur 3 sont passées Route Est-Ouest ouverte, 2 voitures sur 4 sont passées Route Ouest-Est ouverte, 3 voitures sur 3 sont passées Route Est-Ouest ouverte, 3 voitures sur 4 sont passées

Le script EstOuest.sh se bloque avant de faire passer sa quatrième voiture car il indique à OuestEst.sh qu'il peut faire passer une voiture et attend ensuite que OuestEst.sh lui crée le fichier EstOuest.fic. Or OuestEst.sh est terminé puisqu'il a fait passer toutes ses voitures. Il ne peut donc plus créer le fichier.

De façon à éviter le blocage identifié à la question précédente, on vous propose d'utiliser un fichier nommé pas-fini pour indiquer qu'aucun des deux scripts EstOuest.sh et OuestEst.sh ne sont terminés. Pour mettre en œuvre cet algorithme, vous devez modifier vos scripts de la façon suivante :
  • 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.

Mettez en œuvre ce nouvel algorithme.
lancement.c.sh
EstOuest.c.sh
OuestEst.c.sh

Producteur/consommateur (∼ 1h – défi)

Écrivez un script ecrivain.sh qui prend au moins 2 paramètres. Le premier paramètre est une chaîne de caractères. Si la valeur de ce paramètre correspond à un répertoire existant, le script se termine avec un message d'erreur. Sinon, le script écrit successivement les valeurs des autres paramètres dans un fichier dont le nom correspond au premier paramètre. La suite de commandes :
$ ls ecrivain.sh lecteur.sh $ ./ecrivain.sh fic_test 3 2 6 4
a donc pour effet de créer un fichier fic_test qui contient les valeurs 3, 2, 6, 4 (une par ligne) à la fin de l'exécution. Si le fichier existait déjà, son contenu est remplacé.
ecrivain.sh

Écrivez un script lecteur.sh qui prend exactement 1 paramètre. Si ce paramètre ne correspond pas à un fichier, le script termine son exécution avec un message d'erreur. Sinon, il lit le contenu du fichier ligne par ligne. Pour chaque ligne lu, il affiche ligne lue : suivi de la valeur lue.

Pour pouvoir lire un fichier ligne à ligne, vous utiliserez la construction suivante :
(while read x; do ... done) < fichier
Pour comprendre cette construction, vous devez savoir que :
  • 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;
lecteur.sh

Nous souhaitons maintenant synchroniser le lecteur et l'écrivain de manière à ce que chaque valeur écrite dans le fichier soit ensuite lue, mais sans imposer une exécution séquentielle du lecteur et de l'écrivain. Pour mettre en évidence les problèmes qui peuvent se produire, nous ajoutons une instruction sleep 1 dans la boucle d'écriture. Exécutez plusieurs fois la commande suivante (en n'oubliant pas de détruire le fichier fic_test entre deux exécutions). Que constatez-vous ?
$ ./ecrivain.sh fic_test 1 2 3 4 5 & ./lecteur.sh fic_test &
On tombe presque systématiquement sur un des deux cas suivants :
  • 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.

Nous souhaitons maintenant que le lecteur lise (et donc affiche) chacune des valeurs écrites par l'écrivain. Pour obtenir ce résultat, nous allons forcer une alternance stricte entre les écritures et les lectures. Il faut donc garantir que :
  • 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.

Lorsqu'il a terminé ses écritures, l'écrivain écrit la chaîne fin dans le fichier. Lorsqu'il lit cette valeur, le lecteur sait donc qu'il peut se terminer.

Techniquement, pour synchroniser l'écrivain et le lecteur, on vous demande d'utiliser des fichiers nommés "$1-ecr.sync" et "$1-lec.sync", où $1 correspond donc au fichier dans lequel les données sont écrites par l'écrivain. L'écrivain doit attendre que le fichier "$1-ecr.sync" existe avant d'effectuer une écriture, et le lecteur doit attendre que le fichier "$1-lec.sync" existe avant d'effectuer une lecture. Après son écriture (resp. sa lecture), l'écrivain supprime le fichier "$1-ecr.sync" (resp. "$1-lec.sync") et crée le fichier "$1-lec.sync" (resp. "$1-ecr.sync") pour débloquer le lecteur (resp. l'écrivain). Notez que comme la première opération a effectuer est une écriture, c'est au lecteur de créer le premier fichier "$1-ecr.sync".

Modifiez les deux scripts pour qu'ils se synchronisent correctement.
ecrivain2.sh
lecteur2.sh

Telecom SudParis
Institut Polytechnique de Paris

9, rue Charles Fourier
F-91011 Evry Cedex France

19, Place Marguerite Perey
F-91120 Palaiseau Cedex France

Ⓒ 2020–2024 Télécom SudParis