- Rate-monotonic scheduling
-
L'ordonnancement à taux monotone (en anglais, rate-monotonic scheduling) est un algorithme d'ordonnancement temps réel en ligne à priorité constante. 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.
Sommaire
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 (Ci, Di, Ti), 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 (ri, Ci, Di, Ti), où :
- ri correspond à la date réveil de la tâche ;
- Ci correspond au pire temps d'exécution de la tâche ;
- Di correspond à l'échéance relative de la tâche ;
- Ti 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. Di = Ti), il n'est pas rare de ne modéliser les tâches que par un doublet (Ci, Ti).
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 U. Son test d'acceptabilité pour un système composé de n 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 n = 2 est U = 0.8284.
Et quand le nombre de tâches tend vers l'infini :
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
- 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
Liens externes
- (en) Introduction to RMS
Catégorie :- Algorithme d'ordonnancement
![U = \sum_{i=1}^{n} C_i / T_i \leq n(\sqrt[n]{2} - 1)](3/633bb7b941d16d2d364a7d6fbfeb030c.png)
![\lim_{n \rightarrow \infty} n(\sqrt[n]{2} - 1) = \ln 2 \approx 0.693147\ldots](2/362dc1a4438ec99d7387afcad4b3ab69.png)
Wikimedia Foundation. 2010.
