Comme des lutins dans une cuisine, ou Révolution dans la programmation concurrente

L’informatique est en train de vivre une révolution très discrète. Si discrète, en fait, qu’on peine à appeler cela une révolution. Avec la multiplication des machines à multiples coeurs et multiples processeurs (et ce jusque dans les consoles de jeux vidéo), tout un pan de la technique est en train de vivre une révision majeure: la programmation concurrente ne sera plus jamais comme avant.

Qu’est-ce que la programmation concurrente ? C’est l’art de faire faire plusieurs choses complémentaires simultanément à une seule machine. Pour mieux cerner le problème, comparons avec l’art de la cuisine.

Imaginons d’abord une cuisine de particulier: une seule personne s’y active à la fois, prenant tel ustensile, réalisant telle suite d’opérations pour, mettons, préparer des pommes de terre rissolées:

  • ouvrir le frigo,
  • prendre une pomme de terre,
  • fermer le frigo,
  • prendre l’éplucheur,
  • éplucher la pomme de terre,
  • poser l’éplucheur,
  • ouvrir la poubelle,
  • jeter les épluchures,
  • fermer la poubelle,
  • prendre la planche à découper,
  • prendre un couteau,
  • couper la pomme de terre en rondelles,
  • poser le couteau,
  • prendre une poële,
  • prendre l’huile,
  • verser de l’huile dans la poële,
  • poser l’huile,
  • transférer les tranches de la planche à la poële,
  • ranger la planche à découper,
  • poser la poële sur un emplacement libre de la gazinière,
  • allumer le feu
  • attendre 5 minutes,
  • remuer,
  • attendre 5 minutes,
  • remuer,
  • attendre 5 minutes,
  • éteindre le feu,
  • prendre la poële,
  • servir.
  • Cette suite d’opérations, d’une traite, c’est un programme « mono-tâche ». Cela ne veut pas dire qu’il n’est que modérément sale, mais qu’il n’y a jamais qu’une personne qui agit dans la cuisine, et tous les ustensiles lui sont exclusivement réservés. Impossible que quelqu’un fasse autre chose dans cette cuisine en même temps, cela risquerait de fiche en l’air la recette.

    Maintenant, imaginons une cuisine de restaurant, avec huit lutins apprivoisés dedans, qui ne savent que suivre des recettes comme celle ci-dessus (imprimée sur une fiche qu’il garde avec lui) sans réfléchir. Si on leur donne à chacun cette recette, ils vont tous en même temps se jeter sur le frigo et se battre pour savoir lequel pourra l’ouvrir. Et même si l’un est plus rapide que les autres, parvenant à ouvrir le frigo et prendre une pomme de terre avant tous les autres, il ne pourra plus fermer le frigo à cause des autres lutins occupés à essayer de passer la main dans le frigo tous en même temps (et qui pourraient, en plus, essayer de prendre la même pomme de terre que lui). L’instinct finira par reprendre le dessus sous l’effet de la colère et on aura, au lieu de pommes de terre en tranches, une vaste bouille d’entrailles servie sur lit de cadavres.

    C’est ce problème d’accès aux ressources qui est au coeur de la programmation concurrente: comment se débrouiller pour faire travailler ensemble tous les lutins en même temps dans la même cuisine, sans qu’ils n’essaient par exemple de se saisir de la même pomme de terre, et sans que l’un ne s’empare de la poële de l’autre en cours de cuisson pour y mettre ses propres tranches encore crues ?

    En informatique, on peut généralement considérer que tous les problèmes ont déjà été résolus dans les années 70 par quelques grands scientifiques de ce domaine, comme Knuth et Dijkstra. Depuis on ne fait quasiment que réappliquer leurs solutions dans d’autres langages de programmation et sur du matériel plus gros et/ou plus rapide. Leur solution pour coordonner les lutins est d’utiliser des verrous: chaque lutin possède des verrous personnalisés dont il est seul à posséder la clé, qui servent à empêcher tout autre lutin d’accéder aux ressources dont il a besoin temporairement.

    Cela fonctionne plutôt bien. Si on applique cela à notre recette et nos lutins, cela nous donne ceci:

  • Lutin n°1 verrouille l’accès au frigo, les autres font la queue devant.
  • Lutin n°1 prend une pomme de terre, referme le frigo, et le déverrouille: Lutin n°2 verrouille à son tour le frigo, l’ouvre et prend une autre pomme de terre, pendant que les lutins restants poireautent.
  • Lutin n°1 verrouille l’éplucheur et s’en sert pour éplucher sa pomme de terre, pendant ce temps Lutin n°2 vient faire la queue derrière lui, pendant que, l’un après l’autre, les derniers lutins ouvrent le frigo, prennent chacun une pomme de terre, et referment le frigo, chacun à son tour.
  • Etc…

    Au final, on aura réussi à faire préparer 8 parts de pommes de terre rissolées à nos huit lutins dans une seule cuisine en moins de temps qu’il n’en aurait fallu à une seule personne exécutant huit fois la recette. Mais ça n’a pas pris huit fois moins de temps non plus… Cette façon de faire n’est pas si efficace que l’on pourrait espérer. On peut bien sûr améliorer la performance en ajoutant des frigos supplémentaires, des éplucheurs supplémentaires, etc… mais cela reviendrait à avoir huit cuisines individuelles l’une à côté de l’autre, ce qui ne répond pas du tout au problème.

    Il y a autre chose de bien plus grave: si les lutins n’ont pas tous la même recette, il peut se produire de façon aléatoire de véritables catastrophes… Exemple: Lutin n°1 prépare des pommes de terre rissolées, pendant que Lutin n°2 prépare une salade. Tous les deux ont besoin à un moment donné de la planche à découper et d’un couteau, mais Lutin n°1 prend en premier la planche puis le couteau, tandis que Lutin n°2 fait le contraire pour les besoins de sa recette. Et voilà que soudain, Lutin n°1, sa planche à découper dans une main, attend stupidement devant Lutin n°2 qui, lui, tient le couteau dans une main aussi et attend tout aussi stupidement. Nos deux lutins sont définitivement coincés. On appelle cela un « deadlock », ou interblocage.

    Impossible de laisser nos lutins sans surveillance dans ces conditions. Certains gestionnaires de cuisines ont donc dressé l’un des lutins à surveiller les autres et à repérer les interblocages: quand cela arrive à des lutins-cuistots, le lutin-surveillant va leur botter les fesses et leur ordonne de tout remettre en ordre et de recommencer la recette du début. Cela marche à peu près, ce n’est pas efficace, cela occupe un lutin qui pourrait à la place réaliser une recette de plus et ça gâche des pommes de terre presque à chaque recommencement. En plus, il est impossible de toujours distinguer les lutins en interblocage de ceux qui sont simplement en train d’attendre une ressource très demandée. Et on ne peut pas mettre plusieurs surveillants donc le nombre de lutins est limité au maximum qu’il peut gérer à la fois. Bref, on ne fait que réduire les risques sans les éliminer, avec une performance moindre et une échelle limitée.

    Généralement, la caste des gestionnaires de cuisine conseille à ses membres de toujours faire verrouiller les ressources dans le même ordre à tous les lutins pour éviter les cas d’interblocage. Mais ce n’est pas toujours possible, car cela obligerait pour certaines recettes un lutin à se balader pendant des heures avec une planche à la main simplement parce qu’il a besoin du couteau, et puis aussi de la gazinière, et ensuite d’une poële, etc. rien que parce qu’il doit toujours verrouiller la planche AVANT la gazinière ou la poële ou le couteau… ce qui empêche tous les autres lutins d’utiliser cette planche alors même que le gêneur n’en a plus besoin depuis longtemps. On appelle cela un problème de « race conditions », ou famine.

    Aussi, trois types intelligents ont conçu une autre façon de faire qui résout tous ces problèmes: Carl Hewitt, Peter Bishop, et Richard Steiger. Ils ont appelé cela le modèle d’acteurs, et ça consiste à supprimer les verrous et, à la place, confier chaque ressource à un lutin distinct. Au lieu d’aller au frigo, le verrouiller, l’ouvrir, y prendre une pomme de terre, le fermer et le déverrouiller, un lutin va à la place demander au Lutin-du-Frigo de lui donner une pomme de terre.

    Appliquons ce modèle à notre recette de départ:

  • Les lutins n°1 à 8 demandent chacun une pomme de terre au Lutin-du-Frigo. Celui-ci ouvre le frigo, prend les pommes de terre et les lance à chaque lutin puis ferme le frigo.
  • Puis les lutins n°1 à 8 envoient chacun leur pomme de terre au Lutin-de-la-Planche-à-Découper, qui envoie à son tour chaque pomme de terre, accompagnée de la planche, au Lutin-du-Couteau.
  • Etc. On constate que cela revient strictement au même que notre première tentative avec les verrous !

    Mais alors… cette solution a besoin de beaucoup plus de lutins pour faire le même travail ? Des lutins qui passeraient l’essentiel de leur temps à poireauter devant un frigo ou une bouteille d’huile ? Non, car… il suffit de faire faire ce boulot aux lutins qui réalisent les recettes, chaque fois qu’ils ont un instant libre (par exemple pendant qu’ils attendent la réponse d’un autre lutin). Suivez attentivement: le Lutin n°1, occupé à préparer une salade, va de temps en temps aller endosser la casquette de Lutin-de-l’Huile pour répondre aux demandes, puis reprendre sa recette là où il l’avait laissée sitôt que son ingrédient est prêt, tout simplement. Ainsi, les mêmes huit lutins occupés à suivre huit recettes en même temps prendront en charge l’accès aux ressources dont ils ont besoin.

    N’essayez pas de vous représenter un tel bazar si vous n’avez pas l’habitude de la programmation multi-agents, c’est trop compliqué à imaginer du premier coup. Mais le fait est que ça marche parfaitement bien. Et même, ça marche d’autant mieux qu’on divise les recettes en plus petits bouts indépendants: ainsi, au lieu de jouer le rôle du Lutin-du-Frigo quelques instants, un lutin qui fait de la salade s’interrompra pour aller jeter les épluchures d’un autre lutin occupé à faire des pommes de terre rissolées, ce qui lui fait gagner du temps. De même, un lutin qui prépare un dessert pourra s’interrompre pour aller remuer les pommes de terre quelques instants.

    Est-ce que ce modèle résout vraiment les problèmes d’interblocage et de famine ? Voyons un peu:

  • Lutin n°1 prépare des pommes de terre rissolées, pendant que Lutin n°2 prépare une salade.
  • N°1 envoie sa pomme de terre au Lutin-de-la-Planche-à-Découper, n°2 envoie sa salade au Lutin-du-Couteau.
  • Lutin-de-la-Planche-à-Découper envoie ensuite sa planche et la pomme de terre au Lutin-du-Couteau, et celui-ci envoie en même temps son couteau au Lutin-de-la-Planche-à-Découper.
  • Comme ce dernier n’en a pas l’usage pour l’instant, il lui rend en lui disant de réessayer plus tard, et Lutin-du-Couteau peut enfin découper la pomme de terre pour le compte du lutin n°1.
  • Lutin-de-la-Planche-à-Découper récupère la pomme de terre en tranches plus la planche, envoie les tranches au lutin n°1, et pendant ce temps Lutin-du-Couteau, qui s’est fait rembarrer par le Lutin-de-la-Planche-à-Découper la première fois, lui envoie une nouvelle fois la salade accompagnée du couteau.
  • Lutin-de-la-Planche-à-Découper utilise le couteau, puis le renvoie ainsi que la salade en tranches au Lutin-du-Couteau, qui rend la salade en tranches au lutin n°2.
  • Cela fonctionne donc parfaitement pour résoudre les interblocages ! Quant aux famines, elles sont impossibles puisque chaque lutin ne peut se voir confier qu’une seule ressource à la fois.

    Cette révolution dans la façon de faire faire plus d’une chose à la fois aux ordinateurs qui possèdent plusieurs processeurs est en marche, lentement mais sûrement. Depuis quelques années, l’adoption de langages suivant le modèle d’acteurs prend de l’ampleur, avec par exemple Erlang dont tout le monde se met à parler en ce moment. Une mode apparue récemment consiste à modifier une machine virtuelle, comme Java ou .Net, et d’y ajouter le support pour le modèle d’acteurs (exemple: Scala). Nulle doute que la tendance va atteindre aussi les langages compilés, à terme.


    Bonus!
    On constate, grâce aux lutins de cet article, qu’il est plus efficace de communiquer pour obtenir la coopération volontaire des propriétaires exclusifs de ressources, que de mettre en place des règlements complexes et rigides régissant quand et par qui ces ressources peuvent être utilisées et échangées. Sauras-tu faire le parallèle avec la doctrine économique et politique en vigueur dans le monde dit « civilisé » et la comparer avec celle qui est promue par ce blog ?

    Bonus 2!
    Le langage articulé est l’outil par lequel les humains se passent des messages, tels les lutins de nos exemples. Sauras-tu retracer l’évolution qui a entraîné l’apparition par émergence du langage à partir de la compétition pour l’accès aux ressources, confrontée à la recherche de meilleure efficacité dans cet accès ? (Indice: le langage articulé descend du langage gestuel, qui lui-même descend des gestes d’intimidation servant entres autres lors des parades sexuelles, qui eux-même descendent… ?)

    Advertisements

    À propos jesrad
    Semi-esclave de la République Soviétique Socialiste Populaire de France.

    2 Responses to Comme des lutins dans une cuisine, ou Révolution dans la programmation concurrente

    1. Corwin says:

      Fabuleux ! Dommage qu’il n’existe pas de Nobel de pédagogie sinon tu aurais toutes tes chances…

    2. jesrad says:

      Woa, merci 😀

      Je fais autant pour moi que pour les autres, vu que je bosse en ce moment sur un petit projet de programmation distribuée, avec plein de morceaux de programmation concurrente dedans. Comme ça, tout ça reste clair.

    Laisser un commentaire

    Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

    Logo WordPress.com

    Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

    Image Twitter

    Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

    Photo Facebook

    Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

    Photo Google+

    Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

    Connexion à %s

    %d blogueurs aiment cette page :