Ordonnancement (calcul)

En informatique , l'ordonnancement est l'action d'affecter des ressources pour réaliser des tâches . Les ressources peuvent être des processeurs , des liaisons réseau ou des cartes d'extension . Les tâches peuvent être des threads , des processus ou des flux de données .

L'activité de planification est réalisée par un mécanisme appelé planificateur . Les planificateurs sont souvent conçus de manière à maintenir toutes les ressources informatiques occupées (comme dans l'équilibrage de charge ), à ​​permettre à plusieurs utilisateurs de partager efficacement les ressources système ou à atteindre une qualité de service cible .

La planification est fondamentale pour le calcul lui-même et constitue une partie intrinsèque du modèle d'exécution d'un système informatique ; le concept de planification permet d'avoir un ordinateur multitâche avec une seule unité centrale de traitement (CPU).

Un planificateur peut viser un ou plusieurs objectifs, par exemple :

• maximiser le débit (la quantité totale de travail effectuée par unité de temps) ;
• minimiser le temps d’attente (temps écoulé entre le moment où le travail est prêt et le premier point où il commence à être exécuté) ;
• minimiser le temps de latence ou de réponse (temps écoulé entre le moment où le travail est prêt et celui où il est terminé dans le cas d'une activité par lots, ou jusqu'à ce que le système réponde et remette la première sortie à l'utilisateur dans le cas d'une activité interactive) ;
• maximiser l'équité (temps CPU égal pour chaque processus, ou plus généralement des temps appropriés en fonction de la priorité et de la charge de travail de chaque processus).

En pratique, ces objectifs sont souvent en conflit (par exemple, débit versus latence), c'est pourquoi un planificateur mettra en œuvre un compromis approprié. La préférence est mesurée par l'une des préoccupations mentionnées ci-dessus, en fonction des besoins et des objectifs de l'utilisateur.

Dans les environnements temps réel , comme les systèmes embarqués de contrôle automatique dans l'industrie (par exemple la robotique ), l'ordonnanceur doit également s'assurer que les processus peuvent respecter les délais ; cela est crucial pour maintenir la stabilité du système. Les tâches planifiées peuvent également être distribuées à des appareils distants sur un réseau et gérées via un back-end administratif.

Le planificateur est un module du système d'exploitation qui sélectionne les prochaines tâches à admettre dans le système et le prochain processus à exécuter. Les systèmes d'exploitation peuvent comporter jusqu'à trois types de planificateurs distincts : un planificateur à long terme (également appelé planificateur d'admission ou planificateur de haut niveau), un planificateur à moyen terme ou à moyen terme et un planificateur à court terme . Les noms suggèrent la fréquence relative à laquelle leurs fonctions sont exécutées.

Le planificateur de processus est une partie du système d'exploitation qui décide quel processus s'exécute à un moment donné. Il a généralement la capacité de mettre en pause un processus en cours d'exécution, de le déplacer vers la fin de la file d'attente et de démarrer un nouveau processus ; un tel planificateur est connu sous le nom de planificateur préemptif , sinon il s'agit d'un planificateur coopératif .

Nous distinguons la planification à long terme , la planification à moyen terme et la planification à court terme en fonction de la fréquence à laquelle les décisions doivent être prises.

Le planificateur à long terme , ou planificateur d'admission , décide quels travaux ou processus doivent être admis dans la file d'attente prête (dans la mémoire principale) ; autrement dit, lorsqu'une tentative d'exécution d'un programme est effectuée, son admission dans l'ensemble des processus en cours d'exécution est soit autorisée, soit retardée par le planificateur à long terme. Ainsi, ce planificateur dicte quels processus doivent s'exécuter sur un système, le degré de concurrence à prendre en charge à un moment donné (si de nombreux ou de peu de processus doivent être exécutés simultanément) et comment la répartition entre les processus gourmands en E/S et les processus gourmands en CPU doit être gérée. Le planificateur à long terme est responsable du contrôle du degré de multiprogrammation.

