L'illusion du multitâche
Ce que ce chapitre apporte
- Expliquer pourquoi un processeur qui ne traite qu'une instruction à la fois donne l'apparence d'en mener plusieurs.
- Nommer l'ordonnanceur, la tranche de temps et la commutation de contexte, et dire ce que chacun décide.
- Distinguer une tâche qui calcule d'une tâche qui attend, et prévoir laquelle gagne à être menée en parallèle.
- Lire un entrelacement, et séparer ce qu'il change, la chronologie, de ce qu'il ne change pas encore, le résultat.
- Admettre qu'aucune ligne d'un programme ne dit où son fil d'exécution sera interrompu.
Les douze premiers chapitres ont suivi une machine qui exécute une instruction, puis la suivante, et rien d'autre. Ceux qui viennent partent de ce qu'elle devient quand plusieurs traitements se la disputent. Un automate de ligne d'assemblage rafraîchit un écran tactile et surveille un capteur de température. Il n'a qu'un processeur, et pourtant les deux tâches paraissent avancer ensemble. Ce chapitre dit ce qui se passe réellement : le processeur passe de l'une à l'autre, très vite, et le moment où il change n'est écrit nulle part dans le programme. Tout ce qui suit découle de ce seul fait, y compris les défauts qui ne se manifestent qu'une fois sur mille.
Une boucle unique, et la tâche qui fait attendre l'autre
L'automate doit tenir deux engagements. L'écran tactile se rafraîchit trente fois par seconde, sans quoi l'opérateur voit les affichages sauter : trente-trois millisecondes par image. Le capteur de température, lui, est interrogé sur un bus série et met deux cents millisecondes à répondre.
Écrire cela dans une seule boucle est le réflexe naturel, et il se chiffre.
Quatre images par seconde au lieu de trente. L'écran est devenu inutilisable, et pas parce que l'affichage serait lourd : il l'est devenu parce qu'il attend derrière une lecture de capteur qui ne lui doit rien. Deux tâches indépendantes ont été mises en file, et la plus lente commande la cadence de l'autre.
La solution ne consiste pas à acheter un processeur plus rapide. Elle consiste à découper le programme en deux fils d'exécution menés de front, et à laisser le système décider lequel avance à chaque instant.
Un fil d'exécution est une suite d'instructions que le système peut faire progresser indépendamment des autres. Un programme qui n'a qu'un fil exécute ses instructions dans l'ordre où elles sont écrites, du début à la fin. Un programme qui en a deux confie au système le soin de les faire avancer tous les deux, sans garantir lequel avance en premier ni jusqu'où.
Ce que « en même temps » veut dire
Sur un processeur à un seul cœur, deux fils ne s'exécutent jamais au même instant. Le processeur exécute quelques instructions du premier, l'interrompt, exécute quelques instructions du second, l'interrompt à son tour, et recommence. À l'échelle de la milliseconde, le va-et-vient est invisible et l'illusion est parfaite. À l'échelle de l'instruction, il n'y a jamais qu'une seule tâche active.
L'ordonnanceur est la partie du système d'exploitation qui décide, à chaque instant, quel fil occupe le processeur. La tranche de temps est la durée maximale pendant laquelle un fil garde le processeur avant d'être interrompu d'office : quelques millisecondes sur un système courant. La commutation de contexte est l'opération qui met en réserve l'état complet du fil interrompu, registres compris, et restaure celui du fil qui prend sa place.
La figure ci-dessous met les deux tâches côte à côte. Chaque fil a son propre compteur, et personne ne touche au compteur de l'autre : rien ne peut mal se passer, ce qui est exactement l'intérêt de commencer par là.
fil écran
registre vide- lire images
- ajouter +1
- écrire images
- afficher « image affichée »
fil capteur
registre vide- lire mesures
- ajouter +1
- écrire mesures
- afficher « température relevée »
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Les deux ordres donnent la même chose au bout du compte : une image affichée, une mesure relevée. Ce qui change, c'est quand chaque message apparaît, donc la réactivité perçue par l'opérateur. Dans le premier ordre, la température n'est relevée qu'une fois l'écran servi ; dans le second, les deux progressent ensemble.
L'entrelacement décide de la chronologie. Tant que les fils ne touchent pas aux mêmes données, il ne décide de rien d'autre. C'est la situation confortable de ce chapitre, et elle ne durera pas.
Un entrelacement, et tous les autres
Le mot qui désigne un ordre d'exécution possible mérite d'être posé, parce que tout ce qui suit en dépend.
Un entrelacement est un ordre particulier dans lequel les instructions de plusieurs fils se succèdent réellement sur le processeur. Chaque fil garde l'ordre interne de ses propres instructions ; l'entrelacement ne fait que décider, à chaque pas, lequel des fils avance.
Deux fils de trois instructions chacun ont vingt entrelacements possibles. La figure suivante les compte, une fois les deux fils terminés.
fil écran
registre vide- lire images
- ajouter +1
- écrire images
fil capteur
registre vide- lire mesures
- ajouter +1
- écrire mesures
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Vingt ordres différents, un seul résultat. Le programme est donc parfaitement prévisible malgré son indétermination : peu importe où l'ordonnanceur coupe, le compteur d'images vaut un et le compteur de mesures vaut un. Cette figure est la référence à laquelle il faudra comparer celles du troisième chapitre, où le même dénombrement donnera une tout autre réponse.
Rien dans le code ne dit où le fil s'arrête
Un fil ne possède pas le processeur : il l'occupe tant que l'ordonnanceur le lui laisse. Et l'ordonnanceur ne consulte pas le programme. Il interrompt selon l'expiration d'une tranche de temps, l'arrivée d'une interruption matérielle, la priorité d'un autre fil, ou la demande d'une entrée-sortie. Aucun de ces événements n'est visible depuis le code.
La conséquence est brutale : entre deux instructions quelconques, il peut se passer n'importe quoi. Une ligne de programme n'est pas un abri.
fil écran
registre vide- lire images
- ajouter +1
- écrire images
- lire images
- ajouter +1
- écrire images
- lire images
- ajouter +1
- écrire images
fil capteur
registre vide- lire alertes
- ajouter +1
- écrire alertes
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Les deux conduites sont légitimes, et l'ordonnanceur réel choisit entre elles sans avertir. Dans le premier ordre, l'alerte de température est signalée après trois rafraîchissements d'écran ; dans le second, immédiatement. Un programme correct doit rester correct dans les deux cas, parce qu'il n'a aucun moyen d'imposer l'un ou l'autre.
Supposer qu'une tâche courte « a le temps de finir avant que l'autre ne démarre ». Une tâche courte est interruptible exactement comme une longue, et la brièveté ne protège de rien. Elle rend seulement l'interruption moins fréquente, donc le défaut plus difficile à reproduire.
Calculer ou attendre, la distinction qui commande tout
Toutes les tâches ne se ressemblent pas, et la différence décide si le découpage en fils sert à quelque chose.
Une tâche de calcul occupe réellement le processeur du début à la fin : une simulation, un tri, un traitement d'image. Une tâche d'attente passe l'essentiel de son temps à ne rien faire, suspendue à une réponse extérieure : un capteur sur un bus série, une lecture de disque, une requête sur le réseau. Pendant cette attente, le processeur est libre.
Sur un seul cœur, entrelacer deux tâches de calcul ne fait rien gagner : le travail total est le même, il est seulement servi en tranches. Entrelacer une attente et un calcul, en revanche, récupère du temps qui était perdu.
Les trente-trois millisecondes de l'écran disparaissent : elles se logent dans les deux cents millisecondes où le capteur ne fait que patienter. Le processeur n'a pas travaillé plus vite, il a simplement cessé de rester inoccupé.
fil capteur
registre vide- afficher « requête envoyée au capteur »
- afficher « toujours en attente »
- afficher « réponse reçue : 78 °C »
fil écran
registre vide- lire images
- ajouter +1
- écrire images
- afficher « image affichée »
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Les deux messages du capteur qui disent l'attente sont le cœur de la figure : ce sont deux tranches de temps pendant lesquelles le processeur ne fait rien pour lui. Les y remplir par le travail de l'écran ne retarde personne.
Découper en fils une tâche qui attend raccourcit le temps total. Découper en fils une tâche qui calcule ne le raccourcit pas sur un seul cœur : il en faut alors plusieurs. En Python, s'en servir demande de passer par plusieurs processus plutôt que par plusieurs fils, pour une raison propre à ce langage que le chapitre suivant expose.
Trois fils, et le nombre d'ordres explose
L'automate finit rarement à deux tâches. Un journal de production s'ajoute, puis une remontée vers la supervision. Chaque fil supplémentaire multiplie le nombre d'entrelacements possibles, sans rien changer au résultat tant que les fils restent étrangers les uns aux autres.
fil écran
registre vide- lire images
- ajouter +1
- écrire images
fil capteur
registre vide- lire mesures
- ajouter +1
- écrire mesures
fil journal
registre vide- lire lignes
- ajouter +1
- écrire lignes
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Mille six cent quatre-vingts ordres, quatre-vingt-quatre fois plus qu'avec deux fils, et toujours un seul résultat. Ce chiffre est rassurant ici, et il ne le restera pas : il dit surtout qu'aucun essai, aussi patient soit-il, ne parcourt à la main l'ensemble des conduites possibles d'un programme concurrent.
Exercices type
L'automate doit désormais archiver chaque mesure sur une carte mémoire. L'écriture sur la carte prend cinq cents millisecondes, dont quatre cent quatre-vingt-dix d'attente du contrôleur. S'agit-il d'une tâche de calcul ou d'attente ? Le fait de lui donner son propre fil améliore-t-il la cadence de l'écran ?
C'est une tâche d'attente, et de façon presque caricaturale : sur cinq cents millisecondes, dix seulement occupent le processeur. Les quatre cent quatre-vingt-dix autres sont du temps que le processeur passerait à ne rien faire si l'archivage restait dans la boucle principale.
Lui donner son propre fil améliore donc bien la cadence de l'écran : pendant que le fil d'archivage attend le contrôleur de la carte, l'ordonnanceur redonne le processeur au fil d'affichage. Sans ce découpage, un archivage bloquerait quinze images d'affilée.
Le raisonnement s'inverserait si l'archivage demandait de compresser les mesures avant de les écrire. La compression est du calcul : elle occupe vraiment le processeur, et sur un cœur unique elle prendra ce temps à l'écran, dans un fil séparé comme dans la boucle principale.
Combien la figure ci-dessous compte-t-elle d'entrelacements, et combien de chronologies d'affichage différentes ? Les deux nombres sont-ils égaux ?
fil surveillance
registre vide- lire alarmes
- ajouter +1
- écrire alarmes
- afficher « seuil de température dépassé »
fil écran
registre vide- lire images
- ajouter +1
- écrire images
- afficher « écran rafraîchi »
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Deux fils de quatre instructions donnent soixante-dix entrelacements. Le compte se fait en choisissant, parmi les huit pas de l'exécution, les quatre qui reviendront au fil de surveillance : les quatre autres reviennent nécessairement au fil d'écran.
Les chronologies d'affichage, elles, ne sont que deux : soit le seuil est signalé avant le rafraîchissement, soit après. Chaque fil n'a qu'une instruction visible, la dernière, et seul leur ordre relatif est observable.
Les deux nombres ne sont donc pas égaux, et l'écart est le point de l'exercice. Soixante-dix ordres d'exécution ne produisent que deux comportements observables : presque tout ce qui distingue un ordre d'un autre ne laisse aucune trace. Un défaut logé dans l'un de ces ordres reste invisible tant qu'il ne change pas un résultat.
Un fil de ronde effectue quatre instructions, un fil de commande de vanne en effectue deux. Combien d'entrelacements ? Le message « ronde terminée » peut-il apparaître avant « vanne ouverte » ?
fil ronde
registre vide- lire tours
- ajouter +1
- écrire tours
- afficher « ronde terminée »
fil vanne
registre vide- afficher « vanne ouverte »
- afficher « vanne fermée »
Avancer un fil, puis l'autre, dans l'ordre voulu. Un fil peut aussi être avancé plusieurs fois de suite : c'est ce que fait l'ordonnanceur quand il ne l'interrompt pas.
Six pas au total, dont deux reviennent au fil de la vanne : quinze entrelacements.
Oui, « ronde terminée » peut apparaître en premier, et il suffit pour cela d'avancer quatre fois le fil de ronde avant de toucher à la vanne. Trois chronologies de messages sont possibles en tout : « ronde terminée » d'abord, puis les deux messages de la vanne ; ou « vanne ouverte », « ronde terminée », « vanne fermée » ; ou les deux messages de la vanne avant la ronde. Ce qu'aucun entrelacement ne produira jamais, c'est « vanne fermée » avant « vanne ouverte » : à l'intérieur d'un fil, l'ordre des instructions est respecté.
C'est la seule garantie que l'entrelacement laisse intacte, et elle sera constamment utile : un fil ne se réordonne pas lui-même, il se fait seulement interrompre.
Vérification
1.Sur un processeur à un seul cœur, que fait réellement le système quand deux fils « tournent en même temps » ?
2.Qu'est-ce que la tranche de temps ?
3.Qu'est-ce qui, dans le code d'un fil, indique où ce fil sera interrompu ?
4.Une tâche interroge un capteur sur un bus série et attend deux cents millisecondes sa réponse. De quel type est-elle ?
5.Sur un seul cœur, que gagne-t-on à découper deux tâches de calcul pur en deux fils ?
6.Deux fils de trois instructions chacun : combien d'entrelacements possibles ?
7.Dans la figure où chaque fil incrémente son propre compteur, que change l'entrelacement ?
La méthode
- Lister les tâches du programme, une par ligne, en disant pour chacune ce qu'elle attend et ce qu'elle calcule.
- Classer chaque tâche en tâche de calcul ou tâche d'attente, en estimant la part du temps où le processeur travaille vraiment pour elle.
- Chiffrer la boucle unique : additionner les durées, et comparer le résultat à la cadence exigée par la plus contrainte des tâches.
- Séparer en fils les tâches qui attendent, puisque leur attente est du temps processeur récupérable, et seulement celles-là tant qu'un seul cœur est disponible.
- Vérifier qu'aucune conclusion ne repose sur un ordre supposé : reprendre chaque raisonnement en imaginant le fil interrompu juste avant l'instruction en cours.
- Relever les données atteintes par plus d'un fil, sans les traiter encore : ce relevé est le point de départ du troisième chapitre.
Synthèse
- Un processeur à un seul cœur ne mène jamais deux tâches à la fois : il commute de l'une à l'autre, assez vite pour que l'illusion tienne.
- L'ordonnanceur décide qui avance, la tranche de temps borne la durée d'occupation, la commutation de contexte met en réserve l'état du fil interrompu.
- Aucune instruction d'un programme n'indique où son fil sera interrompu : entre deux instructions quelconques, un autre fil peut prendre la main.
- Une tâche d'attente libère le processeur et gagne à être menée dans un fil séparé ; une tâche de calcul l'occupe vraiment et ne gagne rien sur un seul cœur.
- Un entrelacement est un ordre d'exécution possible ; deux fils de trois instructions en ont vingt, trois fils en ont mille six cent quatre-vingts.
- Tant que chaque fil travaille sur ses propres données, l'entrelacement change la chronologie et rien d'autre : tous les ordres donnent le même résultat.
Cette dernière ligne contient une condition, et c'est elle qui va sauter. Le chapitre sur la séparation et le partage de la mémoire dit à quelle condition exacte deux tâches travaillent sur les mêmes données, et à quelle condition elles n'y touchent jamais.