Portail informatique Année 2018 – 2019

CSC 3102 – Introduction aux systèmes d’exploitation

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 et .

  • comprendre et manipuler des fichiers partagés;
  • comprendre les notions de sections critiques et de mutex;
  • savoir utiliser les commandes et .

Soit le script ecriture.sh suivant : Exécutez deux fois de suite la commande ./ecriture.sh a b c et expliquez le contenu des fichiers. Les trois fichiers ont le même contenu, par exemple :
  • Premier 2233
  • Suivant 2234
Le premier processus qui s'exécute crée les fichiers. Le deuxième processus ajoute une ligne au contenu des fichiers.
Soit le script lancement_ecriture.sh suivant qui permet d'exécuter en concurrence deux processus ecriture.sh.

Exécutez ce script jusqu'à ce que le contenu d'un des fichiers f1, f2 ou f3 ne contienne qu'une seule ligne au lieu de deux, c'est-à-dire, jusqu'à ce qu'une des écritures soit perdue. Expliquez le résultat obtenu.

Voici un résultat non satisfaisant : Contenu de f1 ------------------- premier 2277 Contenu de f2 ------------------- premier 2276 suivant 2277 Contenu de f3 ------------------- premier 2276 suivant 2277 Le premier processus teste que le fichier f1 n'existe pas, il fait ensuite une commutation. Le deuxième processus teste alors lui aussi que le fichier f1 n'existe pas et fait une commutation. Le premier processus reprend la main, crée le fichier f1 et fait une commutation. Le deuxième processus reprend la main et poursuit son exécution en créant un nouveau fichier f1. Le texte écrit par le premier processus est perdu. Ce résultat n'est pas satisfaisant car une des écritures est perdue.
Identifiez la section critique dans . La section critique englobe l'ensemble des accès à "elem", c'est à dire qu'elle englobe avec le if [ ! -e "elem" ]; then et se termine après le fi correspondant. Modifiez le script de façon à assurer une exclusion mutuelle sur la section critique. Il suffit de verrouiller la section critique. Normalement, les étudiants devraient utiliser un unique verrou comme dans la réponse. Reprenez le code de la question précédente, mais en faisant attention à ne pas bloquer les processus s'ils n'écrivent pas dans le même fichier.

Il est tout à fait possible que la solution que vous avez proposée à la question précédente assure déjà cette propriété. Dans ce cas, vous avez terminé l'exercice, félicitations !

Le nom du verrou doit dépendre du nom du fichier dans lequel les processus écrivent de façon à garantir que deux processus qui travaillent dans deux fichiers différents utilisent deux verrous différents.

Soit le script suivant qui prend au moins deux paramètres. Le premier paramètre correspond à un fichier d'index (liste des fichiers créés), les autres sont les noms des fichiers à créer. Le script crée les fichiers dont le nom est passé en paramètre (s'ils n'existent pas) et met à jour le contenu du fichier d'index. Un message d'erreur est affiché si le nombre de paramètres n'est pas correct ou si le premier paramètre correspond à un nom de répertoire.

Quel sont les contenus du fichier index et du répertoire après cette exécution : $ ls ajout.sh $ ./ajout.sh index fic1 fic2 fic1 fic3 Lors de l'examen de la deuxième occurrence de fic1, le fichier étant identifié comme existant, rien n'est fait.

Le fichier index contient donc trois lignes :

$ cat index fic1 fic2 fic3 Le répertoire quant à lui contient : $ ls ajout.sh fic1 fic2 fic3 index
Lancez l'exécution suivante : $ rm -f index fic1 fic2 fic3; ./ajout.sh index fic1 & ./ajout.sh index fic1

Observez les contenus du répertoire et du fichier index après cette exécution et expliquez pourquoi fic1 apparaît deux fois dans index.