En général, la plupart des processus peuvent être décrits comme étant liés aux E/S ou au processeur . Un processus lié aux E/S est un processus qui passe plus de temps à effectuer des E/S qu'à effectuer des calculs. Un processus lié au processeur, en revanche, génère des requêtes d'E/S peu fréquentes et utilise davantage de temps pour effectuer des calculs. Il est important qu'un planificateur à long terme sélectionne un bon mélange de processus liés aux E/S et au processeur. Si tous les processus sont liés aux E/S, la file d'attente prête sera presque toujours vide et le planificateur à court terme n'aura pas grand-chose à faire. En revanche, si tous les processus sont liés au processeur, la file d'attente d'E/S sera presque toujours vide, les périphériques resteront inutilisés et le système sera à nouveau déséquilibré. Le système ayant les meilleures performances aura donc une combinaison de processus liés au processeur et aux E/S. Dans les systèmes d'exploitation modernes, cela est utilisé pour s'assurer que les processus en temps réel disposent de suffisamment de temps CPU pour terminer leurs tâches.

La planification à long terme est également importante dans les systèmes à grande échelle tels que les systèmes de traitement par lots , les clusters d'ordinateurs , les supercalculateurs et les fermes de rendu . Par exemple, dans les systèmes concurrents , la co-planification des processus en interaction est souvent nécessaire pour éviter qu'ils ne se bloquent en raison de l'attente des uns des autres. Dans ces cas, un logiciel de planification de tâches à usage spécifique est généralement utilisé pour assister ces fonctions, en plus de toute prise en charge de la planification d'admission sous-jacente dans le système d'exploitation.

Certains systèmes d'exploitation n'autorisent l'ajout de nouvelles tâches que s'ils sont sûrs que tous les délais en temps réel peuvent encore être respectés. L'algorithme heuristique spécifique utilisé par un système d'exploitation pour accepter ou rejeter de nouvelles tâches est le mécanisme de contrôle d'admission .

Le planificateur à moyen terme supprime temporairement les processus de la mémoire principale et les place dans la mémoire secondaire (comme un disque dur ) ou vice versa, ce qui est communément appelé swapping out ou swapping in (également appelé à tort pagination out ou pagination in ). Le planificateur à moyen terme peut décider de swapper un processus qui n'a pas été actif depuis un certain temps, un processus qui a une faible priorité, un processus qui fait souvent des erreurs de page ou un processus qui occupe une grande quantité de mémoire afin de libérer de la mémoire principale pour d'autres processus, de replacer le processus plus tard lorsque davantage de mémoire est disponible, ou lorsque le processus a été débloqué et n'attend plus de ressource.

