Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Rate-monotonic scheduling
Résumé
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 .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.