Il est possible, avec une très faible probabilité, que fic1 n'apparaisse pas deux fois dans index. Si par hasard c'était votre cas, relancez simplement l'exécution (et pensez à jouer au loto aujourd'hui car la probabilité est vraiment extrêmement faible). L'exécution est aléatoire, mais avec le sleep 1, la probabilité d'avoir une exécution différente de celle décrite dans la suite est extrêmement faible. Le répertoire contient : $ ls ajout.sh fic1 index Mais le fichier index contient deux lignes au lieu d'une : $ cat index fic1 fic1 Le premier processus arrive jusqu'au test de l'existence du fichier fic1, ce dernier n'existe pas, il rentre donc dans les instructions du then et commute sur le sleep avant de créer le fichier fic1. Le deuxième processus prend la main et fait la même chose. Les deux processus observent donc que le fichier fic1 n'existe pas et ils vont donc par la suite tous les deux modifier le contenu du fichier index et y ajouter chacun la ligne fic1.
Modifiez le script pour que le problème identifié à la question précédente ne se pose plus, c'est-à-dire pour que le fichier index contienne exactement la liste des fichiers créés, chacun apparaissant en un unique exemplaire (supprimer l'instruction sleep n'est bien sûr pas une solution, ceci ne résout pas le problème de façon générale !). Il faut protéger les accès à la section critique qui est composée des instructions du if. On considère maintenant le script ajout.sh de l'exercice précédent et le script suivant qui prend au moins deux paramètres. Le premier paramètre correspond au fichier d'index et les autres à une liste de fichiers à supprimer. Nous faisons l'hypothèse que le fichier d'index est à jour (tout fichier existant y est référencé). Ce script supprime, s'ils existent, les fichiers dont le nom est passé en paramètre et met à jour le contenu du fichier d'index. Un message d'erreur est affiché si le nombre de paramètres n'est pas correct ou si le fichier d'index n'existe pas.

Le "^$i$" suivant le grep -v signifie une ligne commençant par $i (^ initial) et se terminant par $i ($ final). $i étant l'un des arguments (i.e., un nom de fichier), le motif identifie une ligne contenant uniquement le nom du fichier. Conjointement avec le -v, la commande grep renvoie toute les lignes ne contenant pas le fichier passé en paramètre. Soit le script suivant : Quel sont les contenus du fichier index et du répertoire après l'exécution des commandes suivantes ? $ ls ajout.sh enleve.sh essai1.sh $ ./essai1.sh Le fichier index n'existe pas initialement (voir résultat du ls) et les deux scripts sont exécutés séquentiellement. Après l'exécution, le fichier index existe mais il est vide : fic1 a été ajouté puis retiré.
Pour cette question on ne considère aucune contrainte sur la localisation des commutations de processus, elles peuvent avoir lieu après n'importe quelle instruction.

Soit le script suivant :

Est-il possible d'avoir l'exécution suivante ? Vous pouvez la faire apparaître en décommentant le sleep 2 de ajout.sh. Expliquez la suite d'événements menant à cette exécution.

$ ls ajout.sh enleve.sh essai2.sh index $ cat index $ ./essai2.sh $ ls ajout.sh enleve.sh essai2.sh index $ cat index fic1 Cette exécution est tout à fait possible. Elle peut par exemple arriver lorsque le processus ajout.sh prend la main le premier, teste que le fichier fic1 n'existe pas et le crée. Il passe ensuite la main (commutation de processus) avant d'avoir mis à jour le fichier index.