Dans de nombreux systèmes actuels (ceux qui prennent en charge le mappage de l'espace d'adressage virtuel vers un stockage secondaire autre que le fichier d'échange), le planificateur à moyen terme peut en fait jouer le rôle du planificateur à long terme, en traitant les binaires comme des processus échangés lors de leur exécution. De cette façon, lorsqu'un segment du binaire est requis, il peut être échangé à la demande, ou chargé à la demande , également appelé pagination à la demande .

Le planificateur à court terme (également appelé planificateur de CPU ) décide quels processus prêts en mémoire doivent être exécutés (alloués à un CPU) après une interruption d'horloge , une interruption d'E/S, un appel au système d'exploitation ou une autre forme de signal . Ainsi, le planificateur à court terme prend des décisions de planification beaucoup plus fréquemment que les planificateurs à long terme ou à moyen terme. Une décision de planification devra au minimum être prise après chaque tranche de temps, et celles-ci sont très courtes. Ce planificateur peut être préemptif , ce qui implique qu'il est capable de supprimer de force des processus d'un CPU lorsqu'il décide d'allouer ce CPU à un autre processus, ou non préemptif (également appelé volontaire ou coopératif ), auquel cas le planificateur est incapable de forcer les processus à quitter le CPU.

Un planificateur préemptif s'appuie sur un temporisateur d'intervalle programmable qui appelle un gestionnaire d'interruption qui s'exécute en mode noyau et implémente la fonction de planification.

Un autre composant impliqué dans la fonction de planification du processeur est le répartiteur, qui est le module qui donne le contrôle du processeur au processus sélectionné par le planificateur à court terme. Il reçoit le contrôle en mode noyau à la suite d'une interruption ou d'un appel système. Les fonctions d'un répartiteur impliquent les éléments suivants :

• Changements de contexte , dans lesquels le répartiteur enregistre l' état (également appelé contexte ) du processus ou du thread qui était en cours d'exécution précédemment ; le répartiteur charge ensuite l'état initial ou précédemment enregistré du nouveau processus.
• Passage en mode utilisateur.
• Sauter à l'emplacement approprié dans le programme utilisateur pour redémarrer ce programme indiqué par son nouvel état.

Le répartiteur doit être aussi rapide que possible car il est invoqué à chaque changement de processus. Pendant les changements de contexte, le processeur est pratiquement inactif pendant une fraction du temps, il faut donc éviter les changements de contexte inutiles. Le temps nécessaire au répartiteur pour arrêter un processus et en démarrer un autre est appelé latence de répartition .

Une discipline de planification (également appelée politique de planification ou algorithme de planification ) est un algorithme utilisé pour distribuer des ressources entre des parties qui les demandent simultanément et de manière asynchrone. Les disciplines de planification sont utilisées dans les routeurs (pour gérer le trafic de paquets) ainsi que dans les systèmes d'exploitation (pour partager le temps CPU entre les threads et les processus ), les lecteurs de disque ( planification des E/S ), les imprimantes ( spouleur d'impression ), la plupart des systèmes embarqués, etc.

Les principaux objectifs des algorithmes de planification sont de minimiser la pénurie de ressources et de garantir l'équité entre les parties qui utilisent les ressources. La planification consiste à décider à quelles demandes en attente doivent être allouées des ressources. Il existe de nombreux algorithmes de planification différents. Dans cette section, nous en présentons plusieurs.

Dans les réseaux informatiques à commutation de paquets et autres multiplexages statistiques , la notion d' algorithme de planification est utilisée comme alternative à la mise en file d'attente des paquets de données selon le principe du premier arrivé, premier servi .

Les algorithmes de planification les plus simples sont le round-robin , la mise en file d'attente équitable (un algorithme de planification équitable max-min ), la planification proportionnelle équitable et le débit maximal . Si une qualité de service différenciée ou garantie est offerte, par opposition à une communication au mieux, une mise en file d'attente équitable pondérée peut être utilisée.

Dans les réseaux sans fil radio par paquets avancés tels que le système cellulaire HSDPA (High-Speed ​​Downlink Packet Access) 3,5G , la planification dépendante du canal peut être utilisée pour tirer parti des informations sur l'état du canal . Si les conditions du canal sont favorables, le débit et l'efficacité spectrale du système peuvent être augmentés. Dans des systèmes encore plus avancés tels que LTE , la planification est combinée par une allocation dynamique de canal paquet par paquet en fonction du canal , ou par l'attribution de multiporteuses OFDMA ou d'autres composants d'égalisation du domaine fréquentiel aux utilisateurs qui peuvent le mieux les utiliser.

Le premier entré, premier sorti ( FIFO ), également connu sous le nom de premier arrivé, premier servi (FCFS), est l'algorithme de planification le plus simple. Le FIFO met simplement en file d'attente les processus dans l'ordre dans lequel ils arrivent dans la file d'attente prête. Il est couramment utilisé pour unfile d'attente de tâches , par exemple comme illustré dans cette section.

• Étant donné que les changements de contexte ne se produisent qu'à la fin du processus et qu'aucune réorganisation de la file d'attente du processus n'est requise, la charge de planification est minime.
• Le débit peut être faible, car les processus longs peuvent retenir le processeur, ce qui oblige les processus courts à attendre longtemps (ce que l'on appelle l'effet de convoi).
• Pas de famine, car chaque processus a la possibilité d'être exécuté après un temps défini.
• Le temps de traitement , le temps d’attente et le temps de réponse dépendent de l’ordre de leur arrivée et peuvent être élevés pour les mêmes raisons ci-dessus.
• Aucune priorisation n'est établie, ce qui fait que ce système a du mal à respecter les délais des processus.
• L'absence de priorisation signifie que tant que chaque processus se termine, il n'y a pas de pénurie. Dans un environnement où certains processus ne peuvent pas se terminer, il peut y avoir une pénurie.
• Il est basé sur la mise en file d'attente.

