Faculté des sciences de Tunis
Module:
Système temps réel
Classe: LCE3
Dr. Nizar SGHAIER A.U.2024-2025
Chapitre 2:
Algorithmes
d’ordonnancement des
tâches indépendantes
périodiques
Caractéristiques des tâches temps réel
Une tâche est une séquence d’instructions qui, en l’absence d’interruptions, sont
exécutées sur un processeur jusqu’à son exécution finale. Une tâche sera
3 généralement et concrètement représentée par un processus ou un thread
• ri : date d’activation initiale, phase initiale, offset
• Ci : durée d’exécution sans préemption
• Pi : période d’activation
• Di : délai critique, échéance relative
• d = r+D : échéance (si tâche à contraintes strictes)
tâche périodique : rk = r0 + k*P
•Di = Pi : tâche à échéance sur requête
• Di #Pi : tâche à échéance arbitraire 3
3
Différents Types des tâches temps réel
Tâches périodiques
elles sont activées à intervalles
4
de temps réguliers
Tâches apériodiques
elles sont activées à des instants aléatoires non périodiques.
Tâches sporadiques
une borne minimale de la durée séparant 2 activations successives est
connue.
Il existe un intervalle de temps minimal entre deux réveils d’instances
successives
4
4
États d’une tache
Crée: création d'une tache dans le système
Prête : la tache est placé dans la file d’attente.
Activé: la tache est en cours d'exécution.
Bloquée : la tache attend un événement pour se réveiller
Inexistante: terminaison de l'exécution
5
Pourquoi l’ordonnancement temps réel?
20 l de fluide 1 versé toutes les 100 ms.
40 l de fluide 2 versé toutes les 150 ms.
Sachant que pour verser un litre de fluide, il faut 1 ms.
Donc durée de versement du fluide 1= 20ms
durée de versement du fluide 2= 40ms
Toute les 350 ms on effectue un prélèvement pour mesurer la température.
Duré de prélèvement =100 ms
6
Pourquoi l’ordonnancement temps réel?
20 l de fluide 1 versé toutes les 100 ms. durée de versement du fluide 1 C1= 20ms
40 l de fluide 2 versé toutes les 150 ms. durée de versement du fluide 1 C2= 40ms
Toute les 350 ms on effectue un prélèvement pour mesurer la température Duré de
prélèvement C3=100 ms
On remarque que le prélèvement a été effectué deux fois pendant une période
7
Pourquoi l’ordonnancement temps réel?
40 l de fluide 2 versé toutes les 150 ms. durée de versement du fluide 1 C2= 40ms
20 l de fluide 1 versé toutes les 100 ms. durée de versement du fluide 1 C1= 20ms
Toute les 350 ms on effectue un prélèvement pour mesurer la température Duré de
prélèvement C3=100 ms
P2 ,P1et P3
On remarque que j’ai raté une séquence le prélèvement a été effectué deux fois
pendant une période 8
Les Types d’ordonnancement
Ordonnancement « hors ligne » Statique
• la séquence d’ordonnancement est pré-calculée avant
l’exécution effective à l’exécution, l’ordonnanceur est un
simple séquenceur
Ordonnancement « en ligne » dynamique
• les décisions d’ordonnancement sont prises au cours de
l’exécution à l’exécution, l’ordonnanceur implémente un
algorithme d’ordonnancement surcoûts de mise en oeuvre
mais flexible
9
9
Politique d’ordonnancement:
10
Test d’ordonnancement
11
Test d’ordonnancement
12
Politique d’ordonnancement:
13
Politique d’ordonnancement:
14
15
16
D’où la nécessité de développer des algorithmes pour définir une
politique d’ordonnancement précise
17
Rate Monotonic Analysis (RMA)
Algorithme à priorité constante
Basé sur la période (tâches à échéance sur requête) :
➢ la tâche de plus petite période est la plus prioritaire
Test d'acceptabilité (condition suffisante)
n: nombre de tache,
quand n est très grand : n(21/n – 1) ~ ln 2 = 0,69
dans la pratique, on peut rencontrer des ordonnancements valides qui vont jusqu'à
88%
RMA est un algorithme « optimal » :
➢ une configuration qui ne peut pas être ordonnancée par RMA ne pourra pas
être ordonnée par un autre algorithme à priorité fixe
20
Rate Monotonic Analysis (RMA)
21
21
Rate Monotonic Analysis (RMA)
Hypothèses et Modèle
22
Rate Monotonic Analysis (RMA)
23
Exercice (RMA)
24
Rate Monotonic Analysis (RMA)
25
Rate Monotonic Analysis (RMA)
26
Rate Monotonic Analysis (RMA)
27
28
On remarque que la période d’activité du processeur W=15
Plus longue période d’activité L =9
la période du repos = 5
Temps de réponse de T1= 9
Temps de réponse de T2= 2
Temps de réponse de T3=4
30
31
Deadline Monotonic(DMA)
32
Exercice: Deadline Monotonic(DMA)
33
34
Deadline Monotonic(DMA)
35
Deadline Monotonic(DMA)
36
37
38
39
40
41
42
43
44
45
46
47
Least Laxity First Scheduling (LLF)
48
Least Laxity First Scheduling (LLF)
49
Least Laxity First Scheduling (LLF)
50
51
52
53
54
55
56
57
58
