Le long parcours pour implémenter la « préemption paresseuse » dans l’ordonnanceur CPU de Linux

 (lwn.net)
3 points par GN⁺ 2024-10-20 | 1 commentaires | Partager sur WhatsApp
  • Le noyau Linux maintient depuis longtemps plusieurs modes de préemption afin de trouver un compromis entre débit et temps de réponse, et le nouveau jeu de correctifs de Peter Zijlstra relance sérieusement les discussions autour de la préemption paresseuse (PREEMPT_LAZY)
  • Les modes existants PREEMPT_NONE, PREEMPT_VOLUNTARY, PREEMPT_FULL et PREEMPT_RT diffèrent par l’étendue de la préemption autorisée ; plus la préemption est fréquente, plus la réactivité peut s’améliorer, mais au prix d’une charge accrue sur le débit global et la contention sur les verrous
  • PREEMPT_LAZY utilise le drapeau TIF_NEED_RESCHED_LAZY pour signaler qu’une replanification est nécessaire, mais pas immédiatement, et reporte la plupart des préemptions jusqu’au tick du timer
  • À long terme, l’objectif est de réduire les modes de préemption non temps réel à PREEMPT_LAZY et PREEMPT_FULL, et de supprimer la plupart des appels à cond_resched() disséminés dans le noyau
  • Le jeu de correctifs actuel a encore besoin de stabilisation, d’un examen des points d’appel et de tests de performance ; lors des premiers essais, le débit de PREEMPT_LAZY reste légèrement inférieur à celui de PREEMPT_VOLUNTARY

Les modes de préemption existants du noyau Linux

  • Le noyau actuel propose plusieurs modes de préemption pour contrôler à quel moment une tâche en cours d’exécution peut être préemptée par une autre
    • PREEMPT_NONE : le mode le plus simple, qui n’autorise la préemption que lorsqu’une tâche a épuisé sa tranche de temps
    • PREEMPT_VOLUNTARY : un mode qui ajoute de nombreux points dans le noyau où une préemption peut avoir lieu si nécessaire
    • PREEMPT_FULL : un mode qui autorise la préemption presque partout, sauf dans les sections où le noyau l’interdit, par exemple pendant la détention d’un spinlock
    • PREEMPT_RT : un mode qui donne la priorité à la préemption par rapport à presque tout le reste et rend même préemptable la plupart du code exécuté sous spinlock
  • Un niveau de préemption plus élevé permet de réagir plus vite à des événements comme un mouvement de souris ou le signal annonçant une anomalie imminente dans un réacteur nucléaire
  • En contrepartie, une préemption plus fréquente peut réduire le débit global des charges CPU intensives de longue durée et accroître la contention sur les verrous
  • De nombreuses distributions compilent le noyau avec le pseudo-mode PREEMPT_DYNAMIC
    • Il permet de choisir au démarrage l’un des trois modes non temps réel mentionnés plus haut
    • La valeur par défaut est PREEMPT_VOLUNTARY
    • Sur les systèmes où debugfs est monté, le mode actuel peut être consulté dans /sys/kernel/debug/sched/preempt

Pourquoi cond_resched() était nécessaire

  • PREEMPT_NONE et PREEMPT_VOLUNTARY n’autorisent pas la préemption arbitraire pendant l’exécution du code noyau
  • Quand une longue opération se poursuit à l’intérieur du noyau, cela peut provoquer une latence excessive, même sur des systèmes où la latence minimale n’est pas la priorité absolue
  • Pour éviter cela, des appels à cond_resched() ont été ajoutés dans de nombreuses boucles de longue durée
    • Chaque appel constitue un point supplémentaire de préemption volontaire
    • Ils fonctionnent aussi en mode PREEMPT_NONE
    • Le noyau contient des centaines de ces appels
  • Cette approche reste une heuristique qui ne fonctionne qu’aux endroits ajoutés par les développeurs
    • Certains appels peuvent être inutiles
    • D’autres peuvent manquer là où ils seraient nécessaires
    • Cela disperse la logique de décision d’ordonnancement dans l’ensemble du code du noyau