Earlyest Deadline First (EDF) ou le moins de temps restant est un algorithme de planification dynamique utilisé dans les systèmes d'exploitation en temps réel pour placer les processus dans une file d'attente prioritaire. Chaque fois qu'un événement de planification se produit (une tâche se termine, une nouvelle tâche est publiée, etc.), la file d'attente recherchera le processus le plus proche de sa date limite, qui sera le prochain à être planifié pour exécution.

Similaire à la stratégie Shortest Job First (SJF). Avec cette stratégie, le planificateur organise les processus dont le temps de traitement estimé restant est le plus court pour qu'ils soient les suivants dans la file d'attente. Cela nécessite des connaissances ou des estimations avancées sur le temps nécessaire à l'achèvement d'un processus.

• Si un processus plus court arrive pendant l'exécution d'un autre processus, le processus en cours d'exécution est interrompu (ce que l'on appelle la préemption), ce qui divise ce processus en deux blocs de calcul distincts. Cela crée une surcharge excessive en raison d'un changement de contexte supplémentaire. Le planificateur doit également placer chaque processus entrant dans un emplacement spécifique de la file d'attente, ce qui crée une surcharge supplémentaire.
• Cet algorithme est conçu pour un débit maximal dans la plupart des scénarios.
• Le temps d'attente et le temps de réponse augmentent à mesure que les besoins de calcul du processus augmentent. Étant donné que le temps de traitement est basé sur le temps d'attente plus le temps de traitement, les processus les plus longs sont considérablement affectés par cela. Le temps d'attente global est toutefois inférieur à celui du FIFO, car aucun processus n'a à attendre la fin du processus le plus long.
• Aucune attention particulière n'est accordée aux délais, le programmeur peut seulement tenter de rendre les processus avec des délais aussi courts que possible.
• La famine est possible, en particulier dans un système très occupé avec de nombreux petits processus en cours d'exécution.
• Pour utiliser cette politique, nous devons avoir au moins deux processus de priorité différente

Le système d'exploitation attribue un rang de priorité fixe à chaque processus et le planificateur classe les processus dans la file d'attente prête par ordre de priorité. Les processus de priorité inférieure sont interrompus par les processus entrants de priorité supérieure.

• Les frais généraux ne sont ni minimes ni importants.
• Le FPPS ne présente aucun avantage particulier en termes de débit par rapport à la planification FIFO.
• Si le nombre de classements est limité, il peut être caractérisé comme une collection de files d'attente FIFO, une pour chaque classement de priorité. Les processus dans les files d'attente de priorité inférieure ne sont sélectionnés que lorsque toutes les files d'attente de priorité supérieure sont vides.
• Le temps d'attente et le temps de réponse dépendent de la priorité du processus. Les processus à priorité élevée ont des temps d'attente et de réponse plus courts.
• Les délais peuvent être respectés en accordant une priorité plus élevée aux processus comportant des délais.
• La famine des processus de moindre priorité est possible lorsqu'un grand nombre de processus de haute priorité font la queue pour obtenir du temps CPU.

Le planificateur attribue une unité de temps fixe à chaque processus et les parcourt en boucle. Si le processus se termine dans cette tranche de temps, il est arrêté, sinon il est reprogrammé après avoir donné une chance à tous les autres processus.

