CFS :Ordonnancement de processus totalement équitable sous Linux

Linux adopte une approche modulaire de la planification des processeurs en ce sens que différents algorithmes peuvent être utilisés pour planifier différents types de processus. Une classe d'ordonnancement spécifie quelle politique d'ordonnancement s'applique à quel type de processus. La planification complètement équitable (CFS), qui est devenue une partie du noyau Linux 2.6.23 en 2007, est la classe de planification pour les processus normaux (par opposition aux processus en temps réel) et est donc nommée SCHED_NORMAL .

CFS est conçu pour les applications interactives typiques d'un environnement de bureau, mais il peut être configuré en tant que SCHED_BATCH pour privilégier les charges de travail par lots courantes, par exemple, sur un serveur Web à volume élevé. Dans tous les cas, CFS rompt radicalement avec ce que l'on pourrait appeler "l'ordonnancement préemptif classique". De plus, l'allégation "tout à fait équitable" doit être considérée d'un point de vue technique ; sinon, l'allégation pourrait sembler être une vaine vantardise.

Examinons les détails de ce qui distingue CFS des autres planificateurs de processus. Commençons par un examen rapide de certains termes techniques de base.

Quelques concepts de base

Linux hérite de la vue Unix d'un processus en tant que programme en cours d'exécution. En tant que tel, un processus doit composer avec d'autres processus pour les ressources système partagées :mémoire pour détenir des instructions et des données, au moins un processeur pour exécuter des instructions et périphériques d'E/S pour interagir avec le monde extérieur. La planification des processus est la façon dont le système d'exploitation (OS) attribue des tâches (par exemple, calculer des nombres, copier un fichier) aux processeurs - un processus en cours d'exécution exécute ensuite la tâche. Un processus a un ou plusieurs threads d'exécution , qui sont des séquences d'instructions au niveau de la machine. Ordonnancer un processus revient à ordonnancer un de ses threads sur un processeur.

Le Terminal Linux

Les 7 meilleurs émulateurs de terminaux pour Linux
10 outils de ligne de commande pour l'analyse de données sous Linux
Télécharger maintenant :Aide-mémoire SSH
Aide-mémoire des commandes Linux avancées
Tutoriels de ligne de commande Linux

Dans un mouvement de simplification, Linux transforme la planification des processus en planification des threads en traitant un processus planifié comme s'il s'agissait d'un seul thread. Si un processus est multi-thread avec N fils, puis N des actions de planification seraient nécessaires pour couvrir les threads. Les threads au sein d'un processus multithread restent liés en ce sens qu'ils partagent des ressources telles que l'espace d'adressage mémoire. Les threads Linux sont parfois décrits comme des processus légers, avec la mention lightweight soulignant le partage des ressources entre les threads au sein d'un processus.

Bien qu'un processus puisse se trouver dans différents états, deux présentent un intérêt particulier pour l'ordonnancement. Un bloqué processus attend la fin d'un événement tel qu'un événement d'E/S. Le processus ne peut reprendre son exécution qu'une fois l'événement terminé. Un exécutable processus est celui qui n'est pas actuellement bloqué.

Un processus est lié au processeur (alias lié au calcul ) s'il consomme principalement du processeur plutôt que des ressources d'E/S, et lié aux E/S dans le cas contraire; par conséquent, un processus lié au processeur est généralement exécutable, alors qu'un processus lié aux E/S est généralement bloqué. Par exemple, le traitement des chiffres est lié au processeur et l'accès aux fichiers est lié aux E/S. Bien qu'un processus entier puisse être caractérisé comme lié au processeur ou lié aux E/S, un processus donné peut être l'un ou l'autre à différentes étapes de son exécution. Les applications de bureau interactives, telles que les navigateurs, ont tendance à être liées aux E/S.

Un bon ordonnanceur de processus doit équilibrer les besoins des tâches liées au processeur et liées aux E/S, en particulier dans un système d'exploitation tel que Linux qui prospère sur tant de plates-formes matérielles :ordinateurs de bureau, appareils embarqués, appareils mobiles, clusters de serveurs, superordinateurs. , et plus encore.

Ordonnancement préemptif classique versus CFS

Unix a popularisé la planification préemptive classique, que d'autres systèmes d'exploitation, notamment VAX/VMS, Windows NT et Linux, ont ensuite adoptée. Au centre de ce modèle de planification se trouve une tranche de temps fixe , la durée (par exemple, 50 ms) pendant laquelle une tâche est autorisée à retenir un processeur jusqu'à ce qu'elle soit préemptée en faveur d'une autre tâche. Si un processus préempté n'a pas terminé son travail, le processus doit être replanifié. Ce modèle est puissant dans la mesure où il prend en charge le multitâche (concurrence) grâce au partage du temps du processeur, même sur les machines à processeur unique d'antan.

