Une petite introduction au monde merveilleux de la programmation parallèle.

Cette semaine, est arrivé un petit incident amusant : il y avait un bug dans l'énoncé que nous avions posé aux élèves — l'exemple donné dans la première question du premier exercice fonctionnait sur les machines des enseignants, mais parfois pas sur les machines des élèves. Je m'en étais aperçu la veille, trop tard pour qu'on puisse faire un rectificatif ambitieux, mais cependant nous avions un bricolage pour régler la situation.

Le problème était simple. Nous avions un programme qui, successivement :

  1. ouvrait une fenêtre et l'affichait sur l'écran,
  2. traçait deux traits dedans.

Or, le programme, parfois, n'affichait pas les traits. Diantre ! En fait, l'ouverture de la fenêtre n'est pas forcément instantanée, et suivant divers facteurs (type de machine ? version de l'environnement de développement Java ? environnement graphique ? sens du vent ?) les tracés pouvaient être effectués avant que la fenêtre ne soit visible — et dans ce cas, rien n'est tracé.

Le bricolage retenu a été de rajouter une temporisation entre les deux étapes ci-dessus, de la façon la plus simple à expliquer aux élèves : une boucle qui ne fait rien mais un grand nombre de fois, style for(int i=0; i<100000000; i++).

Là, normalement, les informaticiens qui me lisent devraient avoir une certaine envie de nous lyncher, ou du moins de nous faire renvoyer comme incompétents, à part peut-être ceux qui regrettent la programmation bas niveau sur les microprocesseurs de leur enfance. Comment ! Dans un établissement aussi strict, bien tenu, avec d'aussi belles pelouses, a-t-on pu en arriver là ? Plaisanterie mise à part, j'admets que le programme donné n'était pas conçu comme il aurait dû l'être, mais il avait l'avantage d'être assez facile à lire pour les élèves. D'un point de vue didactique, il vaut sans doute mieux, à un niveau débutant, un programme lisible mais qui viole les conventions d'appel d'une bibliothèque compliquée. qu'un programme complexe et incompréhensible pour les élèves, mais qui fait les choses suivant les règles. Bref, j'admets les critiques de ceux qui voient le problème.

Pour les autres, je vais expliquer, parce qu'en fait notre bête programme d'exemple illustre des problèmes graves en programmation. Si je résume, nous avions proposé un programme dont le résultat de l'exécution dépendait de ce que l'un ou l'autre de deux processus (d'une part, le tracé, d'autre part, l'ouverture de la fenêtre) s'exécutait avant l'autre, cet ordre d'exécution n'étant pas connu et dépendant de divers facteurs. On appelle cela une race condition, et c'est un grand classique de la programmation concurrente (c'est-à-dire lorsque plusieurs processus s'exécutent en parallèle, rien à voir avec le libre marché cher à M. Madelin).