• La planification RR implique une surcharge importante, en particulier avec une petite unité de temps.
• Débit équilibré entre FCFS/FIFO et SJF/SRTF, les tâches plus courtes sont terminées plus rapidement que dans FIFO et les processus plus longs sont terminés plus rapidement que dans SJF.
• Bon temps de réponse moyen, le temps d'attente dépend du nombre de processus et non de la durée moyenne du processus.
• En raison des délais d’attente élevés, les délais sont rarement respectés dans un système RR pur.
• La famine ne peut jamais se produire, car aucune priorité n'est donnée. L'ordre d'allocation des unités de temps est basé sur l'heure d'arrivée du processus, de manière similaire au FIFO.
• Si la tranche de temps est grande, elle devient FCFS/FIFO ou si elle est courte, elle devient SJF/SRTF.

Cette méthode est utilisée dans les situations où les processus sont facilement divisés en différents groupes. Par exemple, une division commune est établie entre les processus de premier plan (interactifs) et les processus d'arrière-plan (par lots). Ces deux types de processus ont des exigences de temps de réponse différentes et peuvent donc avoir des besoins de planification différents. Elle est très utile pour les problèmes de mémoire partagée .

Un planificateur à conservation de travail est un planificateur qui essaie toujours de maintenir les ressources planifiées occupées, s'il existe des tâches soumises prêtes à être planifiées. En revanche, un planificateur sans conservation de travail est un planificateur qui, dans certains cas, peut laisser les ressources planifiées inactives malgré la présence de tâches prêtes à être planifiées.

Il existe plusieurs problèmes de planification dans lesquels l'objectif est de décider quelle tâche va à quelle station et à quelle heure, de telle sorte que le temps de fabrication total soit minimisé :

• Ordonnancement d'atelier – il y a n tâches et m postes identiques. Chaque tâche doit être exécutée sur une seule machine. Ceci est généralement considéré comme un problème en ligne.
• Planification en atelier ouvert – il y a n tâches et m postes différents. Chaque tâche doit passer un certain temps à chaque poste, dans un ordre libre.
• Ordonnancement de l'atelier de fabrication – il y a n tâches et m postes différents. Chaque tâche doit passer un certain temps à chaque poste, dans un ordre prédéterminé.

Une méthode très courante dans les systèmes embarqués consiste à planifier les tâches manuellement. Cela peut par exemple être réalisé de manière multiplexée dans le temps. Parfois, le noyau est divisé en trois parties ou plus : planification manuelle, niveau préemptif et niveau d'interruption. Les méthodes exactes de planification des tâches sont souvent propriétaires.

• Pas de problèmes de pénurie de ressources
• Très haute prévisibilité ; permet la mise en œuvre de systèmes temps réel durs
• Presque aucun frais généraux
• Peut ne pas être optimal pour toutes les applications
• L'efficacité dépend entièrement de la mise en œuvre

Lors de la conception d'un système d'exploitation, un programmeur doit déterminer quel algorithme de planification sera le plus performant pour l'utilisation que le système va subir. Il n'existe pas d'algorithme de planification universel , et de nombreux systèmes d'exploitation utilisent des algorithmes de planification étendus ou des combinaisons des algorithmes ci-dessus.

Par exemple, Windows NT /XP/Vista utilise une file d'attente de rétroaction à plusieurs niveaux , une combinaison d'algorithmes de planification préemptive à priorité fixe, de type round-robin et de premier entré, premier sorti. Dans ce système, les threads peuvent augmenter ou diminuer de manière dynamique en priorité selon qu'ils ont déjà été traités ou qu'ils ont attendu longtemps. Chaque niveau de priorité est représenté par sa propre file d'attente, avec une planification round-robin parmi les threads à priorité élevée et FIFO parmi ceux à priorité faible. Dans ce sens, le temps de réponse est court pour la plupart des threads, et les threads système courts mais critiques sont terminés très rapidement. Étant donné que les threads ne peuvent utiliser qu'une seule unité de temps du round-robin dans la file d'attente à priorité la plus élevée, la famine peut être un problème pour les threads à priorité élevée plus longs.

L'algorithme utilisé peut être aussi simple que le round-robin dans lequel chaque processus se voit attribuer le même temps (par exemple 1 ms, généralement entre 1 ms et 100 ms) dans une liste cyclique. Ainsi, le processus A s'exécute pendant 1 ms, puis le processus B, puis le processus C, puis de nouveau le processus A.

