Rate-monotonic scheduling
L'ordonnancement à taux monotone (en anglais, rate-monotonic scheduling) est un algorithme d'ordonnancement temps réel en ligne à priorité constante (statique). Il attribue la priorité la plus forte à la tâche qui possède la plus petite période. RMS est optimal dans le cadre d'un système de tâches périodiques, synchrones, indépendantes et à échéance sur requête avec un ordonnanceur préemptif. De ce fait, il n'est généralement utilisé que pour ordonnancer des tâches vérifiant ces propriétés. Cet algorithme a été proposé la première fois dans un papier publié par Liu et Layland. Outre l'algorithme à taux monotone, ce papier décrit une modélisation des tâches basée sur un triplet (, , ), ainsi qu'une méthode de calcul des pires temps de réponses pour des systèmes de tâches à échéance inférieure ou égale à la période. Ce papier est actuellement considéré comme étant une base de l'ordonnancement temps-réel. Les tâches (ou tasks en anglais) sont les entités manipulées par cet algorithme. Chaque tâche est modélisée par un quadruplet (, , , ), où : correspond à la date réveil de la tâche ; correspond au coût d'exécution de la tâche ; correspond à l'échéance relative de la tâche ; correspond à la période de la tâche. Toutefois, l'algorithme n'étant optimal que dans un contexte de tâches simultanées (i.e. la date de réveil de chaque tâche est nulle) et à échéance sur requête (i.e. ), il n'est pas rare de ne modéliser les tâches que par un doublet (, ). Afin de valider un système de tâches ordonnancé ainsi, deux moyens sont offerts : soit, calculer le temps de réponse de chaque tâche, puis, vérifier que toutes les tâches respectent leurs échéances ; soit, réaliser une simulation sur un intervalle allant de 0 jusqu'au PPCM des périodes (macrocycle). Il existe également une condition suffisante portant sur la charge processeur . Son test d'acceptabilité pour un système composé de tâches, qui peut être réalisé hors ligne, nous est donné par la formule suivante : Par exemple, la charge limite pour laquelle ce critère est valable pour est .