Le fonctionnement clé de la préemption paresseuse

  • Le noyau s’appuie sur plusieurs variables pour déterminer si la tâche en cours peut être préemptée
  • Parmi elles, TIF_NEED_RESCHED est un drapeau indiquant qu’une tâche de priorité plus élevée attend l’accès au CPU
    • Quand une tâche de priorité plus élevée se réveille, ce drapeau peut être positionné sur la tâche en cours d’exécution
    • En l’absence de ce drapeau, le noyau n’a pas besoin de préempter la tâche courante
  • Le noyau peut vérifier TIF_NEED_RESCHED à plusieurs endroits afin de préempter la tâche en cours
    • lors du tick du timer de l’ordonnanceur
    • lors du retour vers l’espace utilisateur après un appel système
    • à la fin d’un gestionnaire d’interruption
    • lors d’un appel à cond_resched()
  • Le correctif de préemption paresseuse ajoute un nouveau drapeau, TIF_NEED_RESCHED_LAZY
    • Il signifie qu’une replanification est nécessaire, mais pas impérativement tout de suite
    • En mode PREEMPT_LAZY, la plupart des événements positionnent ce nouveau drapeau à la place de TIF_NEED_RESCHED
  • Aux points où le noyau retourne vers l’espace utilisateur, le positionnement de l’un ou l’autre de ces deux drapeaux déclenche l’appel à l’ordonnanceur
  • En revanche, les points de préemption volontaire et les chemins de retour d’interruption ne vérifient que TIF_NEED_RESCHED

Le compromis introduit par PREEMPT_LAZY

  • Avec PREEMPT_LAZY, la plupart des événements à l’intérieur du noyau ne préemptent pas immédiatement la tâche courante
  • À la place, le gestionnaire du tick du timer vérifie si TIF_NEED_RESCHED_LAZY est positionné
    • Si c’est le cas, il positionne aussi TIF_NEED_RESCHED
    • La tâche en cours peut alors être préemptée
  • Une tâche s’exécute donc généralement pendant une durée proche de sa tranche de temps, sauf si elle cède volontairement le CPU
    • Ce comportement devrait favoriser un bon débit
  • Grâce à ce changement, PREEMPT_LAZY peut lui aussi s’exécuter avec la préemption noyau presque toujours activée, comme PREEMPT_FULL
    • La préemption reste possible dès que le compteur de préemption l’autorise
    • Si rien d’autre ne l’empêche, même du code noyau de longue durée peut être préempté
  • Quand une préemption immédiate est réellement nécessaire, elle n’est pas retardée
    • Par exemple, si le traitement d’une interruption rend exécutable une tâche temps réel, TIF_NEED_RESCHED est positionné
    • Dans ce cas, la préemption intervient presque aussitôt, sans attendre le tick du timer
  • Lorsqu’uniquement TIF_NEED_RESCHED_LAZY est positionné, aucune préemption ne se produit
    • Un noyau PREEMPT_LAZY est donc bien moins susceptible de préempter une tâche en cours qu’un noyau PREEMPT_FULL