Les algorithmes plus avancés prennent en compte la priorité du processus, ou l'importance du processus. Cela permet à certains processus d'utiliser plus de temps que d'autres. Le noyau utilise toujours les ressources dont il a besoin pour assurer le bon fonctionnement du système, et on peut donc dire qu'il a une priorité infinie. Dans les systèmes SMP , l'affinité du processeur est considérée comme augmentant les performances globales du système, même si elle peut ralentir l'exécution d'un processus lui-même. Cela améliore généralement les performances en réduisant le thrashing du cache .

IBM OS/360 était disponible avec trois planificateurs différents. Les différences étaient telles que les variantes étaient souvent considérées comme trois systèmes d'exploitation différents :

• L' option Single Sequential Scheduler , également connue sous le nom de Primary Control Program (PCP), permet l'exécution séquentielle d'un seul flux de tâches.
• L' option Multiple Sequential Scheduler , connue sous le nom de Multiprogrammation avec un nombre fixe de tâches (MFT), permettait l'exécution de plusieurs tâches simultanées. L'exécution était régie par une priorité qui avait une valeur par défaut pour chaque flux ou pouvait être demandée séparément pour chaque tâche. La version II de MFT ajoutait des sous-tâches (threads), qui s'exécutaient selon une priorité basée sur celle de la tâche parente. Chaque flux de tâches définissait la quantité maximale de mémoire pouvant être utilisée par n'importe quelle tâche de ce flux.
• L' option Planificateurs à priorités multiples , ou Multiprogrammation avec un nombre variable de tâches (MVT) , proposait des sous-tâches dès le départ ; chaque tâche demandait la priorité et la mémoire dont elle avait besoin avant son exécution.

Les versions ultérieures de stockage virtuel de MVS ont ajouté une fonctionnalité Workload Manager au planificateur, qui planifie les ressources du processeur selon un schéma élaboré défini par l'installation.

Les premiers systèmes MS-DOS et Microsoft Windows n'étaient pas multitâches et ne disposaient donc pas d'un planificateur. Windows 3.1x utilisait un planificateur non préemptif, ce qui signifie qu'il n'interrompait pas les programmes. Il comptait sur le programme pour terminer ou dire au système d'exploitation qu'il n'avait pas besoin du processeur pour pouvoir passer à un autre processus. C'est ce qu'on appelle généralement le multitâche coopératif. Windows 95 a introduit un planificateur préemptif rudimentaire ; cependant, pour la prise en charge des applications héritées, il a choisi de laisser les applications 16 bits s'exécuter sans préemption.

Les systèmes d'exploitation Windows NT utilisent une file d'attente de rétroaction à plusieurs niveaux. 32 niveaux de priorité sont définis, de 0 à 31, les priorités 0 à 15 étant des priorités normales et les priorités 16 à 31 étant des priorités en temps réel souples, nécessitant des privilèges pour leur attribution. 0 est réservé au système d'exploitation. Les interfaces utilisateur et les API fonctionnent avec des classes de priorité pour le processus et les threads du processus, qui sont ensuite combinées par le système dans le niveau de priorité absolu.

Le noyau peut modifier le niveau de priorité d'un thread en fonction de son utilisation des E/S et du processeur et de son caractère interactif (c'est-à-dire qu'il accepte et répond aux entrées des humains), augmentant la priorité des processus interactifs et limités aux E/S et diminuant celle des processus limités au processeur, afin d'augmenter la réactivité des applications interactives. Le planificateur a été modifié dans Windows Vista pour utiliser le registre du compteur de cycles des processeurs modernes afin de suivre exactement le nombre de cycles de processeur qu'un thread a exécuté, plutôt que d'utiliser simplement une routine d'interruption à intervalle. Vista utilise également un planificateur de priorité pour la file d'attente d'E/S afin que les défragmenteurs de disque et autres programmes de ce type n'interfèrent pas avec les opérations de premier plan.

