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.

The significance of RMS lies in its optimality and the existence of a simple schedulability test. It is proven to be an optimal static-priority scheduling policy. This means that if a set of tasks can be scheduled by any static-priority algorithm, it can also be scheduled by RMS. The schedulability of a task set under RMS can be determined using a utilization bound test. For a set of ‘n’ tasks, the total processor utilization ‘U’ is the sum of the execution time [latex]C_i[/latex] divided by the period [latex]T_i[/latex] for each task ‘i’: [latex]U = \sum_{i=1}^{n} \frac{C_i}{T_i}[/latex]. Liu and Layland proved that if this total utilization is less than or equal to a specific bound, [latex]U \le n(2^{1/n}-1)[/latex], then the task set is guaranteed to be schedulable (i.e., no deadlines will be missed). As ‘n’ approaches infinity, this bound converges to [latex]\ln(2) \approx 0.693[/latex]. This provides a sufficient, but not necessary, condition for schedulability. A more precise but complex test, called exact analysis or response time analysis, can also be used.

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.