GL4-RT5
Systèmes Temps-Réel
Chapitre 6 :
Ordonnancement sous
Contraintes Temps Réel
Olfa Mosbahi
olfamosbahi@[Link]
Plan
▪ Types de tâches
▪ Caractéristiques des tâches
▪ Caractérisation d'un ordonnancement
▪ Définitions
▪ Problème d’ordonnancement
▪ Ordonnancement de tâches périodiques indépendantes
▪ Ordonnancement de tâches apériodiques
▪ Ordonnancement de tâches périodiques dépendantes
1
Typologie des tâches
Un système A est modélisé par un nombre fini de tâches : A = {T1, T2, …,Tn}
▪ Tâche / Instance de tâche
▪ Modes d’activation
o Tâches réactivées à intervalle de temps régulier PERIODIQUE
- Une instance doit s’exécuter dans chaque période
- Une instance doit démarrer au début de chaque période
o Tâches activées aléatoirement - sur événement
- L’intervalle de temps entre deux occurrences de
l’événement est borné SPORADIQUE
- L’intervalle de temps entre deux occurrences
APERIODIQUE
de l’événement n’est pas borné
2
Typologie des tâches
Relation avec les autres tâches de l’application
- La tâche n’interagit pas avec les autres tâches de l’application
INDEPENDANTE
- La tâche Ti ne peut pas commencer avant la fin de Tj
A CONTRAINTE
DE PRECEDENCE
Graphe orienté (sans cycle) : nœud = tâche / arc = relation de précédence
Cas particulier : une seule contrainte de précédence par nœud (arbre)
- La tâche peut utiliser des ressources critiques (exclusion mutuelle)
A CONTRAINTE
DE RESSOURCES
Soit l’ensemble {R1, R2,…, Rl} des ressources du systèmes
La tâche spécifie les ressources qu’elle utilise (vecteur des ressources)
3
Caractérisation d’un ordonnancement
Problème :
Étant donné un ensemble de tâches A = {T1, T2, …,Tn}, trouver une
séquence de ces tâches qui respecte la spécification du problème
(contraintes de précédence, de ressources, d’échéances)
▪ Qualité du résultat
exact : l’algorithme fournit une séquence qui est la meilleure possible
et garantit le respect des contraintes
approché : l’algorithme fournit une séquence qui garantit le respect des
contraintes
▪ Algorithme optimal : un algorithme dont on peut prouver que,
- s’il échoue, tous les autres algorithmes échoueront ;
- s’il réussit, il ne donne pas forcément la séquence optimale
Un algorithme d’ordonnancement est dit optimal (pour une classe de
problèmes) quand il produit un emploi du temps processeur faisable chaque
fois qu'un autre algorithme peut le faire.
4
Ordonnançabilité d’un ensemble de tâches
Soit un ensemble de tâches A = {T1, T2, …, Tn} caractérisées (= une configuration)
▪ Un algorithme d'ordonnancement est un algorithme qui produit une séquence
des instances de tâches de A dans le temps,
▪ Une séquence est valide si les contraintes de la configuration A donnée sont
respectées,
▪ Un algorithme est fiable pour la configuration A s'il produit une séquence valide
sur une durée infinie.
Une configuration A est ORDONNANÇABLE (faisable) si il existe un
algorithme d'ordonnancement fiable pour A
Ordonnancement :Politique d’allocation des tranches de temps
processeur
Objectif Ordonnancement : Assurer le respect des échéances des
taches de manière prouvable,
5
Ordonnancement de tâches périodiques
▪ Une tâche périodique est caractérisée par : son temps d’exécution(C),
son échéance ou deadline (D) et sa période (P)
▪ Facteur d'utilisation d'une tâche périodique :
ui = Ci / Pi ui < 1 Ci : temps d’exécution
Pi : période de la tâche
▪ Charge du processeur pour A :
n
U = Ci
i =1 Pi condition nécessaire d'acceptation : U < 1
P = ppcm(T1, T2, …, Tn ) (1-U)P temps creux
Le temps d’oisiveté (temps creux) du processeur est (1-U)P
6
Ordonnancement
7
Panorama des algorithmes
Ordonnancement des tâches périodiques indépendantes
▪ Ordonnancement non préemptif
- Ordonnancement selon l’ordre d’arrivée : FIFO
- Ordonnancement selon la durée de calcul (le plus court d’abord…)
▪ Ordonnancement préemptif sans priorité
Round-Robin
▪ Ordonnancement préemptif à priorités fixes (statiques)
RM, DM
▪ Ordonnancement préemptif à priorités dynamiques
EDF, LLF
Ordonnancement des tâches apériodiques
▪ Serveur en arrière plan
▪ Serveur à scrutation
▪ Serveur différé
▪ Serveur Sporadique
Ordonnancement des tâches périodiques dépendantes partageant des ressources
▪ PIP
▪ PCP
▪ PCP immédiat
8
Ordonnancement non préemptif
9
Ordonnancement non préemptif
10
Ordonnancement non préemptif
11
Ordonnancement préemptif
12
Ordonnancement préemptif
13
Ordonnancement préemptif
14
Ordonnancement préemptif
15
Ordonnancement préemptif
16
Ordonnancement préemptif
17
Ordonnancement préemptif
18
Ordonnancement préemptif
à priorité fixe (FPPS)
19
Ordonnançement préemptif de tâches périodiques
Rate Monotonic
- Principe : Les tâches avec les périodes plus courtes sont les plus prioritaires.
20
Ordonnançement préemptif de tâches périodiques
Rate Monotonic
Exemple 2
Ensemble de tâches qui n’est pas
ordonnançable avec occupation
du processeur < 100 %
21
Ordonnançement préemptif de tâches périodiques
Rate Monotonic
22
Ordonnançement préemptif de tâches périodiques
Rate Monotonic
23
Ordonnançement préemptif de tâches périodiques
Rate Monotonic
24
Ordonnançement préemptif de tâches périodiques
Rate Monotonic
25
Ordonnançement préemptif de tâches périodiques
Rate Monotonic
Exemples
26
Ordonnançement préemptif de tâches périodiques
Rate Monotonic
27
Ordonnançement préemptif de tâches périodiques
Rate Monotonic
28
Ordonnançement préemptif de tâches périodiques
Rate Monotonic
29
Ordonnançement préemptif de tâches périodiques
Rate Monotonic
30
Ordonnançement préemptif de tâches périodiques
Rate Monotonic
31
Ordonnançement préemptif de tâches périodiques
Rate Monotonic
32
Ordonnançement préemptif de tâches périodiques
Deadline Monotonic
33
34
Ordonnançement préemptif de tâches périodiques
Deadline Monotonic
35
Ordonnançement préemptif de tâches périodiques
Deadline Monotonic
36
