### Exposé sur l'Algorithme d'Ordonnancement "Rate Monotonic"
#### Sommaire
1. **Introduction**
- Définition de l'ordonnancement
- Contexte des systèmes temps réel
- Importance de l'ordonnancement dans les systèmes critiques
- Problématique de l'ordonnancement dans les systèmes embarqués
2. **Présentation de l'Algorithme Rate Monotonic (RM)**
- Origine et historique
- Principe de base
- Différence entre ordonnancement statique et dynamique
- Comparaison avec d'autres approches d'ordonnancement
3. **Fondements Théoriques**
- Modèle des tâches périodiques
- Hypothèses de l'algorithme RM
- Analyse de l'ordonnançabilité
- Test d'ordonnançabilité de Liu et Layland
- Preuve mathématique du test d'ordonnançabilité
- Limites théoriques de l'algorithme RM
4. **Caractéristiques de l'Algorithme RM**
- Priorité des tâches
- Politique d'ordonnancement préemptif
- Exemple illustratif détaillé
- Diagramme de Gantt pour l'exemple
- Analyse du comportement dans le pire cas
5. **Avantages et Limites**
- Avantages de l'algorithme RM
- Limites et contraintes
- Comparaison avec d'autres algorithmes en termes de performance
- Cas où RM n'est pas optimal
6. **Comparaison avec d'autres Algorithmes d'Ordonnancement**
- EDF (Earliest Deadline First)
- Least Laxity First (LLF)
- Priority Ceiling Protocol (PCP)
- Tableau comparatif des algorithmes
- Analyse des performances relatives
7. **Applications Pratiques**
- Domaines d'application
- Études de cas détaillées
- Exemples de systèmes utilisant RM
- Analyse de l'utilisation dans l'industrie
8. **Implémentation de l'Algorithme RM**
- Structure de données utilisées
- Pseudo-code de l'algorithme
- Exemple de code en C ou Python
- Optimisations possibles
9. **Extensions et Variantes de l'Algorithme RM**
- RM avec héritage de priorité
- RM pour les systèmes multiprocesseurs
- RM avec gestion des ressources partagées
- RM dans les systèmes distribués
10. **Analyse de Performance**
- Métriques de performance
- Études de performance dans différents scénarios
- Graphiques et tableaux de résultats
- Impact de la charge système sur les performances
11. **Conclusion**
- Résumé des points clés
- Perspectives futures
- Recommandations pour l'utilisation de RM
---
### 1. Introduction
L'ordonnancement est une fonction essentielle dans les systèmes d'exploitation et les
systèmes embarqués, particulièrement dans les systèmes temps réel. Ces systèmes
doivent répondre à des contraintes temporelles strictes pour garantir le bon
fonctionnement des applications critiques. L'algorithme Rate Monotonic (RM) est l'un
des algorithmes d'ordonnancement les plus utilisés pour les systèmes temps réel
périodiques.
#### Problématique de l'ordonnancement dans les systèmes embarqués
Dans les systèmes embarqués, les ressources sont souvent limitées, et les tâches
doivent être exécutées dans des délais précis pour éviter des conséquences
catastrophiques. L'ordonnancement joue donc un rôle crucial pour garantir que toutes
les tâches respectent leurs échéances.
---
### 2. Présentation de l'Algorithme Rate Monotonic (RM)
#### Origine et historique
L'algorithme Rate Monotonic a été introduit par Liu et Layland en 1973 dans leur article
fondateur sur l'ordonnancement des systèmes temps réel. Il est rapidement devenu une
référence pour les systèmes périodiques.
#### Principe de base
Le principe de base de RM est d'attribuer des priorités statiques aux tâches en fonction
de leur période : plus la période d'une tâche est courte, plus sa priorité est élevée. Cette
approche garantit que les tâches les plus fréquentes sont traitées en priorité.
#### Différence entre ordonnancement statique et dynamique
- **Ordonnancement statique** : Les priorités sont fixées à l'avance et ne changent pas
pendant l'exécution.
- **Ordonnancement dynamique** : Les priorités peuvent changer en fonction de l'état
du système (exemple : EDF).
---
### 3. Fondements Théoriques
#### Modèle des tâches périodiques
Chaque tâche périodique est caractérisée par :
- Une période \( T_i \) (intervalle entre deux activations).
- Un temps d'exécution \( C_i \) (temps nécessaire pour exécuter la tâche).
- Une échéance \( D_i \) (souvent égale à la période).
#### Hypothèses de l'algorithme RM
1. Les tâches sont indépendantes.
2. Les tâches sont périodiques.
3. Les temps d'exécution sont constants et connus à l'avance.
4. Les échéances sont égales aux périodes.
#### Test d'ordonnançabilité de Liu et Layland
Le test d'ordonnançabilité est donné par :
\[
\sum_{i=1}^{n} \frac{C_i}{T_i} \leq n(2^{1/n} - 1)
\]
où \( n \) est le nombre de tâches. Ce test garantit que l'ensemble des tâches est
ordonnançable si la condition est vérifiée.
#### Preuve mathématique du test
La preuve repose sur l'analyse du pire cas, où les tâches sont activées simultanément.
Elle montre que si le test est vérifié, alors toutes les tâches respecteront leurs
échéances.
---
### 4. Caractéristiques de l'Algorithme RM
#### Priorité des tâches
Les priorités sont attribuées de manière statique en fonction de la période des tâches.
Par exemple :
- Tâche A : \( T_A = 5 \), priorité élevée.
- Tâche B : \( T_B = 10 \), priorité moyenne.
- Tâche C : \( T_C = 20 \), priorité faible.
#### Politique d'ordonnancement préemptif
Si une tâche de priorité plus élevée devient prête à s'exécuter, elle préempte la tâche en
cours d'exécution de priorité inférieure.
#### Exemple illustratif détaillé
Considérons trois tâches :
- Tâche 1 : \( T_1 = 5 \), \( C_1 = 2 \)
- Tâche 2 : \( T_2 = 10 \), \( C_2 = 4 \)
- Tâche 3 : \( T_3 = 20 \), \( C_3 = 6 \)
Le diagramme de Gantt suivant montre l'ordonnancement des tâches sur une période
de 20 unités de temps.
| Temps | Tâche en cours |
|-------|----------------|
| 0-2 | Tâche 1 |
| 2-4 | Tâche 2 |
| 4-6 | Tâche 1 |
| 6-10 | Tâche 2 |
| 10-12 | Tâche 1 |
| 12-16 | Tâche 3 |
| 16-18 | Tâche 1 |
| 18-20 | Tâche 2 |
---
### 5. Avantages et Limites
#### Avantages de l'algorithme RM
- **Simplicité** : Facile à implémenter.
- **Efficacité** : Utilisation optimale des ressources.
- **Garantie d'ordonnançabilité** : Si le test de Liu et Layland est vérifié.
#### Limites et contraintes
- **Tâches apériodiques** : RM ne gère pas les tâches non périodiques.
- **Ressources partagées** : Difficile à gérer sans mécanismes supplémentaires.
- **Optimalité limitée** : Pas optimal pour des ensembles de tâches ne vérifiant pas le
test.
---
### 6. Comparaison avec d'autres Algorithmes d'Ordonnancement
#### EDF (Earliest Deadline First)
- **Priorités dynamiques** : Basées sur les échéances.
- **Optimalité** : EDF est optimal pour les systèmes monoprocesseurs.
#### Least Laxity First (LLF)
- **Priorités dynamiques** : Basées sur la laxité (temps restant avant l'échéance moins
le temps d'exécution restant).
- **Complexité** : Plus complexe à implémenter que RM.
#### Tableau comparatif
| Algorithme | Priorités | Optimalité | Complexité |
|------------|-----------|------------|------------|
| RM | Statiques | Sous-optimal | Simple |
| EDF | Dynamiques | Optimal | Modérée |
| LLF | Dynamiques | Optimal | Complexe |
---
### 7. Applications Pratiques
#### Domaines d'application
- **Systèmes de contrôle de vol** : Les tâches doivent être exécutées à des intervalles
précis.
- **Systèmes médicaux** : Les délais sont critiques pour les dispositifs comme les
pacemakers.
- **Robotique industrielle** : Les robots doivent exécuter des tâches synchronisées.
#### Études de cas détaillées
- **Contrôle de trafic aérien** : Utilisation de RM pour ordonnancer les tâches de
surveillance et de communication.
- **Systèmes de surveillance médicale** : RM est utilisé pour garantir que les données
des capteurs sont traitées en temps réel.
---
### 8. Implémentation de l'Algorithme RM
#### Structure de données utilisées
- **File de priorité** : Pour gérer les tâches en fonction de leurs priorités.
- **Liste chaînée** : Pour maintenir l'ordre d'exécution des tâches.
#### Pseudo-code de l'algorithme
```python
while True:
tâche = file_de_priorité.pop()
exécuter(tâche)
if tâche.est_terminée():
file_de_priorité.ajouter(tâche)
```
#### Exemple de code en C
```c
#include <stdio.h>
#include <stdlib.h>
struct Task {
int period;
int execution_time;
int priority;
};
void schedule(struct Task tasks[], int n) {
// Implémentation de l'ordonnanceur RM
```
---
### 9. Extensions et Variantes de l'Algorithme RM
#### RM avec héritage de priorité
Permet de gérer les inversions de priorité en héritant temporairement de la priorité d'une
tâche de priorité plus élevée.
#### RM pour les systèmes multiprocesseurs
Des extensions de RM ont été développées pour les systèmes multiprocesseurs, où les
tâches peuvent être exécutées sur plusieurs processeurs.
---
### 10. Analyse de Performance
#### Métriques de performance
- **Taux d'utilisation du processeur** : Pourcentage du temps processeur utilisé.
- **Temps de réponse** : Temps entre l'activation d'une tâche et sa fin d'exécution.
- **Taux de respect des échéances** : Pourcentage de tâches respectant leurs
échéances.
#### Études de performance
Des études montrent que RM est efficace pour des charges de travail modérées, mais
peut devenir sous-optimal pour des charges élevées.
---
### 11. Conclusion
#### Résumé des points clés
L'algorithme Rate Monotonic est un outil puissant pour l'ordonnancement des tâches
périodiques dans les systèmes temps réel. Bien qu'il présente certaines limitations, sa
simplicité et son efficacité en font un choix populaire pour de nombreuses applications
critiques.
#### Perspectives futures
Les recherches futures pourraient explorer des extensions de RM pour gérer des tâches
apériodiques et des systèmes plus complexes.
#### Recommandations pour l'utilisation de RM
Il est recommandé d'utiliser RM dans des systèmes où les tâches sont strictement
périodiques et où les échéances sont égales aux périodes. Pour des systèmes plus
complexes, des algorithmes comme EDF peuvent être plus appropriés.