Mac OS 9 utilise la planification coopérative pour les threads, où un processus contrôle plusieurs threads coopératifs, et fournit également une planification préemptive pour les tâches de multitraitement. Le noyau planifie les tâches de multitraitement à l'aide d'un algorithme de planification préemptive. Tous les processus du gestionnaire de processus s'exécutent dans une tâche de multitraitement spéciale, appelée tâche bleue . Ces processus sont planifiés de manière coopérative, à l'aide d'un algorithme de planification à tour de rôle ; un processus cède le contrôle du processeur à un autre processus en appelant explicitement une fonction de blocage telle que WaitNextEvent. Chaque processus possède sa propre copie du gestionnaire de threads qui planifie les threads de ce processus de manière coopérative ; un thread cède le contrôle du processeur à un autre thread en appelant YieldToAnyThreadou YieldToThread.

macOS utilise une file d'attente de rétroaction à plusieurs niveaux, avec quatre bandes de priorité pour les threads : normal, priorité système élevée, mode noyau uniquement et temps réel. Les threads sont planifiés de manière préventive ; macOS prend également en charge les threads planifiés de manière coopérative dans son implémentation du gestionnaire de threads dans Carbon .

Dans AIX version 4, il existe trois valeurs possibles pour la politique de planification des threads :

• Premier entré, premier sorti : une fois qu'un thread avec cette politique est planifié, il s'exécute jusqu'à son terme, sauf s'il est bloqué, s'il cède volontairement le contrôle du processeur ou si un thread de priorité supérieure devient répartissable. Seuls les threads à priorité fixe peuvent avoir une politique de planification FIFO.
• Round Robin : il s'agit d'un schéma similaire au schéma Round Robin du planificateur AIX version 3 basé sur des tranches de temps de 10 ms. Lorsqu'un thread RR a le contrôle à la fin de la tranche de temps, il se déplace vers la fin de la file d'attente des threads répartissables de sa priorité. Seuls les threads à priorité fixe peuvent avoir une stratégie de planification Round Robin.
• AUTRE : cette stratégie est définie par POSIX1003.4a comme étant définie par l'implémentation. Dans AIX version 4, cette stratégie est définie comme équivalente à RR, sauf qu'elle s'applique aux threads avec une priorité non fixe. Le recalcul de la valeur de priorité du thread en cours d'exécution à chaque interruption d'horloge signifie qu'un thread peut perdre le contrôle car sa valeur de priorité a dépassé celle d'un autre thread répartissable. Il s'agit du comportement d'AIX version 3.

Les threads sont particulièrement intéressants pour les applications qui se composent actuellement de plusieurs processus asynchrones. Ces applications peuvent imposer une charge plus légère au système si elles sont converties en une structure multithread.

AIX 5 implémente les politiques de planification suivantes : FIFO, round robin et round robin équitable. La politique FIFO a trois implémentations différentes : FIFO, FIFO2 et FIFO3. La politique round robin est nommée SCHED_RR dans AIX, et la politique round robin équitable est appelée SCHED_OTHER.

Linux 1.2 utilisait une politique de planification à tour de rôle .

Linux 2.2 a ajouté des classes de planification et la prise en charge du multitraitement symétrique (SMP).

Dans Linux 2.4, un ordonnanceur O(n) avec une file d'attente de rétroaction à plusieurs niveaux avec des niveaux de priorité allant de 0 à 140 a été utilisé ; 0 à 99 sont réservés aux tâches en temps réel et 100 à 140 sont considérés comme des niveaux de tâches agréables . Pour les tâches en temps réel, le quantum de temps pour changer de processus était d'environ 200 ms, et pour les tâches agréables d'environ 10 ms. L'ordonnanceur a parcouru la file d' attente d'exécution de tous les processus prêts, laissant les processus de priorité la plus élevée passer en premier et exécuter leurs tranches de temps, après quoi ils seront placés dans une file d'attente expirée. Lorsque la file d'attente active est vide, la file d'attente expirée devient la file d'attente active et vice versa.

