Les Newsletters Interstices
Source : Flickr © Carol Gillott / Paris Breakfast
    Niveau intermédiaire
    Niveau 2 : Intermédiaire

    De votre boulangerie à un système d’exploitation multiprocesseur

    Architecture & Systèmes
    Culture & Société
    Vous entrez dans votre boulangerie préférée pour acheter une baguette, une des serveuses disponibles s'adresse à vous, traite votre demande puis vous souhaite une bonne journée. Sans le savoir, vous venez d'assister à une représentation grandeur nature d'un système d'exploitation multiprocesseur.

    Le système d’exploitation est un logiciel un peu particulier, une sorte de chef d’orchestre présent sur tous vos ordinateurs. Tout le monde a déjà entendu parler de Windows, MacOS, Linux ou Unix, mais peu de gens connaissent réellement l’utilité de ces systèmes d’exploitation. Pour l’expliquer, prenons l’exemple du fonctionnement d’une boulangerie.

    Quand on achète une baguette ou une viennoiserie, on n’a pas forcément envie de savoir comment le boulanger l’a préparée, comment il a réglé son four, quels ingrédients ont été utilisés et dans quel ordre… Ce qui nous importe, c’est de manger et que ce soit bon. Le fait de masquer la complexité du travail est le premier rôle du système d’exploitation : peu importe quel ordinateur vous avez acheté, vous ne voulez pas savoir comment son processeur ou son disque dur fonctionne, vous voulez simplement pouvoir l’utiliser comme d’habitude.

    Dans un système d’exploitation, à l’instar d’une boulangerie, il y a des tâches à effectuer (exécuter les logiciels de l’utilisateur, gérer les lectures et écritures à travers le réseau, piloter une imprimante, etc.). La machine est composée de processeurs qui peuvent prendre en charge les opérations liées à ces tâches, et de périphériques qui sont dédiés à certaines opérations particulières.

    Le composant principal d’un ordinateur est le processeur. Il est chargé d’exécuter les programmes, c’est-à-dire de longues suites d’opérations. De nos jours, on trouve plusieurs processeurs ou « cœurs » dans chaque ordinateur, on peut donc exécuter plusieurs tâches simultanément. Le problème principal est alors de « partager » au mieux le temps de calcul du ou des processeurs.

    Dans notre boulangerie, cela correspond à différentes serveuses qui s’occupent des différents clients. Chaque client n’est géré que par une seule serveuse à la fois, mais chaque serveuse gère plusieurs clients, soit simultanément soit consécutivement. Le rôle du système d’exploitation est aussi de faire en sorte que chaque client soit servi, si possible rapidement, et que toutes les serveuses soient employées au mieux. Un client de boulangerie mécontent car une serveuse disponible tarde à s’occuper de lui ressemble à s’y méprendre à un utilisateur mécontent devant son écran si son document ne s’ouvre pas assez rapidement.

    Gérer les clients revient à effectuer un certain nombre d’opérations, comme leur demander ce qu’ils veulent, emballer une baguette, encaisser le montant de l’achat, etc. Dans la plupart des cas, cette suite d’opérations est effectuée d’une traite avant que la serveuse ne passe au client suivant. Cependant, si le client devant vous achète une quiche lorraine, vous serez probablement heureux que la serveuse s’occupe de vous pendant que la quiche réchauffe. En informatique, on parle de recouvrement : quand une opération longue peut être traitée par quelqu’un d’autre, on essaie d’utiliser le processeur pour faire autre chose que d’attendre bêtement la fin de l’opération. Dans l’ordinateur, le micro-onde représente souvent un disque dur. La lecture ou l’écriture de données étant très lente, le système d’exploitation utilise par exemple le processeur pour rafraîchir une page web pendant que votre document est enregistré.

    Dans le cas du recouvrement, c’est l’inactivité de la serveuse pendant le réchauffage qui justifie le passage temporaire au client suivant. Cependant, dans certains cas, une serveuse active pourra être amenée à passer au client suivant avant d’avoir fini sa tâche courante. Par exemple, une serveuse faisant l’inventaire des pièces restantes arrêtera temporairement sa tâche à l’heure de pointe pour aider ses collègues à s’occuper de tous les clients en attente. On parle ici de préemption. Ce terme a été annoncé comme une révolution par Microsoft lors de la sortie de Windows 95, mais il existait en fait depuis très longtemps dans les systèmes d’exploitation Unix. Il s’agit de suspendre une tâche courante pour en traiter une autre avant de revenir plus tard à la première. En pratique, si les tâches sont courtes, comme vendre une baguette, pas besoin de les préempter, on peut les finir d’un seul coup. Par contre, si elles sont longues, comme faire l’inventaire, on étale leur traitement sur différentes petites périodes. Entre ces périodes, on traitera d’autres tâches. L’intérêt est que la présence d’une très longue tâche n’empêche pas les autres d’être traitées. Dans un système d’exploitation, la durée de ces périodes est de l’ordre de 10 millisecondes. C’est notamment suffisant pour que votre programme réagisse à votre clic de souris même si le processeur est occupé à afficher une vidéo en Full HD.

    En cas de recouvrement et de préemption, le processeur devra interrompre la tâche courante pour passer à une autre puis y revenir plus tard. On parle de changement de contexte. Le processeur écrit sur un calepin – dans la mémoire de l’ordinateur – où il en était, afin de pouvoir reprendre exactement au même endroit plus tard. Pour éviter d’avoir à faire ce travail, on pourrait imaginer que le processeur écrive au fur et à mesure ce qu’il fait. Ainsi, dans l’idéal, lorsqu’il voudrait passer à autre chose, il n’aurait plus rien à écrire. Cependant, cette écriture coûte cher, et il est plus efficace de se souvenir du nombre de viennoiseries déjà comptées que de les cocher au fur et à mesure sur un calepin.

    Ce traitement des différentes tâches – les clients – est appelé ordonnancement. Il a donné lieu à beaucoup de travaux de recherche pour améliorer la satisfaction globale des clients en traitant par exemple leurs commandes dans un ordre qui permet de minimiser leur temps d’attente. En pratique, cela impose de définir des priorités. Si un client ne veut qu’une baguette alors que les dix clients précédents veulent une formule avec sandwich, boisson et dessert, certaines boulangeries feront passer la baguette en priorité. Cela ralentit légèrement les formules mais accélère grandement la baguette. Certaines boulangeries considèrent par contre que la baguette n’est pas prioritaire. De la même façon, certains systèmes d’exploitation privilégient les tâches courtes, d’autres non.

    L’ordonnancement consiste aussi à répartir les tâches parmi les différents processeurs et à gérer la concurrence. Il faut notamment éviter que deux serveuses ne prennent la même baguette – un morceau du disque dur par exemple – pour la donner à deux clients différents. Le système d’exploitation gère ce problème en mettant en place des mécanismes de verrouillage : lorsqu’un processeur veut prendre un pain au chocolat, il ferme temporairement le verrou du rayon afin que personne d’autre ne puisse prendre le même pain au chocolat en même temps.

    Les systèmes d’exploitation actuels privilégient également certains processeurs vis-à-vis de certaines tâches : une serveuse qui a servi des sandwichs récemment sera probablement plus efficace qu’une autre car elle sait où sont placés les différents sandwichs et combien il en reste. On parle d’affinité de cache : les processeurs comportent une zone de mémoire spéciale appelée cache qui s’habitue au travail en cours afin de pouvoir le répéter plus vite. Par contre, si on leur demande de faire un travail très différent, ils auront besoin d’un petit temps d’adaptation. Plus récemment, on a également vu apparaître des processeurs spécialisés. Par exemple, une serveuse ayant fait un stage en pâtisserie sera plus à même de répondre aux questions des clients du rayon pâtisserie. Le système d’exploitation tient ainsi compte des spécialités des différents processeurs pour mieux répartir les tâches et optimiser l’efficacité globale.

    Au-delà des processeurs, le système d’exploitation doit également gérer les périphériques. Quand vous cliquez sur le bouton « Enregistrer », le processeur indique à la carte graphique d’afficher le bouton comme s’il était enfoncé et demande au disque dur de sauvegarder votre fichier. Plus tard, le disque dur indiquera au processeur qu’il a terminé d’écrire et que le bouton « Enregistrer » peut être ré-affiché normalement. Cet envoi de commande aux périphériques se passe exactement comme lorsqu’une serveuse appelle le boulanger à l’arrière parce qu’il n’y a plus de chaussons aux pommes. Le boulanger en prépare d’autres puis les apporte. Pour éviter d’attendre, le système d’exploitation peut également anticiper et demander la préparation dès que le stock actuel commence à être faible. Ainsi, il y a des chances pour que le boulanger apporte des chaussons aux pommes avant qu’un client ne doive attendre. Par contre, il ne faut évidemment pas en préparer trop à l’avance. Le système d’exploitation doit donc anticiper mais pas trop afin de ne pas gaspiller trop de ressources.

    boulangerie

    Source : Flickr © Brian McCrory / bnm_1972

    Quand le boulanger apporte les viennoiseries demandées, il indique à la serveuse que sa demande a été traitée. Dans un ordinateur, ce message d’indication est appelé une interruption. La serveuse stoppe alors temporairement la tâche en cours, installe les chaussons aux pommes dans le présentoir, puis reprend sa tâche précédente. Le même phénomène se produit lorsque le téléphone sonne parce qu’un client veut passer une commande pour le lendemain : la serveuse interrompt sa tâche courante immédiatement pour répondre. Cependant, pour ne pas faire trop attendre le client qu’elle est en train de servir dans le magasin, elle peut également noter le message sur un post-it et ranger les chaussons aux pommes, ou rappeler le correspondant, plus tard, quand il y aura moins de clients en attente. On dit qu’on retarde le traitement de l’interruption.

    Dans notre boulangerie, les clients représentent les tâches qui sont affectées aux serveuses – les processeurs, et le boulanger joue le rôle d’un périphérique qui reçoit des commandes. Tant que le nombre d’acteurs impliqués (clients, vendeuses et boulangers) reste faible, un fonctionnement reposant sur des prises de décisions autonomes et intuitives est possible. Mais, au-delà d’un certain seuil, l’intervention d’un superviseur s’avère nécessaire. C’est clairement le cas pour des tâches qui s’exécutent sur un ordinateur, d’autant plus qu’elles ne possèdent pas, à l’évidence, les facultés de pensée et de décision des acteurs humains. C’est donc le système d’exploitation qui joue ce rôle de superviseur ou de « chef d’orchestre ». Si le nombre de processeurs, et conjointement de tâches, est très élevé, ce rôle n’est pas rempli par un programme unique, mais réparti entre les différents processeurs. Ceux-ci disposent alors de mécanismes assurant périodiquement la supervision entre le traitement de différentes tâches.

    Ce qui est remarquable, et ce que cette métaphore illustre, c’est que les mécanismes algorithmiques cités ici « suffisent » à faire fonctionner un système d’exploitation multiprocesseur.

    Newsletter

    Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité

    Niveau de lecture

    Aidez-nous à évaluer le niveau de lecture de ce document.

    Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (Il ne sera pas publié).

    Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !

    Brice Goglin

    Chargé de recherche Inria dans l'équipe RUNTIME.
    Voir le profil