 Bonjour, bienvenue dans ce concours numéro 5 sur la synchronisation des processus.
 Donc jusqu'à présent on considérait un ensemble de processus
 qui pouvaient s'exécuter sur une même machine.
 Maintenant on va complexifier un petit peu les choses en supposant que les
 processus
 qui sont en compétition peuvent partager un certain nombre de ressources.
 Ce qui est assez classique, on calcule parallèlement. Lorsque vous voulez paralyser
 un traitement sur une matrice, cette matrice peut être manipulée
 par plusieurs processus en même temps.
 De même, si vous pouvez, plusieurs processus peuvent modifier le même fichier.
 C'est quelque chose d'assez classique dans les systèmes.
 A partir du moment où vous partagez plusieurs ressources, il faut faire un peu attention.
 Donc notamment l'accès concurrent
 à une même ressource, par exemple un même fichier, si vous êtes plusieurs
 à modifier un même fichier,
 cela peut introduire des incohérences, par exemple un fichier
 dont les données sont fausses.
 Donc c'est très important, à partir du moment où vous avez
 un partage,
 de synchroniser les processus pour assurer
 la cohérence
 de la ressource partagée.
 C'est le but de ce cours, c'est d'étudier les mécanismes de synchronisation
 entre processus partageant une même ressource.
 Pour illustrer ce problème, voici un petit exemple.
 Un exemple très simple, imaginons que j'ai deux processus
 P1 et P2 qui partagent une même ressource,
 un simple entier.
 Par exemple, on peut imaginer que c'est un compte bancaire
 dans lequel deux clients peuvent faire des manipulations sur le même compte bancaire.
 Donc chaque processus fait la même opération,
 qui est indiqué ici.
 Il copie la variable V qui est partagée
 dans une variable locale A, pour le processus P1.
 Il y a un petit traitement local qui est fait sur cette variable locale.
 Donc A est incrémenté, puis réinjecté dans la valeur.
 P2 fait exactement la même chose.
 Il copie la variable
 partagée dans une variable locale B,
 incrémente B, et réinjecte la nouvelle valeur dans la ressource.
 Donc on s'attend ici à la fin de l'exécution de ces deux programmes,
 quel que soit l'ordonnancement,
 on s'attend que la variable V soit incrémentée deux fois.
 Or, le résultat peut être très différent en fonction
 de l'ordonnanceur, en fonction du moment où arrive la fin de quantum.
 Je vous rappelle qu'on est en temps partagé, c'est-à-dire qu'à tout moment,
 il peut y avoir une fin de quantum et P1 peut donner la main à P2.
 Et ça, de façon totalement transparente au programme.
 Lorsque vos programmes s'exécutent, ils n'ont pas conscience d'être interrompus par d'autres programmes.
 C'est complètement masqué par le système d'exploitation.
 Imaginons un petit scénario plutôt favorable.
 Où initialement j'ai ma variable qui vaut 10.
 Ici, P1 est d'abord élu.
 Il exécute les instructions 1, 2 et 3.
 Sur les expanses, ça veut dire que A va être égale à 10, la valeur de V.
 A vaut ensuite 11 et enfin, la valeur 11 est injectée dans V.
 Donc j'ai V qui vaut 11.
 Ensuite, fin de quantum.
 P2 est élu.
 P2 exécute ses instructions.
 Il copie la variable V dans une variable autre qu'elle, B.
 Incrémente B, donc B vaut 12.
 Et injecte sa nouvelle valeur.
 Donc ici, on voit bien qu'on a le résultat attendu.
 V vaut bien 2.
 Donc ça, ça peut marcher pendant très longtemps.
 Mais je peux avoir d'autres scénarios où la valeur finale va changer.
 Imaginons cette fois-ci que P1 commence à s'exécuter.
 Il a le temps uniquement d'exécuter sa première instruction.
 Donc il a uniquement le temps de copier la variable V dans sa variable locale A.
 A ce moment-là, une fin de quantum arrive.
 Et pas de chance, P2 est élu.
 Pas de chance parce que P2 va manipuler la même variable V.
 Donc P2 s'exécute.
 Il copie la variable V qui n'a pas été encore mise à jour dans sa variable locale B.
 Donc à ce moment-là, V qui vaut toujours 10, qui n'a pas changé.
 Donc B est positionné à 10.
 Il est incrémenté.
 Et le contenu de B est copié dans la variable V.
 Donc V vaut 11 à ce moment-là.
 A ce moment-là, fin de quantum.
 P1 continue sa démonstration.
 Il n'a pas conscience d'avoir été interrompu par P2.
 Donc il continue son traitement.
 Il incrémente sa variable A, donc A vaut 11.
 Puis il réinjecte cette valeur dans la variable V.
 Donc on voit bien que si on fait ce petit scénario-là,
 alors que chacun se sont exécutés une fois,
 or la variable V n'est incrémentée qu'une seule fois,
 alors qu'elle aurait dû être incrémentée deux fois.
 Donc là on introduit une incohérence dans le système.
 Ce qui peut être gênant.
 Par exemple, si c'est un compte bancaire qui a été crédité,
 qu'une seule fois au lieu d'être crédité deux fois.
 Donc le but des systèmes d'éclodation
 et des protocoles de synchronisation qu'on va voir aujourd'hui,
 c'est d'éviter ce genre de mésaventure.
 Donc on va avoir d'abord quelques petites définitions.
 Alors ce qu'on appelle une ressource critique dans la suite,
 ce sont les variables partagées.
 Typiquement, ma variable V, c'était une ressource critique.
 Dès qu'une variable est partagée entre plusieurs processus,
 on appelle ça une ressource critique.
 Ensuite, les petites portions de code qui manipulent une ressource critique,
 par exemple, les portions de code 1, 2, 3 pour P1,
 ou 4, 5 et 6 pour P2,
 ce qu'on appelle des sections critiques.
 Portions de code qui manipulent une ressource critique.
 Et enfin, une des propriétés qu'on veut assurer,
 pour assurer la cohérence, c'est l'indivisibilité.
 C'est-à-dire que lorsque j'exécute une section critique,
 donc on va l'appeler SC dans la suite,
 je ne peux pas avoir deux sections critiques
 qui s'exécutent en parallèle sur la même ressource critique.
 Donc du coup, pour pouvoir assurer ce genre de propriétés,
 on va avoir besoin d'opérations de synchronisation,
 ce qui sont des opérations qui influent sur l'ordre d'avancement des processus.
 C'est-à-dire qu'elles vont bloquer pendant un certain temps,
 P2 va être bloqué tant que P1 n'a pas fini sa section critique,
 ou vice-versa.
 Lorsque P2 exécute une section critique, je veux que P1 soit bloquée.
 C'est ça qu'on va appeler la synchronisation.
 Donc on va zoomer dans un premier temps sur un problème tout simple
 qui s'appelle l'exclusion mutuelle,
 qui est le mécanisme qui assure le contrôle d'accès à une section critique.
 C'est-à-dire que je vais exécuter une exclusion mutuelle
 à chaque fois que je vais manipuler une ressource critique.
 C'est un cas particulier de la synchronisation.
 Dans le cours suivant, on verra d'autres problèmes de synchronisation un peu plus compliqués.
 Et donc le but du jeu de l'exclusion mutuelle,
 c'est qu'on veut que P1, excuse P2,
 exclue P2 pendant son exécution de section critique.
 Et on veut que P2 exclue P1 pendant l'exécution de sa section critique.
 Donc on veut assurer l'exclusivité d'un seul processus à tout moment.
 Je peux avoir un seul processus en section critique sur la même variable V.
 Encore quelques petites définitions avant de voir ça plus en détail.
 On va avoir différentes types de solutions.
 Une des solutions qu'on va avoir va être basée sur des attentes actives.
 C'est-à-dire qu'on va tester en permanence l'état d'une ressource
 pour savoir si on a le droit de l'utiliser.
 On va tester en permanence l'état de V pour voir si V est disponible.
 C'est ce qu'on appelle une attente active.
 Ce sont des solutions qui vont marcher,
 mais qui vont être très gourmandes en termes d'exécution de mémoire.
 C'est-à-dire qu'on teste en permanence,
 est-ce que je peux y aller ?
 Ça va prendre du temps au processeur.
 Un autre point auquel il faudra être attentif,
 c'est ce qu'on appelle l'interblocage ou deadlock en anglais.
 C'est-à-dire que très rapidement lorsque vous synchronisez deux processus,
 il faut éviter que les processus se bloquent pour toujours.
 C'est-à-dire que P1 bloque P2 et P2 bloque P1.
 À ce moment-là, chacun s'attend mutuellement et le système est complètement gelé.
 C'est ce qu'on appelle un verrou mortel, interblocage ou deadlock.
 On reviendra dessus.
 Et enfin, ce qu'on appelle la famine.
 Même si le système ne se bloque pas indéfiniment,
 il est possible qu'un des processus n'ait jamais accès à la ressource qu'il demande.
 Un des processus, P3, veut modifier également V,
 mais on ne lui donne jamais la main.
 À ce moment-là, on dit que P3 est sujet à la famine.
 Revenons sur notre petit problème d'exécution mutuelle.
 Je vous rappelle que nous avons nos deux processus, P1 et P2,
 et chacun veut manipuler ma ressource critique, V.
 Ces portions de code-là, c'est ce qu'on appelle une section critique.
 À tout moment, je peux avoir des fins de quantum qui arrivent entre deux instructions.
 Ce qu'on va faire, c'est supposer que P1 et P2, avant de manipuler cette portion de code critique,
 appellent une fonction "EntréeSectionCritique".
 Ils manipulent la ressource critique
 et lorsqu'ils ont fini leur section critique,
 ils appellent la fonction "SortieSectionCritique".
 Le but du jeu, c'est de voir ce qu'on met dans ces deux fonctions.
 On veut assurer deux propriétés.
 La première, qu'on appelle la sûreté.
 Il faut vraiment assurer que je peux avoir au plus un seul processus en section critique.
 Mais également la vivacité.
 À un moment où un processus demande à entrer en section critique,
 il appelle "EntréeSectionCritique",
 et au bout d'un moment, il doit accéder à la section critique.
 Donc il faut que l'algorithme soit vivace.
 On peut assurer la sûreté trivialement en faisant en sorte que tout le monde se bloque.
 Si tout le monde se bloque, je ne peux pas avoir deux processus en même temps en section critique.
 La vivacité assure que si je demande, au bout d'un moment, j'obtiens ma section critique.
 Il faudra bien être vigilant lorsqu'on fait des algorithmes qui gèrent l'action mutuelle,
 et que les deux propriétés soient satisfaites.
 Une première solution, qui va être très simple,
 qui va résoudre en partie notre problème,
 c'est d'utiliser le masquage d'interruption.
 Je vous ai dit que le problème,
 lorsqu'on exécute ce petit code de section critique, ces trois instructions,
 le problème survenait lorsqu'il y avait une fin de quantum,
 qui survenait entre deux instructions ici.
 Pendant l'exécution de P1, je ne voulais pas être interrompu par P2.
 Donc une solution simple pour éviter toute interruption par un autre processus,
 c'est de masquer l'interruption horloge.
 Si vous masquez l'interruption horloge, je vous rappelle,
 il ne peut plus y avoir de fin de quantum.
 La fin de quantum, ce qu'on a vu dans les cours précédents,
 est gérée par l'interruption horloge.
 C'est le système qui positionne une valeur dans le registre horloge,
 et lorsque cette valeur passe à zéro, à ce moment-là, on peut basculer de P1 à P2.
 Donc si l'interruption horloge est masquée, vous ne pourrez plus commuter.
 L'idée, ce serait, lorsque je rentre en section critique,
 je masque l'interruption horloge ici.
 Même si une fin de quantum arrive, elle ne sera pas tout de suite traitée.
 Elle ne sera traitée que lorsque je démasque l'interruption horloge en fin de section critique.
 Donc je masque, démasque, masque, démasque à chaque section critique.
 Donc ça, ça marcherait.
 Donc P1 ne pourrait pas être interrompu par P2.
 De même, si P2 fait la même chose, P2 ne pourra pas être interrompu par P1.
 Par contre, c'est extrêmement dangereux de faire ça.
 Parce que si vous masquez l'interruption horloge, il ne peut plus y avoir de fin de quantum.
 Tout ce qui est gestion des alarmes, commutations, sont reportés.
 Et rien n'empêche le processus de faire autre chose.
 Par exemple ici, si un processus masque l'interruption horloge et se met à boucler indéfiniment,
 votre système est complètement gelé. Il ne peut plus rien faire. Il ne peut plus reprendre la main.
 Donc c'est pour ça qu'il y a un risque très fort de manipuler le processeur.
 Donc il n'existe pas d'appel système pour dire "je masque l'interruption horloge"
 parce que le système ne fait pas confiance dans les programmes.
 Donc il ne veut pas donner un appel système qui vous donne le droit de masquer.
 Seul le système en interne a le droit de masquer pour ses propres sections critiques.
 Mais il n'a pas le droit, il n'offre pas un appel système pour masquer les interruptions.
 Parce qu'il ne sait pas du tout, ça c'est un code utilisateur.
 Il ne veut surtout pas donner la main à un code utilisateur en ayant masqué l'interruption horloge.
 Donc c'est pour ça qu'on ne fait pas ça.
 De même, un autre problème, parce que ça, ça marche bien en effet.
 Imaginons que les processus se comportent bien, qu'ils ne se mettent pas à boucler, qu'ils soient raisonnables.
 Mais ce mécanisme-là est trop fort.
 Parce que si P1 masque l'interruption horloge pour faire ses sections critiques,
 en effet il va bien exclure P2 qui manipule la même variable,
 mais il exclut également tous les autres processus.
 Il va exclure un processus P3, P4, P5 qui ne manipule pas du tout la variable V.
 Donc là ici c'est trop fort comme mécanisme.
 Non seulement il y a le risque de monopoliser le processeur,
 mais en même temps on exclut tous les autres processus du système.
 Ce que je veux, c'est juste que P1 exclue P2 et que P2 exclue P1.
 Mais un processus qui ne manipule pas du tout la ressource critique V,
 il n'y a aucune raison que je lui arrête et interdise de m'interrompre.
 Il a le droit de m'interrompre à partir du moment où il ne manipule pas la même variable,
 la même ressource critique que moi.
 Donc ce n'est pas une solution envisageable.
 Le fait que le risque de monopoliser le processeur est un handicap trop fort.
 Donc on oublie cette solution, mais qui marcherait dans l'absolu.
 Donc les autres solutions qu'on va avoir, ce sont des solutions à base de variables de synchronisation.
 Donc là ici on va céder des variables qui vont être elles-mêmes partagées,
 qui vont nous aider à savoir est-ce que j'ai le droit d'y aller ou pas.
 Est-ce que j'ai le droit de rentrer en sélection critique ou pas.
 Donc c'est ce qu'on appelle des variables de synchronisation.
 Ce sont des variables partagées, utilisées, pour savoir si une ressource est disponible ou non.
 Donc une première solution qu'on va avoir,
 on va voir qu'elle a un petit souci, ça va être un premier élément de réflexion.
 Imaginons la solution la plus simple possible.
 J'ai une simple variable partagée boolean, lock,
 qui m'indique si la ressource est verrouillée ou pas.
 Donc lock=true, ça veut dire que la ressource est verrouillée,
 je n'ai pas le droit d'y aller, je n'ai pas le droit d'accéder à ma variable v.
 Si lock=false, ça veut dire que ma ressource est disponible.
 À ce moment-là j'ai le droit d'accéder à ma ressource critique.
 Donc on peut imaginer que ma variable partagée, au départ elle est initialisée à fausse,
 c'est-à-dire que ma ressource est disponible,
 et chaque processus qui veut accéder à la ressource critique va tester l'état de cette variable.
 Donc là, en tant que lock=true, je boucle.
 C'est pour ça que je mets un point virgule ici, c'est-à-dire que là on reste dans le while.
 Donc tant que lock=true, c'est-à-dire que ma ressource est verrouillée,
 donc je ne mets pas l'instruction suivante.
 Dès que lock=false, c'est-à-dire que ma ressource est disponible,
 à ce moment-là le while devient passant,
 donc je vais à l'instruction suivante, je verrouille la ressource,
 comme ça si jamais je suis interrompu par un autre processus,
 il va rester dans son while, et j'exécute ma sélection critique.
 Si ma ressource est disponible, je la verrouille,
 j'exécute ma sélection critique, je manipule la ressource critique,
 et lorsque j'ai fini, je déverrouille la ressource critique.
 Donc lorsque je sors de cette sélection critique, on disait que maintenant lock=false.
 Donc si quelqu'un était bloqué dans le while, il va se débloquer.
 Donc ça, ça semble une solution sensée.
 Donc si on l'exécute, une exécution favorable,
 imaginons qu'il y a deux processus, P1 et P2,
 lock=false initialement, donc P1 est élu.
 Je vous rappelle, à un instant donné, je n'ai pas deux processus élus,
 c'est l'un ou l'autre.
 C'est à chaque fin de quantum que je peux basculer de l'un à l'autre.
 Donc le process est en train de s'exécuter, P1.
 Il fait le test du while.
 Donc là, quand vous faites le while,
 tant que lock=true, je reste dans le while.
 Là, ce n'est pas le cas, le test est faux, parce que lock=false.
 Donc la condition de while est fausse, donc le while devient passant.
 Je positionne lock à true, et je commence ma sélection critique.
 Donc P1 commence sa sélection critique.
 Pendant la sélection critique, je suis interrompu par un process P2,
 qui veut également manipuler la même variable.
 Donc il fait le test, while.
 Donc tant que lock=true, c'est le cas.
 Vous voyez bien que lock=true.
 À ce moment-là, le while est bloquant,
 c'est-à-dire que je reste "bloquant", je suis toujours à l'état "prêt".
 Mais je ne sors pas du while, parce que ma condition est vraie.
 lock=true, lock=true, donc là je reste à l'état de mon while.
 Entre temps, au bout d'un moment, P1 va reprendre la main,
 va être élu de nouveau, il va continuer sa sélection critique,
 et lorsqu'il a terminé, il repositionne lock=false.
 À ce moment-là, la prochaine fois que P2 est élu,
 il va retenter son while, et cette fois-ci, la condition du while devient fausse,
 donc lock=false, donc il sort du while, le while devient passant,
 il positionne lock=true pour bloquer les autres processus qui arrivent,
 commence sa sélection critique, et ainsi de suite.
 Une fois qu'il a terminé, il débloque les autres processus en mettant lock=false.
 Donc ça, ça a l'air de marcher, mais en fait ça ne marche pas.
 Il suffit de trouver un exemple où ça ne marche pas pour prouver que cette solution est inexacte.
 Imaginons un autre cas, moins favorable.
 Donc là, pareil, on commence le même scénario, P1 est élu,
 au départ, ma ressource est disponible, donc lock=false,
 je rentre dans mon while, ce que j'appelle "entrée sélection critique",
 lock étant égal à false, la condition du while n'est pas satisfaite,
 donc le while n'est passant.
 Donc la prochaine instruction à exécuter, c'est lock=true.
 Mais entre le while et le lock, j'ai une fin de quantum qui arrive juste à ce moment-là.
 C'est-à-dire que je vois que ma ressource est disponible, mais je n'ai pas le temps de la verrouiller.
 Je ne contrôle pas du tout à quel instant peut avoir lieu la fin de quantum.
 Donc à ce moment-là, je suis interrompu entre le moment où je fais le test et le moment où je verrouille la ressource,
 et pas de chance, c'est un process P2 qui est élu, qui va manipuler la même ressource.
 Donc qu'est-ce qui se passe ici ? Je suis interrompu ici, entre les deux,
 vu que P1 n'a pas eu le temps de positionner lock=false,
 le while va être passant également pour P2.
 Je vous rappelle la condition, c'est que tant que lock=true, je reste dans le while.
 Là, ce n'est pas le cas, lock=false, le while est bien passant.
 Je positionne lock à true, et je commence ma sélection critique.
 À ce moment-là, la prochaine fois que P1 est élu, il a déjà passé son while, il a déjà testé.
 Donc la prochaine instruction à exécuter, c'est lock=true.
 Donc lui, il exécute lock=true et commence également sa sélection critique.
 On voit bien ici que j'ai bien deux sélections critiques qui commencent à s'exécuter en parallèle.
 Les deux procédures vont manipuler la variable V en même temps,
 et je peux avoir les problèmes qu'on a vus tout au début.
 Là, on a illustré un scénario où la solution ne marche pas, et peut introduire une incohérence.
 Ce n'est pas une solution satisfaisante, et ça ne marche pas.
 Il faut envisager une solution un peu plus compliquée.
 Le deuxième algorithme qu'on va voir, qui lui va marcher,
 qui est un algorithme classique, qui est l'algorithme de Peterson.
 C'est un algorithme.
 Là, on va voir la version de Peterson avec uniquement deux processus, pi et pj,
 en considérant que i, c'est 0, et j est 1.
 C'est généralisable à n processus. Le principe est très similaire.
 Mais là, pour faire plus simple, on considère Peterson avec uniquement deux processus.
 Ici, dans ces algorithmes, on ne va pas s'en sortir avec une seule variable.
 Une seule variable lock, on ne pourra pas assurer la sélection critique.
 Donc là, on a besoin d'un peu plus de variables partagées.
 On va avoir une variable par processus.
 Dans la version Peterson avec deux processus, je vais avoir un tableau de 2.
 Là, ce n'est pas un int, c'est un booléen.
 J'ai un tableau de booléen qui m'indique si le processus est demandeur de la sélection critique.
 Au départ, personne n'est demandeur. Il est positionné à false.
 Si false de i = true, ça veut dire que pi demande.
 A chaque fois que je vais demander, je vais positionner le flag correspondant à true.
 Pour dire que je demande la sélection critique.
 Ensuite, je vais avoir une deuxième variable tour.
 Le problème, c'est que les deux, pi et j, peuvent demander.
 Il est possible que flag de i soit égal à true et flag de j soit égal à true.
 À ce moment-là, il ne faut pas que les deux entrent en sélection critique.
 Il ne faut qu'un des deux entre en sélection critique.
 Si les deux demandent de manière concurrente à entrer en sélection critique,
 les deux ont positionné leur flag à true,
 à ce moment-là, la variable tour va m'indiquer de manière arbitraire à qui c'est le tour.
 C'est pour ça qu'on a besoin de cette variable.
 Le principe est le suivant.
 A chaque fois que je veux entrer en sélection critique, un processus pi va positionner son flag à true.
 Pour dire que je demande la sélection critique.
 Puis, il laisse une chance à l'autre processus d'y aller.
 Il dit que je laisse une chance à j d'entrer en sélection critique.
 Je vais positionner ma variable tour à j.
 Si j veut y aller, il a le droit d'y aller.
 C'est le principe.
 Si j'ai pi et pij qui tentent d'entrer en sélection critique,
 c'est la variable tour qui va discriminer le processus.
 En fonction de la valeur dans la variable tour,
 ça va m'indiquer quel processus est autorisé à entrer en sélection critique.
 L'algorithme est le suivant.
 Il reste assez simple.
 J'ai mon tableau de Boolean qui est à false au départ.
 Ma variable tour.
 Quand j'entre en sélection critique,
 je dis que c'est l'algorithme pour le processus pi.
 Pij fait la même chose, on interverse juste les i par les j.
 Lorsque le processus pi demande d'entrer en sélection critique,
 il dit qu'il est demandeur.
 Il positionne son flag à true.
 Il laisse une chance à l'autre.
 Je dis que le tour s'est agi.
 Je teste.
 Ma condition pour attendre, pour ne pas entrer en sélection critique,
 il faut que le j soit bien demandeur.
 Si j'ai un demandeur et que c'est son tour,
 tant que j'ai un demandeur et que c'est son tour,
 je reste dans le while.
 Je reste bloqué.
 C'est pour ça qu'on met un point virgule ici.
 Là, ça s'appelle une attente active.
 On attend de manière active.
 Je teste en permanence l'état de mes variables.
 Tant que l'autre est demandeur et que c'est son tour, je l'attends.
 Dès qu'une des deux conditions n'est pas satisfaite,
 c'est-à-dire soit il ne demande pas,
 soit ce n'est pas son tour,
 je rentre en sélection critique.
 Et lorsque j'ai terminé, je dis que je ne suis plus demandeur.
 Donc là, cet algorithme ressemble beaucoup au premier qu'on a vu avec l'autre.
 Mais on remarque une propriété assez intéressante ici.
 C'est pour ça que ça va marcher.
 C'est qu'entre le moment où je teste et le moment où j'accède à ma sélection critique,
 je ne mets pas à jour de variable.
 Ici, il faut rappeler avant,
 entre le moment où j'ai testé la variable lock et j'ai accédé à la sélection critique,
 il fallait que je mette à jour pour dire que ma variable est verrouillée.
 Là, je n'ai pas besoin de faire ça.
 Je teste tant que l'autre est demandeur et que c'est son tour, j'attends.
 Et dès qu'une des conditions n'est pas satisfaite, je peux y aller.
 Et c'est uniquement à la fin de ma sélection critique que je mets à jour des variables.
 Donc on va voir que ça marche.
 Pour se convaincre que ça marche,
 on va d'abord faire le premier scénario où, par exemple, un seul processus demande.
 Imaginons que pi demande seul.
 A ce moment-là, si pi demande seul, il positionne sa variable flag2i à true,
 tandis que flag2j n'a pas positionné sa variable.
 Donc flag2j, par défaut, est égale à false.
 A ce moment-là, si on regarde les conditions du while,
 on voit que la condition qui est dans le while est fausse,
 puisque flag2j n'est pas égale à true.
 Donc ça suffit.
 Même si la variable tour est positionnée à j,
 comme flag2j, comme l'autre n'est pas demandeur,
 la condition est fausse.
 Donc le while n'est pas 100,
 et pi entre bien en section critique.
 Quand un processus demande tout seul,
 il n'y a pas de souci, il va bien obtenir sa section critique.
 Maintenant, considérons le cas où les deux demandent.
 Il y a quelques cas plus compliqués.
 Donc pi et pij demandent.
 A ce moment-là, les variables tour vont être positionnées à true pour les deux,
 et c'est la variable tour qui va imposer de manière arbitraire à qui c'est le tour.
 Et comme la variable tour ne peut valoir qu'une seule valeur,
 elle ne peut pas avoir une valeur entre les deux,
 c'est pour ça que ça va marcher.
 Imaginons ici le scénario, pi est d'abord élu.
 On peut inverser facilement le scénario.
 Mais là, il faut bien fixer un scénario.
 Donc pi est d'abord élu,
 qui positionne sa variable flag2j à true.
 A ce moment-là, fin de quantum, pj est élu.
 pj est élu, lui aussi va positionner sa variable à true.
 On voit bien que les deux variables flag sont à true.
 Puis pj donne une chance à l'autre d'y aller.
 Donc il positionne la variable tour à i.
 A ce moment-là, fin de quantum, pi est de nouveau élu.
 Lui fait la même chose, il positionne la variable tour à l'autre processus, à j.
 On voit qu'ici, lorsque les deux sont demandeurs,
 les deux flags sont bien à true,
 mais la variable tour peut valoir soit i soit j.
 Donc seul le processus
 dont la variable tour est positionnée à son identifiant pourra y aller.
 Si vous regardez la condition ici,
 j est bien demandeur et c'est son tour,
 donc je vais rester à l'intérieur de walk.
 Donc pi ne va pas progresser, il reste à l'intérieur de son walk.
 Parce que flag2j est égal à true et tour est égal à j.
 Donc lui, il reste ici.
 Par contre, j, qui fait le test inverse,
 il voit que flag2j est égal à true,
 mais le tour n'est pas égal à i.
 Il voit bien que ce n'est pas son tour.
 A ce moment-là, lui, cette condition est fausse
 grâce à la deuxième condition, la variable tour.
 Donc il quitte le while,
 le while devient "passant"
 et il commence la section critique.
 Si pendant la section critique, je suis interrompu par pi,
 pas de souci, ma condition reste vraie ici.
 Donc je reste coincé dans mon while.
 Parce que c'est bien le tour de j et tour égal à j.
 Donc rien ne peut se passer ici.
 Le pi reste bien bloqué à l'intérieur de son while.
 Et c'est uniquement lorsque pi, lorsque pij a fini sa section critique,
 qu'il positionne sa variable j à false.
 A ce moment-là, la prochaine fois que pi est élu,
 la condition du while va devenir fausse
 parce que l'autre processus n'est pas demandeur.
 Donc le while devient passant, les deux conditions deviennent fausses.
 Je peux quitter le while, je commence ma section critique
 et lorsque j'ai fini, je dis que je ne suis plus demandeur.
 Donc cet algorithme marche très bien.
 Par contre, l'algorithme de Peterson est assez coûteux
 parce qu'il faut un tableau avec une entrée par processus.
 Donc si j'ai n processus, vous avez n booléens à gérer.
 La version n processus, je ne l'ai pas indiqué ici,
 mais c'est vraiment le même principe.
 Vous la retrouverez sur le net, dans Wikipédia,
 il y a la version de Peterson n processus, c'est un grand classique.
 On peut faire un peu plus simple.
 Donc là, on va se réinspirer du premier algorithme qui ne marchait pas.
 Il ne marchait pas, c'est l'algorithme avec le lock,
 dans lequel je testais si ma variable est verrouillée,
 si elle n'est pas verrouillée, je la verrouille et j'accède à ma section critique.
 Ça semblait marcher, mais ça ne marchait pas
 parce qu'entre le moment où je testais ma variable et le moment où je l'ai positionnée,
 je pouvais être interrompu par une fin de quantum.
 Or, il s'avère que dans pas mal de processeurs,
 on peut l'implémenter de façon assez simple,
 il y a une instruction particulière machine qui s'appelle le test anset.
 Le test anset permet justement de pouvoir positionner une variable
 et de retourner sur une ancienne valeur.
 Donc, en une seule opération machine, non interruptible par interruption,
 je peux en même temps positionner et tester l'état d'une variable.
 Souvent, c'est un test anset booléen,
 c'est-à-dire que ça permet de positionner à un trou une variable
 et de retourner sur l'ancienne valeur.
 Donc, à quoi ça ressemble un test anset ?
 Là, c'est juste l'algorithme du test anset, ce n'est pas codé en C.
 C'est une instruction qui est souvent implémentée en hardware.
 Donc, que ferait un algorithme de test anset ?
 Ça ressemblerait à ça, au niveau hardware.
 Vous passez en paramètres une variable.
 Donc, ça positionne cette variable à trou.
 Avant de la positionner à trou, vous mémorisez cette variable
 dans une variable temporaire, une variable locale,
 et vous retournez cette valeur.
 Donc, ça vous positionne à trou et ça vous retourne bien sur l'ancienne valeur.
 Et donc, si je réécris, ce qui est important, c'est que c'est une seule instruction machine.
 C'est-à-dire qu'ici, on ne peut pas être interrompu par une fin de comptant
 entre chacune de ces instructions, sinon ça ne marcherait pas.
 Donc, ça, c'est un bloc indivisible.
 Imaginons que j'ai cette instruction-là, ce qu'on peut faire dans pas mal de processeurs.
 Une instruction qui implémente cet algorithme.
 Donc là, si je réécris, je reprends mon premier petit exemple qui ne marchait pas.
 J'ai ma variable false qui m'indique si ma ressource est verrouillée ou pas.
 Donc, au départ, initialement, ma variable locale était à false.
 Donc là, ici, je réécris ma fonction.
 Donc là, je vais...
 y.loc = true.
 Là, je vais faire y.test_inset.loc = true.
 Ça veut dire quoi ? Ça veut dire que ça me retourne l'ancienne valeur de loc,
 mais en même temps, ça me la positionne à true.
 Donc, tant que c'est à true, je reste bloqué ici.
 Lorsque je sors de... si c'est jamais à false,
 je peux directement exécuter ma section critique.
 C'est pas gênant, parce que ça m'a en même temps positionné loc à true.
 On va le dérouler juste après.
 Donc, on voit bien qu'entre le moment où je teste ma variable
 et le moment où j'accède à ma section critique, je n'ai pas de mise à jour de variable ici.
 Ça, c'est fait de manière atomique.
 Et enfin, lorsque j'ai fini ma section critique, là, comme avant, je dis que je déverrouille ma variable.
 Donc, on va essayer de se convaincre que ça, maintenant, ça marche.
 Donc, si on fait l'exécution maintenant,
 là, on reprend le même petit scénario qu'on avait au début et qui ne marchait pas.
 Donc, j'ai mes deux processus P1 et P2,
 qui tentent tous les deux d'accéder en même temps à la section critique.
 On suppose qu'un des deux est élu.
 Donc, initialement, loc est égal à false.
 Donc, P1 est élu.
 Il appelle test17 à l'intérieur de son while.
 Que fait le test17 ?
 Il récupère la valeur du loc,
 il la positionne dans une variable B,
 puis le test17 positionne la variable loc à true
 et ça me retourne la valeur B.
 Donc, ça me retourne false.
 Donc, le premier des deux, qui appelle test17,
 ça positionne loc à true et ça retourne false.
 Et, entre-temps, pendant ce bloc-là,
 si j'ai une interruption, elle sera traitée ensuite.
 Les interruptions ne peuvent pas arriver à l'intérieur de ce bloc indivisible.
 Donc, on voit bien que pour le process P1,
 ça va lui retourner false,
 puisque loc va aller false.
 Donc, pour P1, on retourne bien false.
 Par contre, on a bien positionné loc à true.
 Donc, à ce moment-là, même si je suis interrompu juste après le test17,
 qu'est-ce qu'il va se passer ?
 Bah, P2 va être élu.
 P2, il appelle également test17,
 mais cette fois-ci, comme loc a été positionné à true,
 bah, B va être égal à true.
 Je repositionne de nouveau loc à true, mais ça, c'est pas gênant.
 Mais surtout, ça va me retourner true.
 Donc, je reste bloqué, je reste coincé à l'intérieur de mon while,
 puisque ça me retourne true, true, true, true,
 même si ça le repositionne à chaque fois.
 À chaque fois, la valeur qui me retourne, c'est true.
 Donc là, je vous rappelle ici,
 tant que c'est à true, je reste à l'intérieur du while.
 C'est exactement ce qui se passe ici.
 Ça n'arrête pas de me retourner true.
 Donc, P2 reste bloqué à l'intérieur de son while.
 Donc, du coup, seul P1 peut exécuter la sélection critique.
 Même si P2 est élu,
 P2 va être élu en première sélection critique,
 mais c'est pas gênant, puisqu'il restera coincé à l'intérieur de son while.
 Et c'est uniquement lorsque P2 aura fini sa sélection critique,
 manipulé la variable V,
 et qu'il aura mis un loc à false,
 donc, cette fois-ci, la prochaine fois que P1 est élu,
 à ce moment-là, ça va lui retourner false,
 et il pourra exécuter sa sélection critique.
 Donc là, on a une solution qui marche,
 qui est plus simple qu'un Peterson.
 Par contre, ça demande une aide du matériel.
 Il faut pouvoir l'implémenter,
 soit de façon matérielle, soit de manière software.
 Il y a une implémentation software qui existe de ça.
 Il faut qu'on puisse bénéficier d'une instruction de type test-tenset sur votre processeur.
 Donc là, on a vu les deux principaux algorithmes
 qui permettent de gérer l'exclusion mutuelle,
 à base de variables de synchronisation,
 le Peterson et l'algorithme qui est à base de loc et de test-tenset.
 Mais je voudrais vous sensibiliser sur un problème.
 Quels que soient ces deux algorithmes qui marchent,
 qui assurent bien l'exclusion mutuelle, il n'y a pas de souci,
 ces algorithmes ne sont pas très performants.
 Donc imaginons, faisons le diagramme de grande de ce qui se passe.
 Imaginons que j'ai la solution toute simple avec le test-tenset qu'on vient de voir.
 Lorsque P1 s'exécute, donc il exécute entrer sélection critique,
 donc lui, il ne reste pas dans son wild,
 il commence à exécuter sa sélection critique, il manipule.
 À ce moment-là, pendant sa sélection critique, il peut être interrompu.
 Il peut être interrompu par P2,
 P2 qui tente également d'accéder à la même variée partagée.
 Donc P2 appelle entrer sélection critique.
 Donc à P2, le système va lui allouer un quantum de temps,
 et donc P2, lorsqu'il appelle entrer sélection critique,
 on a vu, il reste bloqué dans son wild.
 Mais il n'est pas vraiment bloqué, il reste à l'état près,
 c'est-à-dire qu'il reste à l'intérieur de son wild.
 Donc il va prendre tout son quantum de temps CPU à l'intérieur de son wild.
 Donc on voit que P1 est extrêmement ralenti par P2.
 Ça reste cohérent, puisque P2 n'exécute pas sa sélection critique,
 mais il va prendre tout son quantum de temps pour faire ce qu'on appelle la tentative,
 pour dire est-ce que c'est bon, est-ce que c'est bon, est-ce que c'est bon, est-ce que c'est bon.
 Il prend tout son quantum pour faire ça.
 Alors que c'est un peu bête, on sait que ce n'est pas bon,
 parce que lui, il ne peut rien se passer tant qu'il est élu.
 Donc là ici, P2 reste bloqué, il fait son tentative.
 Ensuite P1 va être élu au bout d'un moment, il fait sa sélection critique.
 Et à chaque fois qu'il est interrompu par P2, pareil,
 P2 lui prend tout un quantum de temps rien que pour faire son test, son tentative.
 Donc on voit là, son temps d'exécution est divisé par deux à cause des tentatives.
 Et il est divisé par deux parce que je n'ai que deux processus qui demandent la sélection critique,
 mais si vous avez dix processus qui demandent la sélection critique,
 les dix processus vont faire leur while,
 et je vais avoir mon temps d'exécution critique qui va être divisé par dix.
 Donc c'est très inefficace.
 Sur un multicœur, là, ce serait peut-être plus efficace,
 parce qu'on peut imaginer que P2 serait sur un autre cœur.
 Mais bon, sur un monocœur, c'est une solution qui est très inefficace,
 parce qu'à chaque fois les attentatives me ralentissent les processus qui sont bien en sélection critique.
 Donc au bout d'un certain temps, P1 va finir sa sélection critique,
 et à ce moment-là, à la prochaine fin de quantum,
 là, le while, je vais sortir mon while, et enfin P2 va pouvoir commencer sa sélection critique.
 On voit bien que pendant le temps de sélection critique,
 même si la cohérence est assurée, je suis extrêmement ralenti.
 Donc voilà pour cette première partie de course en synchronisation.
 Dans le prochain cours, on verra comment éviter ces phases de blocage.
 On étudiera les solutions à base de sémaphores.
 Je vous remercie.
