Product Design, Manufacturing & Innovation Resources
Maison » Ordonnancement à taux monotone (RMS)

Ordonnancement à taux monotone (RMS)

1973
  • C. L. Liu
  • James Layland
Poste de travail informatique dans une salle de contrôle analysant l'ordonnancement monotone des systèmes en temps réel.

(Image générée à titre d'illustration uniquement)

L'ordonnancement à fréquence monotone (RMS) est un algorithme d'ordonnancement à priorité statique pour les tâches périodiques dans un système temps réel. Il attribue les priorités en fonction de la fréquence des tâches : plus la période d'une tâche est courte (plus sa fréquence est élevée), plus sa priorité est élevée. RMS est un algorithme à priorité statique optimal ; autrement dit, si tout algorithme à priorité statique peut ordonnancer un ensemble de tâches, RMS le peut également. La capacité d'ordonnancement peut être vérifiée à l'aide d'un test basé sur le taux d'utilisation.

L'ordonnancement à fréquence monotone (RMS) est un pilier de la théorie des systèmes temps réel, introduit dans un article fondateur de 1973 par Liu et Layland. Il offre une méthode simple et efficace pour ordonnancer un ensemble de tâches indépendantes, préemptibles et périodiques sur un seul processeur. Son principe fondamental consiste à attribuer à chaque tâche une priorité fixe, inversement proportionnelle à sa période. Une tâche s'exécutant toutes les 10 ms aura une priorité plus élevée qu'une tâche s'exécutant toutes les 100 ms.

L'importance de RMS réside dans son optimalité et l'existence d'un test d'ordonnançabilité simple. Il est prouvé qu'il s'agit d'une politique d'ordonnancement à priorité statique optimale. Cela signifie que si un ensemble de tâches peut être ordonnancé par n'importe quel algorithme à priorité statique, il peut également l'être par RMS. L'ordonnançabilité d'un ensemble de tâches sous RMS peut être déterminée à l'aide d'un test de limite d'utilisation. Pour un ensemble de n tâches, l'utilisation totale du processeur U est la somme du temps d'exécution Ci divisé par la période Ti pour chaque tâche i : U = ∑i=1n Ci/Ti. Liu et Layland ont démontré que si le taux d'utilisation total est inférieur ou égal à une borne spécifique, [latex]U le n(2^{1/n}-1)[/latex], alors l'ensemble des tâches est garanti planifiable (c'est-à-dire qu'aucune échéance ne sera manquée). Lorsque ‘n’ tend vers l'infini, cette borne converge vers [latex]ln(2) approx 0,693[/latex]. Ceci constitue une condition suffisante, mais non nécessaire, pour la planifiabilité. Un test plus précis, mais plus complexe, appelé analyse exacte ou analyse du temps de réponse, peut également être utilisé.

UNESCO Nomenclature: 1203
- Informatique

Taper

Logiciel/Algorithme

Perturbation

Incrémentale

Usage

Utilisation généralisée

Précurseurs

  • théorie des files d'attente
  • recherche opérationnelle
  • premiers travaux sur les algorithmes d'ordonnancement informatique
  • développement des systèmes d'exploitation à temps partagé

Applications

  • systèmes de contrôle par satellite
  • applications de contrôle automobile
  • systèmes avioniques et de commandes de vol
  • automatisation industrielle et robotique
  • traitement du signal en temps réel

Brevets:

NA

Idées d'innovations potentielles

En raison du trafic généré par les robots de scraping, actuellement supérieur à 40 000 par jour, ce contenu est réservé aux membres de la communauté.
> Connexion < ou > Registre < (100% gratuit) pour y accéder, ainsi qu'à tous les autres contenus et outils à accès restreint.

Lié à : ordonnancement à débit monotone, RMS, systèmes temps réel, algorithme d'ordonnancement, priorité statique, tâches périodiques, analyse d'ordonnançabilité, limite d'utilisation, Liu et Layland, ordonnancement optimal.

Contexte historique

Ordonnancement à taux monotone (RMS)

1970
1970
1970
1973
1980
1980
1980
1970
1970
1970
1970-01-01
1975-06-01
1980
1980
1980

(si la date est inconnue ou non pertinente, par exemple « mécanique des fluides », une estimation arrondie de son émergence notable est fournie)

Les images en pleine résolution et les téléchargements sont uniquement disponibles, et 100% gratuits, pour les membres inscrits.