Le travail restant avant de supprimer cond_resched()

  • L’objectif à long terme est de ramener les modes de préemption non temps réel à deux variantes
    • PREEMPT_LAZY
    • PREEMPT_FULL
  • PREEMPT_LAZY viendrait se placer entre PREEMPT_NONE et PREEMPT_VOLUNTARY, avec pour but de remplacer les deux
  • Si la préemption devient possible presque partout, il devient moins nécessaire d’ajouter des points de préemption volontaire à des endroits précis
  • Pour l’instant, les appels à cond_resched() sont toujours présents
    • Ils restent nécessaires tant que PREEMPT_NONE et PREEMPT_VOLUNTARY existent
    • Ils aident aussi à éviter les problèmes pendant la phase de stabilisation de la préemption paresseuse
  • Dans le jeu de correctifs actuel, cond_resched() ne vérifie que TIF_NEED_RESCHED
    • En conséquence, un grand nombre de situations qui auraient entraîné une préemption immédiate avec PREEMPT_VOLUNTARY ou PREEMPT_NONE peuvent désormais être retardées
  • Steve Rostedt a notamment demandé si conserver l’ancien sens de cond_resched() dans PREEMPT_VOLUNTARY pourrait faciliter la transition
  • Thomas Gleixner estime que le choix de ne vérifier que TIF_NEED_RESCHED est le bon
    • Parce que cela force à réexaminer tous les appels à cond_resched()
    • Les appels qui n’ont pas besoin de vérifier le bit lazy pourront être supprimés avec l’adoption de PREEMPT_LAZY
    • Ceux qui ont besoin de vérifier le bit lazy devront rester
  • Gleixner estime que moins de 5 % des appels à cond_resched() auront besoin de vérifier TIF_NEED_RESCHED_LAZY
  • Avant que la transition soit terminée, il faudra examiner des centaines d’appels à cond_resched() et en supprimer la majorité
  • Un jeu de correctifs distinct d’Ankur Arora traite une partie des détails liés à cette transition
  • Des tests de performance à grande échelle sont également nécessaires
    • Lors des premiers tests de Mike Galbraith, le débit de la préemption paresseuse s’est révélé légèrement inférieur à celui de PREEMPT_VOLUNTARY

Objectif final

  • Si ce travail sur la préemption paresseuse aboutit, le noyau pourrait devenir un peu plus petit et simple
  • L’objectif est un noyau capable d’offrir des latences prévisibles sans éparpiller des appels liés à l’ordonnancement dans tout le code
  • L’approche actuelle semble meilleure, mais il faudra encore du temps pour y parvenir

À lire aussi

