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.

Historique

Cet algorithme a été proposé la première fois dans un papier publié par Liu et Layland^[1].

Outre l'algorithme à taux monotone, ce papier décrit une modélisation des tâches basée sur un triplet (${\displaystyle C_{i}}$, ${\displaystyle D_{i}}$, ${\displaystyle T_{i}}$), 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.

Tâche

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 (${\displaystyle r_{i}}$, ${\displaystyle C_{i}}$, ${\displaystyle D_{i}}$, ${\displaystyle T_{i}}$), où :

• ${\displaystyle r_{i}}$ correspond à la date réveil de la tâche ;
• ${\displaystyle C_{i}}$ correspond au coût d'exécution de la tâche ;
• ${\displaystyle D_{i}}$ correspond à l'échéance relative de la tâche ;
• ${\displaystyle T_{i}}$ 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. ${\displaystyle D_{i}=T_{i}}$), il n'est pas rare de ne modéliser les tâches que par un doublet (${\displaystyle C_{i}}$, ${\displaystyle T_{i}}$).

Test d'ordonnançabilité

Conditions nécessaires et suffisantes

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).

Condition suffisante

Il existe également une condition suffisante portant sur la charge processeur ${\displaystyle U}$. Son test d'acceptabilité pour un système composé de ${\displaystyle n}$ tâches, qui peut être réalisé hors ligne, nous est donné par la formule suivante :

${\displaystyle U=\sum _{i=1}^{n}C_{i}/T_{i}\leq n({\sqrt[{n}]{2}}-1)}$

Par exemple, la charge limite pour laquelle ce critère est valable pour ${\displaystyle n=2}$ est ${\displaystyle U=0.8284}$.

Et quand le nombre de tâches tend vers l'infini :

${\displaystyle \lim _{n\rightarrow \infty }n({\sqrt[{n}]{2}}-1)=\ln 2\approx 0.693147\ldots }$

Ainsi, on estime dans le cas général qu'un RMS peut respecter toutes les échéances si l'utilisation du processeur est inférieure ou égale à 69,3 %. Les 30,7 % restants peuvent être dédiés à des tâches de basse priorité et non temps-réel.

Cependant, cette condition est suffisante mais pas nécessaire. Il est tout à fait possible qu'un système de tâche totalisant une charge de 100 % soit ordonnançable, alors qu'un autre système de tâches n'ayant qu'une charge globale de 80 % ne le soit pas. Tout dépend des caractéristiques du système de tâches.

Validité des tests d'ordonnançabilité

La condition suffisante n'est valable que dans le cas où l'algorithme est optimal.

La simulation n'est également valable que dans le cas où l'algorithme est optimal. Toutefois, il est possible de le rendre valide à d'autre cas en étendant la période de simulation.

Le calcul du pire temps de réponse reste valable quelle que soit la situation.

Cas plus généraux

Deadline Monotonic

L'algorithme deadline monotonic est également optimal dans une situation dans laquelle les périodes et les deadlines sont identiques, dans le fait que les algorithmes sont alors identiques, et de plus, le DMS est optimal quand les deadlines sont inférieures aux périodes.

Algorithme d'Audsley

Dans le cadre plus général de tâches indépendantes, périodiques, concrètes non simultanées et à échéance arbitraire, l'algorithme d'Audsley fournit une méthode optimale d'ordonnancement.

Notes et références

1. C.L. Liu & J.W. Layland, "Scheduling algorithms for multiprogramming in a hard real-time environment", Journal of the Association for Computing Machinery 20 (1973), no. 1, p. 46-61.

Voir aussi

Articles connexes

• Système temps réel
• Système déterministe

Liens externes

• (en) Introduction to RMS

• Portail de l'informatique théorique
• Portail de la programmation informatique