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. Traveling salesman problem applications also include sequencing jobs, a combinatorial task related to real-time scheduling. Scheduling theory, like the linear programming developed by Dantzig, aims for the best use of limited resources.

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
  • avionique et commande de vol systèmes
  • automatisation industrielle et robotique
  • temps réel traitement du signal

Brevets:

NA

Idées d'innovations potentielles

  • analyseurs d'ordonnançabilité pour les systèmes à criticité mixte
  • algorithmes de planification écoénergétiques qui adaptent les taux de tâches
  • planification partitionnée pour les systèmes temps réel multicœurs
  • RMS adaptatif pour les tâches avec des temps d'exécution variables dans les applications d'IA
  • Planification des paquets réseau dans les commutateurs TSN (Time-Sensitive Networking).
  • Protocoles de réservation de ressources pour le cloud computing en temps réel
  • cadres d'analyse compositionnelle pour les systèmes distribués temps réel à grande échelle
  • Analyse probabiliste de l'ordonnançabilité des systèmes à temps d'exécution incertains
  • planification prenant en compte la sécurité pour prévenir les attaques par canal auxiliaire basées sur le temps
  • co-planification des tâches en temps réel et des applications non temps réel sur un seul processeur
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)

10e année anniversaire

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