Cependant, certaines distributions Linux d'entreprise telles que SUSE Linux Enterprise Server ont remplacé ce planificateur par un rétroportage du planificateur O(1) (qui était maintenu par Alan Cox dans sa série Linux 2.4-ac Kernel) vers le noyau Linux 2.4 utilisé par la distribution.

Dans les versions 2.6.0 à 2.6.22, le noyau utilisait un ordonnanceur O(1) développé par Ingo Molnar et de nombreux autres développeurs du noyau pendant le développement de Linux 2.5. Pour de nombreux noyaux au cours de la période, Con Kolivas a développé des ensembles de correctifs qui ont amélioré l'interactivité avec cet ordonnanceur ou l'ont même remplacé par ses propres ordonnanceurs.

Les travaux de Con Kolivas, et plus particulièrement son implémentation de la planification équitable appelée Rotating Staircase Deadline (RSDL), ont inspiré Ingo Molnár à développer le Completely Fair Scheduler (CFS) en remplacement de l' ordonnanceur O(1) antérieur , en créditant Kolivas dans son annonce. CFS est la première implémentation d'un ordonnanceur de processus de mise en file d'attente équitable largement utilisé dans un système d'exploitation à usage général.

Le CFS utilise un algorithme de planification classique et bien étudié appelé « fair queuing » inventé à l'origine pour les réseaux de paquets . Le fair queuing avait déjà été appliqué à la planification du processeur sous le nom de stride scheduling . Le planificateur CFS de fair queuing a une complexité de planification de , où N est le nombre de tâches dans la file d'attente d'exécution . Le choix d'une tâche peut être effectué en temps constant, mais la réinsertion d'une tâche après son exécution nécessite des opérations, car la file d'attente d'exécution est implémentée sous la forme d'un arbre rouge-noir .

Le Brain Fuck Scheduler , également créé par Con Kolivas, est une alternative au CFS.

En 2023, Peter Zijlstra a proposé de remplacer le CFS par un planificateur de processus de planification virtuelle éligible au plus tôt (EEVDF). L'objectif était de supprimer le besoin de correctifs de latence CFS .

FreeBSD utilise une file d'attente de rétroaction à plusieurs niveaux avec des priorités allant de 0 à 255. Les valeurs de 0 à 63 sont réservées aux interruptions, de 64 à 127 à la moitié supérieure du noyau, de 128 à 159 aux threads utilisateur en temps réel, de 160 à 223 aux threads utilisateur à temps partagé et de 224 à 255 aux threads utilisateur inactifs. De plus, comme Linux, il utilise la configuration de file d'attente active, mais il dispose également d'une file d'attente inactive.

NetBSD utilise une file d'attente de rétroaction à plusieurs niveaux avec des priorités allant de 0 à 223. 0 à 63 sont réservés aux threads à temps partagé (par défaut, politique SCHED_OTHER), 64 à 95 aux threads utilisateur qui sont entrés dans l'espace noyau , 96 à 128 aux threads du noyau, 128 à 191 aux threads utilisateur en temps réel (politiques SCHED_FIFO et SCHED_RR) et 192 à 223 aux interruptions logicielles .

Solaris utilise une file d'attente de rétroaction à plusieurs niveaux avec des priorités comprises entre 0 et 169. Les priorités 0 à 59 sont réservées aux threads à temps partagé, 60 à 99 aux threads système, 100 à 159 aux threads en temps réel et 160 à 169 aux interruptions à faible priorité. Contrairement à Linux, lorsqu'un processus est terminé en utilisant son quantum de temps, il reçoit une nouvelle priorité et est remis dans la file d'attente. Solaris 9 a introduit deux nouvelles classes de planification, à savoir la classe à priorité fixe et la classe à partage équitable. Les threads à priorité fixe ont la même plage de priorité que celle de la classe à temps partagé, mais leurs priorités ne sont pas ajustées de manière dynamique. La classe de planification équitable utilise les parts de CPU pour hiérarchiser les threads pour les décisions de planification. Les parts de CPU indiquent le droit aux ressources de CPU. Elles sont allouées à un ensemble de processus, qui sont collectivement connus sous le nom de projet.