Un exemple classique en matière de race condition est l'exécution en parallèle de deux programmes copies identiques de :

  1. Lire la variable a (une variable, pour faire simple, c'est juste une sorte de case nommée dans laquelle on peut mettre des nombres).
  2. Ajouter un au nombre ainsi obtenu.
  3. Mettre le résultat dans la variable a.

Supposons que a vaut initialement zéro. Sans faire d'hypothès supplémentaires, on ne peut savoir si le résultat que l'on obtiendra au final sera 1 ou 2. En effet, on peut avoir des exécutions où chaque copie s'exécute successivement, auquel cas on obtient 2 au final ; mais on peut avoir aussi les deux exécutions pile en même temps (ou très légèrement décalées) : les deux lisent a (qui vaut 0), ajoutent 1, rangent le résultat, et au final on obtient 1.

La technique d'ajout d'une temporisation est boiteuse. En effet, le bon fonctionnement reposera toujours sur une hypothèse pas toujours fondée que cette temporisation sera suffisante. Certes, elle pourra fonctionner la plupart du temps... et lorsque la machine sera chargée, elle sera insuffisante.

Qui plus est, la technique proposée, l'ajout d'une boucle qui ne fait rien, est mauvaise. Premier problème, la temporisation effectivement obtenue va dépendre de la vitesse de la machine (ainsi que d'autres éléments). C'est le problème bien connu des vieux logiciels, notamment des jeux, qui vont trop vite voire ne fonctionnent plus du tout sur des systèmes trop récents et trop rapides. Deuxième problème, on fait travailler le microprocesseur pour rien, ce qui fait qu'il utilise du courant, chauffe le local, et pompe les batteries (sur un portable) en pure perte (sans parler du fait que sur certaines machines, un processeur trop chaud fait démarrer un ventilateur bruyant). Bref, mauvaise idée, en général. Dans les systèmes modernes, il y a des fonctions qui permettent d'attendre un délai précis.

Dans le cas de notre programme du début, la vraie technique est d'attendre la communication d'un évènement, d'un ordre « maintenant, tracez dans la fenêtre », selon les mécanismes usuels en matière d'interfaces graphiques. Par ailleurs, cette technique règle un autre problème de notre programme : si la fenêtre se retrouve cachée, puis de nouveau au premier plan, son contenu n'est pas redessiné, alors qu'il suffirait normalement de redessiner systématiquement à chaque évènement le demandant.

Dans le cas des programmes qui ajoutent 1 à la même variable, la technique normale est le verrou d'exclusion mutuelle (souvent dit mutex). La suite d'instructions (lecture de a, ajout de 1, écriture dans a) ne doit pas être interrompue par une autre manipulation de a (on dit que c'est une « section critique »). On rajoute avant l'opération de lecture une acquisition du verrou, et après l'écriture un relâchement du verrou. Le langage Java a d'ailleurs une construction directement dans sa syntaxe pour verrouiller une variable, faire une suite d'actions, et la déverrouiller.

(Petit aparté : en Java, il y a eu une certaine volonté d'intégrer dans le langage même, par opposition aux bibliothèques, un certain nombre de constructions bien utiles et qui simplifient l'expression du programmeur : concaténation de chaînes avec auto-conversion des autres types, exclusion mutuelle, et maintenant itérateurs.)

Le problème des verrous est qu'on peut vite se retrouver dans une situation ubuesque du style : A veut accéder à une ressource verrouillée par B, qui attend que C libère une ressource, mais C est lui même en train d'attendre A. Chacun attend le suivant dans un cercle fermé. On parle alors d'interblocage ou de deadlock. Les conséquences peuvent être graves.

Aussi arrive-t-il que l'on préfère courir le risque de la race condition que celui du deadlock : souvent, une race condition provoquera une corruption bénigne des données ; ou bien, la race condition ne pourra se produire que dans des conditions assez rares (c'est souvent le cas de celles détectées lorsqu'un système est déjà en service : sinon, on les auraient détectées aux essais. Par exemple, après qu'une panne liée à une race condition avait été détectée dans la sonde spatiale Deep Space one, il a été décidé de ne pas modifier le logiciel : la probabilité d'une seconde panne semblait faible, et il semblait plus risqué de mettre en œuvre un logiciel modifié non testé. (Nayak et al., 1999)

Un de mes distingués collègues fait un analyseur de programmes pour y rechercher les race condition. Une de ses conclusions était que ce n'est pas d'une grande utilité si l'on n'a pas également un outil de recherche de deadlocks.

Un autre écho amusant : Coverity fait des analyseurs de programmes (C et C++). Je leur ai demandé s'ils géraient les problèmes de concurrence, de programmes parallèles. Ils m'ont dit que non. Sachant que toute leur approche est pragmatique — ils développent des analyses qui intéressent leurs clients — j'en conclus que peu de gens programment des systèmes parallèles compliqués en C ou C++. Et en fait, effectivement, il doit s'agir essentiellement des systèmes d'exploitation. Le cas doit être différent pour Java, où la facilité d'utilisation de threads et l'utilisation de bibliothèques basées sur l'utilisation de threads multiples font que les programmes concurrents en mémoire partagée sont plus courants.