1 commentaires

 
GN⁺ 2024-10-20
Avis de Hacker News

  • Ça semble prometteur. Comme EEVDF, c’est une orientation qui simplifie l’état actuel tout en l’améliorant ; difficile de faire mieux.

  • Je me demande pourquoi le niveau de préemption est un mode global, et non une propriété de certains événements. Certains événements doivent être traités avec une latence plus faible que d’autres.

    • Pour évaluer la priorité d’un événement, il faut d’abord du temps CPU. Cette évaluation n’est possible qu’après avoir interrompu le processus en cours d’exécution sur le CPU actuel.
      La priorité maximale qu’un événement peut avoir est donc limitée par la brièveté de la tranche de temps qu’un programme peut recevoir avant de passer par un changement de contexte. Pour répondre de façon fiable et à faible latence à n’importe quel type d’événement, tous les programmes intensifs en CPU doivent toujours en payer le coût en performance, même si cet événement est très rare.
    • Il y a ici deux notions faciles à confondre. L’une est le moment où un processus peut être préempté, l’autre est le fait qu’il le soit réellement ou non.
      Les points de préemption potentiels sont une propriété du planificateur, et c’est ce qui est discuté ici comme mode global. Plus il y a de points de préemption, plus la probabilité qu’un processus soit préempté à un moment gênant augmente évidemment, mais cela donne aussi davantage d’occasions de refléter correctement les priorités. Le niveau de préemption mentionné dans la question, c’est-à-dire la priorité donnée par le planificateur, est bien une propriété du processus et peut être configuré. Le planificateur par défaut de Linux donne aussi davantage de tranches de temps aux processus prioritaires et essaie de moins préempter les autres processus.
    • PREEMPT_VOLUNTARY, décrit dans l’article, était dans une certaine mesure une tentative allant dans ce sens, et on peut considérer qu’il est désormais en cours d’abandon.
    • Ce patch joue en partie ce rôle. D’après https://lwn.net/ml/all/20241008144829.GG14587@noisy.programm... :
      SCHED_IDLE, SCHED_BATCH et SCHED_NORMAL/OTHER utilisent la préemption différée, tandis que FIFO, RR et DEADLINE conservent le comportement Full existant.
    • Un tel système risque fort de créer une lutte entre programmes, chacun réclamant une priorité en affirmant être important. Dans la pratique, il est probable que les grandes entreprises l’exploitent pour offrir une « meilleure » expérience utilisateur.
      Il est donc important soit de réduire au minimum le nombre d’applications en cours d’exécution, soit de contrôler manuellement les brefs moments que rencontrent la plupart des utilisateurs. Les tâches intensives en CPU sont parfois plus probablement du mauvais code qu’un usage réellement efficace des ressources. Dans les jeux, il faut privilégier les performances, mais il faut un équilibre délicat pour ne pas immobiliser le système au détriment du multitâche. Quoi qu’il en soit, comme cela vise surtout les tâches inactives, il ne semble pas nécessaire d’automatiser beaucoup plus que de fournir une commande simple permettant à l’utilisateur d’activer ou désactiver plusieurs comportements depuis un script.

  • L’article dit que « le noyau actuel dispose de quatre modes qui contrôlent les moments où une tâche peut être préemptée au profit d’une autre ». Je me demande si cela concerne les tâches du noyau ou si cela inclut aussi les tâches utilisateur.

    • Il s’agit du code du noyau. Le code en espace utilisateur est toujours préemptible.

  • Je n’ai pas trouvé de chiffres dans le fil lié où le patch a été publié. Je suppose qu’il existait déjà au moins quelques benchmarks initiaux montrant le potentiel concret de ce changement, et cela m’intéresse.

    • C’est dans l’avant-dernier paragraphe de l’article.
      Il y est dit qu’il faudra des tests de performance étendus, que Mike Galbraith a commencé les premiers travaux, et que les résultats montrent que le débit de la préemption différée est légèrement inférieur à celui de PREEMPT_VOLUNTARY.
    • Je me demande comment on devrait benchmarker ce genre de chose. Faut-il lancer plusieurs processus simultanément puis les trier par temps d’exécution total, ou bien mesurer le temps d’attente de chaque processus ?

  • Je me demande à quel point le planificateur est fortement couplé au reste du code du noyau.
    Par exemple, si l’on voulait simplifier fortement le planificateur pour une application de calcul scientifique qui ne se soucie pas du tout de la préemption, serait-ce possible de façon propre et modulaire ? Y aurait-il aussi un avantage réel ?

    • Si l’on veut exécuter un ensemble de processus en réduisant autant que possible la préemption, par exemple dans un environnement HPC, la méthode la plus robuste consiste à configurer certains cœurs comme CPU isolés, à redémarrer, puis à y placer directement les tâches avec taskset.
      Mais cela oblige à affecter réellement les tâches aux CPU à la main, et il devient aussi facile de se retrouver avec toutes les tâches sur le mauvais CPU. La méthode standard consiste à définir des masques d’interruptions pour empêcher les interruptions d’aller vers les CPU de « travail », et à utiliser cpuset afin que seuls certains cgroups s’exécutent dans un cpuset donné.
    • Sur un système propre avec très peu de démons, si l’application est alignée sur un thread du système d’exploitation par thread CPU et qu’on lui applique une affinité CPU pour l’empêcher de migrer, on peut atteindre environ 95 % de l’objectif.
      Comme la liste d’exécution devient très courte, l’impact de ce que fait le planificateur restera assez limité. Si l’application ne fait pas beaucoup d’entrées/sorties, il n’y aura pas non plus beaucoup d’interruptions. Si l’on peut utiliser un noyau tickless — je ne sais pas si c’est encore une option séparée ou le comportement par défaut aujourd’hui — il peut n’y avoir presque aucune interruption pendant de longues périodes.
    • La dernière fois que j’ai regardé, c’était étonnamment bien séparé.
      Cela dit, la raison de simplifier fortement serait d’éviter les bugs, pas de gagner beaucoup de performances par rapport à un planificateur par défaut bien configuré. Il y a beaucoup de paramètres, mais pas tant de bugs de ce côté-là non plus. Une simplification naïve ferait le plus souvent perdre des performances plutôt qu’en gagner. Si vous exploitez un système non interactif, le changement le plus simple consiste à augmenter le quota de temps des processus.
    • J’utiliserais simplement RT Linux. Il a son propre planificateur par défaut, le planificateur du noyau tourne comme tâche inactive, et les tâches temps réel ont priorité sur tout le reste.