Le processus enleve.sh prend alors la main et s'exécute jusqu'au bout sans être interrompu. Il teste donc que le fichier fic1 existe, il le supprime (la commande rm -f n'affiche aucun message si le fichier à supprimer n'existe pas), met à jour le fichier index (comme il ne contenait pas de ligne fic1, le contenu du fichier n'est pas modifié) et se termine.

Le processus ajout.sh reprend ensuite la main et poursuit son exécution en ajoutant fic1 au contenu du fichier index.
Modifiez le script pour que le problème identifié à la question précédente ne se pose plus. Il faut protéger les accès à la section critique qui est composée des instructions du if, en utilisant bien sûr le même verrou que dans . On garantit ainsi la cohérence entre le contenu du fichier index et la liste des fichiers qui existent. La solution de la question précédente permet-elle d'assurer que l'exécution du script donnera toujous le même résultat ? Expliquez votre réponse. Non, la solution n'impose pas un ordre sur l'exécution des scripts et , elle garantit juste la cohérence entre le contenu du fichier index et la liste des fichiers qui existent. On peut donc avoir soit :
  • le fichier fic1 existe et il apparaît dans le fichier index (ce qui correspond à une exécution de avant ),
  • le fichier fic1 n'existe pas et il n'apparaît pas dans le fichier index (ce qui correspond à une exécution de avant ).
Soit une application nécessitant l'identification d'utilisateurs et le stockage d'informations les concernant. Les informations sur les utilisateurs sont stockées dans trois fichiers différents :
  • le fichier login.txt contient l'identifiant de connexion de chaque utilisateur connu du système à raison d'un identifiant par ligne,
  • le fichier pass.txt contient le mot de passe de chaque utilisateur, à raison d'un mot de passe par ligne,
  • le fichier nom.txt contient le nom de chaque utilisateur, à raison d'un nom par ligne.

Les informations sont associées en fonction de leur position dans les fichiers (les informations se trouvant à la ième/sup> ligne de chaque fichier concernent le même utilisateur).

Le script suivant est une première version du script de création d'un nouvel utilisateur : Nous considérons que la base de fichiers est incorrecte si :
  • deux utilisateurs ont pu être créés avec le même identifiant (deux lignes identiques dans le fichier login.txt),
  • les informations concernant un utililisateur ne sont pas à la même ligne dans les trois fichiers.

Le premier cas peut se produire lors de l'exécution de : ./creation_utilisateur.sh l p u & ./creation_utilisateur.sh l p u et le second lors de l'exécution de : ./creation_utilisateur.sh l1 p1 u1 & ./creation_utilisateur.sh l2 p2 u2

Donnez, pour chaque cas, un ordonnancement pouvant conduire à une base de fichiers incorrecte. Pour le premier cas, on suppose donc qu'on exécute : ./creation_utilisateur.sh l p u & ./creation_utilisateur.sh l p u On peut alors avoir une commutation du premier script juste avant la ligne echo "$1" >> login.txt. Dans ce cas, le second script va aussi observer que le fichier login.txt n'existe pas (ou que le fichier existe mais que l'utilisateur n'est pas enregistré dans le fichier) et va donc, lui aussi, sauter la partie then.

Pour le second cas, on suppose donc qu'on exécute : ./creation_utilisateur.sh l1 p1 u1 & ./creation_utilisateur.sh l2 p2 u2

On peut alors avoir une commutation du premier script juste après la ligne echo "$1" >> login.txt. À ce moment, login.txt contient u1 et les autres fichiers sont vides. Le second script s'exécute entièrement et ajoute le triplet (l2, p2, u2) aux fichiers. Ensuite, le premier script reprend la main et ajoute p1 puis u1. Au résultat, les fichiers contiendront :
login.txt pass.txt nom.txt
l1 p2 u2
l2 p1 u1
Identifiez la section critique dans le script . La section critique commence dès le premier accès à un des fichiers (test sur login.txt) et se termine après la dernière mise à jour puisqu'un un nouvel utilisateur n'est entièrement créé que lorsque les trois fichiers ont été mis à jour. Modifiez le script en utilisant un unique verrou pour assurer que la section critique s'exécute en exclusion mutuelle. Comme une seule section critique a été identifiée, il ne faut utiliser qu'un seul verrou et protéger avec ce verrou les trois fichiers afin de rendre séquentielle leur mise à jour. Écrivez une nouvelle version du script creation_utilisateur.sh en utilisant 3 verrous différents pour permettre plus de parallélisme entre les prosessus. On veut que les processus ne se "doublent" pas tout en pouvant faire des actions en parallèle (un processus peut modifier le fichier nom.txt pendant qu'un autre modifie le fichier login.txt). De façon à éviter que deux processus se doublent, il suffit d'acquérir le verrou suivant avant de relâcher le verrou précédent. Voici le script modifié avec trois verrous. Elle a l'avantage de permettre un meilleur parallélisme puisque les processus peuvent écrire en même temps sur des fichiers différents. Le programme reste aussi correct puisque la pose du nouveau verrou avant la suppression du précédent assure que les écritures se font dans le même ordre dans tous les fichiers.
Soit le script atomicite.sh suivant : Expliquez l'ordonnancement pouvant conduire à l'exécution suivante : $ echo 3 > fic $ ./atomicite.sh & ./atomicite.sh & [1] 19371 [2] 19372 ./atomicite.sh: line 6: [: -ne: unary operator expected Pour observer ce résultat sur vos machines, vous devrez probablement exécuter plusieurs fois la ligne de commande ./atomicite.sh & ./atomicite.sh & car ce résultat est aléatoire. La redirection avec remplacement du fichier se fait en deux étapes :
  • Le contenu du fichier est supprimé. On a alors un fichier vide.
  • Le nouveau contenu est écrit dans le fichier.
Ces deux étapes ne sont pas atomiques, c'est-à-dire qu'il peut donc y avoir une commutation entre les deux. C'est ce qui se produit dans notre exécution :
  • le processus 19371 écrit son PID dans le fichier, il y a une commutation de processus entre les deux étapes de l'écriture.
  • le processus 19372, qui a repris la main après la suppression du contenu mais avant la nouvelle ériture, lit dans un fichier vide, la variable val est donc une chaîne vide.
  • le test [ $val -ne 0 ] du processus 19372 est évalué à [ -ne 0]. Il manque donc un opérateur pour pouvoir effectuer la comparaison, d'où l'erreur signalée lors de l'exécution.