Les buts de l' ordonnancement diffèrent en fonction du type de systèmes.

Nous décrivons ci-dessous les politiques mises en oeuvre dans des systèmes interactifs ou à traitements par lots. Les politiques spécifiques aux systèmes temps réel sont abordées dans la leçon suivante.

C'est une politique à l'ancienneté, sans réquisition ; l'unité centrale est allouée selon l'ordre de soumission des processus. Dans cette politique, des processus de faible temps d'exécution peuvent être pénalisés parce qu'un processus de longue durée les précède dans la file.

Fig 4 : Politique Premier Arrivé, Premier Servi

Cette politique tente de remédier à l'inconvénient mentionné pour la politique précédente. Maintenant, l'unité centrale est allouée au processus de plus petit temps d'exécution. Cette politique est également une politique sans réquisition. Elle a la propriété de minimiser le temps de réponse moyen pour l'ensemble des algorithmes d'ordonnancement sans réquisition. Elle pénalise les travaux longs. Elle impose également d'estimer la durée des processus ce qu'on ne connaît pas habituellement. Il existe une version avec réquisition de cette politique appelée "temps restant le plus court d'abord" : dans ce cas, le processus en exécution restitue le processeur lorsqu'un nouveau processus de temps d'exécution inférieur à son temps d'exécution restant devient prêt.

On définit une tranche de temps appelée quantum qui peut varier de 10 ms à 100 ms. Chaque processus présent dans la file des processus prêts acquiert le processeur à tour de rôle, et ce pour au maximum un temps égal au quantum de temps. Si le processus a terminé son exécution avant la fin du quantum, il libère le processeur et le processus suivant dans la file des processus prêts est élu. Si le processus n'a pas terminé son exécution avant la fin du quantum, il perd le processeur et est réinséré en fin de file des processus prêts. Cette politique du tourniquet est usuellement utilisée dans les systèmes en temps partagé. Sa performance dépend largement de la taille du quantum. Un quantum trop grand augmente les temps de réponse alors qu'un quantum trop petit multiplie les commutations de contexte jusqu'à les rendre non négligeables.

Fig 6 : Politique par tourniquet

Un niveau de priorité constant est affecté à chaque processus et à un instant donné, le processus élu est toujours celui de plus forte priorité. Cet algorithme présente une version sans réquisition et une version avec réquisition. Le défaut de cette politique est le risque de famine encouru par le processus de faible priorité. Une solution à ce problème est de faire "vieillir" la priorité des processus en attente, c'est-à-dire d'augmenter celle-ci en fonction du temps d'attente. La priorité des processus devient ainsi variable.

Fig 7 : Politique par priorités constantes

Les politiques présentées jusqu'à présent utilisent une seule file d'attente des processus prêts. On choisit ici de définir plusieurs files de processus prêts, chaque file correspondant à un niveau de priorité ; on peut alors avoir n files de priorités différentes variant de 0 à n-1. Dans une file donnée, tous les processus ont la même priorité et sont servis soit selon une politique à l'ancienneté sans préemption , soit selon une politique de tourniquet. Le quantum peut être différent selon le niveau de priorité de la file. L' ordonnanceur sert d'abord tous les processus de la file de priorité n, puis ceux de priorité n-1 dès que la file de niveau n est vide et ainsi de suite...

On peut définir deux variantes de l'algorithme, fonction de l'évolution de la priorité des processus :

Fig 8 : Politique par priorités multiniveaux avec ou sans extinction de priorité

Il existe trois politiques (classes) d' ordonnancement dans Linux qui correspondent aux politiques définies dans la norme pour les systèmes d'exploitation ouverts, POSIX.: deux sont dites temps réel, SCHED_FIFO et SCHED_RR, la troisième est classique SCHED_OTHER. On peut attribuer un processus à l'une de ces trois classes grâce à l'appel système : sched_setscheduler(). Comme dans les systèmes Unix, la politique d'ordonnancement SCHED_OTHER de Linux a plusieurs objectifs : avoir de bons temps de réponses, assurer une bonne capacité de traitement et essayer de répartir équitablement le temps CPU entre les différents processus. Elle correspond à ce qu'on appelle la politique "en temps partagé". Chaque processus Linux a une priorité variable qui dépend de nombreux facteurs parmi lesquels nous pouvons citer le taux d'utilisation de la CPU et l'intensité des entrées / sorties. 

Il existe deux autres classes d'ordonnancement dites temps réel : SCHED_FIFO et SCHED_RR.Les rubriques "policy" et "rt_priority" stockées dans la structure des processus Linux permettent de leur attribuer une classe d'ordonnancement et une priorité temps réel. SCHED_FIFO et SCHED_RR ne sont pas des classes temps réel strictes, mais relatives. Quand un processus temps réel est prêt, tous les processus de priorité inférieure sont mis de côté. Un processus de la classe SCHED_FIFO peut s'exécuter jusqu'à la fin de son traitement ou jusqu'à ce qu'un processus de la classe SCHED_FIFO de priorité temps réel plus forte soit prêt. Un processus de la classe SCHED_RR est interrompu à la fin de son quantum de temps ou dès qu'un processus de priorité temps réel (SCHED_FIFO ou SCHED_RR) supérieure est prêt. Il existe dans cette classe un principe de tourniquet parmi les processus de même priorité.