Rate-monotonic scheduling

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
Les algorithmes d'ordonnancement

EDF - Rate-monotonic - Round-robin

LIFO - FIFO -


Sommaire

[modifier] Description

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.

[modifier] Historique

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

Outre l'algorithme Rate Monotonic, 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.

[modifier] Tâche

Les tâches (ou thread en anglais) sont les entités manipulées par Rate Monotonic. 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, Rate Monotonic n'étant optimal que dans un contexte de tâches simultanées (ie, la date de réveil de chaque tâche est nulle) et à échéance sur requête (ie, Di = Ti), il n'est pas rare de ne modéliser les tâches que par un doublet (Ci, Ti).

[modifier] Test d'ordonnançabilité

[modifier] Conditions nécessaires et suffisantes

Afin de valider un système de tâches ordonnancé par Rate Monotonic, deux moyens s'offrent à nous :

  • calculer le temps de réponse de chaque tâche, et de vérifier que toutes les tâches respectent leurs échéances ;
  • réaliser une simulation sur un intervalle allant de 0 jusqu'au PPCM des périodes.

[modifier] 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 :

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 n = 2 est U = 0.8284.

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

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

[modifier] Validité des tests d'ordonnançabilités

La condition suffisante n'est valable que dans le cas où l'algorithme Rate Monotonic 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.

[modifier] Cas plus généraux

[modifier] 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.

[modifier] 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.

[modifier] Liens externes

[modifier] 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.