Rate-monotonic scheduling

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Cet article est une ébauche à compléter concernant l'informatique, vous pouvez partager vos connaissances en le modifiant.

Les algorithmes d'ordonnancement

EDF - Rate-monotonic - Round-robin

LIFO - FIFO -

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 n'utilisant que la notion de période des tâches pour effectuer son ordonnancement, il ne peut être utilisé que pour des tâches à échéances sur requête.

Son test d'acceptabilité qui peut être réalisé hors ligne nous est donné par la formule suivante :

$\sum_{i=1}^{n} C_i / T_i \leq n(\sqrt[n]{2} - 1)$

Remarque : Les entrées de l'algorithme sont des process (tâches, threads) possédant les caractéristiques suivantes :

pas de partage de ressources entre les process (un périphérique, une file d'attente, un sémaphore…),
des échéances ou deadlines connues égales aux périodes,
des priorités statiques (à chaque fois qu'un processeur est disponible ou qu'une nouvelle période de tâche commence, la tâche avec la plus haute priorité statique est choisie pour préempter toutes les autres tâches),
des priorités statiques assignées d'après le principe Rate-monotonic scheduling (on donne une priorité aux tâches d'autant plus haute qu'elles possèdent une plus courte période ou une plus proche échéance).

En 1973, Liu et Layland ont prouvé que, pour un ensemble de n tâches périodiques avec une période constante, il existe un ordonnancement respectant les échéances à condition que l'utilisation U du (ou des) processeur(s) respecte :

$U = \sum_{i=1}^{n} C_i / T_i \leq n(\sqrt[n]{2} - 1)$

où $C i$ est la durée nécessaire à l'accomplissement de la tâche i, et $T i$ la périodicité de la tâche i. Par exemple $U = 0.8284$ pour $n = 2$ . Quand le nombre de process 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 deadlines si l'utilisation du (ou des) processeur(s) 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 possible qu'un ordonnancement de tâches possède une utilisation allant jusqu'à 88%, mais ceci dépend des paramètres particuliers des tâches à ordonnancer.

L'assignement des priorités par l'algorithme RMS est dit optimal ; cela signifie que si un algorithme d'ordonnancement à priorités statiques peut respecter toutes les deadlines, alors l'algorithme RMS le peut également. 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.

Il reste un problème ouvert dans ce domaine : trouver un algorithme d'ordonnancement à priorités statiques optimal quand les deadlines sont plus grandes que les périodes.