Le modèle classique comprend généralement plusieurs files d'attente de planification, une par priorité de processus :chaque processus d'une file d'attente de priorité supérieure est planifié avant tout processus d'une file d'attente de priorité inférieure. Par exemple, VAX/VMS utilise 32 files d'attente prioritaires pour la planification.

CFS se passe de tranches de temps fixes et de priorités explicites. La durée d'une tâche donnée sur un processeur est calculée dynamiquement à mesure que le contexte d'ordonnancement change au cours de la durée de vie du système. Voici un croquis des idées motivantes et des détails techniques :

Imaginez un processeur, P, qui est idéalisé en ce sens qu'il peut exécuter plusieurs tâches simultanément . Par exemple, les tâches T1 et T2 peuvent s'exécuter sur P en même temps, chacune recevant 50 % de la puissance de traitement magique de P. Cette idéalisation décrit le multitâche parfait , que CFS s'efforce d'atteindre sur des processeurs réels plutôt que sur des processeurs idéalisés. CFS est conçu pour se rapprocher d'un multitâche parfait.
Le planificateur CFS a une latence cible , qui est la durée minimale (idéalisée à une durée infiniment petite) nécessaire pour que chaque tâche exécutable obtienne au moins un tour de processeur. Si une telle durée pouvait être infiniment petite, alors chaque tâche exécutable aurait eu un tour sur le processeur pendant un laps de temps donné, aussi petit soit-il (par exemple, 10 ms, 5 ns, etc.). Bien sûr, une durée infiniment petite idéalisée doit être approximée dans le monde réel, et l'approximation par défaut est de 20 ms. Chaque tâche exécutable obtient alors un 1/N tranche de la latence cible, où N est le nombre de tâches. Par exemple, si la latence cible est de 20 ms et qu'il y a quatre tâches concurrentes, chaque tâche obtient une tranche de temps de 5 ms. Soit dit en passant, s'il n'y a qu'une seule tâche lors d'un événement de planification, cette tâche chanceuse obtient la totalité de la latence cible comme tranche. La foire dans CFS vient au premier plan dans le 1/N tranche donnée à chaque tâche en lice pour un processeur.
Le 1/N tranche est, en effet, une tranche de temps, mais pas fixe car une telle tranche dépend de N , le nombre de tâches actuellement en compétition pour le processeur. Le système change avec le temps. Certains processus se terminent et de nouveaux sont générés ; les processus exécutables bloquent et les processus bloqués deviennent exécutables. La valeur de N est dynamique et donc, par conséquent, le 1/N tranche de temps calculée pour chaque tâche exécutable en concurrence avec un processeur. Le traditionnel nice la valeur est utilisée pour pondérer le 1/N slice :un nice de faible priorité signifie que seule une fraction du 1/N slice est attribué à une tâche, alors qu'un nice hautement prioritaire signifie qu'une fraction proportionnellement plus grande du 1/N tranche est donnée à une tâche. En résumé, sympa les valeurs ne déterminent pas la tranche, mais modifient seulement le 1/N tranche qui représente l'équité entre les tâches concurrentes.
Le système d'exploitation subit une surcharge chaque fois qu'un changement de contexte se produit; c'est-à-dire lorsqu'un processus est préempté au profit d'un autre. Pour éviter que cette surcharge ne devienne excessivement importante, il existe un laps de temps minimum (avec un réglage typique de 1 ms à 4 ms) pendant lequel tout processus planifié doit s'exécuter avant d'être préempté. Ce minimum est connu sous le nom de granularité minimale . Si de nombreuses tâches (par exemple, 20) se disputent le processeur, la granularité minimale (supposons 4 ms) peut être plus que le 1/N tranche (dans ce cas, 1 ms). Si la granularité minimale s'avère supérieure au 1/N tranche, le système est surchargé car il y a trop de tâches en lice pour le processeur et l'équité disparaît.
Quand la préemption a-t-elle lieu ? CFS essaie de minimiser les changements de contexte, compte tenu de leur surcharge :le temps passé sur un changement de contexte est du temps indisponible pour d'autres tâches. En conséquence, une fois qu'une tâche obtient le processeur, elle s'exécute pendant toute sa pondération 1/N slice avant d'être devancé au profit d'une autre tâche. Supposons que la tâche T1 s'est exécutée pour son 1/N pondéré tranche, et la tâche exécutable T2 a actuellement le temps d'exécution virtuel le plus bas (vruntime) parmi les tâches en lice pour le processeur. Le vruntime enregistre, en nanosecondes, la durée d'exécution d'une tâche sur le processeur. Dans ce cas, T1 serait préempté en faveur de T2.
Le planificateur suit le vruntime pour toutes les tâches, exécutables et bloquées. Plus le vruntime d'une tâche est faible, plus la tâche est méritante pour le temps sur le processeur. CFS déplace en conséquence les tâches à faible temps d'exécution vers le début de la ligne de planification. Les détails sont à venir car la ligne est implémenté sous forme d'arborescence, pas de liste.
À quelle fréquence le planificateur CFS doit-il reprogrammer ? Il existe un moyen simple de déterminer la période de planification . Supposons que la latence cible (TL) soit de 20 ms et que la granularité minimale (MG) soit de 4 ms :

