# Ordonnancement dans les Systèmes temps-réel

## Intro

On étudie un ensemble de *n* tâches, avec départ simultané ou échelonné.

### Durée d'exécution *C*

Temps nécessaire à un CPU pour exécuter un travail sans interruption : 

- Dépend de la vitesse du CPU
- Théorique (car en pratique non constante)
  - Durée minimale
  - Durée maximale (WCET : Worst Case Execution Time)
→ Le temps de travail correspond au WCET

### Attributs d'un travail

- Date de début au plus tôt (activation) : *Td*
- Date de fin au plus tard (Echéance) : *Tf*
- Durée d'exécution d'un travail *i* (Besoin) : *Ci*
- Cas non préemptif : Marge Statique *Ms = ( Tf - Td) - Ci*
- Cas préemptif : Marge dynamique (laxité) : *Md = (Tf - Tc) - Ri*
  - *Tc* : instant courant
  - *Ri* : durée restante du travail *i*

### Notion de tâche

- Périodique : un travail toutes les périodes *T* avec *T* > 0
- Sporadique : travaux séparés par un intervalle minimal connu
- Apériodique : modèle plus général, création de travaux à des instants connu

### Période d'étude (cas périodique)

L'exécution est infinie mais le comportement de la configuration est périodique. C'est le PPCM des périodes de chaque tâche.

### Plan d'ordonnancement

- Méthode de prévision pour l'allocation des ressources
- Optimal si toutes les contraintes temporelles sont respectées
- Surchage quand le volume de tâches à ordonnancer est tel qu'un plan d'ordonnancement ne permet pas de respecter toutes les tâches (= pas d'ordonnancement optimal)
- Un algorithme d'ordonnancement est optimal si pour une classe de problèmes il produit des ordonnancements optimaux

### Type d'algorithmes d'ordonnancement

- Statique : Plan décidé avant exécution (hors ligne)
    - Nécessite la connaissance à priori du système ; peu flexible mais très prédictible
    - Adapté à un modèle périodique
    - Ordonnanceur simple
    - Régularité d'exécution
- Dynamique : Varie pendant l'exécution (en ligne)
  - Flexible
  - Efficacité calculatoire requise
  - Difficile de prendre en compte des contraintes variées
  - Non oisif, le CPU est toujours utilisé

## Algorithmes d'ordonnancement

- Statiques
  - FP (fixed prioritu)
  - RMS
- Dynamiques
  - FCFS  (first come first served)
  - Round Robin
  - EDF (échance la plus proche)
  - LLF (plus petite laxité)

### Priorité Fixe

- Les tâches ont une priorité fixe
- La tâche avec la plus haute priorité d'exécute (préemption possible)
- Très proche du HW
- Ponctualité pour une tâche
- Peut de vivacité

### RMS

- Hypothèses du modèle
  - Chaque tâche est périodique
  - Préemption possible
  - Priorité fixe
  - Pas de dépendance entre les tâches
  - L'échéance est la période
  - La priorité est l'inverse de la période

Critère de faisabilité : 

Pour *n* tâches, le temps d'occupation du CPU est égal à la somme de pour chaque tâche, sa durée d'exécution sur sa période.

- W doit toujours être <= à 1, sinon surcharge (condition nécessaire)
- W doit être <= à U(n) (condition suffisante)

Avantages :

- Peut être étendu à une tâche apériodique
- Peut être étendu à la surcharge
- Simple à implémenter

Inconvénients :

- Hypothèses très simples
- Famine si bug dans une tâche de haute priorité

### Priorité et syncrhonisation

Si un tâche prend un mutex et qu'un tâche plus prioritaire le demande ensuite, cela crée un blocage.

Solutions : 
- Héritage de priorité : le détenteur de la mutex hérite de la priorité du demandeur jusqu'à ce qu'il le libère
- Superpriorité : le détenteur d'une mutex est prioritaire sur tout tant qu'il ne l'a pas libéré.

## FCFS