TL / MG = (20 / 4) = 5 ## five or fewer tasks are ok

Dans ce cas, cinq tâches ou moins permettraient à chaque tâche d'activer le processeur pendant la latence cible. Par exemple, si le numéro de tâche est cinq, chaque tâche exécutable a un 1/N tranche de 4 ms, ce qui correspond à la granularité minimale ; si le numéro de tâche est trois, chaque tâche obtient un 1/N tranche de presque 7ms. Dans les deux cas, le planificateur reprogrammera dans 20 ms, la durée de la latence cible.

Un problème survient si le nombre de tâches (par exemple, 10) dépasse TL / MG car maintenant chaque tâche doit obtenir le temps minimum de 4 ms au lieu du 1/N calculé tranche, qui est de 2 ms. Dans ce cas, le planificateur reprogrammerait dans 40 ms :

(number of tasks) * MG = (10 * 4) = 40ms ## period = 40ms

Les planificateurs Linux antérieurs à CFS utilisent l'heuristique pour promouvoir le traitement équitable des tâches interactives en ce qui concerne la planification. CFS adopte une approche assez différente en laissant les faits vruntime parler principalement d'eux-mêmes, ce qui se trouve à soutenir l'équité des dormeurs . Une tâche interactive, de par sa nature même, a tendance à beaucoup dormir dans le sens où elle attend les entrées de l'utilisateur et devient donc liée aux E/S; par conséquent, une telle tâche a tendance à avoir un vruntime relativement faible, ce qui a tendance à déplacer la tâche vers le début de la ligne de planification.

Caractéristiques spéciales

CFS prend en charge le multitraitement symétrique (SMP) dans lequel tout processus (qu'il s'agisse du noyau ou de l'utilisateur) peut s'exécuter sur n'importe quel processeur. Des domaines de planification encore configurables peut être utilisé pour regrouper les processeurs pour l'équilibrage de charge ou même la ségrégation. Si plusieurs processeurs partagent la même politique d'ordonnancement, alors l'équilibrage de charge entre eux est une option; si un processeur particulier a une politique de planification différente des autres, alors ce processeur sera séparé des autres en ce qui concerne la planification.

Groupes de planification configurables sont une autre fonctionnalité du CFS. Prenons l'exemple du serveur Web Nginx qui s'exécute sur mon ordinateur de bureau. Au démarrage, ce serveur dispose d'un processus maître et de quatre processus de travail, qui agissent comme des gestionnaires de requêtes HTTP. Pour toute requête HTTP, le travailleur particulier qui gère la requête n'est pas pertinent ; il importe seulement que la demande soit traitée en temps opportun, et ainsi les quatre travailleurs fournissent ensemble un pool à partir duquel puiser un gestionnaire de tâches au fur et à mesure que les demandes arrivent. Il semble donc juste de traiter les quatre travailleurs Nginx comme un groupe plutôt que en tant qu'individus à des fins de planification, et un groupe de planification peut être utilisé à cette fin. Les quatre nœuds de calcul Nginx pourraient être configurés pour avoir un seul vruntime parmi eux plutôt que des vruntimes individuels. La configuration se fait à la manière traditionnelle de Linux, par le biais de fichiers. Pour le partage vruntime, un fichier nommé cpu .shares , avec les détails donnés par les commandes shell familières, serait créé.

Comme indiqué précédemment, Linux prend en charge les classes de planification afin que différentes politiques d'ordonnancement, ainsi que leurs algorithmes de mise en œuvre, puissent coexister sur la même plate-forme. Une classe d'ordonnancement est implémentée en tant que module de code en C. CFS, la classe d'ordonnancement décrite jusqu'ici, est SCHED_NORMAL . Il existe également des classes de planification spécifiquement pour les tâches en temps réel, SCHED_FIFO (premier entré, premier sorti) et SCHED_RR (tournoi à la ronde). Sous SCHED_FIFO , les tâches sont exécutées jusqu'à la fin ; sous SCHED_RR , les tâches s'exécutent jusqu'à épuisement d'une tranche de temps fixe et sont préemptées.

Implémentation CFS

CFS nécessite des structures de données efficaces pour suivre les informations sur les tâches et un code hautes performances pour générer les horaires. Commençons par un terme central dans la planification, la runqueue . Il s'agit d'une structure de données qui représente une chronologie pour les tâches planifiées. Malgré son nom, la file d'attente n'a pas besoin d'être implémentée de manière traditionnelle, en tant que liste FIFO. CFS rompt avec la tradition en utilisant un arbre rouge-noir ordonné dans le temps comme file d'attente. La structure de données est bien adaptée au travail car il s'agit d'un arbre de recherche binaire auto-équilibré, avec une insertion efficace et supprimer opérations qui s'exécutent en O(log N) temps, où N est le nombre de nœuds dans l'arbre. En outre, un arbre est une excellente structure de données pour organiser les entités dans une hiérarchie basée sur une propriété particulière, dans ce cas un vruntime.

Dans CFS, les nœuds internes de l'arborescence représentent les tâches à planifier, et l'arborescence dans son ensemble, comme toute file d'attente, représente une chronologie pour l'exécution des tâches. Les arbres rouge-noir sont largement utilisés au-delà de la planification; par exemple, Java utilise cette structure de données pour implémenter son TreeMap .

Sous CFS, chaque processeur a une file d'attente spécifique de tâches, et aucune tâche ne se produit en même temps dans plus d'une file d'attente. Chaque runqueue est un arbre rouge-noir. Les nœuds internes de l'arborescence représentent des tâches ou des groupes de tâches, et ces nœuds sont indexés par leurs valeurs vruntime de sorte que (dans l'arborescence dans son ensemble ou dans n'importe quelle sous-arborescence) les nœuds internes à gauche aient des valeurs vruntime inférieures à celles de droite :

    25     ## 25 is a task vruntime

    /\

  17  29   ## 17 roots the left subtree, 29 the right one

  /\  ...

 5  19     ## and so on

...  \

     nil   ## leaf nodes are nil

En résumé, les tâches avec le temps de vruntime le plus bas (et, par conséquent, le plus grand besoin de processeur) résident quelque part dans la sous-arborescence de gauche; les tâches avec des vruntimes relativement élevés se rassemblent dans la sous-arborescence de droite. Une tâche préemptée irait dans le sous-arbre de droite, donnant ainsi aux autres tâches une chance de se déplacer vers la gauche dans l'arbre. Une tâche avec le plus petit vruntime se termine dans le nœud (interne) le plus à gauche de l'arborescence, qui est donc le devant de la file d'attente.

Le planificateur CFS a une instance, le C task_struct , pour suivre des informations détaillées sur chaque tâche à planifier. Cette structure intègre une sched_entity structure, qui à son tour contient des informations spécifiques à la planification, en particulier le vruntime par tâche ou groupe de tâches :

struct task_struct {       /** info on a task **/

  ...

  struct sched_entity se;  /** vruntime, etc. **/

  ...

};

L'arbre rouge-noir est implémenté de manière familière en C, avec une prime sur les pointeurs pour l'efficacité. Un cfs_rq instance de structure intègre une rb_root champ nommé tasks_timeline , qui pointe vers la racine d'un arbre rouge-noir. Chacun des nœuds internes de l'arborescence a des pointeurs vers le parent et les deux nœuds enfants ; les nœuds feuilles ont nil comme valeur.

CFS illustre comment une idée simple - donner à chaque tâche une part équitable des ressources du processeur - peut être mise en œuvre de manière simple mais très efficace. Il convient de répéter que CFS réalise une planification juste et efficace sans artefacts traditionnels tels que des tranches de temps fixes et des priorités de tâches explicites. La recherche d'ordonnanceurs encore meilleurs se poursuit, bien sûr; pour le moment, cependant, CFS est aussi bon que possible pour la planification de processeurs à usage général.